Сколько обозначает число: tree(3) ?

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

1. Первое дерево может содержать не более 1 узла.
2. Второе дерево — не более 2 узлов.
3. $n$-е дерево — не более $n$ узлов.

Главное правило: никакое дерево в последовательности не может «содержать» в себе (в качестве минора) любое из предыдущих деревьев. Если у нас есть только 1 цвет (TREE(1)), игра закончится на первом шаге. Если 2 цвета (TREE(2)), последовательность будет состоять из 3 деревьев. Но как только мы добавляем третий цвет, количество возможных деревьев в последовательности взрывается до невероятных масштабов. TREE(3) — это длина максимально возможной последовательности в такой игре с тремя цветами. Масштаб числа TREE(3) невозможно записать обычными цифрами, даже если использовать всю наблюдаемую Вселенную в качестве бумаги. Более того, для него недостаточно стандартных математических нотаций:

• Оно больше числа Грэма: Число Грэма ( $G_{64}$) долгое время считалось самым большим числом, использованным в серьезном математическом доказательстве. TREE(3) намного, намного больше, чем число Грэма. Оно не выражается через башни степеней: Даже если вы построите башню из экспонент вида ${10}^{{10}^{10.\mathrm{.}\mathrm{.}}}$, где количество «этажей» равно числу Грэма, результат все равно будет ничтожно мал по сравнению с TREE(3). Нотация Кнута: Для его описания не хватает обычных стрелок Кнута. Потребовалась бы гораздо более мощная система, такая как быстрорастущая иерархия функций. В этой иерархии TREE(3) примерно соответствует уровню $f_{\theta \left({\Omega }^{\omega }\omega \right)}\left(n\right)$.

Почему это важно? Несмотря на свою непостижимость, TREE(3) является конечным числом. Это было доказано с использованием методов логики второго порядка. Его существование демонстрирует, как простые правила комбинаторики могут приводить к структурам, которые выходят за рамки возможностей стандартной арифметики Пеано. Хотите, я попробую объяснить на более простом примере, как именно работает "вложение" деревьев, которое делает это число таким огромным?