Twierdzenie Dilwortha
Twierdzenie Dilwortha to fundamentalne twierdzenie w dziedzinie kombinatoryki, które zajmuje się strukturą zbiorów częściowo uporządkowanych. Sformułowane przez amerykańskiego matematyka Roberta Dilwortha w 1950 roku, twierdzenie to dostarcza istotnych informacji o relacjach między różnymi podzbiorami tych zbiorów, zwanych łańcuchami i antyłańcuchami. W skrócie, twierdzenie stwierdza, że maksymalna liczba elementów w antyłańcuchu w skończonym zbiorze częściowo uporządkowanym jest równa minimalnej liczbie łańcuchów potrzebnych do pokrycia tego zbioru.
Definicje podstawowe
Aby lepiej zrozumieć treść twierdzenia Dilwortha, warto zacząć od definicji kluczowych terminów związanych z teorią częściowego porządku. Relacja częściowego porządku na zbiorze X to taka relacja, która spełnia trzy właściwości: zwrotność, antysymetryczność oraz przechodniość. Zbiór L nazywamy łańcuchem, jeśli każdy jego element jest porównywalny z innym elementem tego samego zbioru. Oznacza to, że dla dowolnych dwóch elementów x i y z L zachodzi x ≼ y lub y ≼ x.
Antyłańcuch natomiast to podzbiór A zbioru X, w którym żadne dwa elementy nie są porównywalne. W związku z tym, dla każdego x, y należącego do A zachodzi brak relacji porządku między nimi (x ≼ y jest fałszywe). Wiedząc to wszystko, możemy przystąpić do analizy samego twierdzenia Dilwortha.
Treść twierdzenia
Twierdzenie Dilwortha mówi, że w dowolnym skończonym zbiorze częściowo uporządkowanym maksymalna liczba elementów w antyłańcuchu jest równa minimalnej liczbie łańcuchów, które pokrywają ten zbiór. Oznacza to, że istnieje ścisła zależność między tymi dwoma pojęciami: im większy antyłańcuch, tym więcej łańcuchów potrzebujemy do pokrycia całego zbioru.
Warto zaznaczyć, że choć twierdzenie zostało sformułowane dla zbiorów skończonych, jego prawdziwość pozostaje także aktualna dla zbiorów nieskończonych, pod warunkiem że maksymalna liczba elementów w antyłańczu pozostaje ograniczona. Dowód tego twierdzenia opiera się na metodzie indukcyjnej.
Dowód twierdzenia Dilwortha
Dowód indukcyjny przedstawiony przez Helge Tverberga w 1967 roku zaczyna się od założenia, że twierdzenie jest prawdziwe dla wszystkich zbiorów o mocy mniejszej niż n. Następnie zakładamy istnienie zbioru X o mocy n oraz maksymalnej liczby m elementów w antyłańczu. Wybieramy dowolny maksymalny łańcuch L w X.
Jeśli każdy antyłańcuch w pozostałej części zbioru (X L) ma mniej niż m elementów, stosując założenie indukcyjne możemy stwierdzić, że X można pokryć przy pomocy sumy łańcucha L oraz odpowiedniej liczby łańcuchów pokrywających pozostałą część zbioru. Natomiast jeśli istnieje antyłańcuch A o m elementach w X L, musimy wykazać sprzeczność przyjętej hipotezy.
Zauważamy, że każdy element antyłańcucha A powinien być również maksymalny w kontekście całego zbioru X. Idąc dalej z dowodem dochodzimy do stwierdzenia, że możemy podzielić zbiór X na dwa podzbiory: G i D. Ostatecznie uzyskujemy rozkład zbioru X na m łańcuchów, co kończy
Artykuł sporządzony na podstawie: Wikipedia (PL).