3. Второе доказательство

В этом пункте будет доказано обещанное ранее более сильное утверждение .

Начать следует с набора интуитивно ясных определений, конкретизирующих как семантический, так и синтаксический аспекты понятия «противоречивость».

Определение 3.2. (1) Множество Р булевых формул называется совместным, если существует набор значений переменных, входящих в них, при котором все формулы, входящие в Р, истинны.

(2) В противном случае множество Р называется несовместным.

Это – семантическое определение противоречивости (в формулы семейства Р нельзя подставить что-то такое, что сделает их истинными одновременно, некоторая формула обязательно окажется ложной и будет противоречить в этом смысле тем, которые случайно оказались истинными; формулы семейства Р, тем самым, противоречат друг другу). Заметим, что формула q является тавтологией тогда и только тогда, когда набор формул (состоящий из одной формулы, а что тут такого!? ) является несовместным. Кроме того, несовместность множества формул можно записать коротко и элегантно: , поскольку О – одна из формул, которые никогда не бывают истинными (то есть, если все формулы семейства Р по какому-то недосмотру показались одновременно истинными, то и формула О окажется истинной, а это невозможно).

(3) Формула q называется выполнимой, если соответствующая булева функция не есть тождественная ложь. Заметим, что формула является тавтологией тогда и только тогда, когда её отрицание не является выполнимой формулой.

(4) Множество формул Р называется противоречивым, если существует формула q, такая, что и . Это – синтаксическое определение противоречивости. Как уже отмечалось, из противоречивого множества формул можно в три строчки вывести всё что угодно. Например, формулу О:

(аксиома (А9));

(МР);

О (МР).

Верно и обратное: как только формула О доказана, становится возможным доказать что угодно, в том числе и два противоположных утверждения (тривиально используя аксиому (А12)). Поэтому для констатации противоречивости множества можно использовать запись . Оказывается, в исчислении высказываний семантическая противоречивость равносильна синтаксической.

Теорема 3.3. .

Доказательство непротиворечивости совместного множества совсем просто: в противном случае на наборе аргументов, обращающем в истины все формулы множества Р, обязана была бы оказаться истинной и формула О, а это невозможно.

Доказательство обратного утверждения существенно сложнее. Пусть Р – непротиворечивое множество формул. Требуется предъявить набор значений входящих в них переменных, на котором все формулы из Р истинны. Иногда соответствующее значение переменной очевидно. Если переменная x такова, что , то из предыдущего соображения ясно, что эта переменная в хорошем наборе должна быть истинна. Если же , то эта переменная должна быть ложна. Осталось:

а) как-то определить значения остальных переменных;

б) после этого не забыть убедиться, что полученный набор действительно является «хорошим»: отмеченные условия на значения переменных необходимы, но, возможно, не достаточны!

Пункт а исполняется очень радикально . За счёт увеличения множества Р удаётся добиться того, чтобы вообще любая формула q обладала свойством: либо , либо (хотя нам-то это свойство, повторимся, нужно только для формул, состоящих из одной-единственной переменной ). При этом предлагается не скромничать, и если , то немедленно добавлять формулу q в множество Р, что, конечно, не лишит его свойства непротиворечивости (почему?), и писать (если это удобно) .

Определение 3.3. Множество формул называется полным, если для любой формулы q либо , либо .

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

Лемма 3.4. Для любого непротиворечивого множества формул Р существует непротиворечивое полное множество формул , такое, что .

Доказательство. Пусть формула q такова, что ни q, ни не выводятся из Р. Покажем, что по крайней мере одно из двух множеств формул или непротиворечиво.

Пусть это не так: оба эти множества противоречивы. Тогда, согласно пункту б доказательства леммы 3.2., из противоречивости множества следует, что , а из противоречивости следует, что , то есть множество Р оказывается противоречивым (а это не так).

Соответственно, можно выбрать из двух формул ту, добавление которой не делает множество противоречивым, и добавить её. В случае, когда множество всех формул счётно, можно просто добавлять формулы по одной, и в пределе получить искомое множество . Значит, в этом случае лемму можно считать доказанной.

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

Определение 3.4. Частично-упорядоченное множество называется индуктивным, если в нём любое линейно-упорядоченное подмножество (цепь) имеет верхнюю грань.

