Арифметизация метаматематики

 

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

Рассмотрим такой популярный пример. При входе в большие универсальные магазины покупателям иногда выдают билетики с номерами, определяющими порядок дальнейшего обслуживания покупателей. Достаточно бывает посмотреть на эти номера, чтобы ответить на вопросы, сколько покупателей уже обслужено, сколько ожидает своей очереди, кто за кем стоит, сколько всего покупателей было с утра в магазине и т. п. Если, скажем, миссис Смит имеет номер 37, а миссис Браун – номер 53, то вместо того чтобы объяснить миссис Браун, что она должна пропустить вперед миссис Смит, достаточно обратить ее внимание на то, что 37 меньше, чем 53.

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

Проиллюстрируем все эти общие замечания одним элементарным примером. Возьмем первую аксиому исчисления высказываний, являющуюся, кстати, аксиомой и рассматриваемого сейчас логико‑арифметического исчисления: «(p ˅ p) ﬤ p». Ее гёделевский номер, равный, как легко убедиться, числу 2⁸ × 3¹¹ × 5² × 7^{11^2} × 11⁹ × 13⁸ × 17¹¹ мы обозначим буквой а. Рассмотрим теперь формулу «(p ˅ p)», гёделевский номер которой, равный числу 2⁸ × 3^{11^2} × 5² × 7^{11^2} × 11⁹, обозначим через 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 = 2 ^m × 3 ⁿ. Самый беглый анализ приводит нас к выводу, что здесь вводится вполне определенное, хотя и далеко не простое, арифметическое отношение между k (будем для простоты считать его номером всего доказательства) и n – гёделевским номером заключения этого доказательства.) Мы будем записывать отношение между числами x и z посредством формулы «Dem(x, z)»[15] напоминающей нам самим своим обликом о том метаматематическом утверждении, которому она соответствует (а именно, об утверждении «Последовательность формул, имеющая гёделевский номер 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») цифру[16], обозначающую число m, мы получим в результате формулу «Ǝ x (x = sm)», выражающую утверждение, согласно которому существует такое число x, что это ж непосредственно следует за числом m.

Последняя формула также имеет некоторый гёделевский номер, который совсем нетрудно вычислить. Но вместо того чтобы фактически производить это вычисление, мы можем совершенно однозначно охарактеризовать этот номер чисто метаматематическим образом, говоря, что это гёделевский номер формулы, получаемый из формулы, имеющей гёделевский номер m, подстановкой вместо входящей в эту формулу переменной с гёделевским номером 13 цифры «m». Такая метаматематическая характеристика однозначно определяет некоторое число, являющееся некоторой определенной функцией от чисел m и 13, причем сама эта функция может быть выражена средствами нашей формализованной арифметической системы. Значит, и само число можно выразить внутри нашего исчисления. Обозначим его через «sub(m, 13, m)», напоминая тем самым, что речь идет о гёделевском номере формулы, полученной из формулы, имеющей гёделевский номер m, подстановкой[17] вместо входящей в нее переменной с гёделевским номером 13 цифры, обозначающей число m. Вообще, через «sub(y, 13, y)» мы будем обозначать теперь арифметическую формулу, выражающую внутри арифметического исчисления метаматематическую характеристику: «гёделевский номер формулы, получаемой из формулы, имеющей гёделевский номер y, подстановкой вместо входящей в нее переменной, имеющей гёделевский номер 13, цифры, обозначающей число „ y “». Если в выражение «sub(y, 13, y)» мы подставим теперь вместо «y» какую‑нибудь определенную цифру, скажем, цифру, обозначающую число m, или выражение 243 000 000, то получающееся в результате выражение также будет обозначать некоторое определенное натуральное число, являющееся притом гёделевским номером некоторой определенной формулы.

У читателя не раз мог возникнуть вопрос, почему, собственно, мы говорили сейчас не просто о «числе y», а – столь вычурно и длинно! – о «цифре, обозначающей y». Впрочем, сама форма вопроса уже отчасти подсказывает ответ. Мы ведь уже упоминали о важном различии между понятиями «число» и «цифра». Цифра – это некоторый знак, т. е. выражение языка, которое можно записывать, стирать, зачеркивать, повторять и т. д. и т. п. Число же – это то, именем (или названием, обозначением) чего является обозначающая его цифра; само по себе число нельзя записать, стереть, зачеркнуть, повторить.

