У интуиции есть своя логика. Гёдель. Теоремы о неполноте - [30]

код которого — само число m.

— Шаг 6: Теперь докажем синтаксически, что G недоказуемо. Предположим, от противного, что G доказуемо.

Тогда существует доказательство G, и ему соответствует код, к примеру k. Следовательно, высказывание

"k — код доказательство высказывания с кодом m"

истинное (поскольку m — код G, a k — код доказательства G) и, кроме того, финитное, поскольку можно проверить его истинность за конечное число шагов (можно проверить алгоритмически, что k — действительно код доказательства G). Так как оно финитное и истинное, то, по гипотезе, высказывание доказуемо. Тогда одно из правил логики позволяет нам сделать вывод, что также доказуемо высказывание

"Существует у, являющееся кодом доказательства высказывания с кодом т".

Схема доказательства того, что G недоказуемо.

Мы исходим из предположения, что G доказуемо. Стрелки показывают последовательные выводы, которые получаются из этого предположения, пока мы не приходим к заключению, что отрицание G также доказуемо. Это содержит противоречие, следовательно G не может быть доказуемо.

Если сравнить последнее высказывание с тем, как мы формулировали G, оказывается ясным, что оно соответствует не-G. Получается, мы говорим, что G и не-G одновременно доказуемы. Мы пришли к противоречию. Оно возникает из предположения, что G доказуемо, следовательно делаем вывод: G недоказуемо (см. схему на предыдущей странице).

— Шаг 7: Теперь докажем, что не-G также недоказуемо. Снова сделаем это от противного. Предположим, что не-G доказуемо, и придем к противоречию. Так как множество аксиом непротиворечиво, если не-G доказуемо, то G не может быть доказуемым.

ОМЕГА-НЕПРОТИВОРЕЧИВОСТЬ

Когда мы показали, что высказывание не-G недоказуемо, мы основывались на том факте, что если для свойства Р верно

высказывание "1 не удовлетворяет свойству Р" доказуемо,

высказывание "2 не удовлетворяет свойству Р" доказуемо,

высказывание "3 не удовлетворяет свойству Р" доказуемо

...и так далее,

то высказывание "существует некое х, удовлетворяющее свойству Р" недоказуемо. Но так ли это? Сначала рассмотрим этот вопрос семантически. Предположим, что Р — арифметическое свойство, для которого выполняется:

высказывание "1 не удовлетворяет свойству Р" истинно,

высказывание "2 не удовлетворяет свойству Р" истинно,

высказывание "3 не удовлетворяет свойству Р" истинно

...и так далее,

то есть для любого числа л справедливо, что свойство Р не выполняется. Тогда ясно, что высказывание "существует некоторый х, для которого выполняется свойство Р" ложно (поскольку мы сказали, что ни для 1, ни для 2, ни для 3 и так далее свойство не выполняется). Но оно ложно, если мы говорим о мире натуральных чисел, и может быть истинным, когда говорим о другом мире. Например, если свойство Р — это "х² = 2", а мы говорим о мире чисел, образованных на основе √2, то для 1 свойство не выполняется, как и для 2, 3 и так далее. Но для √2 свойство Р выполняется. Что же происходите синтаксической точки зрения? Рассмотрим снова свойство Р, но теперь предположим, что:

"1 не удовлетворяет свойству Р" доказуемо,

"2 не удовлетворяет свойству Р" доказуемо,

"3 не удовлетворяет свойству Р" доказуемо

...и так далее.

Верно ли, что "существует некоторое х, которое удовлетворяет свойству Р" недоказуемо? Поскольку в некоторых мирах это истинно, мы не можем точно утверждать, что это никогда не будет доказуемо. В доказательстве того, что не-G недоказуемо, имеется логический пробел, поскольку мы не можем утверждать, что это высказывание не окажется доказуемым. Чтобы справиться с этой проблемой, Гёдель ввел синтаксическое понятие омега-непротиворечивости. Множество аксиом омега-непротиворечиво, если притом что каждое из высказываний "1 не удовлетворяет свойству Р", "2 не удовлетворяет свойству Р", и так далее доказуемо, "существует некоторый х, который удовлетворяет свойству Р" недоказуемо (в какой-то степени это синтаксически вынуждает считать, что мы имеем в виду мир натуральных чисел). Следовательно, в начало синтаксического изложения первой теоремы Гёделя, где говорится, что множество аксиом непротиворечиво, следовало бы добавить "омега-непротиворечиво".

Вклад Россера

К счастью, в 1936 году американский логик Джон Б. Россер в статье объемом всего две страницы изменил рассуждение Гёделя так, чтобы оно было справедливо и при гипотезе непротиворечивости. Благодаря Россеру в изложении теоремы Гёделя можно опустить упоминание омега-непротиворечивости, и она может быть записана в том виде, в каком мы привели ее в тексте. Изменение, внесенное Россером в рассуждение Гёделя, состояло в том, чтобы заменить самореферетное высказывание "это высказывание недоказуемо" другим: "если это высказывание доказуемо, то также доказуемо и его отрицание".

Это означает, что не существует доказательства G; следовательно, ни одно число не является кодом доказательства G: число 1 — не код доказательства G, так же как 2,3 и так далее.

Получается, что высказывания

"1 — не код доказательства высказывания с кодом m",

"2 — не код доказательства высказывания с кодом m", "k — не под доказательства высказывания с кодом т" и так далее являются финитными истинными высказываниями. Раз они финитные и истинные, они доказуемы. Следовательно,