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

• Название: ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда
• Автор: Даглас Хофштадтер
• Издательство: Издательский Дом «Бахрах-М», 2001.
• Жанр: Математика
• Год: 2001
• ISBN: ISBN 5-94648-001-4

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

Выдающийся американский ученый изобретает остроумные диалоги, обращается к знаменитым парадоксам пространства и времени, находит параллели между картинами Эшера, музыкой Баха и такими разными дисциплинами, как физика, математика, логика, биология, нейрофизиология, психология и дзен-буддизм.

Автор размышляет над одной из величайших тайн современной науки: каким образом человеческое мышление пытается постичь самое себя. Хофштадтер приглашает в мир человеческого духа и «думающих» машин. Это путешествие тесно связано с классическими парадоксами, с революционными открытиями математика Курта Геделя, а также с возможностями языка, математических систем, компьютерных программ и предметного мира говорить о самих себе с помощью бесконечных отражений.

Начав читать эту книгу,вы попадете в волшебные миры, отправитесь в путешествие, изобилующее увлекательными приключениями, путешествие, после которого вы по-иному взглянете на мир и на самого себя.

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

---

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

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

~Eа:Eа':<ЧЕРЕПАШЬЯ ПАРА{а, а'}ΛДЕСЯТАЯ СТЕПЕНЬ{SS0/а'',а'}>

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

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

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

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

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

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

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

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

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

ложность <==> нетеоремность

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

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

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

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

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

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

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

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

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

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

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

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

.                                                     |_________|

.                                                  «S» 223666111666 раз

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

ТТЧ страдает ω-неполнотой

От какой именно разновидности неполноты «страдает» ТТЧ? Мы вскоре увидим, что речь идет о неполноте типа «омега», определенной в главе VIII. Это означает, что существует некая бесконечная пирамидальная семья строчек, каждая из которых является теоремой — но при этом соответствующая «итоговая» строчка теоремой не является. Эту итоговую не-теорему найти нетрудно:

~Aа:~Eа':<ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{а,а'}

ΛARITHMOQUINE{SS… SSSO/a'',a'}>

.                       |_____|

.                     «S» d раз

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

~Eа':<ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{O/а,а}ΛARITHMOQUINE{SSS…SSSO/а",а}>

~Eа':<ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{SO/а,а}ΛARITHMOQUINE{SSS…SSSO/а",а}>

~Eа':<ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{SSO/а,а}ΛARITHMOQUINE{SSS…SSSO/а",а}>

~Eа':<ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{SSSO/а,а}ΛARITHMOQUINE{SSS…SSSO/а",а}>

*   *

*   *

*   *

Что утверждает каждая из этих строчек? Вот их соответствующие переводы.

«0 и арифмоквайнификация d — не пара доказательства ТТЧ».

«1 и арифмоквайнификация d — не пара доказательства ТТЧ».

«2 и арифмоквайнификация d — не пара доказательства ТТЧ».

«3 и арифмоквайнификация d — не пара доказательства ТТЧ».

«4 и арифмоквайнификация d — не пара доказательства ТТЧ».

*   *

*   *

*   *

Каждое из этих утверждений говорит о том, формируют ли два определенных числа пару доказательства, или нет. (С другой стороны, G говорит о том, является ли одно определенное число. числом-теоремой, или нет.) Поскольку G — не теорема, не существует такого числа, которое составляло бы пару доказательства с Гёделевым номером G. Таким образом, каждое из утверждений пирамидальной семьи истинно. Основная идея в том, что свойство являться парой доказательств примитивно рекурсивно и, следовательно, представимо — поэтому каждое из утверждений выше должно быть переводимо в теорему ТТЧ, что означает, что все утверждения в нашей бесконечной пирамидальной семье — теоремы. И это показывает, почему ТТЧ ω-неполна.

Два разных способа заткнуть дыру

Поскольку интерпретация G истинна, интерпретация ее отрицания ~G ложна. Из нашего предположения о непротиворечивости ТТЧ следует, что в ней не могут быть выведены ложные утверждения.

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