TREE(3)

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

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

Файл:1 first20.png

Начало последовательности деревьев. Общее число деревьев в ней равно TREE(3).

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

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

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

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

Интересно отметить, что первое дерево имеет одну «красную» вершину, и вне зависимости от n больше ни одно дерево не имеет «красных» вершин. Иначе, при удалении всех вершин, кроме этой «красной», получилось бы первое дерево.

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

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

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

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

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

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

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

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

Литература

• Friedman, Harvey M. (2002), Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998), Lect. Notes Log., vol. 15, Urbana, IL: Assoc. Symbol. Logic, pp. 60—91, MR 1943303
• Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory" (PDF), Ann. Pure Appl. Logic, 53 (3): 199—260, doi:10.1016/0168-0072(91)90022-E, MR 1129778
• Kruskal, J. B. (May 1960), "Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture" (PDF), Transactions of the American Mathematical Society, 95 (2), American Mathematical Society: 210—225, doi:10.2307/1993287, JSTOR 1993287, MR 0111704
• 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, MR 0153601
• 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. (eds.), Harvey Friedman's Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 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. (eds.), Harvey Friedman's Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 119—136