Zbiór częściowo uporządkowany (poset) to para \( \mathbf{P}=( X,\leq ) \), 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:
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:
Dla elementów \( x,y\in X \), jeśli \( y < x \), to punkt przypisany elementowi \( x \) jest powyżej punktu przypisanemu elementowi \( y \).
Łańcuch w zbiorze częściowo uporządkowanym \( \mathbf{P}=( X,\leq ) \) to taki podzbiór \( C \) zbioru \( X \), że dla dowolnych \( x,y\in X \) zachodzi:
Antyłańcuch w zbiorze częściowo uporządkowanym \( \mathbf{P}=( X,\leq ) \) to taki podzbiór \( A \) zbioru \( X \), że dla dowolnych \( x,y\in X \) zachodzi:
Szerokość posetu \( \mathbf{P}=( X,\leq ) \) to maksymalny możliwy rozmiar antyłańcucha w \( \mathbf{P} \). Szerokość oznaczana będzie za pomocą \( {\sf width}\!( \mathbf{P} ) \).
W ogólności szerokość \( {\sf width}\!( Y ) \) 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}=( X,\leq ) \) to taka rodzina łańcuchów \( C_1,\ldots C_k \), że
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}=( P,\leq ) \). Niech \( w={\sf width}\!( \mathbf{P} ) \). 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:
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 \).
Niech \( A \) bedzie antyłańcuchem realizującym szerokość zbioru \( P- C \), tzn. \( \vert A \vert=w \). Połóżmy:
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 \( \lbrace a_0 \rbrace\cup C \) jest łańcuchem istotnie większym od maksymalnego w sensie inkluzji łańcucha \( C \). To pokazuje, że \( \vert U \vert < \vert P \vert \). Podobnie możemy uzasadnić, że również \( \vert D \vert < \vert P \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 \lbrace p \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}=( X,\leq ) \) 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}=( P,\leq ) \) 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:
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 \( \lbrace p_1 \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:
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}=( P,\leq ) \) 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ż \( \vert A_i \vert\leq s \), to
\( \vert P \vert=\vert A_1 \vert+\ldots+\vert A_{r'} \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=( a_1,\ldots,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 )\leq( j,a_j ) \) 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.
Dla dowolnego zbioru \( X \) rodzina \( \mathscr{P}\!( X ) \) jego podzbiorów wraz z inkluzją tworzy zbiór częściowo uporządkowany \( ( \mathscr{P}\!( X ),\subseteq ) \).
Rodzina Sperner'a podzbiorów zbioru \( X \) to antyłańcuch w posecie \( ( \mathscr{P}\!( X ),\subseteq ) \).
Starano się oszacować liczność rodzin Spernera, czyli znaleźć szerokość posetu \( ( \mathscr{P}\!( X ),\subseteq ) \). Poniższe twierdzenie pomaga odpowiedzieć na to pytanie.
Twierdzenie 2.5 [K. Yamamoto 1954; L. D. Meshalkin 1963; D. Lubell 1966]
Niech \( \lbrace A_1,\ldots,A_m \rbrace \) będzie rodziną Spernera podzbiorów zbioru \( X \). Wówczas
\( \sum_{i=1}^{m}{\vert X \vert \choose \vert A_i \vert}^{-1}\leq 1. \)
Dowód [D. Lubell]
Niech \( n=\vert X \vert \). W posecie \( ( \mathscr{P}\!( X ),\subseteq ) \) każdy maksymalny łańcuch
\( \emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{n-1}\subseteq C_n=X \)
musi spełniać \( \vert C_j \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_{\vert A_i \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 \( \vert A_i \vert \) sposobów. Tak więc \( C_2 \) może być wybrane już jedynie na \( \vert A_i \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_{\vert A_i \vert}=A_i \)
jest \( \vert A_i \vert! \). W analogiczny sposób otrzymujemy, że różnych łańcuchów postaci
\( A_i=C_{\vert A_i \vert}\subseteq C_{\vert A_i \vert+1}\subseteq\ldots\subseteq C_n=X \)
jest \( ( n-\vert A_i \vert )! \). Podsumowując, liczba maksymalnych łańcuchów, w których występuje \( A_i \) wynosi \( \vert A_i \vert!( n-\vert A_i \vert )! \).
Ponieważ \( \lbrace A_1,\ldots,A_m \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{\vert A_i \vert!( n-\vert A_i \vert )!}\leq n!. \)
To w konsekwencji daje
\( \sum_{i=1}^{m}{\frac{1}{{n\choose\vert A_i \vert}}} =\sum_{i=1}^m{\frac{\vert A_i \vert!( n-\vert A_i \vert )!}{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=/n/2\rfloor \), to \( n \)-elementowy podzbiór ma rodzinę Spernera o mocy \( {n \choose /n/2\rfloor} \). Następne twierdzenie pokazuje, że jest to najliczniejsza rodzina Spernera.
Twierdzenie 2.6 [E. Sperner 1928]
Jeśli \( \mathscr{A} \) jest rodziną Spernera podzbiorów zbioru \( X \), to
\( \vert \mathscr{A} \vert\leq{\vert X \vert\choose\lfloor\vert X \vert/2\rfloor}. \)
Dowód
Niech \( n=\vert X \vert \) oraz \( \mathscr{A}=\lbrace A_1,\ldots,A_m \rbrace \). Wartość \( {n\choose k} \) jest maksymalna dla \( k=/2\rfloor \). Tak więc \( {n\choose\vert A_i \vert}\leq{n\choose{n/2}} \). Na mocy Twierdzenia 2.5 otrzymujemy:
\( m\frac{1}{{n \choose/2\rfloor }}\leq\sum_{i=1}^{m}{\frac{1}{{n\choose\vert A_i \vert}}}\leq 1, \)
skąd natychmiast
\( m\leq{n\choose/2\rfloor}. \)
Uwaga
W posecie \( ( \mathscr{P}\!( X ),\subseteq ) \) dowolne dwa jego elementy \( A,B\in\mathscr{P}\!( X ) \) spełniają:
W takim razie dowolne dwa elementy posetu \( ( \mathscr{P}\!( X ),\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}=( P,\leq ) \), w którym dla dowolnych \( a,b\in P \) istnieją
Kres dolny oznaczać bedziemy przez \( a \wedge 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\textrm{wtedy i tylko wtedy, gdy}\quad a\ \textrm{dzieli}\ b\quad\textrm{dla}\ a,b\in\mathbb{N}. \)
Relacja \( \sqsubseteq \) jest zwrotna, antysymetryczna, i przechodnia. Tak więc para \( ( \mathbb{N},\sqsubseteq ) \) tworzy częściowy porządek. Jako ćwiczenie 6 pozostawiamy do udowodnienia, że \( ( \mathbb{N},\sqsubseteq ) \) 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ść.