Гёдель знакомится с Фибоначчи
В свои двадцать с небольшим юноша из Брюнна был уже превосходным математиком и, как и все математики, знал, что разнообразие целых чисел не имеет предела. Он знал множество других разновидностей чисел кроме квадратов, кубов, простых чисел, степеней десятки, суммы двух квадратов и прочих обычных подозреваемых. Критически важным для его будущего был тот факт, что благодаря Леонардо Пизанскому (более известному как Фибоначчи) юный Курт знал: классы чисел можно определять рекурсивно.
В 1300-х годах[17] Фибоначчи сочинил и исследовал то, что мы сегодня знаем как «числа Фибоначчи»:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …
В этой стремительно возрастающей бесконечной последовательности, члены которой я теперь буду называть числами F, каждый новый элемент создается из суммы двух предыдущих (кроме первой пары, 1 и 2, которые мы просто напрямую объявляем числами F).
Этот почти-но-не-совсем-циклический способ задания числовой последовательности через самое себя называется рекурсивным определением. Это означает, что есть некое строгое вычислительное правило для создания новых элементов из предыдущих. Это правило может включать сложение, умножение, деление, что угодно – лишь бы оно было задано как следует. Первый шаг рекурсивной последовательности (в этом случае числа 1 и 2) можно представить как мешочек семян, из которых заранее определенным образом, основанным на заданном правиле, вырастает гигантское растение – со всеми его бесчисленными ветвями и листьями.
Каспийские самоцветы: аллегория
Последовательность Леонардо Пизанского до краев наполнена удивительными закономерностями, но, к сожалению, углубившись в это, мы сильно собьемся с курса. И все же я не могу сдержаться и не упомянуть, что из этого списка нескольких первых чисел F в глаза бросается 144, как ярко выраженный полный квадрат. Не считая числа 8, которое является кубом, и числа 1, которое довольно вырожденный случай, никакой другой полный квадрат или куб, никакая другая степень не появляются среди первых нескольких сотен членов последовательности F.
Несколько десятков лет назад люди стали задаваться вопросом, появились ли 8 и 144 в последовательности F согласно какой-то причине или это было «просто случайностью». Со временем вычислительные средства становились все более мощными, и поиски возложили на них. Весьма любопытно, что даже с возникновением суперкомпьютеров, которые позволяли выдавать миллионы и миллиарды чисел F, никто и никогда не обнаружил других полных степеней в последовательности Фибоначчи. Шанс, что вскоре в последовательности F появится какая-то степень, был призрачным, но почему бы числам F и степеням совершенно избегать друг друга? Какое отношение n-ные степени с произвольным n имели к сложению пар чисел по особому рекурсивному правилу Фибоначчи? Разве не могут 8 и 144 быть просто случайным сбоем? Почему других сбоев было не видно?
Представим это в аллегорическом свете. Вообразите, что однажды кому-то удалось вытащить со дна великого зеленого Каспийского моря в Центральной Азии огромный бриллиант, великолепный рубин и крошечную жемчужину, и прочие охотники за удачей, воодушевленные этими поразительными находками, стали неистово вычерпывать дно самого большого в мире озера в поисках бриллиантов, рубинов, жемчуга, изумрудов, топазов и т. д., но, сколько бы ни черпали, так ничего и не нашли. Естественно было бы гадать, нет ли там, внизу, других самоцветов, но как узнать наверняка? (Оговорка: в моей аллегории есть небольшой изъян, поскольку мы можем вообразить, хотя бы в теории, что хорошо профинансированная научная группа однажды полностью вычерпает дно озера, поскольку оно конечно, хоть и огромно. Чтобы аналогия стала «идеальной», нам нужно представить, что Каспийское море бесконечно. Раздвинь границы своего воображения, читатель!)
Теперь поворот. Предположим, один геолог с математическим складом ума вознамерился доказать, что два изысканных каспийских камня плюс крошечная круглая жемчужина были уникальны – иначе говоря, что по определенной причине ни одного самоцвета и ни одной жемчужины любого размера и вида нельзя, невозможно больше достать из Каспийского моря. Есть ли смысл в том, чтобы искать такое доказательство? Откуда может взяться неопровержимая научная причина, полностью исключающая возможность найти самоцветы – не считая одной жемчужины, одного рубина и одного бриллианта – на дне Каспийского моря? Звучит абсурдно.
В нашем типичном представлении физический мир наполнен непредвиденными событиями, обстоятельствами, которые могли сложиться иначе, ситуациями, у которых нет фундаментальных причин на то, чтобы быть именно таковыми. Но позвольте напомнить, что математики видят свой первозданный, абстрактный мир полной противоположностью случайного, наполненного неопределенностями физического мира, в котором мы все обитаем. Вещи, которые случаются в математическом мире, кажутся математикам происходящими по причинам, которые можно выявить и понять, без исключений.
Этот образ мышления – Кредо Математика – вам необходимо принять и освоить, если вы хотите понять, как думают математики. В нашем конкретном случае загадка о нехватке степеней у Фибоначчи, пусть и незначительная в глазах большинства математиков, особенно сбивала с толку, поскольку к ней, казалось, было неоткуда подступиться. Два вовлеченных в нее явления – целые степени с произвольными показателями с одной стороны, числа Фибоначчи с другой – выглядели попросту (как и драгоценности в Каспийском море) слишком далекими друг от друга, чтобы иметь какую-то глубокую, систематическую, неизбежную взаимосвязь.
А затем прибыла большая команда математиков, которые коллективно нацелились на «большую игру» Последней Теоремы Ферма (знаменитое заявление, сделанное Пьером Ферма в середине семнадцатого века, которое гласит, что не существует таких натуральных чисел a, b, c, что an + bn равняется cn, где показатель n – это целое число, большее 2). Этой великой международной эстафетной команде, финальный победный рывок которой великолепно выполнил Эндрю Уайлс (этот рывок занял у него восемь лет), в конце концов удалось доказать заявление Ферма многовековой давности с использованием удивительных техник, которые сочетали в себе идеи со всех уголков обширной карты современной математики.
Вследствие революционной работы этой команды открылись новые пути, от которых, похоже, пошли трещины по многим старым добрым дверям, включая накрепко закрытую дверь маленькой, но манящей загадки степеней Фибоначчи. И в самом деле, где-то через десять лет после доказательства Последней Теоремы Ферма трое математиков, используя техники Уайлса и других, смогли выделить точную причину, по которой куб 8 и квадрат 144 никогда не найдут себе приятеля, полную степень, среди членов рекурсивной последовательности Леонардо Пизанского (кроме 1). Пусть и крайне невразумительная, но причина бесконечного танца взаимного избегания была найдена. Это стало еще одним триумфом Кредо Математика – еще одна причина купить ворох акций у концепции, гласящей, что в математике где есть паттерн, там есть причина.
Крошечная искра в мозгу Гёделя
Теперь вернемся к истории Курта Гёделя и к его встрече с могущественной идеей, что все виды бесконечных классов чисел могут быть определены через разнообразные рекурсивные правила[18]. Образ бесконечной структуры или паттерна, который органически вырастает из конечного набора начальных семян, вызывал у Гёделя куда больше, чем просто любопытство; он напомнил ему о том, что теоремы ПМ (как и теоремы в «Началах» Евклида) всегда вырастали (следуя формальным правилам вывода) из более ранних теорем ПМ, за исключением нескольких первых теорем, которые были объявлены теоремами напрямую и потому назывались «аксиомами» (и были аналогами семян).
Другими словами, в тщательной аналогии, вспыхнувшей в сознании Гёделя от искры этого смутного сходства, аксиомы ПМ играли роль семян Фибоначчи 1 и 2, а правила вывода ПМ играли роль сложения двух последних чисел. Главным отличием было то, что в ПМ было не одно, а несколько правил вывода, поэтому на каждом этапе имелся выбор, что делать дальше, и, более того, не обязательно было применять выбранное правило к последней порожденной теореме (теоремам), что предоставляло еще больший выбор. Но, не считая дополнительных степеней свободы, аналогия Гёделя была подогнана очень точно и оказалась чрезвычайно плодородной.
Умные правила насыщают символы смыслом
Я должен подчеркнуть, что каждое правило вывода в формальной системе вроде ПМ не только ведет от одной или более начальных формул к конечным формулам, но это происходит исключительно типографскими средствами – то есть исключительно механической перестановкой символов, для которой не требуется ни единой мысли о значении символов. С точки зрения человека (или машины), который следует правилам с целью произвести теоремы, символы с тем же успехом могут быть совершенно лишены смысла.
С другой стороны, каждое правило должно быть продумано достаточно тщательно для того, чтобы из истинных входных формул на выходе также получалась истинная формула. Так что проектировщик формул (в данном случае Рассел и Уайтхед) должен был думать о предполагаемых значениях символов, чтобы быть уверенным, что правило сработает совершенно четко для оператора (не важно, человека или нет), который не думает о предполагаемых значениях символов.
В качестве простого примера возьмем символ «ν», который, как предполагается, обозначает понятие «или». Тогда возможное правило вывода выглядит так:
Из любой формулы «P ν Q» можно вывести перевернутую формулу «Q ν P».
Это правило вывода обоснованно, так как если «или-высказывание» (вроде: «Я сошел с ума, или вы сошли с ума») истинно, то истинно и перевернутое «или-высказывание» («Вы сошли с ума, или я сошел с ума»).
Конкретно это ν-зеркальное правило не входит в число правил вывода ПМ, хотя и могло бы. Суть в том, что это правило показывает, как можно механически передвигать символы, игнорируя их смысл, но сохраняя при этом истинность. Это правило достаточно тривиально, но есть и более хитрые, которые занимаются настоящим делом. В этом и есть вся суть символической логики, впервые предложенной Аристотелем; затем она в течение долгих веков по кусочкам развивалась мыслителями, среди которых были Блез Паскаль, Готфрид Вильгельм фон Лейбниц, Джордж Буль, Август де Морган, Готлоб Фреге, Джузеппе Пеано, Давид Гильберт и многие другие. Рассел и Уайтхед просто развивали античную мечту о полной механизации рассуждений более целеустремленно, чем их предшественники.
Механизируя Кредо Математика
Если вы примените правила вывода ПМ к ее аксиомам (к семенам, которые составляют «нулевое поколение» теорем), вы получите некоторое «потомство» – теоремы «первого поколения». Затем снова примените правила к теоремам первого поколения (а также к аксиомам) всеми возможными способами; так вы получите новую охапку теорем – второе поколение. Затем из всего этого варева получится третья охапка теорем, и дальше, до бесконечности, они будут разрастаться как снежный ком. Бесконечная масса теорем ПМ полностью определена начальными семенами и типографскими «правилами роста», которые позволяют создавать новые теоремы из старых.
Нужно ли говорить, что мы надеемся на то, что все механически произведенные теоремы ПМ являются истинными утверждениями теории чисел (т. е. никогда не будет произведено ложное утверждение), и в то же время мы надеемся на то, что все истинные утверждения теории чисел будут механически произведены внутри ПМ (т. е. нет такого истинного утверждения, которое никогда не будет произведено). Первая из этих надежд называется непротиворечивостью, а вторая называется полнотой.
Короче говоря, мы хотим, чтобы вся бесконечная масса теорем ПМ точно совпадала с бесконечной массой истинных утверждений теории чисел – мы хотим идеального, безупречного соответствия. По крайней мере, этого хотели Рассел и Уайтхед, и они верили, что с ПМ у них получится достичь цели (в конце концов, «s0 + s0 = ss0» – это теорема, не так ли?).
Давайте вспомним Кредо Математика, которое в той или иной форме существовало за много веков до появления Рассела и Уайтхеда:
X истинно, поскольку существует доказательство X;
X истинно, и потому существует доказательство X.
Первая строка выражает вышеописанную первую надежду – на непротиворечивость. Вторая строка выражает вышеописанную вторую надежду – на полноту. Теперь мы видим, что Кредо Математика очень тесно связано с намерениями Рассела и Уайтхеда. Их целью, однако, было установить Кредо на новый жесткий фундамент с ПМ в качестве пьедестала. Другими словами, там, где Кредо Математика говорит лишь «доказательство», не объясняя, что за этим термином стоит, люди должны были понимать, что это «доказательство внутри ПМ» – вот чего хотели Рассел и Уайтхед.
Сам Гёдель весьма уважал мощь ПМ, это можно увидеть во вводной части его статьи 1931 года:
Развитие математики в направлении большей аккуратности привело – как известно – к тому, что значительные ее территории были формализованы, чтобы доказательства можно было получать согласно нескольким механическим правилам. Наиболее всеобъемлющими из созданных формальных систем являются, с одной стороны, «Принципы математики» (ПМ), а с другой, система аксиом для теории множеств Цермело – Френкеля (позже расширенная Дж. фон Нейманом). Эти две системы настолько обширны, что все методики доказательств, ныне используемые, были формализованы в них, т. е. сжаты до нескольких аксиом и правил вывода.
И все же, несмотря то, как великодушно Гёдель снял шляпу перед трудом Рассела и Уайтхеда, он не верил ни в то, что было достигнуто идеальное соответствие между истиной и теоремами ПМ, ни в то, что такая цель была в принципе достижима, и его глубокий скепсис происходил от того, что он учуял крайне странную петлю, свернувшуюся в похожем на лабиринт дворце математического рассуждения – бездумного, механически передвигающего символы и лишенного смысла.
Удивительная синхронность шагов
Концептуальная параллель между рекурсивно определенной последовательностью целых чисел и скачкообразно созданным множеством теорем ПМ (или, если на то пошло, любой формальной системы, в которой есть аксиомы в качестве семян и правила вывода в качестве механизмов роста) навела Гёделя на мысль, что типографские паттерны символов на страницах «Принципов математики» – то есть жесткие логические выводы новых теорем из предыдущих – могут таким же образом как-то «отражаться» в мире чисел. Внутренний голос сказал ему, что эта связь была не просто смутным сходством, а имела все шансы превратиться в абсолютно точное соответствие.
Если говорить подробнее, Гёдель вообразил множество целых чисел, которые органически вырастали одно из другого при помощи арифметических операций, почти как числа Фибоначчи F, но которые также однозначным образом соответствовали множеству теорем ПМ. Например, если вы получили теорему Z из теорем X и Y, использовав типографское правило R5, и если вы получили число z из чисел x и y, использовав вычислительное правило r5, то все сходится. То есть если x был числом, соответствующим теореме X, а y был числом, соответствующим теореме Y, то z «чудесным образом» окажется числом, соответствующим теореме Z. Так образуется полная синхронность; две стороны (типографская и числовая) будут двигаться друг с другом в ногу. Сперва предвидение этой чудесной синхронности было лишь маленькой искрой, но Гёдель быстро осознал, что его новорожденная мечта может стать настолько проработанной, что ею можно будет поделиться с другими, и начал настойчиво преследовать ее.
Перескакивая между формулами и очень большими числами
Чтобы превратить свое интуитивное ощущение в серьезную, проработанную и уважаемую идею, Гёдель сперва должен был разобраться, как строка символов ПМ (безотносительно того, утверждает она истину или ложь, даже если это просто случайный винегрет из символов, набранных наобум) может систематически конвертироваться в целое число, и наоборот, как это целое число может быть «расшифровано» и выдать строку, из которой оно изначально получилось. Первый этап мечты Гёделя – систематическое отображение, по которому каждая формула получала бы числовое «имя», – был следующим.
Базовый алфавит ПМ состоял всего лишь из дюжины символов (остальные символы были введены позже, но все они были заданы в терминах нескольких исходных, так что концептуально не были необходимы), и к каждому из этих символов Гёдель прикрепил уникальное маленькое целое число (выбор этих нескольких исходных чисел был достаточно произвольным – правда, совершенно не важно, какому числу был сопоставлен каждый отдельный символ).
Идея была в том, чтобы в многосимвольных формулах (кстати говоря, в этой книге термины «строка символов» – для краткости «строка» – и «формула» синонимичны) один за другим, слева направо, заменить символы на их кодовые номера, а затем объединить все эти отдельные кодовые номера (используя их в качестве показателей степени, в которые возводятся последовательно идущие простые числа) в одно уникальное большое число. Таким образом, благодаря номерам, прикрепленным к отдельным символам, номер, прикрепленный к строке, уже не был случайным.
Например, предположим, что (произвольный) кодовый номер для символа «0» это 2, а кодовый номер для символа «=» это 6. Тогда для трех символов в очень простой формуле «0 = 0» кодовые номера будут 2, 6, 2, и эти три номера используются как показатели степени для трех первых простых чисел (2, 3 и 5) следующим образом:
22·36·52 = 72 900.
Так мы узнаем, что 72 900 является единственным числом, соответствующим формуле «0 = 0». Разумеется, это довольно большое число для такой короткой формулы, и вы легко можете себе представить, что пятидесятисимвольной формуле соответствует число и вовсе астрономическое, поскольку оно подразумевает возведение первых пятидесяти простых чисел в разные степени, а затем перемножение всех этих больших чисел между собой, что порождает настоящего колосса. Но это не важно – числа есть числа, как бы велики они ни были. (К счастью для Гёделя, простых чисел бесконечно много, ведь если бы их было только, скажем, миллиард штук, его метод позволил бы ему закодировать лишь формулы, составленные не более чем из миллиарда символов. Вот это был бы настоящий удар!)
Процесс декодирования заключается в разложении числа 72 900 на простые множители (единственно возможным образом) и считывании показателей степени в порядке возрастания простых оснований – в нашем случае 2, 6, 2.
В общем, таким неочевидным, но простым образом Гёдель нашел способ заменить любую формулу ПМ на эквивалентное ей число (которое люди вскоре окрестят числом Гёделя). Затем он распространил идею «арифметизации» также на произвольные последовательности формул, поскольку доказательства в ПМ – это последовательности формул, а он хотел работать с доказательствами, не только с формулами самими по себе. Таким образом, последовательность формул произвольной длины можно было преобразовать в одно большое целое число, используя, по сути, тот же прием с простыми числами и степенями. Подумайте только, какие это поистине огромные числа.
Короче говоря, Гёдель показал, как абсолютно любому визуальному символьному паттерну в специфической нотации «Принципов математики» могло быть сопоставлено уникальное число, которое могло быть легко декодировано и выдать обратно визуальный паттерн (т. е. последовательность символов), которому оно соответствовало. В том, чтобы придумать и довести до блеска это точное двустороннее отображение, которое теперь повсеместно называется «нумерацией Гёделя», и заключался первый, ключевой шаг работы Гёделя.
Очень большие числа идут в ногу с формулами
Следующий ключевой шаг заключался в том, чтобы создать рекурсивные описания в стиле Фибоначчи для специальных числовых множеств – так, чтобы целые числа органически вырастали из тех, что были сгенерированы раньше, при помощи сложения, умножения или более сложных вычислений. Одним из примеров будут числа ППФ – числа, которые в кодировке Гёделя представляют «правильно построенные» или «осмысленные» формулы ПМ, в отличие от тех, которые представляют бессмысленные или грамматически неверные строки. (Примером правильно построенной формулы, для краткости ППФ, служит «0 + 0 = = sss0». Хотя это утверждение ложно, оно все же осмысленно. С другой стороны, «=) 0 (=» и «00 = = 0 + =» не являются ППФ. Как и случайная последовательность псевдослов «ззип дуббивубби пизз», они ничего не утверждают.) Поскольку получается так, что более длинные ППФ в ПМ строятся из более коротких ППФ по нескольким простым и стандартным правилам непосредственного типографского сочленения, их длинные кодовые номера также могут быть построены из меньших кодовых номеров более коротких формул по нескольким простым и стандартным правилам численных расчетов.
Я сказал об этом довольно небрежно, но на самом деле этот шаг был, возможно, самым глубоким из ключевых осознаний Гёделя – а именно, что после «арифметизации» строки символов (присвоения ей ответной числовой части) для любого типографского перемешивания строк на бумаге можно было найти полную аналогию среди чисто арифметических вычислений, производящихся над их числовыми посредниками – которые были пусть и огромными, но все же просто числами. То, что для Рассела и Уайтхеда выглядело как тщательная перестановка символов, для Курта Гёделя больше было похоже на непосредственную обработку чисел (хотя он, конечно, не использовал такой современный термин, поскольку все это происходило в те доисторические дни, когда компьютеров еще не было). Это были просто два разных взгляда на происходящее – два взгляда, стопроцентно эквивалентные и взаимозаменяемые.
Намеки на то, как ПМ может обернуться и посмотреть на себя
Гёдель заметил, что игра, которая заключалась в построении бесконечного класса чисел вроде чисел ППФ путем рекурсии – то есть получение новых «членов клуба» путем соединения старых, ранее определенных членов с помощью некоего правила по обработке чисел – по сути своей ничем не отличалась от рекурсивной игры Фибоначчи, которая заключалась в построении класса чисел F путем складывания двух предыдущих членов. Конечно, рекурсивный процесс мог быть куда более сложным, чем просто вычисление суммы двух последних членов клуба.
Любое рекурсивное определение, пусть и неявно, разделяет множество всех целых чисел на членов и не-членов клуба – то есть на те числа, которые рано или поздно достижимы с помощью рекурсивного процесса построения, и на те, которые не достижимы никогда, сколько бы мы ни ждали. Так, 34 является членом клуба F, тогда как 35 им не является. Откуда мы знаем, что 35 не является числом F? Очень просто – правило, по которому создаются новые числа F, всегда создает большие числа из меньших, так что, когда мы переступаем определенную величину, нет никаких шансов, что мы вернемся к ней и «подберем» другие числа поблизости. Иными словами, получив числа F 1, 2, 3, 5, 13, 21, 34, 55, мы уже знаем, что они единственные в этом диапазоне, так что, очевидно, 35, 36 и так далее до 54, не являются числами F.
Впрочем, если какой-нибудь другой клуб определен рекурсивным правилом, в котором числа на выходе иногда больше, чем на входе, а иногда меньше, тогда, в отличие от простого случая с клубом F, вы не можете быть уверены, что никогда не вернетесь и не повстречаете меньшие числа, которые пропустили на предыдущих шагах.
Давайте еще немного подумаем о рекурсивно определенном клубе чисел, который мы называем числами ППФ. Мы видели, что число 72 900 обладает «ППФ-ностью», и, если вы подумаете немного, вы поймете, что 576 и 2916 этим свойством не обладают. (Почему? Что ж, если вы разложите их на множители и посмотрите на степени 2 и 3, вы увидите, что эти числа являются численным кодом для строк «0=» и «=0» соответственно, ни одна из которых не имеет смысла, и потому правильно построенными формулами они не являются.) Другими словами, несмотря на странное определение, ППФ-ность, не в большей и не в меньшей степени, чем квадратность, простота или F-ность Фибоначчи, является полноправным объектом для изучения в мире чисел. Теоретико-числовое различие между членами и не-членами «клуба ППФ» так же подлинно, как и для клуба квадратов, клуба простых чисел или клуба чисел F, поскольку числа ППФ определяемы в рекурсивной арифметической (т. е. вычислительной) манере. Более того, получается, что рекурсивные правила определения ППФ-ности всегда производят результат больший, чем исходное число, так что ППФ-ность разделяет с F-ностью это простое свойство – однажды превзойдя определенную величину, вы можете быть уверены, что уже никогда не вернетесь навестить эту область.
Как любопытство некоторых людей разжигало то, что они замечали квадрат в рекурсивно определенной последовательности Фибоначчи, так некоторых людей может заинтересовать вопрос о том, есть ли квадраты (кубы и т. д.) в рекурсивно определенной последовательности чисел ППФ. Они могут провести много времени, расследуя подобные чисто теоретико-числовые вопросы, ни разу не задумавшись о соответствующих им формулах «Принципов математики».
Можно не иметь никакого представления о том, что гёделевские числа ППФ берут свои истоки в правилах определения правильнопостроенности, сформулированных в «Принципах математики», точно так же, как можно изучать законы вероятностей, даже не подозревая, что изначально эта обширная ветвь математики была создана для анализа азартных игр. То, что когда-то кого-то сподвигло сочинить некое специфическое рекурсивное определение, очевидно, не влияет на числа, которые это определение задает; важно лишь то, что должен существовать чисто вычислительный способ, как вырастить любого члена клуба из начальных семян, применяя правила некоторое конечное количество раз.
Итак, числа ППФ, похоже, относительно просто определить рекурсивным способом, и по неким причинам ППФ-ность (в точности как и F-ность) является разновидностью математических сущностей, для изучения которых были созданы «Принципы математики». Уайтхед и Рассел уж точно никогда не мечтали о том, что их механическая система рассуждений cможет применяться таким причудливым образом, что ее свойства как машины подвергнутся ее собственному наблюдению, как если бы мы использовали микроскоп, чтобы изучить его собственные линзы на предмет возможных дефектов. Впрочем, изобретения часто удивляют своих изобретателей.
Принципиальные числа
Осознав, что в теории один из томов Уайтхеда и Рассела мог бы определить и систематически исследовать разнообразные численные свойства чисел ППФ, Гёдель продолжил аналогию и, использовав немало изощренных, но при этом концептуально не слишком сложных алгоритмов, показал, что существует бесконечно более интересный рекурсивно определенный класс целых чисел, который я буду здесь называть принципиальными числами (неистово салютуя названию знаменитого трехтомника) и к которому относятся числа для доказуемых формул ПМ (т. е. теорем).
Доказательство в ПМ – это, разумеется, набор формул, составляющих весь путь от аксиом ПМ до нужной формулы, где каждый шаг возможен благодаря определенному правилу рассуждения, которые в ПМ становятся формальными типографскими правилами вывода. Для каждого типографского правила вывода, работающего на строках ПМ, Гёдель предоставил идеально соответствующее вычислительное правило, которое работало на числах. Численные методы чихать хотели на типографские манипуляции, дерзко заявляя: «Все, что вы умеете, я умею лучше!» Впрочем, не то чтобы лучше – но Гёдель, несомненно, показал: суть в том, что вычислительные правила всегда будут в точности совпадать – оставаться в полной синхронности – с любым формальным типографским правилом, так что численные правила были ровно настолько же хороши.
В конечном счете, каждой доказуемой строке в формальной системе Рассела и Уайтхеда соответствовало принципиальное число. Каждое принципиальное целое число могло быть расшифровано в символы, и полученная вами строка являлась бы доказуемой-внутри-ПМ формулой. Аналогично, каждая доказуемая-внутри-ПМ формула могла быть зашифрована как одно вопиюще огромное число, и, богом клянусь, после достаточного количества вычислений вы могли показать, что полученное число – принципиальное. Простым примером принципиального числа вновь будет наш старый друг 72 900, поскольку формула «0 = 0» не только является правильно построенной формулой, но также, что не слишком удивительно, выводима внутри ПМ. (В самом деле, если бы это было не так, ПМ была бы чрезвычайно жалкой механической моделью математических рассуждений!)
Существует коренное различие между числами ППФ и принципиальными числами, которое происходит из того факта, что правила вывода в ПМ порой производят выходные строки, которые короче, чем входные. Это значит, что соответствующие арифметические правила, определяющие принципиальные числа, будут порой принимать большие принципиальные числа на вход и делать из них меньшие принципиальные числа на выходе. Поэтому однажды посещенные отрезки числовой оси всегда можно посетить повторно, и из-за этого гораздо, гораздо труднее установить, является данное целое число принципиальным или нет. Это основной и очень сокровенный факт о принципиальных числах.
Как и в случае с квадратами, простыми числами, числами F или ППФ, в теории мог бы существовать отдельный том из серии книг Уайтхеда и Рассела, в котором принципиальные числа были бы определены, а их математические свойства изучены. Например, этот том мог бы содержать доказательство формулы ПМ, которая (подвергнувшись тщательному изучению) утверждала бы, что «72 900 является принципиальным числом», а также в нем могла бы обсуждаться другая формула, которая, как видно, утверждает обратное («72 900 не является принципиальным числом»), и так далее. Последнее утверждение, разумеется, ложно, тогда как предыдущее истинно. И даже более сложные теоретико-числовые концепции, выраженные в нотации ПМ, могли бы обсуждаться в гипотетическом томе вроде: «Существует бесконечно много принципиальных чисел» – что было бы равносильно (по ее коду) утверждению: «Существует бесконечно много формул, которые доказуемы внутри ПМ».
Пусть это и покажется странным, но кто-то, безусловно, может задаться теоретико-числовым вопросом в стиле восемнадцатого века: «Какие целые числа можно выразить в виде суммы двух принципиальных чисел, а какие нет?» Вряд ли кто-то задаст такой эксцентричный вопрос всерьез, но дело в том, что свойство «принципиальности», хоть оно и достаточно «современно», ровно в той же степени является настоящим теоретико-числовым свойством целого числа, что и «классические» свойства вроде квадратности, простоты или вхождения в ряд чисел Фибоначчи.
Поразительные свойства принципиальных чисел
Допустим, кто-то сказал вам, что построил машину – я назову ее Гуру, – которая всегда будет давать верный ответ на вопрос вида: «Является ли n простым числом?», где n – любое целое число, какое захотите. После вопроса: «Является ли 641 простым?» – Гуру немного покрутит своими колесиками и затем ответит «да». Что до числа 642, Гуру, немного «подумав», ответит «нет». Думаю, такая машина не слишком бы вас удивила. То, что такую машину можно построить – не важно, на кремниевой плате или с применением технологии цепочек домино, – уже не поражает ничье воображение в нашу эпоху.
Но, допустим, кто-то сказал вам, что построил аналогичную машину – я назову ее «Гёру», – которая всегда будет давать верный ответ на вопрос вида: «Является ли n принципиальным числом?» Покажется ли вам это заявление – строго аналогичное предыдущему – настолько же банальным? Если да, я со всем уважением предоставляю к вашему размышлению новый вопрос.
Дело вот в чем. Если вы верите в надежность Гёру, а также верите в Кредо Математика (в версии «Принципов математики»), то вы можете заключить, что ваш маленький Гёру, работая сам по себе, может ответить на любой теоретико-числовой вопрос, который вас интересует, прямо как джинн, вызванный из волшебной лампы. Как же так? Что делает Гёру волшебным джинном?
Что ж, допустим, вам хочется узнать, истинно или ложно высказывание X (например, знаменитое утверждение: «Любое четное число, большее 2, является суммой двух простых чисел» – которое, как я объявил выше, несмотря на почти трехвековые исследования, остается недоказанным и по сей день). Вы бы просто записали X в формальной нотации ПМ, затем механически перевели его в число Гёделя x и скормили бы это число Гёру (спросив таким образом, является ли x принципиальным). Конечно, x был бы огромным числом, так что Гёру потребовалось бы немало времени для того, чтобы дать ответ, но рано или поздно (подразумевая, что Гёру вас не дурачит) он выплюнет либо «да», либо «нет». Если Гёру сказал «да», вы узнаете, что x принципиальное число, а это будет означать, что зашифрованная в нем формула – доказуемая формула, что означает, что утверждение X истинно. И напротив, если Гёру ответит вам «нет», вы будете знать, что утверждение X недоказуемо, и потому, веруя в Кредо Математика (в версии «Принципов математики»), вы заключите, что оно ложно.
Другими словами, если бы у нас была машина, способная безупречно отличать принципиальные числа от «нахальных» (не принципиальных), приняв на веру справедливость Кредо Математика в версии «Принципов математики», мы могли бы безупречно отличать истинные утверждения от ложных. Короче говоря, наличие Гёру дало бы нам королевский ключ ко всем математическим знаниям.
Да и сами принципиальные числа, кажется, скрытым образом заключали бы в себе все математические знания! Никакая другая последовательность чисел, придуманная кем-то до Гёделя, не обладала подобным магическим прорицательным свойством. Каждое из этих невероятных чисел, кажется, буквально на вес золота! Но, как я уже говорил, принципиальные числа иллюзорны, поскольку маленькие числа порой присоединяются к клубу на очень поздних порах, так что отличить принципиальные числа от «нахальных» непросто, не говоря о том, чтобы построить Гёру. (Это должно послужить предвестником грядущих событий.)
Гёделевская странность
Наконец, Гёдель привел свою аналогию к неизбежному, эпохальному выводу, который заключался в том, что он продиктовал своим читателям (не посимвольно, конечно, а при помощи точного набора «инструкций по сборке») астрономически длинную формулу ПМ, которая делала с виду невинное заявление: «Определенное целое число g не является принципиальным числом». Однако это «определенное целое g», о котором говорилось в формуле, оказалось, по совершенно неслучайному (кто-то сказал бы, дьявольскому) стечению обстоятельств, числом (т. е. кодом), соответствующим этой самой формуле (число это, конечно же, было исполинским). Как мы скоро увидим, странную формулу Гёделя можно было интерпретировать на двух разных уровнях, и в зависимости от интерпретации она имела два очень различных значения.
На более буквальном уровне формула Гёделя всего лишь утверждает, что это исполинское число g не наделено теоретико-числовым свойством под названием принципиальность. Это заявление очень похоже на заявление, что «79 200 не является простым числом», хотя стоит отметить, что g гораздо больше, чем 79 200, а принципиальность куда более тернистое свойство, чем простота. Однако, раз принципиальность была определена Гёделем так, чтобы она численно отражала доказуемость строк с помощью правил системы ПМ, формула также заявляет:
Формула, которой случилось иметь в качестве кода число g, недоказуема при помощи правил «Принципов математики».
Теперь, как я только что сказал, формула, которой «случилось» иметь в качестве кода число g, это формула, которая делает вышеописанное заявление. Короче говоря, формула Гёделя делает заявление о самой себе – а именно, следующее:
Эта формула не доказуема при помощи правил ПМ.
Порой вторая формулировка специально подается в виде «Я не теорема» или еще более сжато:
Я недоказуема
(внутри системы ПМ, это здесь подразумевается негласно).
Дальше Гёдель показал, что эта его формула, на первый взгляд очень странная и смущающая, была не такой уж и необычной; в самом деле, это был лишь один элемент бесконечного семейства формул, которые делали заявления о ПМ, многие из которых делали (некоторые истинно, некоторые ложно) схожие странные и уклончивые утверждения о себе (например, «Ни я, ни мое отрицание не являются теоремами ПМ», «Если я доказуема внутри ПМ, то доказательство моего отрицания короче, чем мое», и так далее, и тому подобное).
Молодой Курт Гёдель – в 1931 году ему было всего лишь 25 лет – обнаружил целое море поразительно неожиданных, до странности уклончивых формул, спрятанных внутри строгого, формального, защищенного теорией типов и оттого предположительно свободного от парадоксов мира, описанного Расселом и Уайтхедом в грандиозном трехтомном труде «Принципы математики», и многие контринтуитивные свойства оригинальной формулы Гёделя и ее бесчисленных родственников занимают математиков, логиков и философов с тех пор и по сей день.
Как засунуть в формулу число Гёделя для этой формулы
Говоря о великолепных достижениях Гёделя, я не могу обойти один небольшой технический нюанс, поскольку, если я так поступлю, некоторые читатели точно останутся сбиты с толку, а то и скептично настроены к ключевому аспекту работы Гёделя. Более того, эта идея вообще-то довольно магическая, так что ее стоит вкратце упомянуть.
Вот этот зудящий вопрос: как вообще Гёдель сумел поместить число Гёделя для формулы в саму эту формулу? На первый взгляд может показаться, что это как пытаться втиснуть слона в спичечный коробок – и в некотором роде это совершенно так и есть. Ни одна формула не может буквально содержать в себе число, соответствующее ее числу Гёделя, поскольку это число содержит куда больше символов, чем сама формула! Сперва это может выглядеть как фатальное препятствие, но оказывается, что это не так – и если вы мысленно вернетесь к нашей дискуссии о парадоксе Дж. Дж. Берри, возможно, вы увидите почему.
Фокус строится на простом факте, что некоторые огромные числа имеют очень короткие описания (например, число 387 420 489 можно описать всего пятью слогами: «девять в девятой»). Если у вас есть очень короткий рецепт вычисления числа Гёделя для очень длинной формулы, то вместо того, чтобы описывать это огромное число самым медленным и неуклюжим путем («тот, кто следует за тем, кто следует за тем, кто… следует за тем, кто следует за нулем»), вы можете описать его коротким вычислительным путем, и если вы подставите в формулу в виде символов этот путь (а не само число), то вам удастся заставить формулу говорить о себе самой, не запихивая слона в коробок. Я не буду пытаться объяснить это в математических терминах, вместо этого я представлю элегантную лингвистическую аналогию в стиле философа У. В. О. Куайна, которая доносит суть.
Фокус Гёделя «слон в спичечном коробке» через аналогию Куайна
Предположим, вы захотели написать предложение, которое говорит о себе, не используя словосочетание «это предложение». Возможно, вы найдете эту задачку довольно затейливой, поскольку вам придется буквально описать предложение внутри его самого, цитируя слова и словосочетания. Например, рассмотрим вот такую первую (довольно жалкую) попытку:
В предложении «В этом предложении пять слов» пять слов.
То, что я только что написал (а вы только что прочитали), является верным высказыванием, только, увы, оно не говорит о себе. В итоге все целиком содержит девять слов, а также немного кавычек. Это предложение говорит о более коротком предложении, включенном в него при помощи кавычек. Замена «пяти» на «девять» тоже не поможет ему обратиться к себе; это простое действие лишь превратит мое истинное высказывание в ложное. Вот взгляните:
В предложении «В этом предложении девять слов» девять слов.
Это высказывание ложно. И что более важно, оно все еще говорит лишь о более коротком предложении, заключенном внутри его. Как видите, пока мы не особо приблизились к тому, чтобы разработать предложение, говорящее о себе самом.
Что бы я ни заключил в кавычки, проблема в том, что оно все равно будет короче, чем целое предложение, частью которого оно является. Это совершенно очевидно, и, по сути, это полный лингвистический аналог нашего камня преткновения – попыток засунуть в формулу ее собственное число Гёделя. Слон не влезет в коробок! С другой стороны, ДНК слона с легкостью в него влезет…
В самом деле, раз ДНК является описанием слона, а не самим слоном, значит, возможно обойти препятствие, используя описание огромного числа, а не само необъятное число. (Точнее говоря, мы можем использовать емкое символьное описание вместо необъятного численного.) Гёдель обнаружил этот фокус, и хотя он довольно хитрый, аналогия Куайна позволяет достаточно легко его понять. Взгляните на следующий фрагмент предложения, который я называю «Квазитайна Куайна»:
поставленное впереди себя самого в кавычках, образует целое предложение.
Как вы можете заметить, Квазитайна Куайна совершенно точно не является полным предложением, поскольку в нем нет грамматического подлежащего (к которому относилось бы сказуемое «образует»); вот почему я поставил префикс «квази». Но что, если мы поместим перед Квазитайной существительное – скажем, «профессор Куайн»? Тогда Квазитайна Куайна превратится в полное предложение, которое я назову «Тайна Куайна»:
«Профессор Куайн», поставленное впереди себя самого в кавычках, образует полное предложение.
Здесь глагол «образует» имеет подлежащее – а именно, научное звание профессора Куайна, дополненное последующим причастным оборотом из шести слов.
Но что означает эта Тайна Куайна? Чтобы разобраться в этом, нам следует буквально построить сущность, о которой она говорит, то есть поставить перед научным званием профессора Куайна его же, только в кавычках. Получится так:
«профессор Куайн» профессор Куайн.
Тайна Куайна, которую мы создали мгновение назад, всего лишь утверждает (или, скорее, заявляет), что полным предложением является вот такая глупость. Что ж, это заявление, очевидно, ложно. Вышеуказанная фраза не является полным предложением; она даже не содержит глагола.
Впрочем, мы произвольно выбрали научное звание профессора Куайна, тогда как могли выбрать миллион других вещей. Есть ли какое-то другое существительное, которое мы могли бы поставить впереди Квазитайны Куайна, чтобы Тайна Куайна оказалась истинной? Аналогия Куайна помогает понять то, что осознал Гёдель, – чтобы это произошло, в качестве подлежащего при глаголе «образует» необходимо использовать фрагмент предложения без подлежащего.
Каким, например, может быть фрагмент предложения без подлежащего? Что ж, просто возьмите любое привычное предложение вроде «Снег белого цвета» и отрежьте у него подлежащее. Вы получите фрагмент предложения без подлежащего: «белого цвета». Итак, давайте используем это в качестве существительного, чье место перед Квазитайной Куайна:
«белого цвета», поставленное впереди себя самого в кавычках, образует полное предложение.
Эта труднопроизносимая фраза средней длины делает заявление о конструкции, которую нам еще только предстоит обнаружить, так сделаем же это без промедления:
«белого цвета» белого цвета.
(Для убедительности я добавил точку, но давайте не будем придираться.)
То, что мы создали только что, определенно является полным предложением, поскольку там есть сказуемое («белого цвета»), и при нем есть подлежащее (фраза в кавычках), и все это в целом имеет смысл. Заметьте, я не говорю, что это верно, поскольку это, конечно, наглая ложь: «белого цвета» на самом деле черного цвета (хотя, если на то пошло, наряду с черной краской между буквами и словами есть некоторое белое пространство, иначе мы не смогли бы их прочитать). В любом случае Квазитайна Куайна, которой на входе скормили «белого цвета», составила полное предложение, и это именно то, что заявляла Тайна Куайна. Мы определенно продвигаемся вперед.
Самый хитрый шаг
Нашим последним дьявольским трюком будет использование самой Квазитайны Куайна в качестве отправного существительного. Перед вами Квазитайна Куайна, в начало которой установлена ее собственная копия в кавычках:
«поставленное впереди себя самого в кавычках, образует полное предложение», поставленное впереди себя самого в кавычках, образует полное предложение.
Какое заявление делает эта Тайна? Что ж, для начала нам нужно определить, о какой сущности она говорит, а это означает, что нам надо соорудить аналог «“белого цвета” белого цвета». Что ж, в данном случае аналог выглядит так:
«поставленное впереди себя самого в кавычках, образует полное предложение», поставленное впереди себя самого в кавычках, образует полное предложение.
Надеюсь, вы еще не потеряли нить, поскольку нам очень нужно докопаться до сути дела. Получается, Тайна Куайна говорит о предложении, которое идентично самой Тайне! Она заявляет, что нечто является полным предложением, и когда вы принимаетесь составлять это предложение, оно оказывается самой Тайной Куайна. Итак, Тайна Куайна говорит о себе самой, заявляя, что она сама является полным предложением (каковым она, безусловно, является, несмотря на то что построена она из двух фрагментов предложений без подлежащего, один из которых взят в кавычки, а другой нет).
Пока вы размышляете об этом, я вернусь к тому, с чего все началось – то есть к ПМ-формуле Гёделя, которая говорит о самой себе. Суть в том, что числа Гёделя совершенно аналогичны фразам в кавычках, поскольку они могут как служить именем формулы, так и быть вставленными в формулу. А мы только что увидели, что есть способ использовать кавычки и фрагменты предложений, чтобы создать полное предложение, которое говорит о себе (или, если угодно, предложение, которое говорит о другом предложении, которое является его клоном, поэтому что верно для одного, то верно и для другого).
Аналогичным образом Гёдель создал «фрагмент формулы без подлежащего» (я имею в виду формулу ПМ, которая касается не какого-то конкретного целого числа, а некоего неопределенного переменного числа x). А затем, проделав шаг, аналогичный подстановке Квазитайны Куайна в саму себя (только в кавычках), он взял число Гёделя k для этого фрагмента формулы (которое является конкретным числом, не переменной) и заменил им переменную x, получив таким образом формулу (а не ее фрагмент), которая делает заявление о значительно большем целом числе, g. А g – число Гёделя для этого самого заявления. И, наконец, это заявление было не о том, является ли подлежащая рассмотрению сущность полным предложением, а о том, является ли подлежащая рассмотрению сущность доказуемой формулой.
Слон в спичечном коробке – ни рыба ни мясо
Я знаю, тут больше, чем можно проглотить за один раз, так что если вам понадобится несколько глотков (внимательных прочтений), пожалуйста, не отчаивайтесь. Я знаю нескольких весьма просвещенных математиков, которые признают, что никогда до конца не понимали эти рассуждения!
Я думаю, на этом моменте будет полезно привести этакое смешанное предложение, которое передает дух самореферентной конструкции Гёделя, но делает это в терминах Куайна – то есть использует идеи, которые мы обсудили только что. Смешанное предложение выглядит так:
«если подать в нее ее собственное число Гёделя, выдаст не принципиальное число»,
если подать в нее ее собственное число Гёделя, выдаст не принципиальное число.
Предложение выше – ни рыба ни мясо, поскольку это не формула из «Принципов математики», а предложение на русском языке, так что у него, конечно, нет числа Гёделя и оно никак не может быть теоремой (или не-теоремой) ПМ. Какая сложная метафора!
И все же, какой бы сложной эта метафора ни была, она добросовестно выполняет свою задачу передать дух формулы ПМ, которую Гёдель создал на самом деле. Вам лишь нужно держать в уме, что использование кавычек – это метафора для вычисления числа Гёделя (k), а не фрагмент предложения в кавычках. Это означает, что метафорически в нижнюю строку (фрагмент предложения на русском) было подано ее собственное число Гёделя в качестве подлежащего. Очень мило!
Я знаю, что это все очень затейливо, так что позвольте рассказать еще раз, слегка на другой лад. Гёдель просит вас представить формулу, которую обозначает k (эта формула содержит переменную x), а затем подать в нее k (то есть заменить одну букву x на чрезвычайно длинное число k и так получить куда более длинную формулу, чем та, с которой вы начинали) и вычислить число Гёделя для результата. Это будет число g, большее, чем k, – и, наконец, Гёдель утверждает, что это выдающееся число не будет принципиальным. Если вы следили за движением моих рук в этом рассуждении, вы согласитесь, что число Гёделя для полной формулы (g) не находится явным образом внутри формулы, но очень изящно описано этой формулой. Мы использовали ДНК слона, чтобы сложить описание целого слона в спичечный коробок.
Слагго и девушка из «Мортон Солт»
Что же, я не хочу вдаваться в технические подробности. Главное – запомнить, что Гёдель разработал очень искусный трюк с описанием чисел – рецепт по изготовлению огромного числа g из не такого огромного числа k – с целью заставить формулу ПМ сделать заявление о непринципиальности своего собственного числа Гёделя (а это означает, что формула на самом деле делает заявление о собственной «не-теоремности»). А также вы можете попробовать запомнить, что «маленькое» число k – это число Гёделя для «фрагмента формулы», содержащей переменную x, по аналогии с фрагментом предложения без подлежащего, взятым в кавычки, в то время как большее число g – это число Гёделя для полного высказывания в нотации ПМ, по аналогии с полным предложением на русском языке.
У поп-культуры вовсе нет иммунитета к прелестям самореференции, и случилось так, что две противопоставленные друг другу идеи – о формуле, содержащей ее собственное число Гёделя напрямую (что неизбежно повлечет бесконечное повторение), и о формуле, содержащей описание своего числа Гёделя (что изящно обходит бесконечное повторение), – можно проиллюстрировать двумя очаровательными картинками, которые многим читателям могут быть знакомы.
На первой картинке Слагго, персонаж Эрни Бушмиллера (из классического стрипа «Нэнси»), мечтает о себе, мечтающем о себе, мечтающем о себе, и так без конца. Это, очевидно, самореферентный случай, но он подразумевает бесконечное повторение, аналогичное формуле ПМ, содержащей свое собственное число Гёделя напрямую. Такая формула, к сожалению, должна была бы быть бесконечно длинной!
На второй картинке, напротив, знаменитая этикетка с банки соли «Мортон Солт» с изображением девушки, которая держит банку «Мортон Солт». Вы можете решить, что снова учуяли бесконечное повторение, но, если так, вы обманулись! Рука девушки закрывает то самое место, на котором возникло бы повторение. Если бы вы попросили девушку (пожалуйста) передать ее банку, чтобы вы все же увидели бесконечное повторение на этикетке, вас бы постигло разочарование, поскольку этикетка на этой банке изображала бы девушку, держащую еще меньшую банку, и ее рука все так же закрывала бы повтор.
И все же перед нами самореферентная картинка, поскольку покупатели в магазине поймут, что маленькая банка на этикетке точно такая же, как большая банка, которую они держат сами. Как они приходят к этому заключению? По аналогии. Если точнее, мало того, что они держат в руках большую банку, они также могут видеть маленькую банку, которую держит девушка, а у этих двух банок очень много общего (цилиндрическая форма, темно-синий цвет, белые донышки с обеих сторон); в случае, если этого недостаточно, они могут видеть соль, которая сыпется из маленькой банки. Этих улик достаточно, чтобы всех убедить в том, что маленькая и большая банки идентичны, и вот она: самореференция без бесконечных повторений!
В заключение этой главы я хочу особенно обратить внимание на то, что в самых емких переводах на русский язык формулы Гёделя и ее ближайших родственников употребляется слово «Я» («Я недоказуема в ПМ», «Я не теорема ПМ»). Это не совпадение. В самом деле, это неформальное, с виду почти небрежное использование личного местоимения первого лица единственного числа позволяет нам уловить первые намеки на глубокую связь между строгой математической странной петлей Гёделя и очень человеческим представлением об осознанной личности.