ГЛАВА XIV: О формально неразрешимых суждениях ТТЧ и родственных систем
Две идеи «устрицы»
НАЗВАНИЕ ЭТОЙ ГЛАВЫ — адаптация заглавия знаменитой статьи Гёделя, опубликованной в 1931 году; я заменил «Principia mathematica» на ТТЧ. Гёдель написал эту статью строго техническим языком, стараясь дать безупречное доказательство своей теоремы; в этой главе я постараюсь изложить его идеи более интуитивно. Сосредоточусь на двух идеях, лежащих в основе Гёделева доказательства. Первая идея — это открытие того факта, что некоторые строчки ТТЧ могут быть интерпретированы как суждения о других строчках ТТЧ; иными словами, ТТЧ оказалась языком, способным к самоанализу. Этот факт вытекает из Гёделевой нумерации. Вторая идея — это то, что данное свойство может быть сконцентрировано полностью в одной строке: в фокусе такой строки — она сама. Этот прием восходит, в принципе, к диагональному методу Кантора.
По моему мнению, всякий, кто желает достичь глубокого понимания Гёделева доказательства, должен признать, что в его основе лежит слияние этих двух идей. Каждая из них по отдельности уже является шедевром, но чтобы соединить их, потребовался гений. Однако если бы мне предложили выбрать, какая из двух идей важнее, я, безусловно, указал бы на первую — Гёделеву нумерацию, поскольку эта идея приложима к понятию значения и упоминания во всех системах, имеющих дело с символами. Эта идея выходит далеко за пределы математической логики, в то время как Канторов прием, как бы значим он ни был для математиков, почти не связан с реальной жизнью.
Первая идея: пары доказательства
Не откладывая дела в долгий ящик, приступим к рассмотрению самого доказательства. В IX главе мы уже объяснили довольно подробно идею Гёделева изоморфизма. Здесь мы постараемся описать математическое понятие, позволяющее нам перевести предложение типа «Строчка 0=0 — теорема ТТЧ» в высказывание теории чисел. Для этого мы воспользуемся парами доказательства. Пара доказательства — это пара натуральных чисел, соотносящихся между собой таким образом:
Два натуральных числа m и n (в данном порядке) являются парой доказательства в ТТЧ тогда и только тогда, если m — Гёделев номер такой деривации ТТЧ, последняя строчка которой имеет Гёделев номер n.
Аналогичное понятие существует и для системы MIU; пожалуй, интуитивно легче понять именно этот случай. Так что давайте на минуту оставим пары доказательства ТТЧ и обратимся к парам доказательства в системе MIU. Их определение почти такое же:
Два натуральных числа m и n (в данном порядке) являются парой доказательства в MIU тогда и только тогда, если m — Гёделев номер такой деривации MIU, последняя строчка которой имеет Гёделев номер n.
Давайте рассмотрим несколько примеров пар доказательства в системе MIU. Пусть m — 3131131111301, n = 301. Эти значения тип составляют пару доказательства, поскольку m — Гёделев номер следующей деривации MIU:
MI
MII
MIIII
MUI
где последняя строчка — MUI — имеет Гёделев номер 301, то есть n.
С другой стороны, при m = 31311311130, и n = 30 пары доказательства не получается. Чтобы понять, почему, рассмотрим деривацию, кодом которой должно было бы являться m:
MI
MII
MIII
MU
В этой предположительной деривации есть неверный шаг. Это — переход от второй к третьей строке: от MII к MIII. В системе MIU нет правила, которое позволяло бы подобный типографский шаг. Соответственно — и это очень важно — нет такого арифметического шага, который позволил бы вам перейти от 311 к 3111. Возможно, что, после того как вы прочли главу IX, это покажется вам тривиальным, но именно подобные наблюдения лежат в основе Гёделева изоморфизма. Все, что мы делаем в формальных системах, имеет свою параллель в арифметических действиях.
Так или иначе, величины m = 31311311130, и n = 30, безусловно, не являются парой доказательства MIU. Само по себе, это еще не означает, что 30 — не номер MIU. Могло бы найтись другое число, составляющее пару доказательства с 30. (На самом деле, мы уже выяснили ранее, что 30 — не теорема MIU. Следовательно, ни одно число не может составлять пару доказательства с 30.)
А как насчет пар доказательства в ТТЧ? Я приведу вам два параллельных примера, лишь один из которых является действительной парой доказательства. Можете ли вы определить, какой именно? (Кстати, именно здесь появляется кодон «611», функция которого — отделять Гёделевы номера последующих строк в деривации ТТЧ. В этом смысле, «611» служит в качестве знака препинания. В системе MIU эту роль выполняет начальное «3» каждой строки; там не нужна никакая дополнительная пунктуация.)
1) m = 626,262,636,223,123.262,111,666,611,223,123,666,111,666
n = 123,666,111,666
(2) m = 626,262,636,223,123,262,111.666,611,223.333,262,636123,262,111,666
n = 223,333,262,636,123.262,111,666
Легко обнаружить, какая из этих дериваций настоящая, переведя их в традиционную нотацию и произведя стандартный анализ. При этом выясняется:
(1) является ли предполагаемая деривация, кодом которой является m, «законной»;
(2) если это так, то совпадает ли последняя строка деривации со строчкой, кодом которой является n.
Шаг (2) тривиален; шаг (1) тоже довольно прямолинеен, поскольку для него не нужен бесконечный поиск и в нем не спрятаны никакие петли. Вспомните примеры из системы MIU и просто мысленно замените правила MIU и ее аксиому на правила и аксиомы ТГЧ. В обоих случаях алгоритм один и тот же:
Следить за деривацией, переходя от строчки к строчке.
Отмечать строчки, являющиеся аксиомами.
Для каждой строчки, НЕ являющейся аксиомой, проверять, следует ли она из предыдущих строчек предполагаемой деривации.
Если все не-аксиомы следуют по правилам вывода из предыдущих строчек, значит, перед вами — законная деривация; в противном случае, перед вами — фальшивка.
На каждой ступени здесь совершается ограниченное число вполне определенных действий.
Свойство «пара-доказательности» примитивно рекурсивно …
Я делаю такой упор на ограниченность петель потому, что, как вы могли догадаться, я собираюсь доказать
ОСНОВНОЙ ФАКТ 1: Свойство пара-доказательности — это примитивно рекурсивное свойство теории чисел; следовательно, оно может быть проверено на программе Блупа.
Необходимо отличать это свойство от его близкого теоретико-численного родственника: свойства числа-теоремы. Если мы говорим, что n — число-теорема, мы имеем в виду. что существует некое число m, такое, что оно составляет с n пару доказательства. (Кстати, это приложимо как к ТТЧ, так и к системе MIU; пожалуй, полезно иметь в виду обе системы, пользуясь MIU как прототипом.) Чтобы проверить, является ли n числом-теоремой, вам придется проверить всех потенциальных пара-доказательных «партнеров» m — и именно тут вы вполне можете запутаться в бесконечной петле. Невозможно определить, сколько вам придется искать, пока вы наткнетесь на число, составляющее пару доказательства с n. Эта проблема возникает во всех системах, сочетающих удлиняющие и укорачивающие правила; подобная комбинация сообщает системе некоторую непредсказуемость.
Нам может пригодиться сейчас пример Вариации Гольдбаха. Проверить является ли пара чисел (m, n) Черепашьей парой нетрудно; это значит, что как m так и n+m должны быть простыми числами. Эта проверка несложна, потому что свойство простоты — примитивно рекурсивно, то есть может быть обнаружено при помощи конечного теста. Но если мы хотим узнать, обладает ли n свойством Черепахи, тогда нам нужно ответить на вопрос «существует ли некое число m, формирующее вместе с n Черепашью пару?» Это снова уводит нас в область неведомого, в страну бесконечной MU-петельности.
… и, следовательно, представлено в ТТЧ
Таким образом, из Основного Факта 1 мы можем вывести
ОСНОВНОЙ ФАКТ 2: Свойство формировать пару доказательства может быть проверено на Блупе — следовательно, оно представлено в ТТЧ некоей формулой с двумя свободными переменными.
Как и ранее, мы не упоминаем точно, к какой именно системе относятся данные пары доказательств; оказывается, что это не столь важно, потому что оба Основных Факта действительны для любой формальной системы. Это — общее свойство формальных систем: мы всегда можем определить при помощи предсказуемо конечного теста, является ли данная последовательность строк доказательством, или нет. То же верно и для соответствующих арифметических понятий.
Мощь пар доказательства
Для конкретности предположим, что мы имеем дело с системой MIU. Вы, наверное, помните строчку, которую мы назвали МУМОН'ом. На одном из уровней эта строчка интерпретировалась как утверждение «MU — теорема системы MIU.» Можно показать, как МУМОН выражается в ТТЧ с помощью формулы, выражающей понятие пар доказательства в MIU. Давайте сократим эту формулу, в существовании которой нас уверяет Основной Факт 2, следующим образом:
ПАРА-ДОКАЗАТЕЛЬСТВА-MIU{а, а'}
Поскольку это — свойство двух чисел, оно представлено формулой с двумя свободными переменными. (В этой главе мы будем пользоваться строгой версией ТТЧ и нам надо будет различать между переменными а, а', а'' и т. д.) Чтобы сказать: «MU — теорема системы MIU», нам придется взять изоморфное высказывание «30 — число-теорема системы MIU» и перевести его в нотацию ТТЧ. Это несложно, если призвать на помощь наше условное сокращение (вспомните главу VIII, в которой, чтобы указать замену каждого а' на, символ числа, слева от этого символа мы писали «/а'»):
Eа: ПАРА-ДОКАЗАТЕЛЬСТВА-MIU{a,SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS0/a'}
Посчитайте С: их 30 штук. Заметьте, что это — закрытое высказывание ТТЧ, поскольку одна свободная переменная квантифицированна, а другая заменена на символ числа. То, что мы здесь проделали, весьма интересно. Благодаря Основному Факту 2 мы получили возможность говорить о парах доказательства: теперь мы выяснили, как мы можем говорить о числах-теоремах: для этого нужно всего лишь добавить в начале квантор существования! Более точным переводом данной выше строчки было бы «существует некое число а, которое составляет пару доказательства с 30 в качестве второго элемента».
Предположим, что мы захотели бы проделать нечто похожее в ТТЧ — например, выразить высказывание «0=0 — это теорема ТТЧ». Мы можем сократить существующую (согласно Основному Факту 2) формулу аналогичным образом (опять с двумя свободными переменными):
ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{а, а'}
(Эта сокращенная формула ТТЧ читается так: «Натуральные числа а и а' являются парой доказательства».) Следующим шагом является перевод нашего высказывания в теорию чисел, следуя модели МУМОН. Получается высказывание «существует некое число а, которое составляет пару доказательства с 666,111,666 в качестве второго элемента». Это выражается следующей формулой ТТЧ:
Ea:ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{a, SSSSS … SSSSS0/а'}
. |________|
. (Очень много S - целых 666,111.666!)
Это — закрытое высказывание ТТЧ. (Давайте назовем его Джошу — скоро узнаете, почему.) Мы убедились, что возможно говорить не только о примитивно рекурсивном понятии пар доказательства ТТЧ, но и о родственном, хотя и более сложном понятии чисел-теорем ТТЧ.
Чтобы убедиться, насколько хорошо вы поняли эти идеи, попробуйте перевести в ТТЧ следующие высказывания мета-ТТЧ:
(1) 0=0 не является теоремой ТТЧ.
(2) ~0=0 — теорема ТТЧ.
(3) ~0=0 не является теоремой ТТЧ.
Каким образом решения отличаются от примеров, данных выше, и друг от друга? Вот еще несколько упражнений на перевод:
(4) ДЖОШУ — теорема ТТЧ. (Получившуюся строчку ТТЧ назовите МЕТА-ДЖОШУ.)
(5) МЕТА-ДЖОШУ — теорема ТТЧ. (Получившуюся строчку ТТЧ назовите МЕТА-МЕТА-ДЖОШУ.)
(6) МЕТА-МЕТА-ДЖОШУ — теорема ТТЧ.
(7) МЕТА-МЕТА-МЕТА-ДЖОШУ — теорема ТТЧ.
(и т. д., и т. п.)
Пример (5) показывает, что высказывания мета-мета-ТТЧ могут быть переведены в нотацию ТТЧ; пример (6) показывает то же самое для мета-мета-мета-ТТЧ, и т. д.
Важно помнить о разнице между выражением свойства, и его представлением. Например, свойство численно-теоремности ТТЧ выражено следующей формулой:
Eа: ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ {а, а'}
Перевод: «а' — число-теорема ТТЧ». Однако у нас нет гарантии того, что эта формула действительно представляет данное понятие, поскольку у нас нет гарантии того, что это свойство примитивно рекурсивно — на самом деле, у нас есть некоторые основания полагать, что это не так! (Наши подозрения вполне обоснованы. Свойство являться числом-теоремой ТТЧ — НЕ примитивно рекурсивно, и такой формулы ТТЧ, которая могла бы его выразить, не существует!) С другой стороны, свойство являться парой доказательства, являясь примитивно рекурсивным, одновременно выразимо и представимо с помощью формулы, данной выше.
Замена подводит нас ко второй идее
Предыдущее обсуждение показало нам, как ТТЧ может «анализировать» понятие теоремности ТТЧ. Это — основа первой части доказательства. Перейдем теперь ко второй идее доказательства, путем развития понятия, позволяющего сконцентрировать этот «самоанализ» в одной единственной формуле. Для этого давайте посмотрим, что случается с Гёделевым номером какой-либо формулы, когда ее структура слегка меняется. Рассмотрим следующее изменение:
замена всех свободных переменных на определенные символы чисел.
Ниже, в левой колонке, даны два примера этой операции; в правой колонке показаны параллельные изменения в Гёделевых номерах.
Формула Геделев номер
a=a 262,111,262
теперь заменим все свободные переменные на символ числа 2
SS0=SS0 123,123,666,111,123,123,666
*******
~Ea:Ea':Ea''=(SSa*SSa') 223,333,262,636,333,262,163,636,
. 262,163,163,111,362,123,123,262,
. 236,123,123,262,163,323
теперь заменим заменим свободные переменные на символ числа 4
~Ea:Ea':SSSS0=(SSa*SSa') 223,333,262,636,333,262,163,636,
. 123,123,123,123,666,111,362,123,
. 123,262,236,123,123,262,163,323,
В правой колонке происходит изоморфный арифметический процесс, в котором один большой номер превращается в другой, еще больший номер. Функцию, которая производит этот новый номер из старого, несложно описать арифметически в терминах сложения, умножения, возведения в десятую степень и так далее — но нам это не нужно. Важно здесь то, что отношения между (1) первоначальным Гёделевым номером, (2) номером, чей символ мы вставили и (3) Гёделевым номером, при этом получающимся — это примитивно рекурсивные отношения. Это значит, что на Блупе может быть написана программа-тест, которая, если мы введем в нее эти три номера, сможет ответить ДА. если между ними существуют такие отношения, и НЕТ — в противном случае. Вы можете проверить себя на способность проводить такие тесты (и в то же время убедиться, что в этом процессе нет спрятанных открытых петель), проверив следующие два случая:
(1) 362,262,112,262,163,323,111,123,123,123,123,666;
. 2;
. 362,123,123,666,112,123,123,666,323,111,123,123,123,123,666.
(2) 223,362,262,236,262,323,111,262,163;
. 1;
. 223,362,123,666,236,123,666,323,111,262,163.
Как обычно, один из примеров проходит проверку, а другой — нет. Назовем эти отношения между тремя номерами отношениями замены. Поскольку они примитивно рекурсивны, они могут быть представлены некоей формулой ТТЧ с тремя свободными переменными. Давайте запишем эту формулу сокращенно:
ZAM{a, a', a"}
Поскольку эта формула представляет отношения замены, нижеследующая формула ТТЧ должна являться теоремой:
ZAM{SSSSS..... SSSSS0/a, SS0/a', SSSSSS..... SSSS0/a"}
. |________| |________|
. 262,111,262-«S» 123,123,666,111,123,123,666 «S»
(Это основано на первом примере отношений замены, показанном ранее в виде параллельных колонок.) С другой стороны, поскольку формула ZAM представляет собой отношения замены, формула, данная ниже, не является теоремой ТТЧ:
ZAM{SSS0/a, SS0/a', S0/a"}
Арифмоквайнирование
Пора соединить все эти части в одно гармоничное целое. Мы попробуем использовать технику ПАР-ДОКАЗАТЕЛЬСТВА-ТТЧ и формул ZAM для построения суждения ТТЧ, интерпретирующегося как «Эта строчка ТТЧ — не теорема ТТЧ». Как это возможно? Даже теперь, когда у нас есть все необходимые инструменты, ответ на этот вопрос найти нелегко.
Интересный и на вид довольно несерьезный прием состоит в подстановке в формулу ее собственного Гёделева номера. Это весьма похоже на другое, тоже легкомысленное на вид понятие «квайнирования», о котором вы прочли в «Арии в ключе G». Однако квайнирование оказалось важным, поскольку оно представляет из себя новый способ создания автореферентных суждений. Автореферентность подобного типа сначала кажется весьма странной, но, поняв ее принцип, вы найдете ее простой и изящной. Арифметическая версия квайнирования — назовем ее арифмоквайнированием — позволит нам получать суждения ТТЧ, «говорящие о себе самих».
Давайте рассмотрим пример арифмоквайнирования. Нам нужна формула, по меньшей мере, с одной переменной. Для этого годится следующая формула:
a=S0
Гёделев номер этой формулы — 262,111,123,666; теперь мы подставим этот номер в саму формулу — или, точнее, мы подставим в нее символ этого номера. У нас получится:
SSSSS.....SSSSSO=S0
|____________|
262,111,123,666 «S»
Эта новая формула очень глупа: она утверждает, что 262,111,123,666 равняется 1. Если бы мы начали со строчки ~a=S0, и затем арифмоквайнировали ее, у нас получилось бы верное высказывание, в чем вы сами можете убедиться.
Разумеется, арифмоквайнируя, вы проделываете специальную операцию замены, о которой мы упомянули ранее. Чтобы говорить об арифмоквайнировании в ТТЧ, нам понадобилась бы формула:
ZAM{a'',a'',a'}
где две первые переменные совпадают. Это происходит потому, что мы используем один и тот же номер двумя разными способами (эхо Канторовского диагонального метода!) Номер а' является одновременно (1) первоначальным Гёделевым номером и (2) номером-заменой. Давайте сократим вышеприведенную формулу:
ARITHMOQUINE{a'', a'}
В переводе на русский это означает, что:
а' — Гёделев номер формулы, полученной арифмоквайнированием формулы с Гёделевым номером а''.
Предыдущее предложение — длинное и запутанное. Давайте попробуем выразить то же самое с помощью краткого и элегантного термина:
а' — арифмоквайнификация а''
Например, арифмоквайнификацией формулы 262,111,123,666 был бы следующий невероятный гигант:
123,123,123, ...... 123,123,123,666,111,123,666
|_________________________|
«123» повторяется 262, 111, 123,666 раз.
(Это всего-навсего Гёделев номер формулы, полученной, когда мы арифмоквайнировали a=S0.) Как видите, мы можем довольно легко говорить об арифмокваинировании в ТТЧ.
Последняя соломинка
Если вы снова перелистаете «Арию в ключе G», то увидите, что последний трюк, необходимый для получения автореференции по Квайну, заключается в том, чтобы квайнировать высказывание, само говорящее о квайнировании. Одного квайнирования оказывается недостаточно — вы должны квайнировать предложение о квайнировании! Нам придется использовать параллельный трюк и арифмоквайнировать формулу, саму упоминающую квайнирование. Давайте запишем эту формулу; назовем ее дядей G.
~Eа:Eа':<ПАРА-ДОКАЗАТЕЛЬСТВА-
TTЧ{a,a'}Λ ARITHMOQUINE{a",a'}>
Легко увидеть, насколько здесь замешано арифмоквайнирование. У этого «дяди», разумеется, есть Гёделев номер — мы будем называть его d. Начало и конец d и даже кое-какие фрагменты его середины мы можем прочитать без труда:
d = 223,333,262,636,333,262,163,636,212..... 161,.... 213
Для остального нам только нужно знать, как выглядят в записи формулы ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ и ARITHMOQUINE. Приводить здесь эту запись слишком сложно, да и не нужно.
Теперь осталась самая малость — нужно арифмоквайнировать самого дядю! Для этого надо избавиться от свободных переменных, которых у нас только одна — а'' — и заменить их на символ числа d. Мы получим:
~Ea:Ea':<ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{a,a'}
ΛARITHMOQUINE{SS…SSS0/a'',a'}>
. |___|
. 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а':<ЧЕРЕПАШЬЯ ПАРА{а, а'}ΛДЕСЯТАЯ СТЕПЕНЬ{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 не являются теоремами ТТЧ. Мы нашли в нашей системе дыру — неразрешимое суждение. Это не должно нас особенно беспокоить, если мы достаточно свободомыслящи, чтобы признать, что из этого следует. Это означает, что ТТЧ можно дополнить, как можно дополнить абсолютную геометрию. В действительности, ТТЧ, как и абсолютную геометрию, можно расширить в двух направлениях. Она может быть расширена в стандартном направлении, что соответствует расширению абсолютной геометрии в Эвклидовом смысле; или же, она, может быть расширена в нестандартном направлении, что, разумеется, соответствует расширению абсолютной геометрии в неэвклидовом смысле. Стандартным дополнением будет:
добавление G в качестве новой аксиомы.
Это кажется довольно безвредным и даже желательным, поскольку G всего на всего утверждает некую истину о системе натуральных чисел. А как насчет нестандартного расширения? Если следовать аналогии с ситуацией аксиомы параллельности, оно должно означать:
добавление отрицания G в качестве новой аксиомы.
Но как мы можем даже подумать о таком ужасной, отвратительной вещи? В конце концов, если перефразировать Саккери, не является ли то, что утверждает ~G, «противным самой природе натуральных чисел»?
Супернатуральные числа
Надеюсь, что вы оценили иронический смысл этой цитаты. Проблема с подходом Саккери к геометрии заключалась в том, что он основывался на жестком понятии о том, что истинно и что ложно; он хотел доказать только то, что он считал истинным с самого начала. Несмотря на его оригинальный метод — отрицание пятого постулата и доказательство многих «противных» утверждений вытекающей из этого геометрии — Саккери не допускал возможности иного взгляда на точки и линии. Не будем повторять его знаменитой ошибки; вместо этого давайте рассмотрим как можно беспристрастней, что означала бы добавка ~G в качестве аксиомы ТТЧ. Подумайте только, на что была бы похожа современная математика, если бы люди не решили в свое время добавить к ней аксиом типа:
Ea: (a+a)=S0
Ea: Sa=0
Ea: (a*a)=SS0
Ea: S(a*a)=0
Хотя каждое из этих утверждений «противно природе ранее известных числовых систем», каждое из них в то же время означает значительное и замечательное расширения понятия целых чисел: рациональные числа, отрицательные числа, иррациональные числа, мнимые числа. ~G пытается открыть нам глаза на такую возможность. В прошлом каждое новое расширение системы натуральных чисел встречалось в штыки. Это можно заметить по именам, данным непрошеным пришельцам: «иррациональные», «мнимые». Оставаясь верными традиции, давайте назовем числа, которые порождает ~G, супернатуральными, поскольку они противоречат всем понятиям разума и здравого смысла.
Если мы собираемся добавить ~G в качестве шестой аксиомы ТТЧ, мы должны постараться понять, каким образом эта строчка может сосуществовать с вышеприведенной пирамидальной семьей. Ведь ~G утверждает, что
«существуют некое число, составляющее пару доказательства с d».
При этом члены пирамидальной семьи с успехом утверждают, что
«0 не является этим числом»
«1 не является этим числом»
«2 не является этим числом»
*
*
Это сбивает с толку, поскольку кажется совершеннейшим противоречием (именно поэтому это называется ω-противоречивостью). Наша проблема заключается в том, что, так же как и в случае с расширенной геометрией, мы упрямо отказываемся модифицировать интерпретацию символов, несмотря на то, что прекрасно понимаем, что имеем дело с модифицированной системой. Мы хотим обойтись без добавления хотя бы одного символа — что, разумеется, оказывается невозможным.
Проблема разрешается, если мы интерпретируем E как «существует некое обобщенное натуральное число» вместо «существует некое натуральное число». Одновременно с этим нам придется соответствующим образом изменить интерпретацию A. Это значит, что, кроме натуральных, мы открываем дверь для неких новых чисел. Это супернатуральные числа. Натуральные и супернатуральные числа вместе составляют обобщенные натуральные числа.
Кажущееся противоречие теперь испаряется, поскольку пирамидальная семья все еще утверждает, что «никакое натуральное число не составляет пару доказательства ТТЧ с арифмоквайнификацией d» Строчки этой семьи ничего не упоминают о супернатуральных числах, поскольку для них не существует символов. С другой стороны, ~G утверждает, что существует такое обобщенное натуральное число, которое составляет пару доказательства ТТЧ с арифмоквайнификацией d. Противоречия больше нет. ТТЧ+~G превращается в непротиворечивую систему, если ее интерпретация включает супернатуральные числа.
Поскольку мы решили расширить интерпретацию обоих кванторов, это означает, что значение любой включающей их теоремы также расширяется. Например, теорема коммутативности
Aa:Aa':(a+a')=(a'+a)
теперь говорит нам, что сложение коммутативно для всех обобщенных чисел — другими словами, не только для натуральных, но и для супернатуральных чисел. Таким же образом, теорема ТТЧ. утверждающая, что «2 — не квадрат натурального числа» —
~Ea:(a*a)=SSO
теперь говорит нам, что 2 также не является квадратом никакого супернатурального числа. На самом деле, супернатуральные числа имеют те же свойства, как и натуральные, всегда, когда эти свойства выражены в теоремах ТТЧ. Иными словами, все, что может быть формально доказано для натуральных чисел, верно и для супернатуральных чисел. Это означает, что супернатуральные числа не являются чем-то хорошо знакомым, вроде дробей, отрицательных чисел, комплексных чисел и т. п. Вместо этого, супернатуральные числа могут быть представлены, как целые числа, большие чем всё натуральные числа — то есть, как бесконечно большие целые числа. Дело в том, что хотя теоремы ТТЧ могут «запретить» отрицательные числа, дроби, иррациональные и комплексные числа, они бессильны против бесконечно больших величин. Проблема в том, что в ТТЧ невозможно даже выразить высказывание «бесконечных величин не существует».
С первого взгляда это кажется весьма, странным. Насколько велико число, составляющее пару доказательства с Гёделевым номером строчки G? (Давайте назовем это число «I», без особой на то причины.) К несчастью, у нас нет подходящих терминов для описания размера бесконечно больших целых чисел, так что я боюсь, что мне не удастся поведать вам, насколько велико I. С другой стороны, насколько велико i (квадратный корень из -1)? Его величина не может быть выражена в терминах знакомых нам натуральных чисел. Вы не можете сказать, что i вдвое меньше 14. Вам приходится успокоиться на том, что i в квадрате равняется -1. Здесь уместно процитировать Абраама Линкольна. Когда его спросили, какой длины должны быть человеческие ноги, он ответил; «Достаточно длинными, чтобы доставать до земли». Примерно так же нам придется ответить на вопрос о величине I: оно должно равняться числу, определяющему структуру доказательства G: не больше и не меньше.
Разумеется, любая теорема ТТЧ может быть выведена разными способами, так что вы можете пожаловаться, что мое определение I не является единственным. Это верно. Но сравнение с i, квадратным корнем из -1, все равно годится. Вспомните, что существует еще одно число, чей квадрат равняется -1 — а именно, -i. i и -i — не одно и то же число. У них просто есть общее свойство. Проблема в том, что они определяются именно через это свойство! Нам приходится выбрать одно из них — неважно, какое именно — и называть его i. На самом деле, мы никак не можем их различить. Вполне возможно, что все эти годы мы считали за «i» ошибочное число — однако для нас в этом не было никакой разницы. Так же как i, I определено неоднозначно. Вы можете думать об I как о каком-либо из многих супернатуральных чисел, составляющих пару доказательства с арифмоквайнификацией d.
У супернатуральных теорем — бесконечно длинные деривации
Мы еще не выяснили всех последствий добавления —G в качестве аксиомы ТТЧ Дело в том, что ~G утверждает, что у G имеется доказательство! Как может какая-либо система устоять, когда одна из ее аксиом утверждает, что ее собственное отрицание имеет доказательство? Тут-то мы попали в переделку! Однако все не так плохо, как кажется Пока мы строим только конечные доказательства, нам не удастся доказать G. Таким образом, кошмарного столкновения между G и ее отрицанием —G не произойдет никогда Супернатуральное число I не будет причиной несчастья. Однако нам придется привыкнуть к мысли, что теперь истинно ~G (утверждающее, что у G есть доказательство), в то время как G (утверждающее, что у G нет доказательства) ложно. В стандартной теории чисел дело обстоит наоборот — но там нет никаких супернатуральных чисел. Обратите внимание на то, что супернатуральная теорема ТТЧ — а именно, G — может утверждать нечто ложное, но все натуральные теоремы остаются истинными.
Супернатуральное сложение и умножение
Я хотел бы поделиться с вами одним интересным и неожиданным фактом по поводу супернатуральных чисел — при этом я оставлю этот факт без доказательства. (Так как сам его не знаю.) Этот факт напоминает о принципе неопределенности Гейзенберга в квантовой механике. Оказывается, что супернатуральные числа можно «индексировать» простым и естественным образом, ассоциируя с каждым из них тройку обыкновенных чисел (включая отрицательные). Таким образом, наше I может получить индекс (9,-8,3), а следующее за ним I+1 — индекс (9,-8,4). Не существует какого-то одного способа индексировать все супернатуральные числа: у разных методов есть свои плюсы и минусы. Некоторые схемы индексации позволяют легко вычислить тройной индекс для суммы двух супернатуральных чисел, исходя из индексов двух слагаемых. Другие схемы позволяют нам с легкостью вычислить индекс произведения двух супернатуральных чисел, исходя из индексов двух множителей. Но никакая из существующих схем не позволяет нам вычислить и то, и другое. Если индекс суммы вычисляется с помощью рекурсивной функции, то индекс произведения не будет рекурсивной функцией — и наоборот, если индекс произведения — рекурсивная функция, то индекс суммы — нет. Таким образом, супернатуральные детишки, изучающие в своей школе сложение, не смогли бы проходить таблицы умножения — и наоборот! Знать и то и другое одновременно невозможно.
Супернатуральные числа полезны...
Можно пойти еще дальше теории супернатуральных чисел и рассмотреть супернатуральные дроби (отношение двух супернатуральных чисел), супернатуральные действительные числа, и так далее. На самом деле, вычисления могут делаться на новой основе если мы введем понятие действительных супернатуральных чисел. Бесконечно малые величины, такие как dx и dy, этот кошмар для математиков, могут быть с легкостью объяснены если рассматривать их как противоположность бесконечно больших действительных чисел! Некоторые теоремы высшей математики могут быть доказаны более интуитивно с помощью «нестандартного анализа».
… но реальны ли они?
Нестандартная теория чисел при первом знакомстве сбивает с толку. Но ведь и неэвклидова геометрия тоже странная штука! В обоих случаях так и хочется спросить: «Но какая из этих двух соперничающих теорий правильна? Какая из них выражает истину?» В некотором смысле, ответа на этот вопрос не существует. (Но в другом смысле, о котором мы поговорим позже, на этот вопрос можно дать ответ.) То, что ответа нет, объясняется тем фактом, что соперничающие теории, хотя они и пользуются одинаковыми терминами, говорят о разных вещах. Поэтому они соперники только по видимости, точно так же как эвклидова и неэвклидова геометрии. В геометрии слова «точка», «линия» и так далее — неопределенные термины, и их значения определяются той аксиоматической системой, в рамках которой они в данный момент используются.
То же самое можно сказать о теории чисел. Решив формализовать ТТЧ, мы заранее выбрали термины для интерпретации — например, «число», «плюс», «умножить» и так далее. Приступив к формализации, мы тем самым согласились работать с любыми значениями, которые эти термины могут принять. Но оказывается, что, как и Саккери, мы не были готовы к сюрпризам. Мы думали, что нам известно, какая теория чисел истинна, правильна и единственна, и не подозревали о том, что ТТЧ не сможет ответить на некоторые вопросы о числах — вопросы, на которые оказалось возможным ответить ad libitum только расширив теорию чисел в разных направлениях. Таким образом, у нас нет основания утверждать, что теория чисел «в действительности» имеет ту или иную форму, так же как мы не можем сказать, существует ли в действительности квадратный корень из -1.
Варианты геометрии и физики
Против этого можно использовать следующий довод. Предположим, что физические эксперименты в реальном мире могут быть более экономно объяснены с помощью одного определенного варианта геометрии. В таком случае, у нас было бы основание называть именно этот вариант «истинной» геометрией. С точки зрения физика, желающего иметь дело с «правильной» геометрией, имеет смысл различать между «истинным» и остальными вариантами геометрии. Но к этому нельзя подходить слишком упрощенно. Физики всегда имеют дело с приближенными или идеализированными ситуациями. Например, моя собственная диссертация, о которой я упомянул в главе V, была основана на крайней идеализации проблемы кристаллов в магнитном поле. Результатом этого были некие красивые и симметричные математические модели. Несмотря на искусственность модели — или, скорее, благодаря ей — в графике ясно отразились некоторые ее основные черты. Это помогает представить, что может происходить в более реалистических ситуациях. Без упрощающих допущений, использованных мною при построении графика, такие догадки были бы невозможны. Такие ситуации встречаются в физике очень часто: физики используют «воображаемую» ситуацию, чтобы узнать о глубоко спрятанных чертах действительности. Поэтому необходимо быть осторожным, утверждая, что геометрия, используемая физиками, представляет собой «истинную геометрию»; на самом деле, физики используют несколько различных вариантов геометрии, в каждой данной ситуации выбирая наиболее простой и подходящий.
Более того, физики изучают не только трехмерное пространство, в котором мы обитаем. Объектом их изучения являются целые семьи «абстрактных пространств», в которых они производят свои расчеты Геометрические характеристики этих пространств весьма отличны от характеристик того пространства, в котором мы живем. Кто может утверждать, что «истинная» геометрия описывает именно то пространство, в котором Уран и Нептун кружатся вокруг солнца? Чем оно лучше «Гильбертова пространства», в котором зыблются волновые функции квантовой механики — «пространства момента», где обитают компоненты Фурье — «взаимного пространства», где резвятся волны-векторы, «фазового пространства», в котором бурлят конфигурации, состоящие из многих частиц, и так далее? Нет причины для того, чтобы все эти геометрии были одинаковыми, точнее, они никак не могут быть одинаковыми! Таким образом, для физиков очень важно существование различных «соперничающих» геометрий вариант.
Варианты теории чисел и банкиры
Довольно о геометрии — перейдем теперь к теории чисел. Так ли это важно и необходимо, чтобы существовали разные варианты теории чисел? Если бы вы спросили банковского работника, думаю, что он бы сначала не поверил, что вы говорите серьезно — а потом пришел в ужас. Как 2 + 2 может быть отлично от 4? Если бы 2 + 2 не было равно 4, разве не зашаталась бы мировая экономика от невыносимой неуверенности, не развалилась бы она от подобного удара? На самом деле, этого не произошло бы. Прежде всего, нестандартная теория чисел не угрожает старому доброму факту, что дважды два — четыре. Она отличается от привычной нам теории чисел только тем, как она обращается с понятием бесконечности. В конце концов, любая теорема ТТЧ остается теоремой в любой расширенной версии ТТЧ! Так что банкирам не надо волноваться о том что с приходом нестандартной теории чисел в финансовом мире воцарится хаос.
Боязнь что новые варианты математических теорий изменят старые, хорошо известные факты, отражает непонимание взаимоотношений математики с действительностью. Математика дает нам ответы на вопросы о реальном мире только после того, как мы выбрали, какой тип математики мы используем в данный момент. Даже если бы существовал соперничающий вариант теории чисел, использующий символы 2, 3 и +, в котором 2 + 2 = 3 было бы теоремой, у банкиров не было бы причин выбирать именно этот вариант! Эта теория не отражает того, как ведут себя деньги. Мы приспосабливаем математику к действительности, а не наоборот. Например, мы не используем теорию чисел, чтобы описывать облака поскольку там не подходит само понятие целых чисел. Одно облако может соединиться с другим, в результате чего получается не два, а одно облако! Это не доказывает, что 1 плюс 1 равняется 1, это доказывает лишь то, что наше понятие «один» не годится для «облачного исчисления».
Варианты теории чисел и метаматематики
Итак, банковские работники, любители считать облака и все остальные не должны бояться нашествия супернатуральных чисел, так как они абсолютно не затронут нашу повседневную жизнь. Повод для беспокойства есть только у тех людей чья работа связана с бесконечными величинами. Таких людей не очень много но математические логики находятся в их числе. Как может их затронуть существование вариантов теории чисел? Теория чисел играет в логике две роли: (1) когда она аксиоматизирована, она становится объектом изучения, и (2) используемая неформально, она является необходимым орудием, при помощи которого могут изучаться формальные системы. Это напоминает уже знакомое нам различие между использованием и упоминанием, в роли (1) теория чисел упоминается, в роли (2) она используется.
Математики решили, что теория чисел, хотя она и не подходит для подсчета облаков, вполне годится для изучения формальных систем, так же как банковские работники решили, что арифметика действительных чисел годится для их операций. Подобные решения принимаются вне математики; они показывают, что мыслительные процессы, задействованные в изучении математики, так же, как и в других областях человеческой деятельности, включают «запутанные иерархии», где мысли на одном уровне могут влиять на мысли на другом уровне. При этом четкого разделения на уровни не существует, как могут думать последователи формалистского взгляда на математику.
Формалистская философия утверждает, что математики имеют дело с абстрактными символами и что им совершенно все равно, соответствуют ли эти символы окружающей их действительности. Однако это весьма искаженная картина, что становится особенно ясным в метаматематике. Используя саму теорию чисел для получения новых фактов о формальных системах, метаматематики показывают, что они считают эфирные создания, называемые «натуральными числами», частью реального мира, а не просто плодом воображения. Именно поэтому я упомянул ранее о том, что в некотором роде можно ответить на вопрос, какой из вариантов теории чисел является «истинным». Дело в том, что математическим логикам приходится выбирать, в какой из вариантов теории чисел «поверить». В частности, они не могут оставаться в стороне от принятия или не принятия супернатуральных чисел, поскольку эти варианты теории чисел дают разные ответы на вопросы метаматематики.
Возьмем, например, вопрос «Является ли ~G финитно выводимым в ТТЧ?» Ответа на этот вопрос не знает никто. Однако большинство специалистов по математической логике без колебаний ответят «нет». Этот ответ основывается на интуиции, говорящей, что если бы ~G было теоремой, ТТЧ была бы ω-противоречива. Если вы хотите придать смысл интерпретации ТТЧ, вам приходится признать существование супернатуральных чисел — невыносимая мысль для большинства людей. К конце концов, придумывая ТТЧ. мы не ожидали, что супернатуральные числа будут ее частью. Мы (по крайней мере большинство из нас) верим в то. что возможно придумать такую формализацию теории чисел, которая не заставит нас признать реальности супернатуральных чисел. Именно эта вера определяет решение метаматического витязя на распутьи разных теорий чисел. Но эта вера может оказаться ошибочной. Возможно, что любая непротиворечивая формализация теории чисел, которую люди способны изобрести, была бы ω-противоречива, и, следовательно, включала бы супернатуральные числа. Это странная мысль, но в принципе такое возможно.
Если бы это было верно (в чем я сомневаюсь, но доказательства обратного пока не существует), то G не должно бы оставаться неразрешимым. На самом деле, тогда в ТТЧ может вообще не остаться неразрешимых суждений. Это дало бы единственный и неделимый вариант теории чисел, который с необходимостью включал бы существование супернатуральных чисел. Это не то решение, которого ожидает большинство математических логиков, но тем не менее, оно не должно быть полностью отброшено. Обычно считается, что ТТЧ и подобные ей системы ω-непротиворечивы, и что Гёделева строчка, которая может быть выведена в данной системе, неразрешима внутри этой системы. Это значит, что возможно добавить либо эту строчку, либо ее отрицание в качестве аксиомы.
Десятая задача Гильберта и Черепаха
Я хотел бы завершить эту главу упоминанием о расширенном варианте теоремы Геделя (Этот материал излагается подробнее в статье Davis and Hersh, «Hilbert's Tenth Problem», см. Библиографию) Для этого я сначала определю Диофантиново уравнение. Это такое уравнение, в котором многочлен с установленными интегральными коэффициентами и экспонентами приравнивается к 0. Например,
a=0
и
5x + 13y - 1 = 0
и
5р5 + 17q17 - 177 =0
и
a123666111666 + b123666111666 - c123666111666 =0
являются Диофантовыми уравнениями. Обычно трудно узнать, имеет ли данное Диофантово уравнение решение в целых числах. В своей знаменитой лекции в начале века Гильберт предложил математикам найти общий алгоритм, который помог бы определить за конечное количество шагов, имеет ли данное Диофантово уравнение решение в целых числах. Тогда он и не подозревал, что подобного алгоритма не существует!
Обратимся теперь к упрощению G. Доказано, что в каждой достаточно мощной формальной системе с Гёделевой нумерацией существует Диофантово уравнение, эквивалентное G. Это происходит потому, что это уравнение, интерпретированное на метаматематическом уровне, утверждает о себе самом, что у него нет решений. Теперь перевернем это утверждение задом наперед: если бы вы нашли решение этого уравнения, вы смогли бы построить на его основе Гёделев номер доказательства того, что это уравнение не имеет решений! Именно это и проделала Черепаха в «Прелюдии», используя в качестве Диофантинбва уравнения уравнение Ферма. Приятно знать, что если вы сможете это сделать, вам удастся восстановить из молекул воздуха звуки игры самого Баха!