Скажем, когда мы говорим, что 10 – число пальцев на обеих руках, то мы характеризуем этой фразой некоторое «свойство» множества наших пальцев – свойство, которое, разумеется, «цифрой» никак не назовешь. Но число 10 может записываться как арабскими цифрами: «10», так и римскими цифрами (т. е. прописными латинскими буквами) «X»; эти имена сами по себе, конечно, различны, хотя обозначают они одно и то же число. Так вот, когда мы производим подстановку вместо числовой переменной (которая сама есть просто знак, буква), то мы ставим вместо одного знака другой знак. Мы не можем подставить вместо знака число – ведь число, являющееся некоторым свойством (или, как иногда говорят, понятием), вообще не есть что‑то такое, что можно непосредственно нанести на бумагу. Итак, вместо числовой – а лучше сказать, цифровой! – переменной мы подставляем именно цифру (или цифровое выражение, скажем «s 0» или «7 + 5»), а не число. Именно поэтому мы выше говорили о подстановке цифры (обозначающей число) y, а не самого числа у в интересующее нас метаматематическое выражение.

Читатель может далее поинтересоваться, какое же число обозначается выражением «sub(y, 13, y)», если формула, имеющая гёделевский номер у, не содержит переменной, имеющей гёделевский номер 13, т. е. попросту, если формула не содержит переменной «y». Скажем, sub(243 000 000, 13, 243 000 000) есть гёделевский номер формулы, полученной из формулы, имеющей гёделевский номер 243 000 000, подстановкой вместо переменной «y» цифры[18] 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)» или «3² + 4² = 5²») есть формула и является схемой (или формой) некоторого утверждения; в отличие от него запись «sub(y, 13, y)» (подобно «f (x)» или «(7 × 5) + 8») является лишь схемой (формой) имени некоторого числа, но не формулой.

 

Изложение доказательств

 

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

Прежде всего Гёдель показывает (1), как построить арифметическую формулу G, представляющую («кодирующую») метаматематическое высказывание «формула G недоказуема». Иначе говоря, формула G гласит о себе самой, что она недоказуема.

Идея построения такой формулы G по существу заимствована из рассуждения, приводящего к парадоксу Ришара. В этом парадоксе, как мы помним, выражению «ришарово число» сопоставляется некоторое число n, после чего рассматривается предложение «n есть ришарово число». В гёделевском же доказательстве формуле G сопоставляется некоторое число h, причем это делается так, чтобы оно соответствовало предложению «Формула, которой сопоставлено число h, недоказуема». Но затем Гёделю удается показать (2), что формула G доказуема тогда и только тогда, когда доказуемо ее формальное отрицание ~ G. И этот шаг доказательства аналогичен соответствующему этому рассуждению в парадоксе Ришара, где доказывается, что п есть ришарово число в том и только в том случае, если п не есть ришарово число. Но если некоторая формула и ее отрицание доказуемы, то арифметическое исчисление, в котором возможны оба доказательства, противоречиво.

Значит, если это исчисление непротиворечиво, то как G, так и ~ G не выводимы из аксиом арифметики. Следовательно, если арифметика непротиворечива, то G является формально неразрешимой формулой. Далее Гёдель доказывает (3), что хотя формула G формально недоказуема, она является тем не менее истинной арифметической формулой. Она является истинной в том смысле, что утверждает про каждое натуральное число, что оно обладает некоторым арифметическим свойством, причем свойство это такого рода, что наличие его у каждого натурального числа можно действительно подтвердить посредством прямой проверки (4). Поскольку формула G, будучи истинной, является формально недоказуемой, система аксиом арифметики неполна. Иными словами, из аксиом арифметики нельзя вывести все истинные стремления арифметики. Более того, Гёдель доказал су щественную неполноту[19] арифметики: даже если присоединить к ее аксиоматике новые аксиомы, обеспечивающие выводимость истинной формулы 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 г., а впоследствии было получено еще несколько доказательств того же результата. Доказательства эти имеют большую логическую ценность, заключающуюся хотя бы уже в том, что они продемонстрировали существенно новые формы метаматематических рассуждений и конструкций, а также в том, что благодаря им выяснилось, какие новые виды правил вывода надо допустить, если мы хотим установить непротиворечивость арифметики. Но все подобные доказательства уже не могут быть воспроизведены в рамках арифметического исчисления, и, поскольку все новые правила вывода уже не являются финитистскими, доказательства непротиворечивости, полученные с их помощью, никоим образом нельзя считать достижением цели, поставленной в гильбертовской программе в ее первоначальной формулировке.

 

 

