Teopeмa Гёделя

Но для того чтобы наше доказательство непротиворечивости было не относительным, а абсолютным, нам придется дать такое определение понятия тавтологии, которое не зависело бы непосредственно от понятия истины (в свою очередь, подразумевающего некоторую интерпретацию), а было бы дано в чисто формальных, структурных терминах.

Напомним, что формула нашего исчисления — либо просто одна из букв, используемых в нем в качестве пропозициональных переменных (назовем такие формулы «элементарными»), либо же составлена из таких букв с помощью пропозициональных связок и скобок. Условимся отнести каждую элементарную формулу в один из двух непересекающихся классов, в сумме дающих все множество формул исчисления — K₁ или K₂. Формулы, не являющиеся элементарными, относятся к тому или иному из этих классов в силу следующих соглашений:

1) формула, имеющая вид S₁ S₂, принадлежит классу K₂, если как S₁, так и S₂ принадлежат K₂; в противном случае она принадлежит K₁;

2) формула, имеющая вид S₁ S₂, принадлежит классу K₂, если S₁ принадлежит K₁, a S₂ принадлежит K₂; в противном случае она принадлежит K₁;

3) формула, имеющая вид S₁ · S₂, принадлежит классу K₁, если как S₁, так и S₂ принадлежат K₁; в противном случае она принадлежит K₂;

4) формула, имеющая вид ~ S, принадлежит классу K₂, если S принадлежит K₁; в противном случае она принадлежит K₁.

Теперь мы определяем свойство «быть тавтологией»: формула есть тавтология тогда и только тогда, когда она принадлежит классу K₁ независимо от того, какому из классов K₁ и K₂ принадлежит любая из входящих в нее элементарных формул (т. е. переменных). Ясно, что это определение не использует никакой модели или интерпретации нашей системы. Мы можем установить, является ли какая-либо данная формула тавтологией, просто исследуя ее строение с точки зрения выполнения приведенных выше четырех условий.

Такая проверка приводит к выводу, что каждая из четырех аксиом является тавтологией. Процедура такой проверки сводится к составлению таблицы, в которой учитываются все возможные варианты соотнесения элементарных компонент данной аксиомы к любому из двух классов, K₁ и K₂. Просматривая последовательно строки такой таблицы, мы можем определить для каждого из возможных распределений «значений» (т. е. принадлежности классам K₁ и K₂) элементарных формул (т. е. попросту переменных), какому из классов принадлежит каждая неэлементарная «подформула» данной формулы и вся рассматриваемая формула в целом. Возьмем, например, первую аксиому. Таблица для нее состоит из трех столбцов: первый из них соответствует единственной ее элементарной компоненте «p», второй — неэлементарной подформуле «(p p)», а третий — всей формуле «(p  p) p». В каждом из столбцов указаны классы, которым принадлежат соответствующие формулы при данных распределениях значений переменных по этим классам. Вот как выглядит таблица для первой аксиомы:

p pp (pp)p

K₁ K₁ K₁

K₂ K₂ K₁

В первом столбце таблицы приведены возможные значения единственной элементарной компоненты рассматриваемой аксиомы, во втором — соответствующие значения неэлементарной компоненты аксиомы (согласно условию (1), в третьем — значения самой аксиомы (согласно условию (2)). Из последнего столбца сразу видно, что первая аксиома принадлежит классу K₁ всегда, независимо от того, к какому классу отнесена ее элементарная компонента. Значит, первая аксиома является тавтологией.

А вот такая же таблица для второй аксиомы:

p q pq р(рq)

K₁ K₁ K₁ K₁

K₁ K₂ K₁ K₁

K₂ K₁ K₁ K₁

K₂ K₂ K₂ K₁

В первых двух столбцах таблицы указаны все возможные распределения двух элементарных компонент аксиомы по двум классам, в третьем — соответствующие значения ее неэлементарной компоненты (согласно условию (1)), в четвертом — значения самой аксиомы. И здесь из рассмотрения последнего столбца таблицы сразу видно, что аксиома является тавтологией. Точно так же устанавливается тавтологичность остальных двух аксиом.

Докажем теперь, что свойство «быть тавтологией» наследственно относительно применений правила modus ponens. (Доказательство его наследственности относительно правила подстановки предоставляется читателю.) Пусть формулы S₁ и S₁ S₂ — тавтологии; нам надо доказать, что тогда и формула S₂ есть тавтология. Допустим, что S₂ не является тавтологией. В таком случае для хотя бы одного распределения элементарных компонент этой формулы по классам K₁ и K₂ она принадлежит классу K₂. Но, по предположению, S₁ является тавтологией, т. е. принадлежит классу Ki при любых распределениях своих элементарных компонент, в том числе и при том, при котором S₂ принадлежит K₂[7]. Но тогда при этом распределении формула S₁ S₂ должна (в силу второго условия) принадлежать классу K₂, что, однако, противоречит предположению о тавтологичности S₁ S₂. Противоречие показывает, что S₂ должна быть тавтологией. Таким образом, тавтологичность формулы есть свойство наследственное, т. е. передаваемое от посылок правила modus ponens к его заключению.