Matematyka dyskretna 2/Wykład 2: Porządki Częściowe i twierdzenie Dilworth'a

Diagram Hassego przykładowego porządku $\mathbf {P} _{0}$

Łańcuch (a) oraz antyłańcuch (b) w posecie $\mathbf {P} _{0}$

Antyłańcuch realizujący szerokość (a) oraz pokrycie łańcuchowe (b) posetu $\mathbf {P} _{0}$

Zbiór częściowo uporządkowany (poset) to para $\mathbf {P} =\left(X,\leq \right)$, gdzie $X$ jest zbiorem, zaś $\leq$ jest dwuargumentową relacją określoną na $X$, która dla dowolnie wybranych $x,y,z\in X$ spełnia:

• $x\leq x$ (zwrotność),

• $x\leq y$, $y\leq x$ implikuje $x=y$ (antysymetria),

• $x\leq y$, $y\leq z$ implikuje $x\leq z$ (przechodniość).

Uwaga

Częściowy porządek wygodnie przedstawiać jest przy użyciu tzw. diagramu Hassego, który przedstawia się na płaszczyźnie $\mathbb {R} ^{2}$ w następujący sposób:

• Umieszczamy punkty obrazujące elementy zbioru $X$ na płaszczyźnie,oznaczając je małymi kółkami.
  

Dla elementów $x,y\in X$, jeśli $y<x$, to punkt przypisany elementowi $x$ jest powyżej punktu przypisanemu elementowi $y$.

• Łączymy odcinkiem punkt $x\in X$ z punktem $y\in X$, jeśli $x$ jest następnikiem $y$, czyli $y<x$ oraz nie istnieje $z\in X$, taki że $y<z<x$.

Łańcuch w zbiorze częściowo uporządkowanym $\mathbf {P} =\left(X,\leq \right)$ to taki podzbiór $C$ zbioru $X$, że dla dowolnych $x,y\in X$ zachodzi:

• $x\leq y$ oraz $x\leq y$ (liniowość).

Antyłańcuch w zbiorze częściowo uporządkowanym $\mathbf {P} =\left(X,\leq \right)$ to taki podzbiór $A$ zbioru $X$, że dla dowolnych $x,y\in X$ zachodzi:

• $x\not \leq y$ oraz $x\not \leq y$ (niezależność).

Szerokość posetu $\mathbf {P} =\left(X,\leq \right)$ to maksymalny możliwy rozmiar antyłańcucha w $\mathbf {P}$. Szerokość oznaczana będzie za pomocą ${\mathsf {width}}\!\left(\mathbf {P} \right)$.
W ogólności szerokość ${\mathsf {width}}\!\left(Y\right)$ można zdefiniować dla dowolnego podzbioru $Y\subseteq X$, jako największy możliwy rozmiar antyłańcucha zawartego w $Y$.

Pokrycie łańcuchowe posetu $\mathbf {P} =\left(X,\leq \right)$ to taka rodzina łańcuchów $C_{1},\ldots C_{k}$, że

$C_{1}\cup \ldots \cup C_{k}=X$

Twierdzenie 2.1 [R. P. Dilworth 1950]

Minimalna liczba łańcuchów pokrywających poset $\mathbf {P}$ jest równa szerokości posetu $\mathbf {P}$.

Dowód

Oczywiście liczba łańcuchów pokrywających poset nie może być mniejsza niż jego szerokość, bo każdy punkt w antyłańcuchu realizującym tę szerokość musi być pokryty innym łańcuchem.

Dowód implikacji odwrotnej przeprowadzimy indukcyjnie ze względu na liczność $n$ posetu $\mathbf {P} =\left(P,\leq \right)$. Niech $w={\mathsf {width}}\!\left(\mathbf {P} \right)$. Rozważmy maksymalny, w sensie inkluzji, łańcuch $C$ zawarty w $\mathbf {P}$. Po usunięciu łańcucha $C$ szerokość posetu może zmniejszyć się co najwyżej o jeden. Dowód podzielimy więc na dwa przypadki:

