ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда - Хофштадтер Даглас Р. - Страница 141

141

~Ea:Ea':

.                       |___|

.                       d «S» 

Именно это и есть Гёделева строчка, которую мы называем «G». Теперь у нас возникают два вопроса, на которые необходимо ответить без промедления. Вот они:

(1) Каков Гёделев номер G?

(2) Какова интерпретация G?

Сначала ответим на первый вопрос. Как мы получили G? Мы начали с дяди и арифмоквайнировали его, так что, по определению арифмоквайнирования, Гёделев номер G — это:

арифмоквайнификация d.

Теперь второй вопрос. Постараемся перевести G на русский постепенно, шаг за шагом проясняя значение этой строчки. Нашей первой попыткой будет дословный перевод:

«Не существует чисел а и а' таких, что они оба:

(1) составляют пару доказательства ТТЧ и

(2) а' является арифмоквайнификацией d».

Мы знаем, однако, что существует число а', являющееся арифмоквайнификацией d. Следовательно, дело в другом числе, в а. Это позволяет нам перефразировать наш перевод:

«Не существует такого числа а, которое составляло бы пару доказательства ТТЧ с арифмоквайнификацией d»

(Этот шаг может быть немного сложным для понимания; ниже мы остановимся на нем подробнее.) Видите ли вы, что происходит? G утверждает, что:

«Формула, чей Гёделев номер — арифмоквайнификация d, не является теоремой ТТЧ».

Но — и это уже не должно нас удивлять — эта формула не что иное, как сама строчка G! Следовательно, нашим окончательным переводом будет:

«G — не теорема ТТЧ»;

или, если вам так больше нравится —

«Я — не теорема ТТЧ».

Начав с интерпретации на низшем уровне — суждения теории чисел, мы постепенно дошли до интерпретации на высшем уровне — суждения мета-ТТЧ.

ТТЧ выбрасывает полотенце

В главе IX мы уже упоминали о главном следствии этого удивительного построения: это неполнота ТТЧ. Давайте вспомним, как мы при этом рассуждали:

Является ли G теоремой ТТЧ? Если это так, то она должна утверждать истинный факт. Но что именно утверждает G? Свою собственную нетеоремность. Следовательно, из ее теоремности вытекала бы ее нетеоремность. Противоречие!

С другой стороны, что, если G не теорема? Это можно принять, так как противоречия здесь не возникает. Но G утверждает именно собственную нетеоремность — следовательно, G утверждает истинный факт. Значит, поскольку G не теорема, мы можем заключить, что существует по меньшей мере один истинный факт, не являющийся теоремой ТТЧ.

Теперь — обещанное объяснение сложного шага нашего перевода. Я воспользуюсь для этого похожим примером. Возьмем строчку

~Eа:Eа':

где оба сокращения обозначают строчки ТТЧ, которые вы можете дописать сами. ДЕСЯТАЯ СТЕПЕНЬ{а'',а'} представляет высказывание «а' равняется а'' в десятой степени». Таким образом, дословный перевод на русский получается такой:

«Не существует чисел а и а' таких, что они (1) составляют Черепашью пару, и (2) а' — 2 в десятой степени».

Но мы знаем, что десятая степень 2 существует — это 1024. Таким образом, эта строчка на самом деле утверждает, что:

«Не существует числа а, которое составляет Черепашью пару с числом 1024».

Это высказывание, в свою очередь, сводится к:

«1024 не обладает Черепашьим свойством».

Нам удалось заменить символ числа на его описание. Это было возможно, благодаря использованию дополнительной квалифицированной переменной (а' ), В данном случае, число 1024 было описано как «десятая степень двух»— выше это было числом, описанным как «арифмоквайнификация d».

«Будучи арифмоквайнированным, производит нетеоремность!»

Переведем дыхание и посмотрим, что мы сделали до сих пор. Для этого сравним арифмоквайнирование с парадоксом Эпименида. Вот схема этого соответствия:

ложность нетеоремность

цитата фразы Геделев номер строки

предварение предиката цитатой фразы подстановка символа (или определенного терма) в открытую формулу

предварение предиката цитатой фразы подстановка Гёделева номера строчки в открытую формулу

предварение предиката им самим в кавычках (квайнирование) Подстановка Гёделева номера открытой формулы в саму эту формулу (арифмоквайнирование)

После квайнирования производит ложное высказывание (предикат без подлежащего) «дядя» G (открытая формула ТТЧ)

«После квайнирования производит ложное высказывание» (тот же предикат, квайнированныи) номер d (Гёделев номер предыдущей открытой формулы)

«После квайнирования производит ложное высказывание» После квайнирования производит ложное высказывание строчка G (высказывание ТТЧ, полученное путем подстановки d в «дядю», то есть, путем его арифмоквайнирования)

Вторая теорема Гёделя

Поскольку интерпретация G истинна, интерпретация ее отрицания ~G — ложна. Мы знаем, что в ТТЧ невозможно вывести ложные утверждения. Следовательно. ни G, ни ее отрицание ~G не могут быть теоремами ТТЧ. Мы нашли в нашей системе «дыру» — неразрешимое суждение. Из этого следуют несколько фактов. Вот один из них, довольно любопытный: несмотря на то, что ни G, ни ее отрицание ~G не являются теоремами ТТЧ, формула — теорема, поскольку из правил исчисления высказываний следует, что все правильно построенные формулы типа

V ~P> - теоремы.

Это — простой пример того случая, когда утверждение внутри системы и утверждение о системе противоречат друг другу. Возникает вопрос: действительно ли система верно отражает саму себя? Соответствует ли «отраженная метаматематика», существующая внутри ТТЧ, «обыкновенной», повседневной математики? Это было одним из вопросов, интересовавших Гёделя, когда он писал свою статью. В частности, он был заинтересован в том, возможно ли доказать в «отраженной метаматематике» непротиворечивость ТТЧ. Вспомните, что доказательство непротиворечивости систем было важным философским вопросом того времени. Гёдель нашел простой способ выразить высказывание «ТТЧ непротиворечива» в виде формулы ТТЧ; после чего он показал, что эта формула (как и все другие формулы, выражающие похожую идею) является теоремой ТТЧ только при одном условии: если ТТЧ противоречива. Этот еретический результат был тяжелым ударом для оптимистов, считавшим, что возможно найти строгое доказательство непротиворечивости математики.

Как можно выразить высказывание «ТТЧ непротиворечива» в самой ТТЧ? Опираясь на простой факт: противоречивость означает, что две формулы, x и ~x, одна из которых — отрицание другой, одновременно являются теоремами. Но если они обе — теоремы, тогда, согласно исчислению высказываний, все правильно сформированные формулы — теоремы. Таким образом, чтобы доказать непротиворечивость ТТЧ, достаточно доказать нетеоремность единственного высказывания ТТЧ. Следовательно, один возможный способ выразить непротиворечивость ТТЧ - это высказывание типа «формула ~0=0 не является теоремой ТТЧ». Такое высказывание уже было предложено в качестве упражнения несколькими страницами ранее. Вот что у нас должно получиться:

~Eа:ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{а,SSSSS…SSSSSO/a'}

.                                                     |_________|

.                                                  «S» 223666111666 раз

Путем длинных, но несложных рассуждений можно доказать, что пока ТТЧ остается непротиворечивой, ее клятва в собственной непротиворечивости — не теорема. Таким образом, ТТЧ весьма сильна в выражении идей, но слабовата в их доказательстве. Это очень интересный результат, если метафорически приложить его к проблеме человеческого самосознания.