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ł 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}\leqslant T_{2}.$ Jest to działanie, które należy opóźnić, tzn. konstruować drzewa w taki sposób, aby $T_{1}\leqslant T_{2},$ wystąpiło możliwie na końcu. Kruskal udowodnił, iż konstrukcja drzew musi w pewnym momencie spełnić warunek $T_{1}\leqslant T_{2},$ można więc zapisać, że $\forall T:T_{1}\leqslant 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 $\varepsilon _{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 Π11-CA₀, ale próba analizy porządkowej musiałaby zostać udowodniona poza Π11-CA₀.

TREE(3)

Załóżmy, że $P(n)$ spełnia warunek $\forall T:T_{1}\leqslant 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. czerwony), 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 ilość 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 $\Sigma (n)>{\text{TREE}}(n)$ (zobacz funkcja pracowitego bobra) dla dość małych wartości $n$ np. 2000.