Посмотрите на черное семя и крестик на верхних ветвях дерева А и дерева С. Прослеживая родословную в обоих случаях, мы видим, что в случае дерева А их ближайший общий предок — белое семя, а в случае дерева С — черное. Таким образом, получилось расхождение. Соответственно, в этом более слабом смысле дерево А не содержит дерево С.
Проясним ситуацию еще на одном примере. Вот еще два дерева.
Содержит ли дерево D дерево E? Первое, что нужно проверить: можем ли мы привести в соответствие семена? Закрываем все семена-крестики в дереве D и видим, что можем. Теперь нам нужно задаться вопросом о предках. Обратите внимание на белое и черное семена в верхних ветвях обоих деревьев. Проследив их родословную, мы видим, что в обоих случаях ближайшим общим предком оказывается черное семя, находящееся в корне. Подходит по всем статьям. Дерево D действительно содержит дерево E.
Теперь, когда правила понятны, мы готовы играть. Возьмем вариант, когда нам разрешено пользоваться только черными семенами. Я делаю ход первым. Помните, что это первое дерево, поэтому в нем может быть максимум одно семя. Изобразим его так.
Ваш ход. И у вас сразу же неприятности. Поскольку это второе дерево в лесу, в нем может быть не больше двух семян. Существует только два возможных дерева, которые вы можете изобразить: либо еще одно дерево из одного семени, либо дерево из двух семян.
Однако очевидно, что мое дерево содержится в обоих ваших возможных деревьях. Какое бы из них вы ни посадили, лес умрет. Избежать этого невозможно, поэтому игра заканчивается после первого же хода. Если использовать только один тип семян, лес может состоять только из единственного дерева, состоящего из одного семени.
Теперь давайте поиграем, когда разрешены два различных типа семян. Игра гарантированно закончится после трех ходов.
Какое бы дерево вы ни посадили дальше, оно обязательно уничтожит лес. Я догадываюсь, что вы не слишком впечатлены. Кому захочется играть в игру, которая обязательно закончится после трех жалких ходов?
Но подождите.
Пришло время сыграть с семенами трех видов — черные, белые и крестики. Давайте попробуем сделать несколько ходов.
Дела идут хорошо — лес все еще жив. Но сколько ходов мы можем сделать? Мы знаем, что в какой-то момент игра гарантированно завершится (это доказал Краскал). Но когда именно? Через сто ходов? Через гуголплекс? Когда число ходов будет равно числу Грэма?
Гораздо позже.
В этой книге мы уже читали истории о числовых исполинах — числах непостижимых размеров. Но эти колоссы — ничто по сравнению с нашим следующим левиафаном. Число, которое обозначают TREE(3), — гигантское предельное число ходов в игре с тремя семенами. Оно входит в крайне экстравагантную последовательность TREE(n). Если вы играете в Игру деревьев с n различными семенами, то игра закончится через TREE(n) ходов. Взгляните, как неспешно она начинается.
TREE(1) = 1 (поскольку игра с одним семенем продлится всего один ход),
TREE(2) = 3 (поскольку игра с двумя семенами продлится максимум три хода),
а потом бабах!
TREE(3) — это число, достаточно огромное, чтобы поглотить и гуголплекс, и число Грэма.
Все ваши представления превратились в ничто. Вы можете перейти к еще большим числам: TREE(4) получается при игре с четырьмя семенами, TREE(5) — при игре с пятью и т. д. Однако достаточно уже TREE(3). Умопомрачительного, невообразимого и безумного.
Первоначальная гипотеза Важони и последующее доказательство Краскала сообщают нам, что Игра деревьев рано или поздно закончится, пока вы играете с конечным числом семян. Американский математик и философ Харви Фридман понял, что она может порождать заодно чрезвычайно большие числа. Талант Фридмана к логике проявился уже в очень раннем возрасте. Когда ему было всего четыре или пять лет, он нашел словарь и спросил у матери, что это. «Книга со значениями слов», — ответила мать. Через несколько дней мальчик оспорил это утверждение. Он сказал, что словари бесполезны, потому что ходят по кругу. Слово «большой» они определяют через слова «крупный», «значительный», а те — через слово «большой». Как вообще можно узнать, что на самом деле что-либо означает? Примерно через десяток лет его ранние таланты обеспечили ему место в Книге рекордов Гиннесса — как самому молодому университетскому профессору: в возрасте 18 лет он получил в Стэнфордском университете звание ассистент-профессора[77].
Фридман заметил, что число TREE(3) невероятно велико. Математик не мог точно определить его, но сумел показать, что оно больше — гораздо больше, — чем любое другое число, которое вы найдете в этой книге. Он дал оценку — снизу — в терминах огромных чисел, известных как числа Аккермана. Чтобы ощутить их размер, нужно вернуться к лестнице Грэма. Возможно, вы помните, что первая ступенька g1 = 3 ↑ ↑ ↑ ↑ 3 была уже чудовищно велика, а дальше числа принимали совершенно неконтролируемый характер. Вторую ступень мы строили с помощью g1 стрелок: g2 = 3 ↑g1 3, третью — с помощью g2 стрелок: g3 = 3 ↑g2 3 и т. д., пока не дошли до шестьдесят четвертой ступеньки и числа Грэма. Но предположим, что вы продолжаете подниматься: на шестьдесят пятую ступеньку, когда число стрелок равно числу Грэма, на шестьдесят шестую, шестьдесят седьмую, на гуголную ступень этой лестницы. Предположим, что вы не отдыхали, пока не поднялись вот на такое количество ступеней:
2 ↑ 187 195187 196.
В этой формуле 187 195 стрелок Кнута. Это невероятно большое число, но оно всего лишь говорит о количестве ступенек лестницы Грэма! Всего шестьдесят четыре ступени вверх по этой лестнице привели вас к числу Грэма. Можете ли вы хотя бы начать осознавать, куда вас приведут 2 ↑ 187 195187 196 ступеней? Этот настоящий гигант похож на предложенную Фридманом оценку числа TREE(3), но не питайте иллюзий: это сильно заниженная оценка. На самом деле TREE(3) гораздо больше, этот левиафан среди левиафанов доминирует над всем, с чем мы сталкивались в нашем путешествии по большим числам.
В реальности нет интуитивно ясного способа осознать, почему TREE(3) настолько велико. Какой-то намек можно получить, взглянув на варианты игры, которые мы использовали поначалу. В игре с двумя типами семян мы были вынуждены использовать белые семена, начиная со второго круга. Однако если у нас остается всего один цвет, есть огромный риск обнаружить одно дерево внутри другого, и игре суждено быстро закончиться. А вот при игре с тремя видами семян ко второму кругу у нас остается целых два вида допустимых вариантов. Большая разница: мы можем играть с комбинациями, открывая все больше путей для новых экзотических узоров из деревьев. В конце концов мы исчерпаем все возможности, но это будет нескоро.
Подобные деревья имеют практическое значение. Они возникают всякий раз, когда происходит ветвление — от алгоритмов принятия решений в информатике до дерева жизни в эволюционной биологии. Эпидемиологи используют так называемые филогенетические деревья для анализа эволюции вирусов и антител. Их применяли также к другим эволюционирующим системам, например раковым геномам. Однако интерес Фридмана к деревьям был глубже всего этого. Он искал недоказуемую истину: то, что верно, но при этом принципиально не может быть доказано, — по крайней мере, в рамках собственного математического аппарата. Это не имеет ничего общего с отсутствием умений или таланта у математиков. Такие фундаментальные истины гарантированно останутся недоказанными всегда, даже при самых опытных юристах. Как мы увидим, Игра деревьев — игра в этом математическом суде — является игрой недоказуемых истин.
Недоказуемая истина бьет по основам математики. Математика выросла из какого-то базового набора правил и принципов. Например, на понятии последовательности — того факта, что всегда можно увеличить число на единицу, — вы можете построить идею сложения. Вам нужна только продолжающаяся последовательность, где числа снова и снова увеличиваются на единицу. Далее вы можете разработать умножение, возведение в степень, ввести понятие простых чисел и доказать все теоремы, связанные с простыми числами. Математика — это рукотворная система, которая управляет сама собой. Он создает свой фундамент, свои основные строительные блоки, а из них мы строим городки и мегаполисы математической вселенной. Эти строительные блоки называются аксиомами. Чем больше аксиом есть у вас вначале, тем богаче и сложнее будет созданная вами математическая вселенная. Это интуитивно понятно. Если у меня в распоряжении имеются только желтые кирпичи, то все здания в мегаполисе будут желтыми. Но если есть желтые и красные кирпичи, я могу создавать более интересные узоры. Естественно, я по-прежнему способен возводить желтые дома, но теперь можно также создавать здания, украшенные сложной мозаикой желтого и красного цветов. В главе «Бесконечность» мы рассмотрим еще один пример — границу между финитной (конечной) и трансфинитной математикой. Из финитных кирпичей вы строите финитные здания. Оказывается, чтобы вывести математику в бесконечность, вам нужен новый тип кирпича, известный как аксиома бесконечности.
Интерес к аксиомам математики впервые возник в начале XX века. Многие из ведущих математиков мира тогда начали верить в теорию всей математики. Достаточно установить полный набор аксиом, из которых будет следовать все. Имея такие аксиомы, можно доказать истинность всех истинных утверждений, по крайней мере в принципе. Можно показать, что математика полна и не имеет противоречий. Несомненно, такой вере в математику способствовало осознание ее силы и красоты. Математика покоряла Вселенную. Только еретик мог заявить, что она поломана: что она неполна.