Zupełnie inna historia

Skusiło mnie, mimo, że to zupełnie inna historia jak wzmiankowałem tu (warto być może przed czytaniem tego postu zajrzeć do linkowanego), ażeby opowiedzieć coś o twierdzeniu Dilwortha. Spróbuję zmierzyć się z innym jego dowodem (w porównaniu ze znanym choćby z wikipedii) który pozwala zerknąć trochę na strukturę zbioru antyłańcuchów o maksymalnej liczności w skończonym zbiorze uporządkowanym. Nie wiem czy jest to jakiś nowy dowód – twierdzenie Dilwortha nie jest bardzo trudne więc spodziewam się, że wiele osób dla przyjmności, przypadkiem czy w ramach ćwiczenia udowodniło go sobie na wiele różnych sposobów.


Twierdzenie Dilwortha, mówi: W skończonym zbiorze F uporządkowanym przez relację R maksymalna długość antyłańcucha jest równa minimalnej ilości rozłącznych łańcuchów pokrywającej zbiór F.


Uwaga: będę używał dla R zapisu infiksowego, tj. fakt, że (a,b) ∈ R będę oznaczał przez a R b.


Definicja: Kratą nazywamy zbiór częściowo uporządkowany w którym każde dwa elementy mają unikalne supremum (a więc minimalne ograniczenie górne) i unikalne infimum (a więc największe ograniczenie dolne).


Lemat:

Niech dana będzie krata skończona X gdzie relacją porządku jest ≤. Niech W ma wasność: ∀ x, y ∈ X sup(x, y) ∈ W i inf(x, y) ∈ W => x ∈ W i y ∈ W. Wtedy, jeżeli pewien maksymalny łańcuch w X zawiera się w W, to W = X.

Uwaga: ≤ używam tu w zapisie infiksowym, tzn (a,b) ∈ ≤ zapisuję jako a ≤ b . a < b oznacza zaś a ≤ b i a ≠ b

Dowód: Załóżmy nie wprost, że W ma sugerowaną własność, pewien maksymalny łańcuch M ⊆ W, ale W' = X \ W ≠ 0. Weźmy a - element maksymalny w W'. W M są elementy nieporównywalne z a, bo w przeciwnym wypadku M ∪{a} byłoby łańcuchem większym niż M a o M założyliśmy, że jest maksymalny. Weźmy o - najmniejszy z elementów łańcucha M nieporównywalny z a. Z maksymalności a w W' wiemy, że sup (a,o) ∈ W. (bo sup(a,o) > a ) Ponieważ a nie należy do W, wiemy też, że inf(a,o) ∉ W, (bo w przeciwnym razie z własności zbioru W mielibyśmy a ∈ W) Wiemy również, że o nie jest elementem minimalnym łańcucha, bowiem wtedy inf(a,o) < o musiał by być równy o a o jest nieporównywalne z a. Istnieje więc element b bezpośrednio poprzedzający o w W. Weźmy teraz element inf(a,o). Ponieważ b < a (jest porównywalne a nie może być mniejsze bo wtedy a < b < o a a nie jest porównywalny z o). Skoro tak, to b ≤ inf(a,o) (bo b < o i b < a wiec b ≤ inf(a,o) z definicji infimum). Gdyby b = inf(a,o) mielibyśmy znowu sup(a,o), inf(a,o) ∈ M ⊆ W i a ∈ W. Jeżeli zaś b < inf(a,o) < o to M ∪ {inf(a,o)} jest łańcuchem większym od M. Sprzeczność.


Zanim wykorzystam lemat, mała uwaga. Nie znałem wcześniej tego lematu i ciekaw jestem czy ma jakąś wartość (w sensie przydatności) poza dowodem, który tu przeprowadzam. Chętnie bym zobaczył szersze jego zastosowanie.


Druga uwaga - przypomina mi się żart, który opowiadał jeden z wykładowców w IM UJ (ale nie pamiętam który niestety) o dowodach nie wprost. Mianowicie: dowód nie wprost polega na tym, że ktoś pisze bzdurę a potem zaczyna wnioskując z niej wypisywać coraz większe i większe bzdury, aż w końcu wypisze coś tak niesłychanie bzdurnego, że wszyscy zgadzają się, że dalej już nie można kontynuować.


