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

<flash>file=Minmax poset2.swf|width=250|height=250</flash>

<div.thumbcaption>Diagram Hassego przykładowego porządku ${\mathbf{𝐏}}_0$

<flash>file=Minmax poset chain antichain.swf|width=250|height=200</flash>

<div.thumbcaption>Łańcuch (a) oraz antyłańcuch (b) w posecie ${\mathbf{𝐏}}_0$

<flash>file=Minmax poset width partition.swf|width=250|height=200</flash>

<div.thumbcaption>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ą Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf width}\!\left( \mathbf{P} \right)} .
W ogólności szerokość Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf 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{𝐏}=(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle w={\sf width}\!\left( \mathbf{P} \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:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf 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{𝐏}$ za pomocą $w$.

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf width}\!\left( P- C \right)=w}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned U=\left\lbrace p\in P:\textrm{ istnieje }a\in A \textrm{ takie ,że }p\geq a \right\rbrace,\\ D=\left\lbrace p\in P:\textrm{ istnieje }a\in A \textrm{ takie, że }p\leq a \right\rbrace. \endaligned}

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{𝐏}$.

<flash>file=Minmax poset antichain partition.swf|width=250|height=250</flash>

<div.thumbcaption>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.

<flash>file=Minmax poset 2X.swf|width=350|height=200</flash> <div.thumbcaption>Posety: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{P}_\emptyset=\left( \mathscr{P}\!\left( \emptyset \right),\subseteq \right)} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{P}_{\left\lbrace a \right\rbrace}=\left( \mathscr{P}\!\left( \left\lbrace a \right\rbrace \right),\subseteq \right)} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{P}_{\left\lbrace a,b \right\rbrace}=\left( \mathscr{P}\!\left( \left\lbrace a,b \right\rbrace \right),\subseteq \right)} ,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{P}_{\left\lbrace a,b,c \right\rbrace}=\left( \mathscr{P}\!\left( \left\lbrace a,b,c \right\rbrace \right),\subseteq \right)}

Dla dowolnego zbioru $X$ rodzina Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{P}\!\left( X \right)} jego podzbiorów wraz z inkluzją tworzy zbiór częściowo uporządkowany Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right)} .

Rodzina Sperner'a podzbiorów zbioru $X$ to antyłańcuch w posecie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right)} .

Starano się oszacować liczność rodzin Spernera, czyli znaleźć szerokość posetu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left( \mathscr{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 $\{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right)} 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 Parser nie mógł rozpoznać (nieznana funkcja „\lfloorn”): {\displaystyle k=\left/n\lfloorn/2\right\rfloor} , to $n$-elementowy podzbiór ma rodzinę Spernera o mocy Parser nie mógł rozpoznać (nieznana funkcja „\lfloorn”): {\displaystyle {n \choose \left/n\lfloorn/2\right\rfloor}} . Następne twierdzenie pokazuje, że jest to najliczniejsza rodzina Spernera.

Twierdzenie 2.6 [E. Sperner 1928]

Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}} jest rodziną Spernera podzbiorów zbioru $X$, to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert \mathscr{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|X\right|$ oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}=\left\lbrace A_1,\ldots,A_m \right\rbrace} . Wartość $(\genfrac{}{}{0ex}{}{n}{k})$ jest maksymalna dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle k=\left\lfloorn/2\right\rfloor} . Tak więc $(\genfrac{}{}{0ex}{}{n}{\left|A_i\right|})\le (\genfrac{}{}{0ex}{}{n}{n/2})$. Na mocy Twierdzenia 2.5 otrzymujemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle m\frac{1}{{n \choose \left\lfloorn/2\right\rfloor }}\leq\sum_{i=1}^{m}{\frac{1}{{n\choose\left\vert A_i \right\vert}}}\leq 1, }

skąd natychmiast

Parser nie mógł rozpoznać (błąd składni): {\displaystyle m\leq{n\choose\left\lfloorn/2\right\rfloor}. }

Uwaga

W posecie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right)} dowolne dwa jego elementy Parser nie mógł rozpoznać (błąd składni): {\displaystyle A,B\in\mathscr{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left( \mathscr{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,\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{<mrow data-mjx-texclass="ORD">wtedyitylkowtedy<mo>,</mo>gdy</mrow>}a\text{<mrow data-mjx-texclass="ORD">dzieli</mrow>}b\text{<mrow data-mjx-texclass="ORD">dla</mrow>}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ść.