7.1. Гёделевская нумерация
Гёдель прежде всего описал некоторое формализованное исчисление, средствами которого можно выразить все обычные арифметические понятия и установить известные арифметические соотношения.
Гёдель использовал несколько упрошенный вариант системы, описанной в Principia Mathematics. Но для его цели точно так же подходит любое исчисление, в котором можно построить систему натуральных чисел с определенными на ней арифметическими операциями.
Формулы этого исчисления строятся исходя из некоторого запаса элементарных символов, образующих алфавит системы. В этом исчислении, как обычно, выделено некоторое множество исходных формул (аксиом) и точно перечислены правила преобразования (правила вывода), посредством которых из аксиом выводятся теоремы.
Гёдель показал, что каждому элементарному символу, каждой формуле (т. е. цепочке элементарных символов) и каждому доказательству (конечной последовательности формул) можно однозначным образом приписать некоторый номер (натуральное число). Такой номер, служащий своего рода значком, ярлыком, указывающим на отмечаемый им объект — символ, формулу или доказательство — формальной системы, мы будем называть «гёделевским номером» этого символа, формулы или доказательства.
Элементарные символы, составляющие алфавит системы, бывают двух сортов: константы и переменные. Мы будем считать, что у нас есть ровно десять символов-констант, которым мы припишем в качестве гёделевских номеров числа от 1 до 10. Почти все эти символы читателю уже известны: «~» (сокращение для «не»), «˅» («или»), «ﬤ» («если…, то…»), «=» («равно»), «0» (цифровой знак, изображающий число «нуль»), а также три «знака препинания»: левая скобка «(», правая скобка «)» и запятая «,». Кроме того, нам понадобятся еще два символа: перевернутая буква «Ǝ» (читаемая как «существует» и называемая «квантором существования») и строчная латинская буква «s», обозначающая числовой оператор, сопоставляющий каждому натуральному числу непосредственно следующее за ним число. Пример: формулу «Ǝ x (x = s0)» можно прочесть как «существует такое x, что x непосредственно следует за числом 0». Выпишем все используемые нами символы-константы (под ними указаны соответствующие гёделевские номера):
~ ˅ ﬤ Ǝ = 0 s ( ) ,
1 2 3 4 5 6 7 8 9 10
Кроме элементарных символов-констант, в алфавит нашего исчисления входят еще переменные, причем переменные трех сортов: числовые переменные «x», «y», «z» и т. д. (вместо них можно подставлять «цифры» и составленные из них (и числовых переменных) «арифметические выражения», выражающие натуральные числа); пропозициональные переменные «p», «q», «r» и т. д. (вместо них можно подставлять «формулы», выражающие высказывания); и, наконец, предикатные переменные «P», «Q», «R» и т. д. (вместо них можно подставлять арифметические «предикаты», выражающие такие свойства и отношения, как «больше чем», «простое (число)» и т. п.). Переменным также сопоставляются гёделевские номера, причем делается это в соответствии со следующими соглашениями:
1) различным числовым переменным приписываются различные простые числа, большие 10;
2) различным пропозициональным переменным приписываются квадраты различных простых чисел, больших 10;
3) различным предикатным переменным приписываются кубы различных простых чисел, бОльших 10.
* Кавычки (добавленные при переводе) означают здесь, что подставить можно не само написанное в правом столбце слово, а его формальную запись на языке нашего исчисления. — Прим. перев .
Возьмем какую-нибудь формулу нашей системы, например
Ǝ x (x = sy)
(которую можно прочесть как «существует такое x, что x непосредственно следует за y» и которая выражает то обстоятельство, что для каждого числа есть непосредственно следующее за ним число). Выпишем под каждым из входящих в нее символов его (символа) гёделевский номер:
Ǝ x ( x = s у )
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
4 11 8 11 5 7 13 9
Конечно, нам бы хотелось сопоставить каждой формуле не набор номеров (как пока получилось), а один-единственный определенный номер. Но это очень легко сделать. А именно: сопоставим этой формуле произведение первых восьми простых чисел в порядке их величины, причем каждое из них в степени, показатель которой равен гёделевскому номеру соответствующего элементарного символа:
24 × 311 × 58 × 711 × 115 × 137 × 1713 × 99.
Обозначим это число, скажем, через m. Точно таким же образом мы можем приписать в качестве гёделевского номера единственное вполне определенное натуральное число каждой конечной последовательности элементарных символов, в частности каждой формуле, причем число простых сомножителей такого числа всегда будет равно числу вхождений элементарных символов в обозначаемой формуле.
В исчислении могут использоваться и символы, не входящие в его исходный («основной») алфавит; такие символы вводятся посредством определений, записанных в терминах исходных (и вообще ранее определенных) символов. Например, в наше исчисление можно ввести новый символ (константу) «·», обозначающий союз «и», определив его таким образом, чтобы запись « p · q » воспринималась как сокращение записи «~(~ p ˅~ q )». Какой гёделевский номер сопоставить введенному таким образом символу? Ответ станет совершенно очевидным, когда мы заметим, что из выражений, содержащих дополнительные (введенные определениями) символы, эти новые символы можно исключить, заменив их обозначаемыми ими выражениями, составленными исключительно из исходных символов (для этого мы просто читаем соответствующие определения «справа налево»); для последних же гёделевеcкие номера мы строить умеем. Поэтому нам достаточно условиться считать гёделевским номером формулы « p · q » гёделевский номер эквивалентной ей формулы «~(~ p ˅~ q )», гёделевским номером «формулы» «2 ≠ 3» — номер заменяемой ею «настоящей» формулы «~( ss 0= sss 0)» и т. п., условившись, конечно (что совсем нетрудно), об однозначном порядке таких «расшифровок».
Рассмотрим, наконец, какую-нибудь последовательность формул (могущую быть в частном случае доказательством), например последовательность
Ǝ x (x = sy),
Ǝ x (x = s0).
Вторая формула последовательности, читаемая как «существует число, непосредственно следующее за нулем», — выводимая из первой формулы посредством подстановки цифры 0 вместо числовой переменной.
Читатель, конечно, помнит, что формальное доказательство мы определяли выше как конечную последовательность формул, каждая из которых есть либо аксиома, либо выводима из предыдущих формул этой последовательности по правилам вывода данного исчисления. Согласно этому определению приведенная пара формул доказательством не является (первая ее формула — не аксиома) — это лишь «кусок» доказательства, на примере которого мы столь же понятно (но далеко не так громоздко) поясним идею нумерации, как и на целом доказательстве.
Выше мы уже определили гёделевский номер первой из этих формул — мы обозначили его тогда через m. Пусть гёделевским номером второй формулы является число n. Как и выше, мы хотим сопоставить нашей последовательности не пару чисел m и n, а некоторое единственным образом определенное натуральное число. Для этого нам достаточно взять в качестве такого гёделевского номера число, являющееся произведением степеней первых двух простых чисел (т. е. чисел 2 и 3), причем первый сомножитель будет входить в это произведение в степени, показатель которой равен гёделевскому номеру первой формулы, и аналогично для второго сомножителя (а также для третьего и других, если мы имеем дело с последовательностью, состоящей более чем из двух формул). Обозначим это число через k: k = 2 m × 3n . Такой простой и компактный метод применим, очевидно, для получения гёделевского номера произвольной последовательности формул. Таким образом, любое выражение нашей системы — будь то элементарный символ, последовательность символов или последовательность таких последовательностей — может быть однозначно занумеровано посредством некоторого гёделевского номера.
Теперь уже полная «арифметизация» нашего формального исчисления не представит никакого труда. Такая «арифметизация» попросту сводится к устанорлению некоторого взаимно-однозначного соответствия между выражениями, входящими в исчисление, и некоторым подмножеством натурального ряда.
Не всякое натуральное число есть гёделевский номер константы, переменной или формулы; предоставляем читателю придумать и разобрать примеры на различные возможные случаи.
Если нам дано какое-нибудь выражение, мы без труда напишем его гёделевский номер. Это, однако, лишь полдела. Важно то, что когда нам дано какое-либо натуральное число, то мы можем установить, является ли это число гёделевским номером, а если да — то можем точно «восстановить» обозначаемое этим номером выражение. Если данное число не превосходит 10, то это, как мы знаем, просто номер некоторой константы. Если же данное число больше 10, то его можно разложить, причем единственным образом (в этом состоит так называемая основная теорема арифметики), на простые сомножители. Если оно оказалось простым, квадратом простого или кубом простого числа, то это — гёделевский номер переменной.
Если данное число оказалось произведением степеней первых последовательных простых чисел, то оно может (хотя, конечно, и не обязано) быть гёделевским номером формулы или последовательности формулы.
И в таком случае выражение, которому соответствует данный номер, может быть точно определено.
Следуя намеченной программе, мы можем для любого данного числа совершенно единообразным методом («как машина») проверить, является ли оно гёделевским номером, а если да — то какого выражения. Пусть, например, нам дано число 243 000 000. Разложим его (оно, очевидно, составное) на простые сомножители: 243 000 000 = 64 × 243 × 15 625 = 26 × 35 × 56. Вспомнив, что 6 есть гёделевский номер константы «0», а 5 — гёделевский номер знака «=», рисуем схему:
6 5 6
↓ ↓ ↓
0 = 0
Теперь видно, что число «243 миллиона» действительно есть гёделевский номер некоторой формулы, а именно, формулы «0 = 0» (т. е. «нуль равен нулю»).
7.2. Арифметизация метаматематики
Следующим шагом, который проделал Гёдель, было чрезвычайно остроумное применение описанного выше «кодирования» («гёделевской нумерации»). Он показал, что все метаматематические высказывания о структурных свойствах выражений, входящих в рассматриваемое исчисление, можно изобразить (причем взаимно-однозначным образом) в самом этом исчислении. В основе этой процедуры лежит следующая идея. Поскольку каждому выражению нашего исчисления приписан некоторый (гёделевский) номер, то каждое метаматематическое высказывание о выражениях исчисления и отношениях, имеющих место между ними, можно рассматривать и как высказывание о соответствующих (гёделевских) номерах и отношениях между ними. Таким путем метаматематика оказывается полностью «арифметизированной».
Рассмотрим такой популярный пример. При входе в большие универсальные магазины покупателям иногда выдают билетики с номерами, определяющими порядок дальнейшего обслуживания покупателей. Достаточно бывает посмотреть на эти номера, чтобы ответить на вопросы, сколько покупателей уже обслужено, сколько ожидает своей очереди, кто за кем стоит, сколько всего покупателей было с утра в магазине и т. п. Если, скажем, миссис Смит имеет номер 37, а миссис Браун — номер 53, то вместо того чтобы объяснить миссис Браун, что она должна пропустить вперед миссис Смит, достаточно обратить ее внимание на то, что 37 меньше, чем 53.
В метаматематике дело обстоит в точности, как в этом магазине. Каждое метаматематическое высказывание кодируется теперь вполне однозначным образом посредством некоторой арифметической формулы; отношения же, имеющие место между метаматематическими высказываниями, и логические зависимости между ними также однозначно переводятся в некоторые числовые соотношения и зависимости между соответствующими арифметическими формулами. И здесь, как и раньше, числовое кодирование облегчает рассмотрение всех достаточно сложных соотношений. Изучение метаматематических вопросов сводится к исследованию арифметических соотношений и свойств некоторых чисел.
Проиллюстрируем все эти общие замечания одним элементарным примером. Возьмем первую аксиому исчисления высказываний, являющуюся, кстати, аксиомой и рассматриваемого сейчас логико-арифметического исчисления: «(p ˅ p) ﬤ p». Ее гёделевский номер, равный, как легко убедиться, числу 28 × 311 × 52 × 711^2 × 119 × 138 × 1711 мы обозначим буквой а. Рассмотрим теперь формулу «(p ˅ p)», гёделевский номер которой, равный числу 28 × 311^2 × 52 × 711^2 × 119, обозначим через b. Сформулируем теперь метаматематическое утверждение, гласящее, что формула «(p ˅ p)» есть начальная «подформула» (т. е. часть формулы, сама также являющаяся формулой) выбранной аксиомы. Какой арифметической формуле рассматриваемой формальной системы соответствует это утверждение? Очевидно, что более короткая формула «(p ˅ p)» является начальной подформулой более длинной формулы «(p ˅ p) ﬤ p» в том и только в том случае, если (гёделевский) номер b, соответствующий первой из этих формул, есть делитель (гёделевского) номера a, соответствующего второй формуле. В предположении, что термин «делитель» определен некоторым подходящим образом в формализованной арифметической системе арифметической формулой, однозначным образом соответствующей упомянутому выше метаматематическому утверждению о том, что первая аксиома начинается с подформулы «(p ˅ p)», является формула «b есть делитель a». Более того, если эта последняя формула истинна, т. е. если b действительно является делителем a, то верно и то, что «(p ˅ p)» есть начальная подформула формулы «(p ˅ p) ﬤ p».
Рассмотрим теперь повнимательнее следующее метаматематическое высказывание: «Последовательность формул, имеющая гёделевский номер x, является доказательством формулы, имеющей гёделевский номер z». Высказывание кодируется (изображается) посредством некоторой вполне определенной формулы арифметического исчисления, выражающей некоторое чисто арифметическое отношение между числами x и z. (Некоторое представление о том, насколько сложным является такое отношение, читатель получит, вспомнив приводившийся выше пример, в котором конец доказательства (а не все доказательство!) некоторой формулы, имеющей гёделевский номер, n, получал гёделевский номер k = 2m × 3n . Самый беглый анализ приводит нас к выводу, что здесь вводится вполне определенное, хотя и далеко не простое, арифметическое отношение между k (будем для простоты считать его номером всего доказательства) и n — гёделевским номером заключения этого доказательства.) Мы будем записывать отношение между числами x и z посредством формулы «Dem(x, z)» напоминающей нам самим своим обликом о том метаматематическом утверждении, которому она соответствует (а именно, об утверждении «Последовательность формул, имеющая гёделевский номер x, является доказательством формулы, имеющей гёделевский номер z»).
Читатель должен твердо уяснить себе, что хотя «Dem( x, z )» кодирует некоторое метаматематическое утверждение, сама эта запись является формулой арифметического исчисления. Формула эта в более привычных обозначениях может быть записана в виде f ( x, z ) = 0, где буква f обозначает некоторый довольно-таки сложный комплекс арифметических операций над числами. Однако эта более привычная запись не «подсказывает» сразу своей метаматематической интерпретации, почему мы и предпочли запись, приведенную в тексте.
Читатель теперь легко убедится в том, что метаматематическое утверждение, гласящее, что некоторая последовательность формул есть доказательство данной формулы, является истинным в том и только в том случае, если гёделевский номер этой последовательности формул находится с гёделевским номером данной формулы как раз в том арифметическом отношении, которое мы обозначили здесь через «Dem». Вообще, чтобы утверждать истинность или ложность какого-либо интересующего нас метаматематического утверждения, нам достаточно решить вопрос о том, находятся ли некоторые два числа в отношении, обозначаемом через «Dem». Но и обратно: чтобы убедиться, что два числа находятся в названном отношении, достаточно установить истинность метаматематического утверждения, «кодируемого» этим арифметическим отношением. Аналогично, метаматематическое высказывание «Последовательность формул, имеющая гёделевский номер x, не является доказательством формулы, имеющей гёделевский номер z», кодируется некоторой вполне определенной формулой формализованной арифметической системы, являющейся формальным отрицанием формулы «Dem(x, z)», т. е. формулой «~ Dem(x, z)».
Еще несколько слов об обозначениях, используемых в доказательстве теоремы Гёделя. Начнем с примера. Формула «Ǝ x (x = sy)» имеет гёделевский номер m (см. выше, с. 81), а переменная «y» — гёделевский номер 13. Подставив в эту формулу вместо переменной, имеющей гёделевский номер 13 (т. е. вместо «y») цифру, обозначающую число m, мы получим в результате формулу «Ǝ x (x = sm)», выражающую утверждение, согласно которому существует такое число x, что это ж непосредственно следует за числом m.
Последняя формула также имеет некоторый гёделевский номер, который совсем нетрудно вычислить. Но вместо того чтобы фактически производить это вычисление, мы можем совершенно однозначно охарактеризовать этот номер чисто метаматематическим образом, говоря, что это гёделевский номер формулы, получаемый из формулы, имеющей гёделевский номер m, подстановкой вместо входящей в эту формулу переменной с гёделевским номером 13 цифры «m». Такая метаматематическая характеристика однозначно определяет некоторое число, являющееся некоторой определенной функцией от чисел m и 13, причем сама эта функция может быть выражена средствами нашей формализованной арифметической системы. Значит, и само число можно выразить внутри нашего исчисления. Обозначим его через «sub(m, 13, m)», напоминая тем самым, что речь идет о гёделевском номере формулы, полученной из формулы, имеющей гёделевский номер m, подстановкой вместо входящей в нее переменной с гёделевским номером 13 цифры, обозначающей число m. Вообще, через «sub(y, 13, y)» мы будем обозначать теперь арифметическую формулу, выражающую внутри арифметического исчисления метаматематическую характеристику: «гёделевский номер формулы, получаемой из формулы, имеющей гёделевский номер y, подстановкой вместо входящей в нее переменной, имеющей гёделевский номер 13, цифры, обозначающей число „y“». Если в выражение «sub(y, 13, y)» мы подставим теперь вместо «y» какую-нибудь определенную цифру, скажем, цифру, обозначающую число m, или выражение 243 000 000, то получающееся в результате выражение также будет обозначать некоторое определенное натуральное число, являющееся притом гёделевским номером некоторой определенной формулы.
У читателя не раз мог возникнуть вопрос, почему, собственно, мы говорили сейчас не просто о «числе y», а — столь вычурно и длинно! — о «цифре, обозначающей y». Впрочем, сама форма вопроса уже отчасти подсказывает ответ. Мы ведь уже упоминали о важном различии между понятиями «число» и «цифра». Цифра — это некоторый знак, т. е. выражение языка, которое можно записывать, стирать, зачеркивать, повторять и т. д. и т. п. Число же — это то, именем (или названием, обозначением) чего является обозначающая его цифра; само по себе число нельзя записать, стереть, зачеркнуть, повторить.
Скажем, когда мы говорим, что 10 — число пальцев на обеих руках, то мы характеризуем этой фразой некоторое «свойство» множества наших пальцев — свойство, которое, разумеется, «цифрой» никак не назовешь. Но число 10 может записываться как арабскими цифрами: «10», так и римскими цифрами (т. е. прописными латинскими буквами) «X»; эти имена сами по себе, конечно, различны, хотя обозначают они одно и то же число. Так вот, когда мы производим подстановку вместо числовой переменной (которая сама есть просто знак, буква), то мы ставим вместо одного знака другой знак. Мы не можем подставить вместо знака число — ведь число, являющееся некоторым свойством (или, как иногда говорят, понятием), вообще не есть что-то такое, что можно непосредственно нанести на бумагу. Итак, вместо числовой — а лучше сказать, цифровой! — переменной мы подставляем именно цифру (или цифровое выражение, скажем «s0» или «7 + 5»), а не число. Именно поэтому мы выше говорили о подстановке цифры (обозначающей число) y, а не самого числа у в интересующее нас метаматематическое выражение.
Читатель может далее поинтересоваться, какое же число обозначается выражением «sub(y, 13, y)», если формула, имеющая гёделевский номер у, не содержит переменной, имеющей гёделевский номер 13, т. е. попросту, если формула не содержит переменной «y». Скажем, sub(243 000 000, 13, 243 000 000) есть гёделевский номер формулы, полученной из формулы, имеющей гёделевский номер 243 000 000, подстановкой вместо переменной «y» цифры 243 000 000. Выше (с. 85) мы уже выяснили, что 243 000 000 — гёделевский номер формулы «0 = 0», не содержащей переменной «y». Но какая же формула получится из формулы «0 = 0» в результате подстановки вместо не входящей в нее переменной «y» цифры, обозначающей число 243 000 000? Ответ очень простой: раз формула не содержит этой переменной, то и подстановка чисто фиктивная, т. е. такая «подстановка» не меняет формулы, иначе говоря, число, обозначаемое записью «sub(243 000 000, 13, 243 000 000)», есть само число 243 000 000.
Заметим, наконец, что выражение «sub(y, 13, y)» не является формулой нашей арифметической системы в том смысле, в каком, например являются формулами выражения «Ǝ x (x = sy)» или «Dem(x, z)», и вот почему. Выражение «0 = 0» мы называем формулой; такая запись утверждает наличие некоторого отношения между двумя числами, так что имеет смысл ставить вопрос, истинно или ложно это утверждение. Аналогично, когда вместо переменных, входящих в выражение «Dem(x, z)», подставляются некоторые цифры, то получающееся выражение оказывается записью некоторого утверждения (о том, что два числа находятся в некотором отношении), о котором опять-таки имеет смысл ставить вопрос, истинно оно или ложно. То же самое можно сказать и о выражении «Ǝ x (x = sy)».
Что же касается выражения «sub(y, 13, y)», даже если переставить в него вместо «y» какую-нибудь конкретную цифру, то оно все равно не будет ничего утверждать и по этой причине не будет ни истинным, ни ложным. Выражение это лишь обозначает (или называет) некоторое число, характеризующее его как некоторую функцию от других чисел. Итак, выражение «Dem(x, z)» (подобно, например, записям «у = f(x)» или «32 + 42 = 52») есть формула и является схемой (или формой) некоторого утверждения; в отличие от него запись «sub(y, 13, y)» (подобно «f(x)» или «(7 × 5) + 8») является лишь схемой (формой) имени некоторого числа, но не формулой.
7.3. Изложение доказательств
Перейдем, наконец, к описанию идеи самого доказательства теоремы Гёделя. Вначале мы дадим совсем простой его набросок, разделив доказательство на пять основных шагов.
Прежде всего Гёдель показывает (1), как построить арифметическую формулу G, представляющую («кодирующую») метаматематическое высказывание «формула G недоказуема». Иначе говоря, формула G гласит о себе самой, что она недоказуема.
Идея построения такой формулы G по существу заимствована из рассуждения, приводящего к парадоксу Ришара. В этом парадоксе, как мы помним, выражению «ришарово число» сопоставляется некоторое число n, после чего рассматривается предложение «n есть ришарово число». В гёделевском же доказательстве формуле G сопоставляется некоторое число h, причем это делается так, чтобы оно соответствовало предложению «Формула, которой сопоставлено число h, недоказуема». Но затем Гёделю удается показать (2), что формула G доказуема тогда и только тогда, когда доказуемо ее формальное отрицание ~G. И этот шаг доказательства аналогичен соответствующему этому рассуждению в парадоксе Ришара, где доказывается, что п есть ришарово число в том и только в том случае, если п не есть ришарово число. Но если некоторая формула и ее отрицание доказуемы, то арифметическое исчисление, в котором возможны оба доказательства, противоречиво.
Значит, если это исчисление непротиворечиво, то как G, так и ~ G не выводимы из аксиом арифметики. Следовательно, если арифметика непротиворечива, то G является формально неразрешимой формулой. Далее Гёдель доказывает (3), что хотя формула G формально недоказуема, она является тем не менее истинной арифметической формулой. Она является истинной в том смысле, что утверждает про каждое натуральное число, что оно обладает некоторым арифметическим свойством, причем свойство это такого рода, что наличие его у каждого натурального числа можно действительно подтвердить посредством прямой проверки (4). Поскольку формула G, будучи истинной, является формально недоказуемой, система аксиом арифметики неполна. Иными словами, из аксиом арифметики нельзя вывести все истинные стремления арифметики. Более того, Гёдель доказал существенную неполноту арифметики: даже если присоединить к ее аксиоматике новые аксиомы, обеспечивающие выводимость истинной формулы G, все равно и для такой пополненной (расширенной) системы можно всегда указать истинную, но формально недоказуемую формулу (5). В заключение Гёдель указал, как построить арифметическую формулу А, представляющую метаматематическое высказывание «Арифметика непротиворечива», и доказал, что формула «А ﬤ G» формально недоказуема. Из этого следует недоказуемость и самой формулы А. Окончательный вывод: непротиворечивость арифметики нельзя установить посредством рассуждения, представимого в формальном арифметическом исчислении.
Перейдем теперь к более подробному изложению доказательства теоремы Гёделя.
1. Мы уже определили выше формулу «~ Dem(x, z)», представляющую в формальном арифметическом исчислении метаматематическое высказывание: «последовательность формул, имеющая гёделевский номер x, не является доказательством формулы, имеющей гёделевский номер z». Теперь мы доставив перед формулой приставку «∀x», являющуюся формальным аналогом языкового оборота «для всех x» (или «для любого x»), и получим в результате новую формулу «∀ x ~ Dem (x, z)», представляющую в формальной арифметике метаматематическое высказывание: «для любого x последовательность формул, имеющая гёделевский номер x, не является доказательством формулы, имеющей гёделевский номер z». Таким образом, эта новая формула является как раз той формулой формального арифметического исчисления, которая представляет в нем метаматематическое высказывание «формула, имеющая гёделевский номер z, недоказуема», или, что то же: «для формулы с гёделевским номером z нельзя построить доказательство».
Гёдель далее показал, что некоторый частный случай этой формулы является формально недоказуемым. Чтобы получить формулу, мы будем исходить из следующей формулы:
∀ x ~ Dem(x, sub(y, 13, y)) (1)
Эта формула, принадлежащая формальному арифметическому исчислению, представляет некоторое метаматематическое высказывание. Какое же именно? Читатель должен помнить, что выражение «sub(y, 13, y)» обозначает некоторое число, которое есть гёделевский номер формулы, получаемой из формулы, имеющей гёделевский номер у, подстановкой вместо переменной, имеющей гёделевский номер 13, (т. е. переменной y) цифры, обозначающей число у. Отсюда видно, что формула (1) представляет метаматематическое высказывание: «формула, имеющая в качестве гёделевского номера число sub(y, 13, y), недоказуема».
Но так как формула (1) принадлежит арифметическому исчислению, она имеет некоторый гёделевский номер, который можно фактически вычислить. Пусть этим номером является число n. Подставим в (1) вместо переменной, имеющей гёделевский номер 13 (т. е. вместо переменной «y»), цифру, обозначающую это число n. В результате подстановки мы получим некоторую формулу, которую назовем (в честь Гёделя) «G»:
∀ x ~ Dem(x, sub(n, 13, n)). (G)
Формула G и есть тот частный случай формулы (1), который мы хотели построить. Формула G принадлежит арифметическому исчислению и должна иметь некоторый гёделевский номер. Каков же этот номер? Нетрудно показать, что таким номером задается число sub(n, 13, n). В самом деле, вспомним, что sub(n, 13, n) есть гёделевский номер формулы, получаемой из формулы, имеющей гёделевский номер n, подстановкой вместо переменной «y» (имеющей гёделевский номер 13) цифры, обозначающей число п. Но ведь формула G как раз и получена из формулы, имеющей гёделевский номер n (т. е. из формулы (1)), подстановкой цифры для числа n вместо входящей в формулу переменной у. Таким образом, действительно sub(n, 13, n) есть гёделевский номер формулы G.
Однако формула G — арифметическая формула, которая представляет в арифметическом исчислении математическое высказывание
«формула „∀ x ~ Dem(x, sub(n, 13, n))“ недоказуема».
Можно, следовательно, сказать, что формула G утверждает свою собственную недоказуемость.
2. Следующий шаг, как уже говорилось, состоит в доказательстве того факта, что формула G является формально недоказуемой. Доказательство очень похоже на рассуждение, приводящее к парадоксу Ришара, но не подвержено тем возражениям, которые вызывает последнее.
Как мы помним, в парадоксе Ришара фигурирует некоторое число n, связанное с определенным математическим высказыванием . В рассуждении же Гёделя число п связывается с определенной арифметической формулой (которая лишь прелставляет метаматематическое высказывание). Таким образом, в теореме Гёделя в отличие от парадокса Ришара идет речь о некотором арифметическом свойстве чисел (задается вопрос, обладает ли число sub( n , 3, n ) свойством, выражаемым формулой «∀ x ~ Dem( x , sub( n , 13, n ))»), а не о метаматематическом , благодаря чему и не возникает дискредитирующего парадокса Ришара смешения высказывания на языке арифметики с высказыванием об арифметике.
Ход рассуждения относительно несложен. Задача его сводится к тому, чтобы доказать, что если бы формула G была доказуема, то ее формальное отрицание (т. е. формула «~ ∀ x ~ Dem(x, sub(n, 13, n))» также было бы доказуемо, и обратно, если бы отрицание формулы G было доказуемо, то была бы доказуема и сама формула G. Отсюда мы получаем, что формула G доказуема в том и только в том случае, если доказуема формула ~ G.
Это утверждение доказано, строго говоря, не самим Гёделем, а Аж, Б. Россером (1936). Гёдель же получил несколько более слабый результат, позволяющий, впрочем, получить все интересующие нас важные выводы.
Воспроизведем вкратце первую часть рассуждения Гёделя, согласно которой, если G доказуема, то и ~ G доказуема. Пусть G доказуема. Тогда должна существовать последовательность арифметических формул, являющаяся доказательством для G. Пусть гёделевский номер доказательства есть k. В таком случае между этим k и числом sub(n, 13, n), являющимся гёделевским номером G, должно иметь место арифметическое отношение, обозначаемое через «Dem(x, z)», т. е. «Dem(k, sub(n, 13, n)» должна быть истинной арифметической формулой. Можно, однако, показать, что это арифметическое отношение обладает тем свойством, что если оно имеет место для каких- либо двух чисел, то формула, выражающая это обстоятельство, непременно доказуема. Таким образом, формула «Dem(x, sub(n, 13, n))» не только истинна, но и формально доказуема, т. е. является теоремой. Но правила вывода элементарной логики позволяют нам немедленно вывести из этой теоремы формулу «~ ∀ x ~ Dem(x, sub(n, 13, n))». Таким образом, мы вывели из доказуемости формулы G доказуемость ее формального отрицания. Значит, если наша формальная система непротиворечива, то G в ней недоказуема.
Чтобы показать, что доказуемость ~ G влечет доказуемость G, требуется аналогичное, но несколько более громоздкое рассуждение, которое мы не будем пытаться здесь воспроизводить.
Как мы уже отмечали, если и некоторая формула, и ее отрицание выводимы из некоторой системы аксиом, то эта система противоречива (несовместна). Поэтому если аксиомы формализованной системы арифметики совместимы, то ни G, ни ее отрицание не могут быть доказуемыми. Иначе говоря, если наши аксиомы непротиворечивы, то G формально неразрешима в том точном смысле, что ни G, ни ~ G не выводимы из арифметических аксиом.
3. Важность предыдущего заключения не сразу бросается в глаза. Что особенного — можно было бы задать вопрос — в том, что некоторая формула, сформулированная на арифметическом языке, оказалась неразрешимой? Но приходится признать, что из этого результата действительно вытекают чрезвычайно важные выводы. Все дело в том, что, хотя формула G и является недоказуемой, можно, как выясняется, чисто метаматематическим рассуждением установить ее истинность. Иными словами, удается показать, что формула G выражает некоторое (довольно-таки громоздко выражаемое, но тем не менее вполне определенное) свойство, с необходимостью принадлежащее всем натуральным числам (аналогично, скажем, свойству, выражаемому гораздо более простой формулой «∀ x ~ (x + 3 = 2)», интерпретируемой обычно как утверждение, что никакое натуральное число, сложенное с числом 3, не дает в сумме 2).
Приведем здесь рассуждение, устанавливающее истинность формулы G. Во-первых, в предположении непротиворечивости арифметики можно доказать, что метаматематическое утверждение
«формула „∀ x ~ Dem(x, sub(n, 13, n))“ недоказуема»
истинно. Во-вторых, такое утверждение представляется (выражается) в арифметике той самой формулой, которая в нем упоминается. В-третьих, мы вспоминаем, что истинным метаматическим утверждениям при осуществляемом посредством гёделевской нумерации отображении их в арифметику соответствуют истинные же арифметические формулы. (Именно это обстоятельство обусловливает всю плодотворность такого отображения; ситуация здесь совершенно та же, что в аналитической геометрии, где координатное «кодирование» обеспечивает перевод истинных геометрических высказываний в истинные алгебраические высказывания.) Отсюда и вытекает, что формула G, соответствующая истинному метаматематическому высказыванию, сама должна быть истинной. Следует, однако, еще раз подчеркнуть, что истинность арифметического высказывания установлена нами отнюдь не формальным выводом выражающей его формулы из аксиом, а посредством некоторого метаматематического рассуждения.
4. Теперь нам придется напомнить читателю понятие «полноты», введенное нами в заключение раздела, посвященного исчислению высказываний. Мы назвали тогда систему аксиом полной, если любое истинное предложение, выражаемое на языке данной системы, можно из них вывести. В противном случае (т. е. если не каждое истинное предложение, выразимое в данной системе, выводится из ее аксиом) система аксиом «неполна». Но мы только что как раз и установили, что G есть истинная арифметическая формула, не выводимая из арифметических аксиом, иными словами, система аксиом арифметики неполна (разумеется, в предположении непротиворечивости этой системы аксиом), более того, формальная арифметика существенно неполна: даже если добавить к ней формулу G в качестве новой аксиомы, расширенная система аксиом будет все равно недостаточна для формального вывода всех арифметических истин. Дело в том, что по отношению к пополненной таким образом системе аксиом мы можем провести в точности то же рассуждение, что и раньше, и та же конструкция даст нам новый пример предложения, истинного в расширенной арифметической системе, но не выводимого из ее аксиом, и такое предложение будет снова выражаться неразрешимой арифметической формулой. И этот поистине удивительный вывод остается в силе независимо от того, сколько раз мы ни производили бы такое расширение системы. Таким образом, мы вынуждены признать некоторую принципиальную ограниченность возможностей аксиоматического метода. Вопреки, казалось бы, самым естественным ожиданиям, запас арифметических истин оказывается столь обширным, что ни из никакой точно зафиксированной системы аксиом не удается их все формально вывести.
5. Мы подошли теперь к месту, которое можно назвать кодой это поразительной интеллектуальной симфонии — творения Гёделя. Описанные выше шаги позволили обосновать метаматематическое утверждение «если арифметика непротиворечива, то она неполна». Но Гёделю удалось доказать и нечто большее, а именно, что само условное метаматематическое утверждение (именно все утверждение в целом) изображается в формализованной арифметике некоторой доказуемой формулой.
Построить такую замечательную формулу нам будет теперь совсем нетрудно. Мы уже говорили выше (в разделе 5), что метаматематическое высказывание «арифметика непротиворечива» эквивалентно высказыванию «существует хода бы одна недоказуемая арифметическая формула». Последнее же высказывание, очевидно, представляемся в формальном (арифметическом) исчислении следующей формулой:
Ǝ y ∀ x ~ Dem(x, y). (А)
Формула эта, если выразить ее словесно, гласит: «существует по крайней мере одно натуральное число у, такое что для любого натурального x числа x и у не находятся между собой в отношении Dem». Если же интерпретировать формулу как метаматематическое высказывание, то мы получим: «существует по крайней мере одна арифметическая формула, для которой никакая последовательность формул не является ее доказательством». Таким образом, формула А как раз и представляет посылку метаматематического утверждения «Если арифметика непротиворечива, то она неполна». В то же время заключение утверждения «Она (т. е. арифметика) неполна» непосредственно вытекает из высказывания «имеется истинное арифметическое утверждение, не являющееся формально доказуемым в арифметике»; последнее же высказывание представляется в арифметическом исчислении посредством нашей старой знакомой — формулы G. Итак, условное метаматематическое высказывание «Если арифметика непротиворечива, то она неполна» представимо формулой
Ǝ у ∀ x ~ Dem(x, y) ﬤ ∀ x ~ Dem(x, sub(n, 13, n)),
которую можно было бы теперь сокращенно обозначить через «A ﬤ G». Именно для этой формулы можно установить ее формальную доказуемость, но мы не будем здесь пытаться это делать.
Покажем лишь, что формула А недоказуема. Допустим противное. Тогда, поскольку формула A ﬤ G доказуема, modus ponens позволяет нам заключить, что доказуемой должна бы быть и формула G. Но если наше исчисление непротиворечиво, G формально неразрешима, а потому, конечно, недоказуема. Таким образом, если арифметика непротиворечива, то формула А недоказуема.
Что это означает? Формула А представляет метаматематическое высказывание «Арифметика непротиворечива». Значит, если бы высказывание можно было обосновать каким нибудь рассуждением, отобразимым в последовательность формул, являющуюся доказательством в арифметическом исчислении, сама формула А была бы доказуема. Но это, как мы только что видели, невозможно, если во всяком случае считать, что арифметика непротиворечива. Мы дошли, наконец, до заключительного аккорда: нам приходится согласиться, что если арифметика непротиворечива, то непротиворечивость ее не может быть установлена никаким метаматематическим рассуждением, допускающим представление в арифметическом формализме
Надо сказать, что этот замечательный результат проведенного Гёделем анализа проблемы не исключает, однако, возможности метаматематического доказательства непротиворечивости арифметики. Из него следует лишь, что невозможно такое доказательство непротиворечивости, которое могло бы быть отображено (переведено) в формальное доказательство, проводимое внутри самой формальной арифметики.
Положение здесь очень напоминает то, которое сложилось в геометрии в связи о доказательством невозможности деления произвольного угла на три части о помощью циркуля и линейки. Доказательство это отнюдь не исключает возможности произвести искомое деление при помощи каких-либо более сильных средств. И действительно, его можно осуществить, добавив к циркулю и линейке ещё постоянный эталон длины.
На самом деле метаматематические доказательства непротиворечивости арифметики были получены; первым такое доказательство осуществил представитель школы Гильберта Герхард Генцен в 1936 г., а впоследствии было получено еще несколько доказательств того же результата. Доказательства эти имеют большую логическую ценность, заключающуюся хотя бы уже в том, что они продемонстрировали существенно новые формы метаматематических рассуждений и конструкций, а также в том, что благодаря им выяснилось, какие новые виды правил вывода надо допустить, если мы хотим установить непротиворечивость арифметики. Но все подобные доказательства уже не могут быть воспроизведены в рамках арифметического исчисления, и, поскольку все новые правила вывода уже не являются финитистскими, доказательства непротиворечивости, полученные с их помощью, никоим образом нельзя считать достижением цели, поставленной в гильбертовской программе в ее первоначальной формулировке.