Читать «Teopeмa Гёделя» онлайн - страница 23
Джеймс Рой Ньюмен
Напомним, что формула нашего исчисления — либо просто одна из букв, используемых в нем в качестве пропозициональных переменных (назовем такие формулы «элементарными»), либо же составлена из таких букв с помощью пропозициональных связок и скобок. Условимся отнести каждую элементарную формулу в один из двух непересекающихся классов, в сумме дающих все множество формул исчисления — K1 или K2. Формулы, не являющиеся элементарными, относятся к тому или иному из этих классов в силу следующих соглашений:
1) формула, имеющая вид S1 ˅ S2, принадлежит классу K2, если как S1, так и S2 принадлежат K2; в противном случае она принадлежит K1;
2) формула, имеющая вид S1 ﬤ S2, принадлежит классу K2, если S1 принадлежит K1, a S2 принадлежит K2; в противном случае она принадлежит K1;
3) формула, имеющая вид S1 · S2, принадлежит классу K1, если как S1, так и S2 принадлежат K1; в противном случае она принадлежит K2;
4) формула, имеющая вид ~ S, принадлежит классу K2, если S принадлежит K1; в противном случае она принадлежит K1.
Теперь мы определяем свойство «быть тавтологией»: формула есть тавтология тогда и только тогда, когда она принадлежит классу K1 независимо от того, какому из классов K1 и K2 принадлежит любая из входящих в нее элементарных формул (т. е. переменных). Ясно, что это определение не использует никакой модели или интерпретации нашей системы. Мы можем установить, является ли какая-либо данная формула тавтологией, просто исследуя ее строение с точки зрения выполнения приведенных выше четырех условий.
Такая проверка приводит к выводу, что каждая из четырех аксиом является тавтологией. Процедура такой проверки сводится к составлению таблицы, в которой учитываются все возможные варианты соотнесения элементарных компонент данной аксиомы к любому из двух классов, K1 и K2. Просматривая последовательно строки такой таблицы, мы можем определить для каждого из возможных распределений «значений» (т. е. принадлежности классам K1 и K2) элементарных формул (т. е. попросту переменных), какому из классов принадлежит каждая неэлементарная «подформула» данной формулы и вся рассматриваемая формула в целом. Возьмем, например, первую аксиому. Таблица для нее состоит из трех столбцов: первый из них соответствует единственной ее элементарной компоненте «p», второй — неэлементарной подформуле «(p ˅ p)», а третий — всей формуле «(p ˅ p) ﬤ p». В каждом из столбцов указаны классы, которым принадлежат соответствующие формулы при данных распределениях значений переменных по этим классам. Вот как выглядит таблица для первой аксиомы:
p p˅p (p˅p)ﬤp
K 1 K 1 K 1
K 2 K 2 K 1
В первом столбце таблицы приведены возможные значения единственной элементарной компоненты рассматриваемой аксиомы, во втором — соответствующие значения неэлементарной компоненты аксиомы (согласно условию (1), в третьем — значения самой аксиомы (согласно условию (2)). Из последнего столбца сразу видно, что первая аксиома принадлежит классу K1 всегда, независимо от того, к какому классу отнесена ее элементарная компонента. Значит, первая аксиома является тавтологией.