Эрнст Нагель - Teopeма Гёделя
Перейдем, наконец, к описанию идеи самого доказательства теоремы Гёделя. Вначале мы дадим совсем простой его набросок, разделив доказательство на пять основных шагов.
Прежде всего Гёдель показывает (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). Гёдель же получил несколько более слабый результат, позволяющий, впрочем, получить все интересующие нас важные выводы.
