к Оглавлению
За доказательством 2-й т. Гёделя о неполноте много лет принято отсылать к двухтомнику Д. Гильберта, П. Бернайса «Основания математики». Или приводить свойства для предикатов доказуемости и уже на их базе доказывать теорему. Но с предикатами доказуемости без названного двухтомника не понятно, почему в одном свойстве имеет место выводимость, а в другом – импликация.
«Основания математики» – отличная книга, но там, в основном, даны сведения для профессионалов, которые не являются обязательными для принципиального понимания доказательства теорем Гёделя. А теоремы Гёделя стали уже чуть ли не частью культурного кода широкого слоя непрофессионалов. Поэтому пора дать компактное доказательство всех принципиальных моментов 2-й теоремы Гёделя.
Так вот, идея 2-й т. Гёделя в том, что утверждение G из 1-й т. Гёделя в случае своего доказательства позволяет доказать и противоречие. В качестве «любимого» у математиков обычно выступает противоречие 1=0, и мы не будем нарушать традицию.
То есть, из доказуемости G следует доказуемость 1=0. Это импликация (вот тут принципиальный момент, который надо будет раскрыть в доказательстве) P(«G») ⇒ P(«1=0»). Из импликации по принципу контрапозиции получим ~P(«1=0») ⇒ ~P(«G»). Из последнего выражения вместе с свойством для G:
~P(«G») ó G, получим:
~P(«1=0») ⇒ G
Таким образом, если бы в теории была доказана непротиворечивость, то было бы доказано и утверждение Гёделя из 1-й теоремы Гёделя, а это означает противоречивость. Как и было обещано выше в 1-й т. Гёделя – нам потребовалась только 1-я часть 1-й т. Гёделя для доказательства 2-й. Итак:
Вторая теорема Гёделя о неполноте.
Если в рамках теории имеется доказательство её непротиворечивости, то теория противоречива.
Доказательство.
Начиная с выражения P(«G») ⇒ P(«1=0») у нас имеется вывод до конца доказательства – см. выше. Значит, нам осталось доказать только P(«G») ⇒ P(«1=0»).
Тут мы и воспользуемся ради упрощения тем, что P_0(x, y) у нас – алгоритм, а не предикат. И за счет этого вместо импликаций будем иметь дело на начальном этапе с равенствами, что понятно в наше время очень многим (программистам, например). А затем по теореме Дедукции перейдём к импликации.
Если у нас есть доказательство k для G, то мы можем достроить вывод до противоречия и получить в результате доказательства 1=0. Это значит, что есть алгоритм f(k), который вернет по k доказательство для 1=0. И тогда P_0(«1=0», f(k)) вернет 1. Запишем это в виде равенства:
P_0(«1=0», f(y)) = if[ P_0(«G», y), 1, … ]
Где алгоритм if[x1, x2, x3]– вычисляет результат работы алгоритма x1, и если он вернет 1, то if[x1, x2, x3] возвращает результат работы алгоритма x2, а иначе возвращает результат работы x3. На месте многоточия (место x3) стоит P_0(«1=0», f(y)) – но не будем его писать ради краткости. Равенство правильное, потому что результат работы правой сторона равенства отличается от результата работы левой стороны P_0(«1=0», f(y)) только если в переменой y – доказательство для G, но в этом случае левая часть равенства P_0(«1=0», f(y)) тоже вернет 1 – как и правая часть равенства.
Начнем процедуру из теоремы Дедукции. В качестве гипотезы берём P_0(«G», y)=1. Теперь можем считать, что это равенство истинное, можем пользоваться этим, но в конце процедуры должны будем поставить эту гипотезу в качестве посылки импликации, а заключением будет результат процедуры.
Из P_0(«1=0», f(y)) = if[ P_0(«G», y), 1, … ] и Гипотезы P_0(«G», y)=1:
P_0(«1=0», f(y)) = if[1, 1, … ]. Так как по свойствам if[x1, x2, x3] имеем if[1, 1, … ] = 1, то:
P_0(«1=0», f(y)) = 1
Завершаем процедуру из теоремы Дедукции и получаем истинную импликацию:
(P_0(«G», y)=1) ⇒ (P_0(«1=0», f(y)) = 1). Поменяем переменную, чтобы использовать переменную y с кванторами:
(P_0(«G», k)=1) ⇒ (P_0(«1=0», f(k)) = 1).
Разумеется, я тут не разбирал алгоритм (условный оператор) if(…, …, …). Но для программиста такое доказательство, думаю, вполне понятно.
