Matematyka dyskretna 2/Ćwiczenia 2: Porządki Częściowe i twierdzenie Dilworth'a

Porządki częściowe

Ćwiczenie 1

Niech $\mathbf {T} =\left(V,E\right)$ będzie drzewem z wyróżnionym elementem $r\in V$ . Pokaż, że definiując dla $v,w\in V$ :

$v\leq w$ wtedy i tylko wtedy, gdy ścieżka z $w$ do $r$ odwiedza wierzchołek $v$ ,

otrzymana para $\left(V,\leq \right)$ jest zbiorem częściowo uporządkowanym.

Wskazówka

Rozwiązanie

Sprawdzamy po kolei warunki na to, aby $\left(V,\leq \right)$ był zbiorem częściowo uporządkowanym:

zwrotość:

Każda ścieżka z $w$ do $r$ oczywiście odwiedza swój początek, czyli $w$ .

antysymetria:

Załóżmy, że dla dwu różnych wierzchołków $v,w$ , wierzchołek $w$ leży na ścieżce z $v$ do $r$ oraz $v$ leży na ścieżce z $w$ do $r$ . Mamy więc dwie ścieżki:

{\begin{aligned}&&w\to \ldots \to v\to \ldots \to r,\\&&v\to \ldots \to w\to \ldots \to r.\end{aligned}}

Między dwoma wierzchołkami drzewa istnieje dokładnie jedna ścieżka. Idąc więc pierwszą z tych ścieżek z $w$ do $r$ dojdziemy do $v$ , co wobec jedyności, zmusza do przejścia później drugą ścieżką, czyli przez $w$ . Na ścieżce punkty nie mogą sie jednak powtarzać.

przechodniość:

Załóżmy, że $u\leq v$ oraz $v\leq w$ , tzn. $u$ leży na jedynej ścieżce z $v$ do $r$ , a $v$ na jedynej ścieżce z $w$ do $r$ . Z jedyności ścieżek dostajemy, że fragment od $v$ do $r$ ścieżki z $w$ do $r$ , odwiedza $u$ .

Ćwiczenie 2

Pokaż, że elementy $p_{1},p_{2},\ldots ,p_{k}\in P$ zbioru częściowo uporządkowanego $\left(P,\leq \right)$ spełniające $p_{1}\leq p_{2}\leq \ldots \leq p_{k}\leq p_{1}$ muszą być równe.

Wskazówka

Przeprowadź dowód indukcyjny ze względu na $k$ .

Rozwiązanie

Rozumowanie przeprowadzimy indukcyjnie ze względu na $k$ . Dla $k=1$ jest to oczywiste. Podobnie, gdy $p_{1}\leq p_{2}\leq p_{1}$ , to antysymetria daje Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p_1=p_2} . Niech więc Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle k>2} . Nierówność Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p_{k-1}\leq p_k\leq p_1} daje Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p_{k-1}\leq p_1} , co pozwala skrócić wyjściowy ciąg nierówności

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p_1\leq p_2\leq \ldots \leq p_k\leq p_1 }

do

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p_1\leq p_2\leq \ldots \leq p_{k-1}\leq p_1} ,

i z założenia indukcyjnego dostać

p_{1}=p_{2}=\ldots =p_{k-1}

Jedyna brakująca równość $p_{1}=p_{k}$ wynika z $p_{1}=p_{k-1}\leq p_{k}\leq p_{1}$ .

Ćwiczenie 3

Korzystając z Twierdzenia Dilworth'a 2.1 pokaż, że każdy zbiór częściowo uporządkowany o $rs+1$ elementach zawiera łańcuch o liczności $r+1$ lub antyłańcuch o liczności $s+1$ .

Wskazówka

Rozwiązanie

Niech $\mathbf {P} =\left(P,\leq \right)$ będzie posetem, w którym każdy łańcuch jest liczności co najwyżej $r$ , a każdy antyłańcuch jest liczności co najwyżej $s$ . Twierdzenie Dilworth'a 2.1 dostarcza pokrycia łańcuchami

