TREE(3)

TREE(3) — большое число, которое является верхней границей решения в теоретико-графовой теоремы Краскала. TREE(3) в невообразимое число раз больше числа Грэма. Число TREE(3) столь велико, что стрелочные нотации Кнута и Конвея не способны его записать.

Теорема Краскала

Запрос «Теорема Краскала» перенаправляется сюда. На эту тему нужна отдельная статья.

В теории графов деревом называется граф, в котором все вершины соединены рёбрами (возможно, посредством других вершин) и отсутствуют циклы (последовательности рёбер, соединяющие какую-либо вершину саму с собой). В данном случае деревья являются корневыми, то есть имеют определённую вершину - корень. Это понятное, но неформальное определение дерева. Теорема Краскала утверждает последовательность деревьев TREE(n), описанную следующими законами:

1. Каждое i-е дерево имеет не более i вершин.
2. Вершины имеют один из n видов; для TREE(3) удобно называть их «красными», «зелёными» и «синими».
3. Ни одно дерево не должно являться топологическим минором более позднего дерева.

TREE(1) даёт единственное дерево с одной вершиной: если попытаться добавить ещё одно с двумя вершинами, при удалении любой из них получится первая. TREE(2)=3, в этой последовательности дерево с одной «красной» вершиной, с двумя «синими» и с одной «синей». Но начиная с TREE(3), происходит настоящий взрыв длины последовательности. Тем не менее, теорема Краскала утверждает, что при любом конечном n число TREE(n) будет конечным.

Не умаляя общности, можно назвать единственную вершину первого дерева «красной». Далее, вне зависимости от n, ни одно дерево не имеет «красных» вершин. Ведь если бы имело хоть одну, при удалении всех вершин, кроме этой «красной», получилось бы первое дерево.

Слабая tree-функция

Определим tree(n), слабую tree-функцию, как длину самой длинной последовательности из деревьев с вершинами одного цвета, описываемой следующими законами:

1. Каждое i-е дерево имеет не более i+n вершин.
2. Ни одно дерево не должно являться топологическим минором более позднего дерева.

Известно, что [math]\displaystyle{ tree(1)=2 }[/math], [math]\displaystyle{ tree(2)=5 }[/math], [math]\displaystyle{ tree(3)\geq 844424930131960 }[/math], а [math]\displaystyle{ tree(4) }[/math] уже больше числа Грэма.

Также известно, что TREE(3) намного больше, чем [math]\displaystyle{ tree^{tree^{tree^{tree^{tree^8(7)}(7)}(7)}(7)}(7) }[/math] (верхний индекс в данном случае обозначает итерированную функцию).

Масштаб числа TREE(3)

Распространённым заблуждением является утверждение книги рекордов Гиннесса о том, что число Грэма — самое большое число, которое когда-либо использовалось в математическом доказательстве: эта информация давно устарела, так как число TREE(3) также используется в математическом контексте, и оно несоизмеримо больше числа Грэма. Для представления числа TREE(3) бесполезны не только башни степеней, но и нотации Кнута и Конвея. В массивной нотации Бёрда TREE(3) можно примерно выразить как [math]\displaystyle{ \{3, 6, 3 [1 [1 \neg 1,2] 2] 2\} }[/math]. Общая скорость роста функции TREE(n) оценивается как [math]\displaystyle{ f_{\theta\left(\Omega^{\omega}\omega\right)}(n) }[/math] в терминах быстрорастущей иерархии.

При этом TREE(3) далеко не самое большое число, встречавшееся в математических работах: в последующие годы описывались бо́льшие числа, например такие как SSCG(3), SCG(13), а также числа, задаваемые с помощью невычислимых функций, такие, как число Райо.

Литература

• Friedman, Harvey M. (2002), Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998), vol. 15, Lect. Notes Log., Urbana, IL: Assoc. Symbol. Logic, с. 60–91 
• Gallier, Jean H. (1991), What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory, Ann. Pure Appl. Logic Т. 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, <http://www.cis.upenn.edu/~jean/kruskal.pdf> 
• Kruskal, J. B. (May 1960), Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture, Transactions of the American Mathematical Society (American Mathematical Society) . — Т. 95 (2): 210–225, doi:10.2307/1993287, <http://www.ams.org/journals/tran/1960-095-02/S0002-9947-1960-0111704-1/S0002-9947-1960-0111704-1.pdf> 
• Marcone, Alberto. Wqo and bqo theory in subsystems of second order arithmetic (англ.) // Reverse Mathematics : journal. — 2001. — Vol. 21. — P. 303—330.
• Nash-Williams, C. St.J. A. (1963), On well-quasi-ordering finite trees, Proc. Camb. Phil. Soc. Т. 59 (4): 833–835, DOI 10.1017/S0305004100003844 
• Rathjen, Michael; Weiermann, Andreas. Proof-theoretic investigations on Kruskal's theorem (англ.) // Annals of Pure and Applied Logic : journal. — 1993. — Vol. 60, no. 1. — P. 49—88. — doi:10.1016/0168-0072(93)90192-g.
• Simpson, Stephen G. (1985), Nonprovability of certain combinatorial properties of finite trees, in Harrington, L. A.; Morley, M. & Scedrov, A. et al., Harvey Friedman's Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, North-Holland, с. 87–117 
• Smith, Rick L. (1985), The consistency strengths of some finite forms of the Higman and Kruskal theorems, in Harrington, L. A.; Morley, M. & Scedrov, A. et al., Harvey Friedman's Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, North-Holland, с. 119–136