dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

8.2. Вторая теорема Гёделя о неполноте.

к Оглавлению

За доказательством 2-й т. Гёделя о неполноте много лет принято отсылать к двухтомнику Д. Гильберта, П. Бернайса «Основания математики». Или приводить свойства для предикатов доказуемости и уже на их базе доказывать теорему. Но с предикатами доказуемости без названного двухтомника не понятно, почему в одном свойстве имеет место выводимость, а в другом – импликация.

«Основания математики» – отличная книга, но там, в основном, даны сведения для профессионалов, которые не являются обязательными для принципиального понимания доказательства теорем Гёделя. А теоремы Гёделя стали уже чуть ли не частью культурного кода широкого слоя непрофессионалов. Поэтому пора дать компактное доказательство всех принципиальных моментов 2-й теоремы Гёделя.

Так вот, идея 2-й т. Гёделя в том, что утверждение G из 1-й т. Гёделя в случае своего доказательства позволяет доказать и противоречие. В качестве «любимого» у математиков обычно выступает противоречие 1=0, и мы не будем нарушать традицию. 

То есть, из доказуемости G следует доказуемость 1=0. Это импликация (вот тут принципиальный момент, который надо будет раскрыть в доказательстве) PG») P(«1=0»). Из импликации по принципу контрапозиции получим ~P(«1=0») ~PG»). Из последнего выражения вместе с свойством для G:

~PG») ó G, получим:

~P(«1=0») G

Таким образом, если бы в теории была доказана непротиворечивость, то было бы доказано и утверждение Гёделя из 1-й теоремы Гёделя, а это означает противоречивость. Как и было обещано выше в 1-й т. Гёделя – нам потребовалась только 1-я часть 1-й т. Гёделя для доказательства 2-й. Итак:

Вторая теорема Гёделя о неполноте.

Если в рамках теории имеется доказательство её непротиворечивости, то теория противоречива.

Доказательство.

Начиная с выражения PG») P(«1=0») у нас имеется вывод до конца доказательства – см. выше. Значит, нам осталось доказать только PG») 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(…, …, …). Но для программиста такое доказательство, думаю, вполне понятно.


Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments