Просмотр кода страницы TREE(3)

{{проверить факты|дата=2021-02-07}}
'''TREE(3)'''<ref>{{cite web|author=Jay Bennett|title=Wrap Your Head Around the Enormity of the Number TREE(3)|url=https://www.popularmechanics.com/science/math/a28725/number-tree3/|website=Popular Mechanics|date=2017-10-20|accessdate=2020-05-27|archive-date=2020-07-01|archive-url=https://web.archive.org/web/20200701035303/https://www.popularmechanics.com/science/math/a28725/number-tree3/|deadlink=no}}</ref> — [[Большие числа|большое число]], которое является верхней границей решения  в [[Теория графов|теоретико-графовой]] теоремы Краскала{{Переход|#Теорема Краскала|||Kruskal's tree theorem}}. TREE(3) в невообразимое число раз больше [[Число Грэма|числа Грэма]]. Число TREE(3) столь велико, что стрелочные нотации [[Стрелочная нотация Кнута|Кнута]] и [[Стрелочные обозначения Конвея|Конвея]] не способны его записать.

== Теорема Краскала ==
[[File:TREE(3) sequence.png|thumb|300px|Пример последовательности деревьев для случая 3 цветов. Каждое i-е дерево имеет не более i вершин. Ни одно дерево не является топологическим минором более позднего дерева. Число TREE(3) определяется как максимально возможная длина такой последовательности.]]
{{falseredirect|Теорема Краскала}}
В [[Теория графов|теории графов]] деревом называется граф, в котором все вершины соединены рёбрами (возможно, посредством других вершин) и отсутствуют циклы (последовательности рёбер, соединяющие какую-либо вершину саму с собой). В данном случае деревья являются корневыми, то есть имеют определённую вершину - корень. Это понятное, но неформальное определение [[Дерево (теория графов)|дерева]]. Теорема Краскала<ref>{{Cite web |url=https://cp4space.wordpress.com/2012/12/19/fast-growing-2 |title=TREE(3) and impartial games {{!}} Complex Projective 4-Space<!-- Заголовок добавлен ботом --> |access-date=2020-02-01 |archive-date=2020-02-01 |archive-url=https://web.archive.org/web/20200201144311/https://cp4space.wordpress.com/2012/12/19/fast-growing-2/ |deadlink=no }}</ref> утверждает последовательность деревьев TREE(''n''), описанную следующими законами:

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

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

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

== Слабая tree-функция ==
Определим tree(''n''), ''слабую'' tree-функцию<ref name="автоссылка1">{{Cite web |url=https://googology.wikia.org/wiki/TREE_sequence#Weak_tree_function |title=TREE sequence {{!}} Googology Wiki {{!}} Fandom<!-- Заголовок добавлен ботом --> |access-date=2020-02-01 |archive-date=2020-01-09 |archive-url=https://web.archive.org/web/20200109010222/https://googology.wikia.org/wiki/TREE_sequence#Weak_tree_function |deadlink=no }}</ref>, как длину самой длинной последовательности из деревьев с вершинами одного цвета, описываемой следующими законами:

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

Известно<ref name="автоссылка1" />, что <math>tree(1)=2</math>, <math>tree(2)=5</math>, <math>tree(3)\geq 844424930131960</math>, а <math>tree(4)</math> уже больше числа Грэма.

Также известно<ref>{{Cite web |url=https://math.stackexchange.com/questions/313134/how-does-tree3-grow-to-get-so-big-laymen-explanation |title=graph theory - How does TREE(3) grow to get so big? (Laymen explanation) - Mathematics Stack Exchange<!-- Заголовок добавлен ботом --> |access-date=2020-02-01 |archive-date=2020-02-01 |archive-url=https://web.archive.org/web/20200201144301/https://math.stackexchange.com/questions/313134/how-does-tree3-grow-to-get-so-big-laymen-explanation |deadlink=no }}</ref>, что TREE(3) намного больше, чем <math>tree^{tree^{tree^{tree^{tree^8(7)}(7)}(7)}(7)}(7)</math> (верхний индекс в данном случае обозначает [[Итерированная функция|итерированную функцию]]).

== Масштаб числа TREE(3) ==
Распространённым заблуждением является утверждение [[Книга рекордов Гиннесса|книги рекордов Гиннесса]] о том, что [[число Грэма]] — самое большое число, которое когда-либо использовалось в [[Математическое доказательство|математическом доказательстве]]: эта информация давно устарела, так как число TREE(3) также используется в математическом контексте, и оно несоизмеримо больше числа Грэма. Для представления числа TREE(3) бесполезны не только [[тетрация|башни степеней]], но и нотации [[Стрелочная нотация Кнута|Кнута]] и [[Стрелочные обозначения Конвея|Конвея]]. В массивной нотации Бёрда<ref>{{Cite web |url=https://googology.wikia.org/wiki/Bird%27s_array_notation |title=Bird’s array notation |access-date=2022-05-20 |archive-date=2021-11-11 |archive-url=https://web.archive.org/web/20211111083152/https://googology.wikia.org/wiki/Bird%27s_array_notation |deadlink=no }}</ref> TREE(3) можно примерно выразить как <math>\{3, 6, 3 [1 [1 \neg 1,2] 2] 2\}</math>. Общая скорость роста функции TREE(''n'') оценивается как <math>f_{\theta\left(\Omega^{\omega}\omega\right)}(n)</math> в терминах [[Быстрорастущая иерархия|быстрорастущей иерархии]].

При этом TREE(3) далеко не самое большое число, встречавшееся в математических работах: в последующие годы описывались бо́льшие числа, например такие как {{нп5|SSCG(3)|SSCG(3)||SSCG(3)}}, SCG(13)<ref>{{Cite web |url=https://googology.wikia.org/wiki/Subcubic_graph_number |title=Subcubic graph number |access-date=2020-02-01 |archive-date=2020-02-01 |archive-url=https://web.archive.org/web/20200201144302/https://googology.wikia.org/wiki/Subcubic_graph_number |deadlink=no }}</ref>, а также числа, задаваемые с помощью невычислимых функций, такие, как [[число Райо]].

== Примечания ==
{{примечания}}

== Литература ==
* {{citation|mr=1943303
|last=Friedman|first= Harvey M.
|title=Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998)|pages= 60–91
|series=Lect. Notes Log.|volume=15|publisher= Assoc. Symbol. Logic|location= Urbana, IL|year= 2002}}
* {{citation|mr=1129778|last=Gallier|first=Jean H.|authorlink= Jean Gallier |title=What's so special about Kruskal's theorem and the ordinal Γ<sub>0</sub>? A survey of some results in proof theory|journal=Ann. Pure Appl. Logic|volume= 53 |year=1991|issue=3|pages=199–260|url=http://www.cis.upenn.edu/~jean/kruskal.pdf|doi=10.1016/0168-0072(91)90022-E}}
* {{citation
 | first = J. B.
 | last = Kruskal
 | authorlink = Joseph Kruskal
 |date=May 1960
 | title = Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture
 | journal = Transactions of the American Mathematical Society
 | volume = 95
 | issue = 2
 | pages = 210–225
 | url = http://www.ams.org/journals/tran/1960-095-02/S0002-9947-1960-0111704-1/S0002-9947-1960-0111704-1.pdf
 | mr = 0111704
 | doi = 10.2307/1993287
 | publisher = American Mathematical Society
 | jstor = 1993287
 }}
* {{статья
 |заглавие= Wqo and bqo theory in subsystems of second order arithmetic
 |издание= Reverse Mathematics
 |том= 21
 |страницы= 303—330
 |ссылка= https://users.dimi.uniud.it/~alberto.marcone/wqobqo.pdf
 |ref=  Marcone
 |язык=en
 |тип= journal
 |автор= Marcone, Alberto
 |год= 2001
}}
* {{citation|first=C. St.J. A. |last=Nash-Williams|authorlink=Crispin St. J. A. Nash-Williams|title= On well-quasi-ordering finite trees|journal= Proc. Camb. Phil. Soc. |volume=59|issue=4 |year=1963|pages= 833–835|mr=0153601|doi=10.1017/S0305004100003844}}
* {{статья
|заглавие= Proof-theoretic investigations on Kruskal's theorem
|ссылка= https://archive.org/details/sim_annals-of-pure-and-applied-logic_1993-02-24_60_1/page/n54
|издание= Annals of Pure and Applied Logic
|том= 60
|номер= 1
|страницы= 49—88
|doi=10.1016/0168-0072(93)90192-g
|ref=   Rathjen
|язык=en
|тип= journal
|автор= Rathjen, Michael; Weiermann, Andreas
|год= 1993
}}
* {{citation|first= Stephen G. |last=Simpson | authorlink = Steve Simpson (mathematician)
 |chapter=   Nonprovability of certain combinatorial properties of finite trees
|editor1-first=L. A.|editor1-last= Harrington|editor2-first= M. |editor2-last=Morley|editor3-first= A. |editor3-last=Scedrov|editor4-first= S. G.|display-editors = 3 |editor4-last= Simpson
|title=Harvey Friedman's Research on the Foundations of Mathematics|series= Studies in Logic and the Foundations of Mathematics|publisher= North-Holland
 | pages =87–117|year= 1985}}
* {{citation|first= Rick L. |last=Smith 
 |chapter=   The consistency strengths of some finite forms of the Higman and Kruskal theorems
|editor1-first=L. A.|editor1-last= Harrington|editor2-first= M. |editor2-last=Morley|editor3-first= A. |editor3-last=Scedrov|editor4-first= S. G.|display-editors = 3 |editor4-last= Simpson
|title=Harvey Friedman's Research on the Foundations of Mathematics|series= Studies in Logic and the Foundations of Mathematics|publisher= North-Holland
 | pages =119–136|year= 1985}}

{{rq|style|check|tex}}
{{Гугология}}

[[Категория:Большие числа]]
[[Категория:Теоремы дискретной математики]]
[[Категория:Деревья (графы)]]