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

Diagram Hassego przykładowego porządku ${\mathbf{𝐏}}_0$

Łańcuch (a) oraz antyłańcuch (b) w posecie ${\mathbf{𝐏}}_0$

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

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

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

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

• $x\le y$, $y\le z$ implikuje $x\le 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{ℝ}}^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{𝐏}=(X,\le )$ to taki podzbiór $C$ zbioru $X$, że dla dowolnych $x,y\in X$ zachodzi:

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

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

• $x\le ̸y$ oraz $x\le ̸y$ (niezależność).

Szerokość posetu $\mathbf{𝐏}=(X,\le )$ to maksymalny możliwy rozmiar antyłańcucha w $\mathbf{𝐏}$. Szerokość oznaczana będzie za pomocą $\mathsf{w}\mathsf{i}\mathsf{d}\mathsf{t}\mathsf{h}\left(\mathbf{𝐏}\right)$.
W ogólności szerokość $\mathsf{w}\mathsf{i}\mathsf{d}\mathsf{t}\mathsf{h}\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{𝐏}=(X,\le )$ to taka rodzina łańcuchów $C_1,\dots C_k$, że

$C_1\cup \dots \cup C_k=X$

Twierdzenie 2.1 [R. P. Dilworth 1950]

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

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,\le )$. Niech $w=\mathsf{w}\mathsf{i}\mathsf{d}\mathsf{t}\mathsf{h}\left(\mathbf{𝐏}\right)$. Rozważmy maksymalny, w sensie inkluzji, łańcuch $C$ zawarty w $\mathbf{𝐏}$. 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{w}\mathsf{i}\mathsf{d}\mathsf{t}\mathsf{h}(P-C)=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{𝐏}$ za pomocą $w$.

• $\mathsf{w}\mathsf{i}\mathsf{d}\mathsf{t}\mathsf{h}(P-C)=w$

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

$\begin{array}{r}U=\{p\in P:\text{ istnieje }a\in A\text{ takie ,że }p\ge a\},\\ D=\{p\in P:\text{ istnieje }a\in A\text{ takie, że }p\le a\}.\end{array}$

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\in ̸C$ i w konsekwencji $\left\{a_0\right\}\cup C$ jest łańcuchem istotnie większym od maksymalnego w sensie inkluzji łańcucha $C$. To pokazuje, że $\left|U\right|<\left|P\right|$. Podobnie możemy uzasadnić, że również $\left|D\right|<\left|P\right|$. 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 \dots \cup C_w,D={C_1}^{\prime }\cup \dots \cup {C_w}^{\prime }$

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}^{\prime }$. 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}^{\prime }$ jest jakiś element z $A$. Pozwala to na takie przenumerowanie łańcuchów $C_i$ i ${C_j}^{\prime }$, by $C_i\cap {C_j}^{\prime }\ne \mathrm{\varnothing }$, tzn. że dla $a\in A$ mamy $a\in C_i$ wtedy i tylko wtedy, gdy $a\in {C_i}^{\prime }$. To z kolei oznacza, że każda suma $C_i\cup {C_i}^{\prime }$ jest łańcuchem. Oczywiście te nowe łańcuchy $C_i\cup {C_i}^{\prime }$ 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\{p\right\}$ 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}^{\prime })\cup \dots \cup (C_w\cup {C_w}^{\prime })$

całego zbioru $P$.

Pokrycie antyłańcuchowe posetu $\mathbf{𝐏}=(X,\le )$ to taka rodzina antyłańcuchów $A_1,\dots A_k$, że

$A_1\cup \dots \cup A_k=X$

Twierdzenie 2.2 [Dualne Twierdzenie Dilworth'a]]

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

Pokrycie antyłańcuchowe posetu ${\mathbf{𝐏}}_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 =\{x\in P:p\le x\}$

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\{p_1\right\}\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{𝐏}$. Oczywiście każdy punkt $p\in P$ musi być w którymś ze zbiorów $A_1,\dots ,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 \dots \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,\le )$ 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 \dots \cup A_{r^{\prime }}$,

gdzie $r^{\prime }\le r$ jest mocą łańcucha o maksymalnej liczności. Ponieważ $\left|A_i\right|\le s$, to

$\left|P\right|=\left|A_1\right|+\dots +\left|A_{r^{\prime }}\right|\le r^{\prime }s\le rs$

