Теорема Гёделя

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

Напомним, что формула нашего исчисления — либо просто одна из букв, используемых в нем в качестве пропозициональных переменных (назовем такие формулы «элементарными»), либо же составлена из таких букв с помощью пропозициональных связок и скобок. Условимся отнести каждую элементарную формулу в один из двух непересекающихся классов, в сумме дающих все множество формул исчисления — 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 p˅p (p˅p)ﬤp

K₁ K₁ K₁

K₂ K₂ K₁

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

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

p q p˅q рﬤ(р˅q)

K₁ K₁ K₁ K₁

K₁ K₂ K₁ K₁

K₂ K₁ K₁ K₁

K₂ K₂ K₂ K₁

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