• ${\mathsf {width}}\!\left(P-C\right)=w-1$

Na mocy założenia indukcyjnego poset $P-C$ daje się pokryć $w-1$ łańcuchami, które wobec tego wraz z $C$ tworzą szukane pokrycie całego posetu $\mathbf {P}$ za pomocą $w$.

• ${\mathsf {width}}\!\left(P-C\right)=w$

Niech $A$ bedzie antyłańcuchem realizującym szerokość zbioru $P-C$, tzn. $\left\vert A\right\vert =w$. Połóżmy:

${\begin{aligned}U=\left\lbrace p\in P:{\text{ istnieje }}a\in A{\text{ takie ,że }}p\geq a\right\rbrace ,\\D=\left\lbrace p\in P:{\text{ istnieje }}a\in A{\text{ takie, że }}p\leq a\right\rbrace .\end{aligned}}$

Jeśli $U=P$, to łańcuch $C$ całkowicie zawiera się w $U$. Z definicji zbioru $U$ wynika, że istnieje element $a_{0}\in A$, który jest mniejszy od najmniejszego elementu łańcucha $C$, a tym samym od wszystkich elementów w $C$. Skoro $A\subseteq P-C$, to $a_{0}\not \in C$ i w konsekwencji $\left\lbrace a_{0}\right\rbrace \cup C$ jest łańcuchem istotnie większym od maksymalnego w sensie inkluzji łańcucha $C$. To pokazuje, że $\left\vert U\right\vert <\left\vert P\right\vert$. Podobnie możemy uzasadnić, że również $\left\vert D\right\vert <\left\vert P\right\vert$. Do obu zbiorów $U,D$ możemy więc zastosować założenie indukcyjne, dostając ich pokrycia łańcuchowe

$U=C_{1}\cup \ldots \cup C_{w},\quad D=C_{1}'\cup \ldots \cup C_{w}'$

Ponieważ $A\subseteq D\cap U$, to każdy element z $A$ należy do jakiegoś łańcucha $C_{i}$ i do jakiegoś łańcucha $C_{j}'$. Z drugiej strony fakt, że $A$ jest $w$-elementowym antyłańcuchem gwarantuje, że w każdym łańcuchu postaci $C_{i}$ lub $C_{j}'$ jest jakiś element z $A$. Pozwala to na takie przenumerowanie łańcuchów $C_{i}$ i $C_{j}'$, by $C_{i}\cap C_{j}'\neq \emptyset$, tzn. że dla $a\in A$ mamy $a\in C_{i}$ wtedy i tylko wtedy, gdy $a\in C_{i}'$. To z kolei oznacza, że każda suma $C_{i}\cup C_{i}'$ jest łańcuchem. Oczywiście te nowe łańcuchy $C_{i}\cup C_{i}'$ pokrywają zbiór $D\cup U$. Zauważmy jednak, że $D\cup U=P$, bo inaczej istniałby element $p\in P$ nieporównywalny z żadnym elementem antyłańcucha $A$, czyli $A\cup \left\lbrace p\right\rbrace$ byłby antyłańcuchem istotnie większym niż maksymalny antyłańcuch $A$. W konsekwencji otrzymujemy pokrycie łańcuchowe

$P=(C_{1}\cup C_{1}')\cup \ldots \cup (C_{w}\cup C_{w}')$

całego zbioru $P$.

Pokrycie antyłańcuchowe posetu $\mathbf {P} =\left(X,\leq \right)$ to taka rodzina antyłańcuchów $A_{1},\ldots A_{k}$, że

$A_{1}\cup \ldots \cup A_{k}=X$

