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)^[1] oraz Nasha-Williamsa (1963)^[2]. 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 ${\displaystyle T}$ z korzeniem (głównym punktem tworzącym drzewo) oraz danymi wierzchołkami ${\displaystyle v,w}$ mówimy, że ${\displaystyle w}$ jest odgałęzieniem ${\displaystyle v,}$ oznacza to, iż istnieje bezpośrednie połączenie z ${\displaystyle w}$ do ${\displaystyle 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 ${\displaystyle X}$ będzie zbiorem częściowego porządku. Jeżeli drzewa ${\displaystyle T_{1},T_{2}}$ są połączone ze sobą w ${\displaystyle X,}$ to mówimy, że ${\displaystyle T_{1}}$ jest zawarte w ${\displaystyle T_{2}}$ i piszemy ${\displaystyle T_{1}\leqslant T_{2}.}$ Jest to działanie, które należy opóźnić, tzn. konstruować drzewa w taki sposób, aby ${\displaystyle 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 ${\displaystyle T_{1}\leqslant T_{2},}$ można więc zapisać, że ${\displaystyle \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 ${\displaystyle X=\{1\},}$ tak że:

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

Wiemy, że tree(1) = 2, tree(2) = 5 i tree(3) > 844424930131960^[3]. 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 ${\displaystyle \varepsilon _{0}}$ i dochodzi do małej liczby porządkowej Veblena^[4].

Praca Friedmana

Dla skończonego zbioru ${\displaystyle 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^[5]. Friedman spostrzegł, że nie można udowodnić twierdzenia Kruskala w ATR₀^[6][7]. 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 ${\displaystyle P(n)}$ spełnia warunek ${\displaystyle \forall T:T_{1}\leqslant T_{2},}$ czyli za ${\displaystyle n}$ nie można wstawić liczby zespolonej, kwaterionu itd., oraz że drzewo na pozycji ${\displaystyle k}$ może mieć maksymalnie ${\displaystyle k}$ punktów. TREE(3) jest maksymalną liczbą drzew możliwych do skonstruowania, bez zawierania jednego drzewa w drugim z użyciem ${\displaystyle n}$ kolorów^[8][9]. 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^[10][11]. 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^[12].

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

Przypisy

1. J.BJ.B. Kruskal J.BJ.B., Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture, maj 1960, DOI: 10.1016/0168-0072(91)90022-E . Brak numerów stron w książce
2. C. St.J. AC.S.J.A. Nash-Williams C. St.J. AC.S.J.A., On well-quasi-ordering finite trees, 1963, DOI: 10.1017/S0305004100003844 . Brak numerów stron w książce
3. TREE sequence [online], Googology Wiki [dostęp 2020-05-11]  (ang.).
4. Stephen GS.G. Simpson Stephen GS.G., Nonprovability of certain combinatorial properties of finite trees, Harrington, L. A 1985 . Brak numerów stron w książce
5. Rick L.R.L. Smith Rick L.R.L., The consistency strengths of some finite forms of the Higman and Kruskal theorems, Harrington 1985 . Brak numerów stron w książce
6. Harvey MH.M. Friedman Harvey MH.M., Internal finite tree embeddings. Reflections on the foundations of mathematics, Stanford 2002 . Brak numerów stron w książce
7. AlbertoA. Marcone AlbertoA., Wqo and bqo theory in subsystems of second order arithmetic [online], 2001 .
8. HarveyH. Friedman HarveyH., 273:Sigma01/optimal/size, Uniwersystet w Ohio, 28 marca 2006 . Brak numerów stron w książce
9. Friedman, Long Finite Sequences, Uniwersystet w Ohio 1998 . Brak numerów stron w książce
10. PriyabrataP. Biswas PriyabrataP., How Big Is The Number – Tree(3) [online], Medium, 11 listopada 2019 [dostęp 2020-05-11]  (ang.).
11. Friedman, Enormous Integers In Real Life [online], 2000 .
12. asymptotics – Where does TREE(n) sit on the Fast Growing Hierarchy? [online], Mathematics Stack Exchange [dostęp 2020-05-11] .
13. Chatlin, 1987 . Brak numerów stron w książce