Следующее предложение ложно

Название этого раздела истинно.

Именно из рекурсивных утверждений, подобных тому, которое я нашел в своей хлопушке на прошлое Рождество, Гёдель вывел свое обескураживающее доказательство ограниченности математики.

Хотя утверждения, сформулированные на естественном языке, могут порождать парадоксы, мы привыкли ожидать, что утверждение, сделанное о числах, может быть либо истинным, либо ложным. Гёделя заинтересовал вопрос о возможности использования рекурсивности в математических утверждениях. Поставленная Гильбертом задача уже содержала встроенный рекурсивный элемент: он хотел построить математически неопровержимое рассуждение, доказывающее, что математика не содержит противоречий. Эта задача уже требует рассмотрения математикой самой себя в поисках доказательства того, что в ней не могут внезапно появиться доказательства истинности двух взаимоисключающих утверждений.

Гёдель хотел показать, что в рамках любой системы аксиом теории чисел всегда будут существовать истинные утверждения о числах, которые невозможно доказать на основе этих аксиом. Стоит отметить, что можно попытаться определить, как работают эти числа, установив другую систему аксиом. Гильберт надеялся, что математики сумеют построить единую аксиоматическую систему, исходя из которой можно было бы доказать все математические истины.

Гёделю удалось разрушить эту надежду. Фокус, который использовал Гёдель, заключался в следующем: он разработал код, в рамках которого каждому осмысленному утверждению о числах был присвоен свой кодовый номер. Собственно, похожая идея используется в технологии, позволяющей мне печатать этот текст. Слова, которые я использую для изложения истории Гёделя, преобразуются в последовательности чисел, которые представляют те буквы, которые я печатаю. Например, в десятичном ASCII-представлении слово «Гёдель» изображается числом 195184228229235252[117]. Достоинство кодировки, придуманной Гёделем, состоит в том, что она позволила математике говорить о самой себе.

В кодировке Гёделя каждая из аксиом, которые мы выбираем для выражения теории чисел, – те утверждения, из которых мы выводим математические теоремы, – получает свой собственный кодовый номер. Например, аксиома «Если А = В и В = С, то А = С» имеет некоторый кодовый номер. Но свой собственный кодовый номер также получает и каждое из утверждений, которые можно вывести из этих аксиом, например утверждение «Существует бесконечное количество простых чисел». Даже если утверждение ложно, например «17 – четное число», ему все равно присваивается кодовый номер.

Эти кодовые номера позволили Гёделю рассуждать о доказуемости того или иного утверждения в рамках данной системы на языке теории чисел. Основная идея состояла в том, чтобы получить такую кодировку, в которой кодовый номер доказуемого утверждения обладал бы делимостью на кодовые номера соответствующих аксиом. На самом деле система была более сложной, но такое упрощение поможет нам ее понять.

Теперь Гёдель мог говорить о доказуемости или недоказуемости того или иного утверждения на основе аксиом как о некотором свойстве чисел. Положение, согласно которому «утверждение о существовании бесконечного количества простых чисел может быть доказано, исходя из аксиом теории чисел», преобразовалось в утверждение «кодовый номер утверждения о существовании бесконечного количества простых чисел делится на кодовые номера аксиом теории чисел», то есть в чисто математическое утверждение о свойствах чисел, которое может быть либо истинным, либо ложным.

Держитесь покрепче, пока мы будем преодолевать все логические изгибы и повороты доказательства Гёделя. Гёдель решил рассмотреть следующее утверждение S: «Это утверждение недоказуемо». Утверждению S присвоен некий кодовый номер. Но, если проанализировать содержание утверждения S, оно попросту сводится к утверждению о наличии или отсутствии делимости кодового номера утверждения S на кодовые номера аксиом. Предположим, что аксиоматическая система теории чисел, которую мы анализируем, не порождает противоречий, как надеялся Гильберт.

В кодировке Гёделя S становится всего лишь утверждением о свойствах чисел. Кодовый номер S либо делится на кодовые номера аксиом, либо не делится. Это утверждение должно быть либо истинным, либо ложным. Оно не может одновременно быть и истинным, и ложным, так как это противоречило бы нашему предположению об отсутствии противоречий в данной системе.

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

Чтобы выйти из этого тупика, следует понять, что наше исходное предположение было ложным: мы не можем доказать истинность утверждения S, исходя из аксиом теории чисел. Но именно это и утверждает S. То есть утверждение S истинно. Мы доказали, что предложенное Гёделем утверждение S – истинное утверждение, недоказуемое с использованием этих аксиом.

Это доказательство может напомнить вам, как мы доказали, что квадратный корень из 2 есть иррациональное число. Сначала предположим, что это не так. Это предположение приводит к противоречию. Значит, корень из двух все же должен быть иррациональным. Доказательство обоих результатов основано на том важном допущении, что аксиомы теории чисел не порождают противоречий. Одно из наиболее интересных следствий из доказательства Гёделя состоит в том, что математику нельзя спасти, введя в нее одно из таких недоказуемых утверждений в качестве аксиомы. Можно подумать, что, раз утверждение S истинно, но недоказуемо, почему бы не принять его за аксиому – и тогда, может быть, все истинные утверждения окажутся доказуемыми? Доказательство Гёделя демонстрирует, что, сколько бы новых аксиом мы ни вводили в систему, в ней всегда останутся недоказуемые истинные утверждения.

