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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Diagram Hassego przykładowego porządku
Łańcuch (a) oraz antyłańcuch (b) w posecie
Antyłańcuch realizujący szerokość (a) oraz pokrycie łańcuchowe (b) posetu

Zbiór częściowo uporządkowany (poset) to para , gdzie jest zbiorem, zaś jest dwuargumentową relacją określoną na , która dla dowolnie wybranych spełnia:

  • (zwrotność),
  • , implikuje (antysymetria),
  • , implikuje (przechodniość).
Uwaga

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

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

Dla elementów , jeśli , to punkt przypisany elementowi jest powyżej punktu przypisanemu elementowi .

  • Łączymy odcinkiem punkt z punktem , jeśli jest następnikiem , czyli oraz nie istnieje , taki że .

Łańcuch w zbiorze częściowo uporządkowanym to taki podzbiór zbioru , że dla dowolnych zachodzi:

  • oraz (liniowość).

Antyłańcuch w zbiorze częściowo uporządkowanym to taki podzbiór zbioru , że dla dowolnych zachodzi:

  • oraz (niezależność).

Szerokość posetu to maksymalny możliwy rozmiar antyłańcucha w . Szerokość oznaczana będzie za pomocą .
W ogólności szerokość można zdefiniować dla dowolnego podzbioru , jako największy możliwy rozmiar antyłańcucha zawartego w .

Pokrycie łańcuchowe posetu to taka rodzina łańcuchów , że



Twierdzenie 2.1 [R. P. Dilworth 1950]

Minimalna liczba łańcuchów pokrywających poset jest równa szerokości posetu .

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ść posetu . Niech . Rozważmy maksymalny, w sensie inkluzji, łańcuch zawarty w . Po usunięciu łańcucha 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 daje się pokryć łańcuchami, które wobec tego wraz z tworzą szukane pokrycie całego posetu za pomocą .

Niech bedzie antyłańcuchem realizującym szerokość zbioru , tzn. . Połóżmy:



Jeśli , to łańcuch całkowicie zawiera się w . Z definicji zbioru wynika, że istnieje element , który jest mniejszy od najmniejszego elementu łańcucha , a tym samym od wszystkich elementów w . Skoro , to i w konsekwencji jest łańcuchem istotnie większym od maksymalnego w sensie inkluzji łańcucha . To pokazuje, że . Podobnie możemy uzasadnić, że również . Do obu zbiorów możemy więc zastosować założenie indukcyjne, dostając ich pokrycia łańcuchowe



Ponieważ , to każdy element z należy do jakiegoś łańcucha i do jakiegoś łańcucha . Z drugiej strony fakt, że jest -elementowym antyłańcuchem gwarantuje, że w każdym łańcuchu postaci lub jest jakiś element z . Pozwala to na takie przenumerowanie łańcuchów i , by , tzn. że dla mamy wtedy i tylko wtedy, gdy . To z kolei oznacza, że każda suma jest łańcuchem. Oczywiście te nowe łańcuchy pokrywają zbiór . Zauważmy jednak, że , bo inaczej istniałby element nieporównywalny z żadnym elementem antyłańcucha , czyli byłby antyłańcuchem istotnie większym niż maksymalny antyłańcuch . W konsekwencji otrzymujemy pokrycie łańcuchowe



całego zbioru .

End of proof.gif

Pokrycie antyłańcuchowe posetu to taka rodzina antyłańcuchów , że



Twierdzenie 2.2 [Dualne Twierdzenie Dilworth'a]]

Minimalna liczba antyłańcuchów pokrywających poset jest równa maksymalnej liczności łańcucha zawartego w .

Pokrycie antyłańcuchowe posetu

Dowód

Moc najdłuższego łańcucha oznaczmy przez . Niech będzie zbiorem elementów spełniających:

w zbiorze

najliczniejszy łańcuch jest mocy .

Pokażemy, że każde jest antyłańcuchem. Istotnie, gdyby dwa różne elementy były porównywalne, to możemy bez straty ogólności założyć, że . Ponieważ , to w zbiorze jest łańcuch o liczności .

Łańcuch ten jednak można by przedłużyć (od dołu) do liczniejszego łańcucha . To oczywiście przeczy temu, że . Zatem istotnie każde jest antyłańcuchem. Intuicyjnie antyłańcuchy to kolejne piętra posetu . Oczywiście każdy punkt musi być w którymś ze zbiorów , bo nie może zawierać łańcuchów liczniejszych niż . 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 punktów najdłuższego łańcucha musi leżeć w innym antyłańcuchu.

End of proof.gif

Wniosek 2.3

Każdy zbiór częściowo uporządkowany o elementach zawiera łańcuch o liczności lub antyłańcuch o liczności .

Dowód

Niech będzie posetem, w którym każdy łańcuch jest liczności co najwyżej , a każdy antyłańcuch jest liczności co najwyżej . Dualne Twierdzenie Dilworth'a 2.2 dostarcza pokrycie antyłańcuchami



gdzie jest mocą łańcucha o maksymalnej liczności. Ponieważ , to



Sprzeczność ta pokazuje, że jeśli ma co najmniej elementów, to musi zawierać łańcuch o liczności lub antyłańcuch o liczności .

End of proof.gif
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 liczb rzeczywistych zawiera podciąg monotoniczny o 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 liczb rzeczywistych zawiera podciąg niemalejący o długości lub podciąg malejący o długości .

Dowód

Niech będzie ciągiem liczb rzeczywistych. Na parach postaci , wprowadzamy relację częściowego porządku kładąc

wtedy i tylko wtedy, gdy oraz .

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

End of proof.gif

Krata podzbiorów i twierdzenie Sperner'a.

Posety: , , ,

Dla dowolnego zbioru rodzina jego podzbiorów wraz z inkluzją tworzy zbiór częściowo uporządkowany .

Rodzina Sperner'a podzbiorów zbioru to antyłańcuch w posecie .

Starano się oszacować liczność rodzin Spernera, czyli znaleźć szerokość posetu . Poniższe twierdzenie pomaga odpowiedzieć na to pytanie.

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

Niech będzie rodziną Spernera podzbiorów zbioru . Wówczas



Dowód [D. Lubell]

Niech . W posecie każdy maksymalny łańcuch



musi spełniać . Zbiór może być wybrany na sposobów, z kolei na sposobów. W ogólności może być wybrany na sposobów. Czyli łącznie jest różnych łańcuchów maksymalnych.

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



Ponieważ singleton musi zawierać się w , może być wybrany na sposobów. Tak więc może być wybrane już jedynie na sposobów i tak dalej. A zatem różnych łańcuchów postaci



jest . W analogiczny sposób otrzymujemy, że różnych łańcuchów postaci



jest . Podsumowując, liczba maksymalnych łańcuchów, w których występuje wynosi .

Ponieważ jest antyłańcuchem, to dla w łańcuchu nie mogą wystąpić równocześnie i . Zliczając teraz maksymalne łańcuchy przechodzące przez któreś , możemy pominąć jakiś łańcuch maksymalny. Nie mniej jednak mamy



To w konsekwencji daje



End of proof.gif

Przykład

Oczywiście, dla ustalonego rodzina -elementowych podzbiorów jest rodziną Spernera. Ponieważ wartość jest maksymalna dla , to -elementowy podzbiór ma rodzinę Spernera o mocy . Następne twierdzenie pokazuje, że jest to najliczniejsza rodzina Spernera.

Twierdzenie 2.6 [E. Sperner 1928]

Jeśli jest rodziną Spernera podzbiorów zbioru , to



Dowód

Niech oraz . Wartość jest maksymalna dla . Tak więc . Na mocy Twierdzenia 2.5 otrzymujemy:



skąd natychmiast



End of proof.gif
Uwaga

W posecie dowolne dwa jego elementy spełniają:

  • jest największym wspólnym ograniczeniem dolnym dla i ,
  • jest największym wspólnym ograniczeniem górnym dla i .

W takim razie dowolne dwa elementy posetu 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 , w którym dla dowolnych istnieją

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

Kres dolny oznaczać bedziemy przez .

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

Kres dolny oznaczać bedziemy przez .

Przykład

Rozważmy zbiór liczb naturalnych oraz relacje zdefiniowaną w następujący sposób



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