P=C_{1}\cup \ldots \cup C_{s'}

,

gdzie $s'\leq s$ jest mocą łańcucha o maksymalnej liczności. Ponieważ $\left\vert C_{i}\right\vert \leq r$ , to

\left\vert P\right\vert =\left\vert C_{1}\right\vert +\ldots +\left\vert C_{s'}\right\vert \leq rs'\leq rs

Sprzeczność ta pokazuje, że jeśli $\mathbf {P}$ ma co najmniej $rs+1$ elementów, to musi zawierać łańcuch o liczności $r+1$ lub antyłańcuch o liczności $s+1$ .

Ćwiczenie 4

Pokaż, że dla zbioru częściowo uporządkowanego $\mathbf {P} =\left(P,\leq \right)$ , rodzina ${\mathcal {MA}}\!\left(\mathbf {P} \right)$ antyłańcuchów zbioru $\mathbf {P}$ o maksymalnej liczności wraz z relacją zdefiniowaną poprzez:

$A\leq B$ wtedy i tylko wtedy, gdy każdy element $b\in B$ leży nad jakimś elementem $a\in A$ ,

tworzy kratę.

Wskazówka

Dla $A,B\in {\mathcal {MA}}\!\left(\mathbf {P} \right)$ zbiór elementów maksymalnych w $A\cup B$ jest kresem górnym $A,B$ , a zbiór elementów minimalnych w $A\cup B$ jest kresem dolnym $A,B$ .

Rozwiązanie

By skrócić zapisy niektórych wypowiedzi, dla podzbioru $X\subseteq P$ zbioru częściowo uporządkowanego $\mathbf {P} =\left(P,\leq \right)$ definiujemy stożek górny oraz stożek dolny zbioru $X$ odpowiednio jako

{\begin{aligned}X\!\!\Uparrow &=\left\lbrace p\in P:\ {\text{ istnieje }}\ x\in X\ {\text{ taki, że }}\ x\leq p\right\rbrace ,\\X\!\!\Downarrow &=\left\lbrace p\in P:\ {\text{ istnieje }}\ x\in X\ {\text{ taki, że }}\ p\leq x\right\rbrace .\end{aligned}}

A zatem definicję relacji $\leq$ w zbiorze ${\mathcal {MA}}\!\left(\mathbf {P} \right)$ możemy przeformułować następująco:

A\leq B

wtedy i tylko wtedy, gdy

B\subseteq A\!\!\Uparrow

.

Zauważmy też, że

dla antyłańcuchów $X,Y\subseteq P$ , jeśli $X\subseteq Y\!\!\Uparrow$ , to także $X\!\!\Uparrow \subseteq Y\!\!\Uparrow$ .

Istotnie, niech $p\in X\!\!\Uparrow$ , tzn. $x\leq p$ dla pewnego $x\in X$ . Ale wobec $x\in X\subseteq Y\!\!\Uparrow$ wiemy, że istnieje $y\in Y$ takie, że $y\leq x$ . A zatem $p\geq y\in Y$ , czyli $p\in Y\!\!\Uparrow$ .

gdy $X$ jest antyłańcuchem, to $X$ składa się, że wszystkich elementów minimalnych stożka $X\!\!\Uparrow$ .
dla antyłańcuchów $X,Y\subseteq {\mathcal {MA}}\!\left(\mathbf {P} \right)$ spełniających $X\subseteq Y\!\!\Uparrow$ zachodzi też $Y\subseteq X\!\!\Downarrow$ .

Dla dowodu niewprost, niech $y\in Y-X\!\!\Downarrow$ . Oznacza to, że nie istnieje $x\in X$ taki, że $y\leq x$ . W przypadku, gdy $y$ byłby nieporównywalny z żadnym elementem z $X$ , to $X\cup \left\lbrace y\right\rbrace$ byłby antyłańcuchem, i to większym od antyłańcucha $X$ , wbrew temu, że $X$ jest najbardziej liczny. Musi więc istnieć $x_{0}\in X$ takie, że $x_{0}\leq y$ . Ale teraz $x_{0}\in X\subseteq Y\!\!\Uparrow$ oznacza, że $x_{0}\geq y_{0}$ dla pewnego $y_{0}\in Y$ . Mamy więc $y_{0}\leq x_{0}\leq y$ dla dwu elementów $y_{0},y$ antyłańcucha $Y$ , czyli $y=y_{0}\leq x$ . To jednak daje $y\in X\!\!\Downarrow$ , wbrew założeniu o $y$ .

Pokażemy najpierw, że $\left({\mathcal {MA}}\!\left(\mathbf {P} \right),\leq \right)$ jest częściowym porządkiem. Tak więc kolejno sprawdzamy warunki:

zwrotność:

Ponieważ $A\subseteq A\!\!\Uparrow$ , to $A\leq A$ .

antysymetria:

Niech teraz $A,B\in {\mathcal {MA}}\!\left(\mathbf {P} \right)$ spełniają $A\subseteq B\!\!\Uparrow$ i $B\subseteq A\!\!\Uparrow$ . Wtedy $A\!\!\Uparrow \subseteq B\!\!\Uparrow$ , więc i zbiory $A,B$ muszą być równe, jako zbiory elementów minimalnych odpowiednio w $A\!\!\Uparrow$ i $B\!\!\Uparrow$ .

przechodniość:

Niech $A,B,C\in {\mathcal {MA}}\!\left(\mathbf {P} \right)$ spełniają $A\subseteq B\!\!\Uparrow$ oraz $B\subseteq C\!\!\Uparrow$ . Druga inkluzja daje $B\!\!\Uparrow \subseteq C\!\!\Uparrow$ , a zatem $A\ \subseteq B\!\!\Uparrow \ \subseteq C\!\!\Uparrow$ .

Wiemy więc, że $\left({\mathcal {MA}}\!\left(\mathbf {P} \right),\leq \right)$ jest zbiorem częściowo uporządkowanym. Aby pokazać, że $\left({\mathcal {MA}}\!\left(\mathbf {P} \right),\leq \right)$ jest kratą uzasadnimy, że zbiory opisane we wskazówce są kresami.

kres dolny:

Niech $C$ będzie zbiorem elementów minimalnych zbioru $A\cup B$ . tworzy kres dolny elementów $A,B$ w porządku $\left({\mathcal {MA}}\!\left(\mathbf {P} \right),\leq \right)$ . Nietrudno zauważyć, że $A\cup B\subseteq C\!\!\Uparrow$ , co implikuje, że $C\leq A$ jak i $C\leq B$ . Niech teraz $D\in {\mathcal {MA}}\!\left(\mathbf {P} \right)$ będzie ograniczeniem dolnym dla $A$ i $B$ , tzn. $A\subseteq D\!\!\Uparrow$ oraz $B\subseteq D\!\!\Uparrow$ . Wtedy $C\subseteq A\cup B\subseteq D\!\!\Uparrow$ , czyli $D\leq C$ , a zatem $C$ jest największym ograniczeniem dolnym dla $A,B$ w posecie $\left({\mathcal {MA}}\!\left(\mathbf {P} \right),\leq \right)$ .

kres górny:

Na mocy obserwacji, że dla $X,Y\in {\mathcal {MA}}\!\left(\mathbf {P} \right)$ warunki $X\subseteq Y\!\!\Uparrow$ i $Y\subseteq X\!\!\Downarrow$ są równoważne (i opisują porządek $X\leq Y$ w ${\mathcal {MA}}\!\left(\mathbf {P} \right)$ ) uzasadnienie, że zbiór elementów maksymalnych w $A\cup B$ jest kresem górnym dla $A,B$ , można przeprowadzić analogiczne jak dla kresu dolnego.

1. Poset

\mathbf {P} '

Ćwiczenie 5

Wymiar częściowego porządku $\mathbf {P} =\left(P,\leq \right)$ to minimalny rozmiar rodziny ${\mathcal {R}}=\left\lbrace \mathbf {L} _{1},\mathbf {L} _{2},\ldots ,\mathbf {L} _{k}\right\rbrace$ liniowych porządków $\mathbf {L} _{i}=\left(P,\leq _{i}\right)$ spełniających warunek

$\leq \ =\ \leq _{1}\ \cap \ \leq _{2}\ \cap \ \ldots \ \cap \ \leq _{k}$

Znajdź wymiar posetu $\mathbf {P} '=\left(P',\leq \right)$ przedstawionego na rysunku 1. Znajdź poset o wymiarze $3$ . Odpowiedź uzasadnij.

Wskazówka

Poset $\mathbf {P} '$ ma wymiar $2$ . Rozważ co się stanie, gdy dołożymy jeszcze zależność $v<u$ .

Rozwiązanie

2. Poset

\mathbf {P} ''

Na zbiorze $P'$ zdefiniujmy liniowe $\mathbf {L} _{1}=\left(P',\leq _{1}\right)$ oraz $\mathbf {L} _{2}=\left(P',\leq _{2}\right)$ jako:

${\begin{aligned}\mathbf {L} _{1}:&&x\ \leq _{1}\ u\ \leq _{1}\ w\ \leq _{1}\ t\ \leq _{1}\ v\ \leq _{1}\ s,\\\mathbf {L} _{2}:&&v\ \leq _{2}\ w\ \leq _{2}\ s\ \leq _{2}\ x\ \leq _{2}\ t\ \leq _{2}\ u.\end{aligned}}$

Nietrudno sprawdzić, że $\leq =\leq _{1}\cap \leq _{2}$ , a więc poset $\mathbf {P} '=\left(P',\leq \right)$ ma wymiar co najwyżej $2$ . Oczywiście nie może mieć on wymiaru $1$ , bo posety wymiaru jeden są łańcuchami.

