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

Zagadnienie literackie

Ktoś czytał "Rękopis znaleziony w Saragossie" Potockiego? Zakładam, że film Hassa na motywach tejże powieści oglądał każdy (jest ponoć kultowy również poza Polską, pieniądze na restaurację i koloryzację filmu wyłożył M. Scorsese). OK, to nie odpytywanie z lektury, chodzi mi tylko o to by przypomnieć specyficzną konstrukcję owej powieści, (widzowie filmu mieli okazję poczuć jak to jest zrobione, ale w stopniu komplikacji film nie zbliża się nawet do książkowego oryginału). Jest owa konstrukcja mianowicie taka - pomysł zbieżny z wschodnimi "Baśniami tysiąca i jednej nocy" - mamy opowieść główną i głównego narratora, który przeżywając swoje przygody napotyka inne postaci, które opowiadają mu własne przygody (co narrator przytacza dosłownie więc narracja zawsze pozostaje narracją w pierwszej osobie), w tych opowieściach rekurencyjnie zaczynają się i kończą inne opowieści i tak dalej, przy czym "głębokość stosu" o ile mnie pamięć nie zawodzi sięga w najgłębszym miejscu czterech. To nie koniec, zdarza się, że poszczególne opowieści odwołują się do tych samych postaci i wydarzeń, mają wspólnych bohaterów i/lub są dobrze zlokalizowane w czasie względem wydarzeń historycznych.
Nie sporządziłem czytając, choć kusiło mnie niezmiernie i może kiedyś to zrobię, diagramu wszystkich tych opowieści. Gdyby miał powstać należałoby zrobić coś takiego:

-Wypisać wszystkie wydarzenia (zakładając upraszczająco ich punktowość w czasie) jakie miały miejsce do których odwołują się poszczególne opowieści.

-Wprowadzić relację późniejsze/wcześniejsze pomiędzy wydarzeniami w oparciu o:
a) następstwo chronologiczne wydarzeń wewnątrz opowieści.
b) fakt, że opowiadane są wydarzenia przeszłe w więc miały miejsce przed zdarzeniem polegającym na rozpoczęciu opowiadania
c) następstwo czasu względem wydarzeń historycznych wspomnianych w opowieściach
d) informacje o wieku bohaterów w opowieści w poszczególnych opowieściach
e) inne, które nie przyszły mi teraz do głowy

Teraz załóżmy że zaznaczymy sobie zdarzenia kropkami a fakt następowania zdarzeń po sobie oznaczymy strzałką skierowaną od zdarzenia wcześniejszego do późniejszego.
To co powinniśmy dostać - o ile Potocki sprytnie nie oszukał nas gdzieś (chcący), bądź nie popełnił złośliwego i niezauważanego przez jego samego i czytelników błędu (niechcący w tym wypadku) - to tzw. DAG (czyli Directed Acyclic Graph - skierowany graf bez cykli).
Właściwie, wysycając do końca informacje z punków a-e, powinniśmy uzyskać coś więcej, mianowicie graf reprezentujący silny porządek częściowy. To wysycenie sprowadza się do prostej uwagi, że następstwo w czasie jest relacją przechodnią (bardziej uczenie i z obca: tranzytywną), czyli jeżeli zdarzenie B następuje po zdarzeniu A a zdarzenie C po zdarzeniu B to zdarzenie C następuje po zdarzeniu A.
Sekunda na definicje:

DAG jest to para składająca się ze zbioru wierzchołków V i relacji R ⊆ VxV t.że dla każdego ∀a1...∀an t. że (ai,ai+1) ∈ R dla i = 1,...,n mamy a1 ≠ an

Porządek częściowy w zbiorze A jest to relacja R ⊆ AxA, która jest

1. zwrotna tzn. ∀ a (a,a) ∈ R
2. antysymetryczna tzn. (a,b) ∈ R i (b,a) ∈ R ⇒ a = b
3. przechodnia tzn. ∀ a b c (a,b) ∈ R i (b, c) ∈ R ⇒ (a,c) ∈ R

Nasz porządek wydarzeń w "Rękopisie" nazwałem "silnym porządkiem częściowym" co sprowadza się do tego, że modyfikujemy powyższą definicję i punkty 1 i 2 zastępujemy punktem:
1' antysymetryczna tzn ∀ a (a,a) ∉ R'

