Эрнст Нагель - Teopeма Гёделя

Но так как формула (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 в ней недоказуема.