Wracając do tw. Dilwortha. Niech FM oznacza zbiór antyłańcuchów o maksymalnej długości w F uporządkowanym przez relację R. W FM wprowadźmy relację RM następująco: a RM b z definicji wtedy i tylko wtedy gdy ∀ x ∈ a ∃ y ∈ b t. że x R y

Pokażę, że jest to relacja porządku. A więc :

1) a RM a - oczywiste

2) Niech a RM b i b RM c . Mamy x ∈ a więc ∃ y ∈ b t. że x R y . Zatem ∃ z ∈ c t. że y R z. Z Przechodniości R mamy x R z. Więc a RM c

3) Niech a RM b i b RM a . Weźmy x∈a . Zatem ∃ y ∈ b t. że x R y. Więc ∃ z ∈ a t. że y R z. Ale wtedy x R z i oba należą do antyłańcucha, więc x = z. Mamy więc x R y i y R x, czyli y = x. Rozumując tak ∀ x ∈ a i korzystając z tego, że oba antyłańcuchy mają maksymalną liczbę elementów więc są równoliczne dostajemy a = b



Pokażę więcej, mianowicie FM z porządkiem RM jest kratą. Wystarczy pokazać, że:

∀ a b ∈ FM ∃ sup(a, b) i inf(a,b).



Ponieważ konstrukcje i dowody obu są identyczne z dokładnością do kierunków nierówności, szczegółowo przedstawię przypadek supremum, zostawiając - jak to mają w zwyczaju leniwcy infimum czytelnikowi. A więc, niech a i b ∈ RM .

Mamy a = a₁∪(a ∩ b)∪a₂ gdzie

a₁ = {x : x∈ a\b , ∃ s ∈ b t. że x R s }

a₂ = {x: x∈ a\b , ∃ s ∈ b t. że s R x }

Podobnie b = b₁∪(b ∩ a)∪b₂ gdzie

b₁ = {x : x∈ b\a , ∃ s ∈ a t. że s R x }

b₂ = {x : x∈ b\a , ∃ s ∈ a t. że x R s }



Zauważmy, że a₁ ∩ a₂ = b₁ ∩ b₂ = 0

Gdyby bowiem x ∈ a₁ ∩ a₂ to ∃ y₁, y₂ ∈ b t.że y₁ R x i x R y₂

ale wówczas, (skoro b jest antyłańcuchem) y₁ = y₂ więc y₁ = y₂ = x. Ale a₁ (jak i a₂) z definicji nie ma elementów wspólnych z b. Przy okazji wynika z tego że

#a = #a₁ + #a∩b + #a₂

i podobnie

#b = #b₁ + #a∩b + #b₂

gdzie przez # oznaczam liczność zbioru.

Pokażę teraz, że:

inf(a, b) = a₁∪(a ∩b)∪b₂ i

sup(a, b) = b₁∪(a ∩ b)∪a₂


Zajmijmy się supremum. b₁∪(a ∩ b)∪a₂ jest antyłańcuchem. Mianowicie żadne dwa elementy zbioru b₁∪(a ∩ b) nie są porównywalne między sobą, podobnie (a ∩ b)∪a₂ , Zatem pozostaje pokazać, że elementy b₁ i a₂ nie są porównywalne.

Załóżmy że ∃x ∈ b₁ y ∈ a₂ t.że x i y są porównywalne.

Gdyby y R x mielibyśmy z definicji zbiorów b₁ i a₂ że

∃s z ∈ b t.że s R x i x R y i y R z więc s R z czyli s = z = x = y co jest sprzeczne.

Gdyby zaś x R y wtedy ∃s z ∈ a t.że s R x i x R y i y R z i rozumujemy jak linijkę wyżej.


Podobnie pokazać można, że a₁∪(a ∩ b)∪b₂ jest antyłańcuchem.


Pozostaje pokazać, że oba łańcuchy są maksymalnej długości. Ale wiemy:

#a = #b więc #a₁ + #(a ∩ b) + #a₂ = #b₁ + #(a ∩ b) + #b₂

czyli

#a₁ - #b₁ = #b₂ - #a₂ ale:

# b₁∪(a ∩ b)∪a₂ = #b₁ + #(a ∩ b) + #a₂ =

#b - #(a ∩ b) - #b₂ + #(a ∩ b) + #a₂ = #b + (#a₂ - #b₂)

Podobnie

a₁∪(a ∩ b)∪b₂ = #a₁ + #(a ∩ b) + #b₂ =

