Эта странная математика

Счетно-бесконечные ординалы простираются насколько хватает глаз, и каждый последующий из них – основа для новой, более мощной рекурсивной функции, оставляющей далеко позади предыдущую. Одни омеги составляют ряд такой длины, что он заканчивается только на омеге, возведенной в степенную башню высотой в омегу омег. Этот могучий ординал – эпсилон-ноль – настолько велик, что его невозможно описать средствами нашей классической арифметики, называемой арифметикой Пеано. С каждым шагом вдоль нескончаемой дороги омег конечное число, получаемое путем применения рекурсии, увеличивается на непостижимую величину. Но за самой величественной степенной башней из омег высятся башни, сложенные из многочисленных ярусов еще более внушительных бесконечных ординалов: сначала эпсилонов, потом дзет и так далее, и несть им числа – как мы уже выяснили раньше, когда говорили о бесконечности. С постоянным ростом ординалов растет и эффект обратной связи. И вот наконец мы добрались до умопомрачительно большого ординала гамма-ноль (Γ₀), у которого есть и более звучное название: ординал Фефермана – Шютте, в честь впервые описавших его американского философа и логика Соломона Фефермана и немецкого математика Карла Шютте. Несмотря на то, что гамма-ноль – все еще счетный ординал и есть после него и другие, определить его можно, только используя несчетные ординалы (то есть такие, которые невозможно получить путем перестановки элементов алеф-нуля; для несчетных ординалов требуется алеф-один или больше элементов). Этот процесс напоминает ход развития само2й быстрорастущей иерархии. Как для описания громадных конечных чисел нам пришлось в быстрорастущей иерархии прибегнуть к бесконечным ординалам, так и для описания огромных счетно-бесконечных ординалов мы вынуждены обратиться к ординалам несчетным. В языке просто не существует эпитетов, способных адекватно описать величину конечных чисел, которые можно получить с помощью рекурсии, используя ординал Фефермана – Шютте и другие, следующие за ним. Ни один математик, будь он хоть семи пядей во лбу, не в силах постичь всю безмерность чисел, порождаемых рекурсивными методами. Что, впрочем, нисколько не мешает математикам изобретать все более и более эффективные способы, генерирующие большие числа. Один из самых примечательных методов – функция TREE.

Как явствует из названия функции[47], она напоминает обычное дерево, растущее в лесу, или генеалогическое древо с ветвями, отходящими от общего ствола. Математические деревья – это особая разновидность так называемых графов. Их не нужно путать с графиками. График мы обычно представляем себе как кривую, показывающую соответствие между двумя величинами. Граф же в математике – нечто иное: это способ представления данных, когда точки, называемые узлами или вершинами, соединены отрезками – ребрами. Если, начав с одного из узлов графа и передвигаясь по его ребрам к другим узлам, можно вернуться к исходному, ни разу не проходя ни по одному ребру или узлу дважды, такой маршрут, и сам граф, называется циклом. Если от любого узла можно добраться до любого другого, не проходя дважды ни по одному ребру или узлу, то пройденный маршрут именуют путем, а граф – связным. Деревом называется связный граф, не содержащий циклов. И генеалогические, и биологические деревья имеют именно такую структуру. Если все узлы графа пронумеровать или присвоить им неповторяющиеся цвета, то такое дерево называется помеченным. Если одну из вершин дерева обозначить как корень, то получается корневое дерево. Одно из полезных свойств корневого дерева состоит в том, что от любого его узла можно проследить путь к корню.