TREE(3)
Проверить информацию. |
TREE(3)[1] — большое число, которое является верхней границей решения в теоретико-графовой теоремы Краскала . TREE(3) в невообразимое число раз больше числа Грэма. Число TREE(3) столь велико, что стрелочные нотации Кнута и Конвея не способны его записать.
Теорема Краскала
В теории графов деревом называется граф, в котором все вершины соединены рёбрами (возможно, посредством других вершин) и отсутствуют циклы (последовательности рёбер, соединяющие какую-либо вершину саму с собой). В данном случае деревья являются корневыми, то есть имеют определённую вершину - корень. Это понятное, но неформальное определение дерева. Теорема Краскала[2] утверждает последовательность деревьев TREE(n), описанную следующими законами:
- Каждое i-е дерево имеет не более i вершин.
- Вершины имеют один из n видов; для TREE(3) удобно называть их «красными», «зелёными» и «синими».
- Ни одно дерево не должно являться топологическим минором более позднего дерева.
TREE(1) даёт единственное дерево с одной вершиной: если попытаться добавить ещё одно с двумя вершинами, при удалении любой из них получится первая. TREE(2)=3, в этой последовательности дерево с одной «красной» вершиной, с двумя «синими» и с одной «синей». Но начиная с TREE(3), происходит настоящий взрыв длины последовательности. Тем не менее, теорема Краскала утверждает, что при любом конечном n последовательность не будет бесконечной.
Интересно отметить, что первое дерево имеет одну «красную» вершину, и вне зависимости от n больше ни одно дерево не имеет «красных» вершин. Иначе, при удалении всех вершин, кроме этой «красной», получилось бы первое дерево.
Слабая tree-функция
Определим tree(n), слабую tree-функцию[3], как длину самой длинной последовательности из деревьев с вершинами одного цвета, описываемой следующими законами:
- Каждое i-е дерево имеет не более i+n вершин.
- Ни одно дерево не должно являться топологическим минором более позднего дерева.
Известно[3], что [math]\displaystyle{ tree(1)=2 }[/math], [math]\displaystyle{ tree(2)=5 }[/math], [math]\displaystyle{ tree(3)\geq 844424930131960 }[/math], а [math]\displaystyle{ tree(4) }[/math] уже больше числа Грэма.
Также известно[4], что TREE(3) намного больше, чем [math]\displaystyle{ tree^{tree^{tree^{tree^{tree^8(7)}(7)}(7)}(7)}(7) }[/math] (верхний индекс в данном случае обозначает итерированную функцию).
Масштаб числа TREE(3)
Распространённым заблуждением является утверждение книги рекордов Гиннесса о том, что число Грэма — самое большое число, которое когда-либо использовалось в математическом доказательстве: эта информация давно устарела, так как число TREE(3) также используется в математическом контексте, и оно несоизмеримо больше числа Грэма. Для представления числа TREE(3) бесполезны не только башни степеней, но и нотации Кнута и Конвея. В массивной нотации Бёрда[5] 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)[6], а также числа, задаваемые с помощью невычислимых функций, такие, как число Райо.
Примечания
- ↑ Jay Bennett. Wrap Your Head Around the Enormity of the Number TREE(3) . Popular Mechanics (20 октября 2017). Дата обращения: 27 мая 2020. Архивировано 1 июля 2020 года.
- ↑ TREE(3) and impartial games | Complex Projective 4-Space . Дата обращения: 1 февраля 2020. Архивировано 1 февраля 2020 года.
- ↑ 3,0 3,1 TREE sequence | Googology Wiki | Fandom . Дата обращения: 1 февраля 2020. Архивировано 9 января 2020 года.
- ↑ graph theory - How does TREE(3) grow to get so big? (Laymen explanation) - Mathematics Stack Exchange . Дата обращения: 1 февраля 2020. Архивировано 1 февраля 2020 года.
- ↑ Bird’s array notation . Дата обращения: 20 мая 2022. Архивировано 11 ноября 2021 года.
- ↑ Subcubic graph number . Дата обращения: 1 февраля 2020. Архивировано 1 февраля 2020 года.
Литература
- 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 Γ0? 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
Для улучшения этой статьи желательно: |