Эрнст Нагель - Teopeма Гёделя

K 1 K 1 K 1 K 1

K 1 K 2 K 1 K 1

K 2 K 1 K 1 K 1

K 2 K 2 K 2 K 1

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

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

Теперь нам остается указать пример формулы нашего исчисления, не являющейся тавтологией. Такова, например, формула « p ˅ q », принадлежащая классу K 2, если обе ее компоненты (« p » и « q ») принадлежат этому классу [8] Конечно, еще более простой пример — формула, состоящая из одной-единственной переменной p. — Прим. перев. . (В переводе на содержательный язык: высказывание «„ p “ или q “» ложно, если ложны оба входящие в его состав высказывания « p » и « q ».)

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

Легко видеть, что классы K 1и K 2можно понимать соответственно как класс истинных и класс ложных высказываний. Мы, однако, намеренно воздерживались от этой терминологии в ходе самого доказательства (хотя не раз, комментируя отдельные ее шаги, подразумевали возможность ее использования), чтобы подчеркнуть то обстоятельство, что наше доказательство в принципе не нуждается в ссылках на какую бы то ни было интерпретацию формул исчисления высказываний, хотя понять его как следует легче именно при таком «переводе» на содержательный язык.

В заключение следует сказать еще об одной важной проблеме, относящейся к исчислению высказываний. Мы установили, что каждая теорема этого исчисления является тавтологией, т. е. — если выражаться в терминах неоднократно упоминаемой выше содержательной интерпретации — логической истиной, «законом логики». Естественно задать в известной мере и обратный вопрос: каждое ли логически истинное высказывание, выразимое на языке нашего исчисления (т. е. каждая ли тавтология), является теоремой данного исчисления (выводимой из его аксиом)? И на этот вопрос можно дать положительный ответ; но доказательство такого факта слишком длинно, чтобы приводить его здесь. Но нам хотелось бы обратить внимание на одно обстоятельство, не имеющее отношения к самому доказательству: дело в том, что результат этот свидетельствует о достаточности выбранных нами аксиом для получения всех тавтологичных формул — иными словами, всех логически истинных высказываний, выразимых на языке исчисления высказываний. Системы аксиом, обладающие таким свойством, принято называть «полными».

Вопрос о полноте той или иной системы аксиом представляет, как правило, большой интерес. В самом деле, основным стимулом для аксиоматизации различных разделов математики бывает стремление найти подходящий перечень исходных допущений, из которых затем можно было бы вывести все истинные предложения данной области. Скажем, когда Евклид формулировал некоторую аксиоматизацию элементарной геометрии, он старался отобрать аксиомы таким образом, чтобы из них можно было вывести все истинные геометрические утверждения, не только уже известные в то время, но в принципе и любые другие, которые можно было бы научиться доказывать когда-либо в будущем.