Rozważmy teraz poset $\mathbf {P} ''=\left(P'',\leq ''\right)$ przedstawiony na rysunku 2.

Załóżmy, że $\mathbf {P} ''$ ma wymiar $2$ . Istnieją więc dwa liniowe porządki $\mathbf {L} ''_{1}=\left(P'',\leq ''_{1}\right)$ oraz $\mathbf {L} ''_{2}=\left(P'',\leq ''_{2}\right)$ takie, że $\leq ''=\leq ''_{1}\cap \leq ''_{2}$ . Ponieważ $d\leq ''a$ , to w obu liniowych rozszerzeniach $\mathbf {L} ''_{1}$ oraz $\mathbf {L} ''_{2}$ zachodzi:

${\begin{aligned}\mathbf {L} ''_{1}:&&d\ \leq ''_{1}\ a,\\\mathbf {L} ''_{2}:&&d\ \leq ''_{2}\ a.\end{aligned}}$

Element $e$ jest mniejszy od $a$ , ale nieporównywalny z $d$ , więc bez straty ogólności możemy założyć, że

{\begin{aligned}\mathbf {L} ''_{1}:&&e\ \leq ''_{1}\ d\ \leq ''_{1}\ a,\\\mathbf {L} ''_{2}:&&d\ \leq ''_{2}\ e\ \leq ''_{2}\ a.\end{aligned}}

