Удивительные числа Вселенной - Антонио Падилья

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

Подобные деревья имеют практическое значение. Они возникают всякий раз, когда происходит ветвление — от алгоритмов принятия решений в информатике до дерева жизни в эволюционной биологии. Эпидемиологи используют так называемые филогенетические деревья для анализа эволюции вирусов и антител. Их применяли также к другим эволюционирующим системам, например раковым геномам. Однако интерес Фридмана к деревьям был глубже всего этого. Он искал недоказуемую истину: то, что верно, но при этом принципиально не может быть доказано, — по крайней мере, в рамках собственного математического аппарата. Это не имеет ничего общего с отсутствием умений или таланта у математиков. Такие фундаментальные истины гарантированно останутся недоказанными всегда, даже при самых опытных юристах. Как мы увидим, Игра деревьев — игра в этом математическом суде — является игрой недоказуемых истин.

Недоказуемая истина бьет по основам математики. Математика выросла из какого-то базового набора правил и принципов. Например, на понятии последовательности — того факта, что всегда можно увеличить число на единицу, — вы можете построить идею сложения. Вам нужна только продолжающаяся последовательность, где числа снова и снова увеличиваются на единицу. Далее вы можете разработать умножение, возведение в степень, ввести понятие простых чисел и доказать все теоремы, связанные с простыми числами. Математика — это рукотворная система, которая управляет сама собой. Он создает свой фундамент, свои основные строительные блоки, а из них мы строим городки и мегаполисы математической вселенной. Эти строительные блоки называются аксиомами. Чем больше аксиом есть у вас вначале, тем богаче и сложнее будет созданная вами математическая вселенная. Это интуитивно понятно. Если у меня в распоряжении имеются только желтые кирпичи, то все здания в мегаполисе будут желтыми. Но если есть желтые и красные кирпичи, я могу создавать более интересные узоры. Естественно, я по-прежнему способен возводить желтые дома, но теперь можно также создавать здания, украшенные сложной мозаикой желтого и красного цветов. В главе «Бесконечность» мы рассмотрим еще один пример — границу между финитной (конечной) и трансфинитной математикой. Из финитных кирпичей вы строите финитные здания. Оказывается, чтобы вывести математику в бесконечность, вам нужен новый тип кирпича, известный как аксиома бесконечности.

Интерес к аксиомам математики впервые возник в начале XX века. Многие из ведущих математиков мира тогда начали верить в теорию всей математики. Достаточно установить полный набор аксиом, из которых будет следовать все. Имея такие аксиомы, можно доказать истинность всех истинных утверждений, по крайней мере в принципе. Можно показать, что математика полна и не имеет противоречий. Несомненно, такой вере в математику способствовало осознание ее силы и красоты. Математика покоряла Вселенную. Только еретик мог заявить, что она поломана: что она неполна.

Этим еретиком стал Курт Гедель, блестящий чешский[78] философ и логик, которого многие считают наследником Аристотеля. В декабре 1931 года, когда мир охватила Великая депрессия, Гедель доказал существование недоказуемой истины — тот факт, что математика никогда не может оказаться полной. Какие бы аксиомы в качестве базы вы ни выбрали, всегда найдутся истинные утверждения, которые невозможно доказать. Конечно, вы всегда можете расширить эту базу, добавив в нее еще одну аксиому, которая поможет вам доказать то, что вы хотите. Однако в рамках новой системы все равно существуют верные утверждения, которые не удастся доказать. Аксиомы и доказательства никогда не поспевают за истиной.

Вернемся в наш мегаполис. В нем имеются только желтые и красные кирпичи, поэтому неудивительно, что на улицах преобладают простые здания двух цветов. Эти постройки подобны доказуемым теоремам математики. При наличии достаточного количества времени и усилий городские инженеры могут рассказать вам, как их строили. Однако в каком-нибудь темном закоулке обязательно найдется странное загадочное здание. Нечто недоказуемое. Ни один инженер никогда не сможет рассказать вам, как оно было построено, — по крайней мере, из тех стройматериалов, которыми располагает город. И все же это гордое и безошибочное напоминание о гении Геделя.

Чтобы дать представление о методах, лежащих в основе доказательства Геделя, я планирую убедить вас, что все числа интересны. Предположим, что это не так: существуют неинтересные числа. Если какое-то число действительно неинтересно, вряд ли у него будет своя страница в «Википедии», поскольку писать на странице не о чем. Однако среди этих неинтересных чисел должно быть наименьшее. Для определенности предположим, что это 49 732. Ну теперь мне хочется написать страницу в «Википедии» о числе 49 732, чтобы весь мир узнал об интересном факте: вот самое маленькое неинтересное число. На самом деле число оказывается интересным, и мы пришли к противоречию. Следовательно, неинтересных чисел не существует, все они интересны.

Геделевское доказательство неполноты использует аналогичную идею, хотя оно гораздо строже. Ключом к методу Геделя был разработанный системный код — своеобразный способ математики ссылаться на саму себя. Каждая аксиома, каждое математическое утверждение, истинное или ложное, получили собственный кодовый номер. Вы можете представить, что с каждым утверждением связали определенное число — аналогично коду ASCII. Например, одно число соответствует утверждению «квадратный корень из двух — иррациональное число», а другое — утверждению «1 + 1 = 3». Тогда истинность или ложность любого математического утверждения можно связать со свойством соответствующего числа. Например, можно сказать, что четные числа соответствуют истинным утверждениям, а нечетные — ложным. Конечно, на деле все конструировалось намного сложнее, но дух был именно таким. Вооружившись строгой системой кодирования, Гедель рассмотрел следующее утверждение:

«Это утверждение нельзя вывести из аксиом».

Теперь выйдем за пределы системы и предположим, что математика свободна от противоречий. Это означает, что утверждение Геделя должно быть истинным или ложным. Оно не может быть одновременно истинным и ложным. Предположим, оно ложно. Это означает, что утверждение можно вывести из аксиом. Противоречие. Следовательно, это утверждение должно быть истинным. Итак, мы нашли математически верное утверждение, которое невозможно вывести из аксиом; мы открыли недоказуемую истину, то самое загадочное здание в нашем математическом мегаполисе.

Математика никогда не может оказаться полной.

Теорема Геделя прославила