Sprzeczność ta pokazuje, że jeśli $\mathbf{𝐏}$ 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\ge 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=(a_1,\dots ,a_n)$ będzie ciągiem liczb rzeczywistych. Na parach postaci $(i,a_i)$, wprowadzamy relację częściowego porządku kładąc

$(i,a_i)\le (j,a_j)$ wtedy i tylko wtedy, gdy $i\le j$ oraz $a_i\le 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{𝐏}}_{\mathrm{\varnothing }}=({𝒫}\left(\mathrm{\varnothing }\right),\subseteq )$, ${\mathbf{𝐏}}_{\left\{a\right\}}=({𝒫}\left(\left\{a\right\}\right),\subseteq )$, ${\mathbf{𝐏}}_{\{a,b\}}=({𝒫}\left(\{a,b\}\right),\subseteq )$, ${\mathbf{𝐏}}_{\{a,b,c\}}=({𝒫}\left(\{a,b,c\}\right),\subseteq )$

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

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

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

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

Niech $\{A_1,\dots ,A_m\}$ będzie rodziną Spernera podzbiorów zbioru $X$. Wówczas

$\sum _{i=1}^m{(\genfrac{}{}{0ex}{}{\left|X\right|}{\left|A_i\right|})}^{-1}\le 1$

Dowód [D. Lubell]

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

$\mathrm{\varnothing }=C_0\subseteq C_1\subseteq \dots \subseteq C_{n-1}\subseteq C_n=X$

musi spełniać $\left|C_j\right|=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.

$\mathrm{\varnothing }=C_0\subseteq C_1\subseteq \dots \subseteq C_{\left|A_i\right|}=A_i\subseteq \dots \subseteq C_{n-1}\subseteq C_n=X$

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

$\mathrm{\varnothing }=C_0\subseteq C_1\subseteq \dots \subseteq C_{\left|A_i\right|}=A_i$

jest $\left|A_i\right|!$. W analogiczny sposób otrzymujemy, że różnych łańcuchów postaci

$A_i=C_{\left|A_i\right|}\subseteq C_{\left|A_i\right|+1}\subseteq \dots \subseteq C_n=X$

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

Ponieważ $\{A_1,\dots ,A_m\}$ jest antyłańcuchem, to dla $i\ne 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|A_i\right|!(n-\left|A_i\right|)!\le n!$

To w konsekwencji daje

$\sum _{i=1}^m\frac{1}{(\genfrac{}{}{0ex}{}{n}{\left|A_i\right|})}=\sum _{i=1}^m\frac{\left|A_i\right|!(n-\left|A_i\right|)!}{n!}\le 1$

Przykład

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

Twierdzenie 2.6 [E. Sperner 1928]

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

$\left|{𝒜}\right|\le (\genfrac{}{}{0ex}{}{\left|X\right|}{\lfloor \left|X\right|/2\rfloor })$

Dowód

Niech $n=\left|X\right|$ oraz ${𝒜}=\{A_1,\dots ,A_m\}$. Wartość $(\genfrac{}{}{0ex}{}{n}{k})$ jest maksymalna dla $k=\lfloor n/2\rfloor$. Tak więc $(\genfrac{}{}{0ex}{}{n}{\left|A_i\right|})\le (\genfrac{}{}{0ex}{}{n}{n/2})$. Na mocy Twierdzenia 2.5 otrzymujemy:

$m\frac{1}{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}\le \sum _{i=1}^m\frac{1}{(\genfrac{}{}{0ex}{}{n}{\left|A_i\right|})}\le 1$,

skąd natychmiast

$m\le (\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })$

Uwaga

W posecie $({𝒫}\left(X\right),\subseteq )$ dowolne dwa jego elementy $A,B\in {𝒫}\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(X\right),\subseteq )$ 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,\le )$, 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{\mathbb{N}}$ oraz relacje $⊑$ zdefiniowaną w następujący sposób

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

Relacja $⊑$ jest zwrotna, antysymetryczna, i przechodnia. Tak więc para $(\mathbb{\mathbb{N}},⊑)$ tworzy częściowy porządek. Jako ćwiczenie 6 pozostawiamy do udowodnienia, że $(\mathbb{\mathbb{N}},⊑)$ 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ść.