Teoria Drzew Kruskala

W matematyce Teoria Drzew Kruskala jest jednym 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ł się znaczącym przykładem w teorii odwrotności jako stwierdzenie, którego nie można udowodnić używając ATR0 (forma arytmetycznej rekurencji transfinitowej), a finalne zastosowanie tego twierdzenia umożliwia konstrukcję bardzo szybko rosnącej funkcji TREE(n) (ang. tree – drzewo).

Zasady[edytuj | edytuj kod]

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

Dla danego drzewa z korzeniem (głównym punktem tworzącym drzewo) oraz danymi wierzchołkami mówimy, że jest odgałęzieniem oznacza to, iż istnieje bezpośrednie połączenie z do 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 będzie zbiorem częściowego porządku. Jeżeli drzewa są połączone ze sobą w to mówimy, że jest zawarte w i piszemy Jest to działanie, które należy opóźnić, tzn. konstruować drzewa w taki sposób, aby wystąpiło możliwie na końcu. Kruskal udowodnił, iż konstrukcja drzew musi w pewnym momencie spełnić warunek można więc zapisać, że

Funkcja tree(n)[edytuj | edytuj kod]

Funkcja tree(n), czyli funkcja słabego drzewa to najdłuższy ciąg drzew jedno-oznaczonych, czyli 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[3]. Natomiast TREE(3) (Zobacz poniżej) jest większe od treetreetreetreetree8(7)(7)(7)(7)(7). W szybko rosnącej hierarchii funkcja tree(n) znacznie przewyższa tempem wzrostu i dochodzi do małej liczby porządkowej Veblena[4].

Praca Friedmana[edytuj | edytuj kod]

Dla skończonego zbioru 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 ATR0[6][7]. Oznacza to, że wprawdzie można udowodnić owe twierdzenie w Π11-CA0, ale próba analizy porządkowej musiałaby zostać udowodniona poza Π11-CA0.

TREE(3)[edytuj | edytuj kod]

Załóżmy, że P(n) spełnia warunek 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[8][9]. 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: Treekruskal3.png 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 (zobacz funkcja pracowitego bobra) dla dość małych wartości n np. 2000[13].

Przypisy[edytuj | edytuj kod]

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