Если вы чувствуете легкое головокружение от того логического танца, в который увлек нас Гёдель, не волнуйтесь. Хотя я изучал эту теорему много раз, к концу доказательства у меня всегда несколько кружится голова – настолько поразительны его следствия. Гёдель представил математическое доказательство того, что в любой непротиворечивой аксиоматической системе теории чисел существуют истинные утверждения о свойствах чисел, справедливость которых невозможно доказать в рамках данной системы, – математическое доказательство ограниченности математики. Интересно отметить, что непознаваемо тут не само утверждение S. Собственно говоря, мы доказали его истинность. Дело в том, что для этого нам пришлось выйти за пределы данной конкретной аксиоматической системы математики, и тем самым мы продемонстрировали ее ограниченность. Именно это и продемонстрировал Гёдель – что истинность этого утверждения не может быть доказана в рамках данной системы.

Это уже достаточно обескураживающее открытие Гёделя, известное под названием первой теоремы Гёделя о неполноте, уничтожило надежду Гильберта на математическое доказательство отсутствия в математике противоречий. Гёдель доказал, что утверждение «Это утверждение недоказуемо» истинно в предположении о том, что математика не содержит противоречий. Если отсутствие противоречий можно доказать математически, то это обстоятельство можно использовать для доказательства в рамках такой математики, что утверждение «Это утверждение недоказуемо» истинно. Но при этом как раз и возникает противоречие, поскольку само это утверждение утверждает, что оно недоказуемо. Поэтому любое доказательство отсутствия в математике противоречий неизбежно приводит к противоречию. Мы снова вернулись к нашим рекурсивным утверждениям. Единственный выход из этой ситуации заключается в признании невозможности математического доказательства того, что математика лишена противоречий. В этом состоит вторая теорема Гёделя о неполноте. К ужасу Гильберта, она обнаружила «ignorabimus» в самом сердце математики.

Однако математики считают, что математика не содержит противоречий. Если бы в ней были противоречия, как бы мы смогли зайти так далеко без обрушения всего ее здания? Мы называем теорию, не содержащую противоречий, непротиворечивой. Французский математик Андре Вейль сформулировал потрясающие последствия достижений Гёделя следующим образом: «Бог существует, поскольку математика непротиворечива, а дьявол существует, поскольку мы не можем этого доказать».

Значат ли открытия Гёделя, что математика может быть опровергнута так же, как и любая другая научная теория? Возможно, мы случайно обнаружили правильную модель, но, как и в случае моделей Вселенной или элементарных частиц, мы не можем быть уверены, что в один прекрасный момент она не развалится на кусочки под весом новых данных.

Некоторые философы находили нечто привлекательное в том факте, что, хотя мы не можем доказать истинность утверждения S Гёделя в рамках аксиоматической системы теории чисел, мы по меньшей мере смогли доказать, что оно истинно, выйдя за пределы этой системы. Казалось, что из этого следует, что человеческий мозг – нечто большее, чем механизированная вычислительная машина для математического анализа мира. В 1959 г. философ Джон Лукас выступил в Оксфордском философском обществе с докладом под названием «Разум, машина и Гёдель», в котором он утверждал, что если мы построим модель разума в виде машины, следующей аксиомам и логическим правилам арифметики, то такая машина, разрабатывая доказательства, в какой-то момент наткнется на фразу «Это утверждение недоказуемо» и будет до скончания времен пытаться доказать или опровергнуть это утверждение. В то же время человек может увидеть, что оно неразрешимо, поняв его смысл. «Таким образом, машина все еще не будет адекватной моделью разума. […] разум, будучи “живым”, может всегда пойти на шаг дальше любой формализованной, окостеневшей, мертвой системы»[118].

Это рассуждение выглядело очень привлекательно. Кто не хотел бы верить, что мы, люди, – нечто большее, чем простые вычислительные системы, чем приложения, установленные в неких биологических устройствах? Роджер Пенроуз использовал рассуждение Лукаса в своем недавнем исследовании сознания в качестве основы для своего убеждения в том, что для понимания того, что делает разум сознательным, нам необходима новая физика. Но, хотя мы действительно подтверждаем истинность утверждения «Это утверждение недоказуемо» путем выхода за пределы системы, это также требует большого допущения, а именно, что система, в рамках которой мы пытаемся доказать истинность этого утверждения Гёделя, сама не содержит противоречий. А суть второй теоремы Гёделя о неполноте состоит в том, что мы не можем этого доказать.

Утверждения, подобные созданным Гёделем, истинные, но недоказуемые, могут показаться с математической точки зрения несколько эзотерическими. Не может же быть так, чтобы действительно интересные утверждения о свойствах чисел – гипотеза Римана, гипотеза Гольдбаха, гипотеза PORC – были недоказуемы? Надежда на то, что доказательству не подлежат лишь хитроумные утверждения Гёделя, оказалась ложной. В 1977 г. математики Джефф Пэрис и Лео Харрингтон предъявили вполне настоящее математическое утверждение о свойствах чисел и сумели показать, что оно истинно, но недоказуемо в рамках классической аксиоматики теории чисел. Но в следующей части этой главы мы увидим, что, пытаясь справиться с идеей бесконечности, математики открыли не только недоказуемость некоторых утверждений, но и невозможность определить, истинны они или ложны.