Teoria drzew Kruskala

Teoria drzew Kruskala – w matematyce jeden z problemów w teorii grafów i teorii porządku. Mówi ona, iż skończony zbiór drzew z uporządkowanymi zasadami tworzenia jest homeomorficzny. Twierdzenie to zostało zaprezentowane przez Andrew Vázsonyiego – węgierskiego matematyka, a udowodnione przez Josepha Kruskala (1960) oraz Nasha-Williamsa (1963). Od tego czasu stało się znaczącym przykładem w teorii odwrotności jako stwierdzenie, którego nie można udowodnić, używając ATR₀ (forma arytmetycznej rekurencji transfinitowej), a finalne zastosowanie tego twierdzenia umożliwia konstrukcję bardzo szybko rosnącej funkcji TREE(n) (ang. tree – drzewo).

Zasady

Jest to wersja udowodniona przez Nasha-Williamsa, ponieważ formuła Kruskala jest bardzo zawiła.

Dla danego drzewa $T$ z korzeniem (głównym punktem tworzącym drzewo) oraz danymi wierzchołkami $v,w$ mówimy, że $w$ jest odgałęzieniem $v,$ oznacza to, iż istnieje bezpośrednie połączenie z $w$ do $v,$ lub pośrednie takie, że każdy kolejny punkt na ścieżce ma bezpośrednie połączenie z jednym z dwóch wierzchołków.

Niech $X$ będzie zbiorem częściowego porządku. Jeżeli drzewa $T_1,T_2$ są połączone ze sobą w $X,$ to mówimy, że $T_1$ jest zawarte w $T_2$ i piszemy $T_1⩽T_2.$ Jest to działanie, które należy opóźnić, tzn. konstruować drzewa w taki sposób, aby $T_1⩽T_2,$ wystąpiło możliwie na końcu. Kruskal udowodnił, iż konstrukcja drzew musi w pewnym momencie spełnić warunek $T_1⩽T_2,$ można więc zapisać, że $\mathrm{\forall }T:T_1⩽T_2.$

Funkcja tree(n)

Funkcja tree(n), czyli funkcja słabego drzewa, to najdłuższy ciąg drzew jedno-oznaczonych, czyli $X=\{1\},$ tak że:

• żadne drzewo na pozycji $k$ nie może mieć więcej niż $k+n$ punktów, dla każdego $k,$
• żadne drzewo nie może być homeomorficzne.

Wiemy, że tree(1) = 2, tree(2) = 5 i tree(3) > 844424930131960. Natomiast TREE(3) (Zobacz poniżej) jest większe od tree^{treetreetreetree8(7)(7)(7)(7)}(7). W szybko rosnącej hierarchii funkcja tree(n) znacznie przewyższa tempem wzrostu ${\epsilon }_0$ i dochodzi do małej liczby porządkowej Veblena.

Praca Friedmana

Dla skończonego zbioru $X,$ teoria drzew Kruskala, może być pokazana oraz udowodniona, używając rachunku predykatów drugiego rzędu. Jednak podobnie jak w twierdzeniu Goodsteina, niektóre przypadki można rozwiązać w podsystemach rachunków. Po raz pierwszy zauważył to Harvey Friedman, w latach 80 XX wieku. Friedman spostrzegł, że nie można udowodnić twierdzenia Kruskala w ATR₀. Oznacza to, że wprawdzie można udowodnić owe twierdzenie w ΠSzablon:Su-CA₀, ale próba analizy porządkowej musiałaby zostać udowodniona poza ΠSzablon:Su-CA₀.

TREE(3)

Załóżmy, że $P(n)$ spełnia warunek $\mathrm{\forall }T:T_1⩽T_2,$ czyli za $n$ nie można wstawić liczby zespolonej, kwaterionu itd., oraz że drzewo na pozycji $k$ może mieć maksymalnie $k$ punktów. TREE(3) jest maksymalną liczbą drzew możliwych do skonstruowania, bez zawierania jednego drzewa w drugim z użyciem $n$ kolorów. Aby zobrazować rozmiar TREE(3), warto najpierw zobaczyć rozkład TREE(1) oraz TREE(2).

W przypadku jednego koloru (np. czerwonego) posadzić można jedno drzewo, gdyż każde kolejne, niezależnie od liczby punktów, będzie zawierać drzewo nr 1. Dla dwóch kolorów intuicyjne wydawałoby się stwierdzenie, iż maksymalna liczba drzew, które można zasadzić, wynosi 2 – jedno czerwone, a drugie np. zielone. W rzeczywistości wynik wynosi 3. Można postawić najpierw jednoelementowe drzewo koloru czerwonego, później dwuelementowe drzewo, w którym obydwa punkty mają kolor zielony (pierwsze drzewo nie zawiera się w drugim, ponieważ kolory się różnią), natomiast jako drzewo z numerem trzy postawić jednoelementowy zielony punkt.

Rozkład TREE(1) i TREE(2)

W przypadku TREE(3) sprawa komplikuje się. Kruskal udowodnił, iż niemożliwe jest, by TREE(n) nigdy się nie kończyło. Przykładowy rozkład TREE(3) wygląda następująco:

Liczba kroków w rozkładzie TREE(3) jest skończona, chociaż niewyobrażalnie ogromna. Wiadome jest, iż TREE(3) jest znacznie większe od liczby Grahama. Trudno konkretnie określić położenie TREE(3) w szybko rosnącej hierarchii, jednak uważa się, że znacznie przekracza ono granicę małej liczby porządkowej Veblena, natomiast wiadome jest, że nie przekracza dużej liczby porządkowej Veblena.

TREE(n) jest obliczalne, tzn. istnieją algorytmy, które w łatwy sposób szukają wyniku funkcji. Oznacza to również, że $\mathrm{\Sigma }(n)>\text{TREE}(n)$ (zobacz funkcja pracowitego bobra) dla dość małych wartości $n$ np. 2000.