Teopeмa Гёделя - Нагель Эрнст. Страница 16

Гёдель далее показал, что некоторый частный случай этой формулы является формально недоказуемым. Чтобы получить формулу, мы будем исходить из следующей формулы:

∀ 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, соответствующая истинному метаматематическому высказыванию, сама должна быть истинной. Следует, однако, еще раз подчеркнуть, что истинность арифметического высказывания установлена нами отнюдь не формальным выводом выражающей его формулы из аксиом, а посредством некоторого метаматематического рассуждения.