#a - #(a ∩ b) - #a₂ + #(a ∩ b) + #b₂ = #b + (#b₂ - #a₂)


Gdyby więc #a₂ - #b₂ ≠ 0 jeden z tych dwóch antyłańcuchów miałby długość większą niż długość antyłańcucha o maksymalnej długości – co jest jawną sprzecznością.


Teraz pozostaje pokazać jeszcze, że supremum jest naprawdę supremum, tzn.

jeżeli a RM x i b RM x to sup( a , b ) RM x

Jeżeli a RM x to oczywiście każdy s ∈ a jest porównywalny z jakimś elementem antyłańcucha x (bo inaczej po dołączeniu do x tworzyłby większy antyłańcuch). Gdyby któryś z nich był silnie większy od pewnego elementu x to (patrząc na definicję porządku RM w FM) byłby również silnie większy a więc w szczególności porównywalny z jakimś innym elementem a co daje sprzeczność.

Podobnie można rozumować i dla b. Zatem (b₁∪(a ∩ b)∪a₂ ) RM x.


Niemal identyczne rozumowanie pokazuje, że zdefiniowane przez nas inf jest rzeczywiście infimum zbiorów w RM.


FM jest zatem kratą.


Weźmy teraz A maksymalny łańcuch w FM. Pokażę, że istnieje łańcuch C w F mający wspólny element z każdym elementem A. To proste: niech c₁ będzie maksymalnym elementem w A a x₁ elementem c₁. Teraz indukcyjnie dopóki nie wyczerpiemy elementów A, mając x₁...x_k elementów tworzących łańcuch w F takich, że x_i ∈ c_i i c_i poprzedza c_i-1 w A, definiujemy c_i+1 jako element bezpośrednio poprzedzający c_i w A a x_i+1 element c_i+1 t. że x_i+1 R x_i (element taki istnieje z definicji porządku RM w FM. Zauważmy, że nie musi być różny od x₁ !). Żądanym łańcuchem zbiór będzie {x₁,...,x_n} (tworząc z ciągu zbiór wyeliminowaliśmy powtórzenia).



Niech teraz, przy znaczeniu A i C jak wyżej, S będzie podzbiorem FM takim, że a ∈ S wtedy i tylko wtedy gdy a ∩ C ≠ 0. Łatwo zobaczyć z charakteryzacji inf i sup, że S ma własność z naszego Lematu, tzn że jezeli inf(a,b) i sup(a,b) są w S to i a i b są w S.

Jest tak rzeczywiscie: jeżeli x i y należą do C, x R y i x ∈ inf( a, b) i y ∈ sup (a, b) to albo:

- x ∈ a ∩ b - wtedy oczywiście a ∩ C ≠ 0 i a ∈ S i b ∩ C ≠ 0 i b ∈ S

- x ∈ a₁ wtedy z konieczności y ∈ b₁ i znowu j.w. a ∈ S i b ∈ S

- x ∈ b₂ wtedy z konieczności y ∈ a₁ i j.w.

Co więcej A jest łańcuchem maksymalnym w FM i jest (co wynika ze sposobu konstrukcji) zawarty w S. Na mocy Lematu zatem S = FM. Innymi słowy każdy antyłańcuch o maksymalnej liczbie elementów przecina się z łańcuchem A.

Teraz samo Twierdzenie Dilwortha.

Indukcyjnie. Twierdzenie jest porawdziwe gdy maksymalna długośc antyłańcucha jest 1. Załóżmy, że jest prawdziwe dla zbiorów uporządkowancyh z antyłańcuchem o maksymalnej długości k gdzie k < n. Weźmy teraz zbiór F, z antyłańcuchem o maksymalnej długości n. Z tego co udowodniliśmy powyżej wynika istnieje łańcuch C mający część wspólną z każdym anyłańcuchem maksymalnej długości w F. Wtedy F \ C jest zbiorem z antyłańcuchem o maksymalnej długości równej n-1 i z założenia indukcyjnego minimalna łańcuchów pokrywających go wynosi n-1. Zatem F da się pokryć przez n łańcuchów (łańcuchy pokrywające F\C i C). Jest to rzeczywiście liczba minimalna, bo gdyby dało się pokryć przez mniej (np. n-1) dwa elementy antyłańcucha o długości n musiałyby wpadać do tego samego łańcucha z pokrycia - co jest niemożliwe.



Uff