Mimo, że żaden porządek częściowy nie śmie być silnym porządkiem częściowym i vice versa (co przy okazji ilustruje nieco paradoksalne zjawisko semantyczne, że znaczenie rzeczownika z przymiotnikiem może nie mieścić się w zakresie znaczenia samego rzeczownika), to chwila zastanowienia pozwala stwierdzić, że są te relacje dobrymi krewnymi. Mianowicie (proste ćwiczenie) uzupełniając silny porządek R' o relację identyczności I = {(a,a), a \in A} dostajemy porządek częściowy, tzn R = R' ∪ I jest porządkiem częściowym. Podobnież, odejmując I od porządku R dostaniemy silny porządek częściowy (R'=R\I jest silnym porządkiem częściowym).

Dla pełnej konsystencji, wysycenie o którym wspomniałem w języku porządków sprowadza się do, nazwijmy to szumnie, twierdzenia:
Niech dany będzie DAG (A,R). Zdefiniujmy R'' = R ∪ RR ∪ RRR ∪ ... gdzie napisanie relacji jedna po drugiej oznacza operację ich złożenia. Wówczas (A, R'') jest silnym porządkiem częściowym. W fachowej nomenklaturze R'' nazywa się domknięciem tranzytywnym R. Częściej niż ja to zrobiłem tutaj, i dając lepsze konotacje nazwie "domknięcie tranzytywne" definiuje się ją tak: ∏ {S | s relacja tranzytywna na A} a potem dowodzi, że R'' jest postaci takiej jaką podałem za definicję. Ale operować w myślach, dla zbiorów skończonych przynajmniej, łatwiej znacznie konstruktywnym opisem.


Wracając do naszego modelu. Dla ułatwienia, ponieważ porządki częściowe to to z czym w matematyce pracujemy częściej, w dalszym ciągu wywodu nasz silny porządek częściowy, opisanym wyżej sposobem, zmienimy na porządek częściowy. W naszym kontekście literackim oznacza to, że przyjmujemy założenie z którym łatwo się pogodzić, że każde zdarzenie jest jednoczesne z samym sobą.

OK, zadajmy więc arcyliterackie Pytanie: ile maksymalnie zdarzeń opisanych w powieści mogło rozgrywać się jednocześnie ?
I natychmiast strawestujmy je w języku relacji porządkujących w następujący sposób: mając porządek częściowy w zbiorze skończonym, znaleźć maksymalną możliwą liczbę elementów wśród których żadne dwa nie będą porównywalne. Nazwiemy to szerokością zbioru uporządkowanego.

Można zrobić to na wiele sposobów, z których najprostszy i najbardziej pracochłonny to dla każdego podzbioru zbioru A sprawdzić czy jego elementy są parami nieporównywalne, jeżeli tak zapisać liczność tego zbioru i z zapisanych liczb po przejrzeniu całości wybrać liczbę największą.

Proponuję sposób następujący. Najpierw znowu pooznaczam:

A - zbiór skończony, R - relacja częściowego porządku w A, dla a ∈ A R+(a) = {x| aRx} \ {a} , R-(a) = {x | xRa}\{a}

Zdefiniuję teraz:
łańcuchem w (A,R) nazywamy podzbiór A który jest liniowo uporządkowany względem relacji R zawężonej do niego

antyłańcuchem w (A,R) nazywamy podzbiór w A w którym żadne dwa różne lementy nie są porównywalne. Szerokość zbioru oznaczę przez SZ.

Twierdzę teraz, że:

∀ a SZ(A) = max(SZ(A \ (R+(a) ∪ {a})), SZ(A \ (R+(a) ∪ {a})), 1+SZ(A\(R+(a) ∪ R-(a) ∪ {a})))

Jest tak gdyż:
Dla dowolnego elementu a, jeżeli
Przypadek 1) a należy do pewnego antyłańcucha o maksymalnej liczności. Wtedy antyłańcuch ten zawiera się w A\(R+(a) ∪ R-(a)) - bo ma a jako swój element i nie zawiera żadnego elementu porównywalnego z a. Wystarczy więc znaleźć jakiś antyłańcuch maksymalnej liczności w A\(R+(a) ∪ R-(a) ∪ {a}) i dołączyć do niego a (bo do każdego "dobrego" podzbioru elementów tego zbioru możemy dołączyć a dostajac ciągle dobry zbiór). Jego moc wynosi więc 1+SZ(A\(R+(a) ∪ R-(a) ∪ {a})).
Jeżeli zaś
Przypadek 2) a nie należy do antyłańcucha o maksymalnej liczności. Wtedy to pewien taki antyłańcuch zawiera się w A \ (R+(a) ∪ {a}) lub A \ (R-(a) ∪ {a}) (bo nie zawiera a, i nie może jednocześnie zawierać elementu z R+(a) i R-(a))
Ostatecznie szukając maksymalnej liczności antyłańcucha można sprowadzić do poszukiwania w podzbiorach jak w tezie (+1 dla wyniku w zbiorze A\(R+(a) ∪ R-(a) ∪ {a})) ) i wyboru maksymalnej z tych liczb.

Twierdzenie to sprowadza nam poszukiwanie SZ(A) do wyboru dowolnego elementu a i powtórzenia procedury dla trzech istotnie mniejszych zbiorów a następnie scalenia wyników przy pomocy prostej arytmetyki sprowadzającej się do inkrementacji jednego z wyników i funkcji maximum. To gotowy algorytm rekurencyjny.
Arbitralność wyboru elementu a otwiera pewne perspektywy w ew. optymalizacji algorytmu, ale mniejsza o to.

Ćwiczone na zajęciach z algorytmiki, wykładach z matematyki dyskretnej lub kombinatoryki, względnie ogólnie zainteresowane oko zauważy pokrewieństwo serwowanego problemu z twierdzeniem znanym pod nazwą twierdzenie Dilwortha. Mówi ono mianowicie, że w zbiorze częściowo uporządkowanym liczność maksymalnego (w sensie inkluzji) antyłańcucha w jest równa minimalnej ilości rozłącznych łańcuchów, których suma daje cały zbiór. To jednak jak to mówią, zupełnie inna historia.

Ciekawe, czy na zajęciach dajmy na to z teorii literatury na polonistyce nietaktem byłoby zadać nasze Pytanie ?

Przy okazji, do rozważań nad owym problemem i algorytmem sprowokowało mnie nie literatura wcale, ale pewne zagadnienie dotyczące alokacji zasobów w sieci telekomunikacyjnej. Ale to naprawdę inna historia.