Twierdzenie 2.2 [Dualne Twierdzenie Dilworth'a]]

Minimalna liczba antyłańcuchów pokrywających poset $\mathbf {P} =\left(P,\leq \right)$ jest równa maksymalnej liczności łańcucha zawartego w $\mathbf {P}$.

Pokrycie antyłańcuchowe posetu $\mathbf {P} _{0}$

Dowód

Moc najdłuższego łańcucha oznaczmy przez $h$. Niech $A_{i}$ będzie zbiorem elementów $p\in P$ spełniających:

$(*)$ w zbiorze $p\!\uparrow =\left\lbrace x\in P:p\leq x\right\rbrace$

najliczniejszy łańcuch jest mocy $i$.

Pokażemy, że każde $A_{i}$ jest antyłańcuchem. Istotnie, gdyby dwa różne elementy $p_{1},p_{2}\in A_{i}$ były porównywalne, to możemy bez straty ogólności założyć, że $p_{1}<p_{2}$. Ponieważ $p_{2}\in A_{i}$, to w zbiorze $p_{2}\!\uparrow$ jest łańcuch o liczności $i$.

Łańcuch ten jednak można by przedłużyć (od dołu) do liczniejszego łańcucha $\left\lbrace p_{1}\right\rbrace \cup C_{2}$. To oczywiście przeczy temu, że $p_{1}\in A_{i}$. Zatem istotnie każde $A_{i}$ jest antyłańcuchem. Intuicyjnie antyłańcuchy $A_{i}$ to kolejne piętra posetu $\mathbf {P}$. Oczywiście każdy punkt $p\in P$ musi być w którymś ze zbiorów $A_{1},\ldots ,A_{h}$, bo $p\!\uparrow$ nie może zawierać łańcuchów liczniejszych niż $h$. Dostaliśmy więc następujące pokrycie antyłańcuchami:

$P=A_{1}\cup \ldots \cup A_{h}$

Oczywiście pokrycie to jest najmniej liczne, bo w każdym pokryciu każdy spośród $h$ punktów najdłuższego łańcucha musi leżeć w innym antyłańcuchu.

Wniosek 2.3

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$.

Dowód

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$. Dualne Twierdzenie Dilworth'a 2.2 dostarcza pokrycie antyłańcuchami

$P=A_{1}\cup \ldots \cup A_{r'}$,

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

$\left\vert P\right\vert =\left\vert A_{1}\right\vert +\ldots +\left\vert A_{r'}\right\vert \leq r's\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$.

Uwaga

Dowód wniosku 2.3 można równie dobrze przeprowadzić opierając się na Twierdzeniu Dilworth'a 2.1, co pozostawiamy jako ćwiczenie 3.

Jednym z ciekawszych wniosków z Twierdzenia Dilworth'a jest fakt, że każdy ciąg $r^{2}+1$ liczb rzeczywistych zawiera podciąg monotoniczny o $r+1$ elementach. Pierwszy dowód tego twierdzenia przedstawili P. Erd{o}s oraz G. Szekres w 1939 roku. Poniżej przedstawione jest uogólnienie tego twierdzenia, którego uzasadnienie będzie korzystało z wniosku 2.3.

Twierdzenie 2.4

Każdy ciąg $n\geq rs+1$ liczb rzeczywistych zawiera podciąg niemalejący o długości $r+1$ lub podciąg malejący o długości $s+1$.

Dowód

Niech $A=\left(a_{1},\ldots ,a_{n}\right)$ będzie ciągiem liczb rzeczywistych. Na parach postaci $\left(i,a_{i}\right)$, wprowadzamy relację częściowego porządku kładąc

$\left(i,a_{i}\right)\leq \left(j,a_{j}\right)$ wtedy i tylko wtedy, gdy $i\leq j$ oraz $a_{i}\leq a_{j}$.

Łańcuchy w tym porządku, to nic innego jak podciągi niemalejące ciągu $A$, a antyłańcuchy to podciągi malejące ciągu $A$. Po tym utożsamieniu wystarczy powołać się na Wniosek 2.3.

Krata podzbiorów i twierdzenie Sperner'a.

Posety: $\mathbf {P} _{\emptyset }=\left({\mathcal {P}}\!\left(\emptyset \right),\subseteq \right)$, $\mathbf {P} _{\left\lbrace a\right\rbrace }=\left({\mathcal {P}}\!\left(\left\lbrace a\right\rbrace \right),\subseteq \right)$, $\mathbf {P} _{\left\lbrace a,b\right\rbrace }=\left({\mathcal {P}}\!\left(\left\lbrace a,b\right\rbrace \right),\subseteq \right)$, $\mathbf {P} _{\left\lbrace a,b,c\right\rbrace }=\left({\mathcal {P}}\!\left(\left\lbrace a,b,c\right\rbrace \right),\subseteq \right)$

Dla dowolnego zbioru $X$ rodzina ${\mathcal {P}}\!\left(X\right)$ jego podzbiorów wraz z inkluzją tworzy zbiór częściowo uporządkowany $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$.

Rodzina Sperner'a podzbiorów zbioru $X$ to antyłańcuch w posecie $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$.

Starano się oszacować liczność rodzin Spernera, czyli znaleźć szerokość posetu $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$. Poniższe twierdzenie pomaga odpowiedzieć na to pytanie.

Twierdzenie 2.5 [K. Yamamoto 1954; L. D. Meshalkin 1963; D. Lubell 1966]

Niech $\left\lbrace A_{1},\ldots ,A_{m}\right\rbrace$ będzie rodziną Spernera podzbiorów zbioru $X$. Wówczas

$\sum _{i=1}^{m}{\left\vert X\right\vert \choose \left\vert A_{i}\right\vert }^{-1}\leq 1$

Dowód [D. Lubell]

Niech $n=\left\vert X\right\vert$. W posecie $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$ każdy maksymalny łańcuch

$\emptyset =C_{0}\subseteq C_{1}\subseteq \ldots \subseteq C_{n-1}\subseteq C_{n}=X$

musi spełniać $\left\vert C_{j}\right\vert =j$. Zbiór $C_{1}$ może być wybrany na $n$ sposobów, z kolei $C_{2}$ na $n-1$ sposobów. W ogólności $C_{j}$ może być wybrany na $n-j+1$ sposobów. Czyli łącznie jest $n!$ różnych łańcuchów maksymalnych.

Z drugiej strony policzymy ile jest łańcuchów, w których występuje konkretny zbiór $A_{i}$ z rodziny Spernera, tzn.

$\emptyset =C_{0}\subseteq C_{1}\subseteq \ldots \subseteq C_{\left\vert A_{i}\right\vert }=A_{i}\subseteq \ldots \subseteq C_{n-1}\subseteq C_{n}=X$

Ponieważ singleton $C_{1}$ musi zawierać się w $A_{i}$, może być wybrany na $\left\vert A_{i}\right\vert$ sposobów. Tak więc $C_{2}$ może być wybrane już jedynie na $\left\vert A_{i}\right\vert -1$ sposobów i tak dalej. A zatem różnych łańcuchów postaci

$\emptyset =C_{0}\subseteq C_{1}\subseteq \ldots \subseteq C_{\left\vert A_{i}\right\vert }=A_{i}$

jest $\left\vert A_{i}\right\vert !$. W analogiczny sposób otrzymujemy, że różnych łańcuchów postaci

$A_{i}=C_{\left\vert A_{i}\right\vert }\subseteq C_{\left\vert A_{i}\right\vert +1}\subseteq \ldots \subseteq C_{n}=X$

jest $\left(n-\left\vert A_{i}\right\vert \right)!$. Podsumowując, liczba maksymalnych łańcuchów, w których występuje $A_{i}$ wynosi $\left\vert A_{i}\right\vert !\left(n-\left\vert A_{i}\right\vert \right)!$.

Ponieważ $\left\lbrace A_{1},\ldots ,A_{m}\right\rbrace$ jest antyłańcuchem, to dla $i\neq j$ w łańcuchu nie mogą wystąpić równocześnie $A_{i}$ i $A_{j}$. Zliczając teraz maksymalne łańcuchy przechodzące przez któreś $A_{i}$, możemy pominąć jakiś łańcuch maksymalny. Nie mniej jednak mamy

$\sum _{i=1}^{m}{\left\vert A_{i}\right\vert !\left(n-\left\vert A_{i}\right\vert \right)!}\leq n!$

To w konsekwencji daje

$\sum _{i=1}^{m}{\frac {1}{n \choose \left\vert A_{i}\right\vert }}=\sum _{i=1}^{m}{\frac {\left\vert A_{i}\right\vert !\left(n-\left\vert A_{i}\right\vert \right)!}{n!}}\leq 1$

Przykład

Oczywiście, dla ustalonego $k$ rodzina $k$-elementowych podzbiorów jest rodziną Spernera. Ponieważ wartość ${n \choose k}$ jest maksymalna dla $k=\left/n\lfloor n/2\right\rfloor$, to $n$-elementowy podzbiór ma rodzinę Spernera o mocy ${n \choose \left/n\lfloor n/2\right\rfloor }$. Następne twierdzenie pokazuje, że jest to najliczniejsza rodzina Spernera.

Twierdzenie 2.6 [E. Sperner 1928]

Jeśli ${\mathcal {A}}$ jest rodziną Spernera podzbiorów zbioru $X$, to

$\left\vert {\mathcal {A}}\right\vert \leq {\left\vert X\right\vert \choose \left\lfloor \left\vert X\right\vert /2\right\rfloor }$

Dowód

Niech $n=\left\vert X\right\vert$ oraz ${\mathcal {A}}=\left\lbrace A_{1},\ldots ,A_{m}\right\rbrace$. Wartość ${n \choose k}$ jest maksymalna dla $k=\left\lfloor n/2\right\rfloor$. Tak więc ${n \choose \left\vert A_{i}\right\vert }\leq {n \choose {n/2}}$. Na mocy Twierdzenia 2.5 otrzymujemy:

$m{\frac {1}{n \choose \left\lfloor n/2\right\rfloor }}\leq \sum _{i=1}^{m}{\frac {1}{n \choose \left\vert A_{i}\right\vert }}\leq 1$,

skąd natychmiast

$m\leq {n \choose \left\lfloor n/2\right\rfloor }$

Uwaga

W posecie $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$ dowolne dwa jego elementy $A,B\in {\mathcal {P}}\!\left(X\right)$ spełniają:

• $A\cap B$ jest największym wspólnym ograniczeniem dolnym dla $A$ i $B$,

• $A\cup B$ jest największym wspólnym ograniczeniem górnym dla $A$ i $B$.

W takim razie dowolne dwa elementy posetu $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$ mają najmniejsze ograniczenie górne oraz największe ograniczenie dolne. Posety o tej własności nazywane są kratami.

Krata to częściowy porządek $\mathbf {P} =\left(P,\leq \right)$, w którym dla dowolnych $a,b\in P$ istnieją

• kres dolny, czyli największe ograniczenie dolne wspólne dla $a$ i $b$.

Kres dolny oznaczać bedziemy przez $a\wedge b$.

• kres górny, czyli najmniejsze ograniczenie górne wspólne dla $a$ i $b$.

Kres dolny oznaczać bedziemy przez $a\vee b$.

Przykład

Rozważmy zbiór liczb naturalnych $\mathbb {N}$ oraz relacje $\sqsubseteq$ zdefiniowaną w następujący sposób

$a\sqsubseteq b\quad {\text{wtedy i tylko wtedy, gdy}}\quad a\ {\text{dzieli}}\ b\quad {\text{dla}}\ a,b\in \mathbb {N}$

Relacja $\sqsubseteq$ jest zwrotna, antysymetryczna, i przechodnia. Tak więc para $\left(\mathbb {N} ,\sqsubseteq \right)$ tworzy częściowy porządek. Jako ćwiczenie 6 pozostawiamy do udowodnienia, że $\left(\mathbb {N} ,\sqsubseteq \right)$ jest kratą, oraz że kres dolny dwu liczb naturalnych to ich największy wspólny dzielnik, a kres ich kres górny to najmniejsza wspólna wielokrotność.