Заключительные замечания

 

Выводы, к которым пришел Гёдель, имеют ряд важных следствий, безусловно, не оцененных еще в достаточной мере. Выводы эти показывают прежде всего, что решение задачи отыскания для каждой дедуктивной системы (и в частности, для системы, в которой можно было бы выразить всю совокупность арифметических теорем) абсолютного доказательства непротиворечивости, удовлетворяющего предложенным Гильбертом «финитистским» критериям, если и не является логически невозможным (хотя бы в силу некоторой неопределенности самого понятия «финитности»), то во всяком случае в высшей степени маловероятно. Выводы эти показывают также, что имеется бесконечно много истинных арифметических предложений, которые нельзя формально вывести из произвольной данной системы аксиом посредством некоторого точного перечня правил вывода. Отсюда следует, что аксиоматический подход к арифметике натуральных чисел, кроме всего прочего, не в состоянии охватить всю область истинных арифметических суждений. Отсюда также вытекает, что то, что мы понимаем под процессом математического доказательства, не сводится к использованию аксиоматического метода. Формализованные аксиоматические процедуры доказательств основаны на некотором множестве выделенных и фиксированных с самого начала аксиом и правил вывода. Как видно уже из самих рас‑ суждений, использованных в гёделевских доказательствах, изобретательность математиков в деле отыскания новых правил доказательства не поддается никаким априорным ограничениям. Таким образом, совершенно безнадежно рассчитывать на то, что понятию убедительного математического доказательства можно придать раз навсегда четко очерченные логические формы. В связи со всем этим возникает целый ряд новых проблем, далеко еще не решенных и слишком трудных для подробного рассмотрения их здесь – независимо от того, можно ли рассчитывать на то, что понятия математической и логической истинности можно исчерпывающим образом определить или же (мнение, к которому стал склоняться сам Гёдель) такое определение находится в компетенции безоговорочного философского «реализма» платонистского толка.

 

^{Платонизм (реализм) – доктрина, согласно которой математика не творит и не придумывает рассматриваемые в ней «объекты», а открывает их, подобно тому как, например, Колумб открыл Америку. Таким образом, согласно этой точке зрения, объекты должны в некотором смысле «существовать» до их «открытия». Платонистская доктрина не предполагает, что объекты математического исследования находятся между собой в пространственно‑временных отношениях. Обьекты эти суть отделенные от материальных оболочек вечные Формы, прототипы, населяющие особые абстрактные Сферы, доступные лишь Интеллекту. Согласно такой концепции треугольные или круглые формы физических предметов, данные нам в ощущениях, сами по себе вовсе не являются объектами математического исследования. Эти пространственные формы суть лишь несовершенные воплощения единого «совершенного» Треугольника или «совершенного» Круга, вечных, неизменных, лишь частично проявляющихся в облике материальных предметов и являющихся подлинными объектами рассмотрения математической мысли. Сам Гёдель обнаружил близость к такого рода воззрениям, заявляя, «что допущение… классов и общих понятий столь же законно, как и допущение физических тел… и имеются столь же высокие основания верить в их существование» (из работы Гёделя «Russell's, Mathematical Logic» в книге The Philosophy of Bertrand Russei. Evanston; Chicago, 1944. C. 137). (Данная здесь авторами характеристика «платонизма» довольно‑таки поверхностна, а традииионная квалификаиия Гёделя как платониста далеко не бесспорна. Впрочем, тема эта далеко выходит за рамки настоящей книги. См., например: Френкель А., Бар ‑ Хиллел И}