Аксиома (лемма Цорна). В индуктивном частично-упорядоченном множестве обязательно есть максимальный элемент.

Замечание. В рассматриваемом случае (как и во многих других) множество Т есть множество (не всех) подмножеств некоторого множества. Конкретно, в нашем случае Т есть множество непротиворечивых подмножеств множества L всех формул. Частичный порядок в данном случае (тоже – стандартно) есть просто отношение «являться подмножеством», а в качестве верхней грани цепи , где при в I, берётся объединение . Соответственно, проверка индуктивности множества Т есть, попросту, проверка того, что если уж , то и . Простыми словами: объединение цепочки непротиворечивых множеств само есть непротиворечивое множество. Искомый же «максимальный элемент» окажется, как ни удивительно, тем самым полным непротиворечивым множеством.

Итак, пусть цепь состоит из непротиворечивых множеств формул, но объединение всех её элементов оказалось противоречивым, то есть оказалось, что . Выпишем соответствующий вывод. В него, возможно, входят и посылки. Вывод – конечное множество формул, поэтому и множество использованных посылок тоже конечно. Номером посылки назовём наименьший среди номеров множеств , в которые эта посылка входит. Отметим среди элементов линейно-упорядоченного множества I номера всех использованных посылок. Множество отмеченных элементов конечно, поэтому найдётся максимальный отмеченный элемент I, обозначим его k. Поскольку – цепь, то все использованные посылки суть элементы . Отсюда следует, что , то есть множество противоречиво, а это не так.

Итак, множество непротиворечивых множеств формул индуктивно. Значит в нём есть максимальный элемент . Если множество неполно, то найдётся формула s, такая, что ни она, ни её отрицание из не выводятся. Оба множества и больше, чем само , поэтому они не входят в Т, то есть – противоречивы. Но это невозможно, как было показано в начале обсуждения.

QED

Итак, показано, что любое непротиворечивое множество формул Р содержится в некотором непротиворечивом полном множестве , то есть в таком, что для любой формулы q либо сама q, либо содержится в Р. В частности, этим свойством обладает любая формула x, состоящая из одной переменной. Тем самым набор значений переменных , который может оказаться «хорошим», определён (необязательно однозначно: при добавлении любой формулы q могло статься, что оба набора и непротиворечивы, но мы добавили что-то одно). Покажем, что он и есть «хороший».

Лемма 3.5. Для любой формулы q равносильны условия:

(1) ;

(2) (или, равносильно, ).

Доказательство снова проводится индукцией по множеству формул с использованием выводимостей, приведённых в доказательстве леммы 3.2. Пусть, например, и для формул r и s утверждение уже доказано. Тогда возможны четыре случая.

Случай 1. . Тогда и . С другой стороны, и . Отсюда, как обычно, , и в этом случае для формулы q утверждение доказано.

Случай 2. . Тогда и . С другой стороны, это означает, что и , то есть , отсюда .

Остальные два случая и все случаи, касающиеся других логических связок, рассматриваются как случай 1 (почему?).

QED

В частности доказано, что , то есть набор ν действительно «хороший».

QED

Как из теоремы 3.3. следует теорема о полноте исчисления высказываний?

Пусть . Тогда, очевидно, , поскольку все наборы аргументов, на которых истинны формулы, входящие в Р, обращают q в истину, и, соответственно, – в ложь. Следовательно , откуда, по лемме о дедукции, получаем . Вместе с аксиомой и вариантом аксиомы (А10) это позволяет вывести . Осталось воспользоваться стандартной выводимостью .

QED

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

Теорема 3.6. (Теорема о компактности для исчисления высказываний)

Пусть P – множество формул, всякое конечное подмножество которого совместно. Тогда и само множество Р совместно.

Доказательство. Пусть Р несовместно. Тогда Р противоречиво. Тогда из множества Р можно вывести формулу О. Обозначим символом множество всех посылок, входящих в этот вывод. Тогда , т.е. противоречиво, следовательно – несовместно. Противоречие.

QED

Замечание. Основная идея доказательства состоит в том, что для выводимости и непротиворечивости теорема компактности тривиальна. И если уж непротиворечивость равносильна совместности, то…