Element $c$ jest większy niż $e$ , ale nieporównywalny z $a$ oraz $d$ , więc jedyną możliwością umieszczenia $c$ jest

{\begin{aligned}\mathbf {L} ''_{1}:&&e\ \leq ''_{1}\ c\ \leq ''_{1}\ d\ \leq ''_{1}\ a,\\\mathbf {L} ''_{2}:&&d\ \leq ''_{2}\ e\ \leq ''_{2}\ a\ \leq ''_{2}\ c.\end{aligned}}

Z kolei $f$ musi być pod $c$ , i jako nieporównywalny ze zbiorem $\left\lbrace a,d,e\right\rbrace$ może więc być umieszczony tylko w następujący sposób:

{\begin{aligned}\mathbf {L} ''_{1}:&&f\ \leq ''_{1}\ e\ \leq ''_{1}\ c\ \leq ''_{1}\ d\ \leq ''_{1}\ a,\\\mathbf {L} ''_{2}:&&d\ \leq ''_{2}\ e\ \leq ''_{2}\ a\ \leq ''_{2}\ f\ \leq ''_{2}\ c.\end{aligned}}

Element $b$ powinien być nad $d$ oraz $f$ , a być nieporównywalny z elementami $a,c,e$ , co już jest niemożliwe. Nie istnieją więc dwa takie rozszerzenia liniowe, które w przecięciu dają $\mathbf {P} ''$ .

Nietrudno jednak sprawdzić, że dla liniowych porządków $\mathbf {L} '''_{1}=\left(P'',\leq '''_{1}\right)$ , $\mathbf {L} '''_{2}=\left(P'',\leq '''_{2}\right)$ , oraz $\mathbf {L} '''_{3}=\left(P'',\leq '''_{3}\right)$ zadanych przez: