Языки и исчисления

       

Второе доказательство теоремы о полноте


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

Начнем с такого определения: множество формул

называется совместным,если существует набор значений переменных, при которых все формулы из истинны. Заметим, что формула является тавтологией тогда и только тогда, когда множество, состоящее из единственной формулы , не является совместным. Для случая одной формулы есть специальный термин: формула выполнима, если существуют значения переменных, при которых она истинна, то есть если множество совместно. Тавтологии — это формулы, отрицания которых не выполнимы.

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

Теорема 19 (корректность исчисления высказываний, вторая форма).

Всякое совместное множество формул непротиворечиво.

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

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

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

Мы называем это утверждение другой формой теоремы о корректности исчисления высказываний, поскольку из него формально можно вывести, что всякая теорема является тавтологией: если — теорема, то множество противоречиво (из него выводятся и ), потому несовместно, значит, всегда ложна, поэтому всегда истинна.

Теорема 20 (полнота исчисления высказываний, вторая форма). Всякое непротиворечивое множество совместно.

Нам дано непротиворечивое множество , а надо найти такие значения переменных, при которых все формулы из

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

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

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

Проведем это рассуждение подробно. Рассмотрим все переменные, входящие в какие-либо формулы из множества ; обозначим множество этих переменных через . Зафиксируем это множество и до конца доказательства теоремы о полноте будем рассматривать только формулы с переменными из множества , не оговаривая этого особо.

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

Утверждение теоремы о полноте очевидно следует из двух лемм:

Лемма 1. Всякое непротиворечивое множество

содержится в непротиворечивом полном множестве .

Лемма 2. Для всякого непротиворечивого полного множества существует набор значений переменных (из , напомним), при котором все формулы из истинны.

Доказательство леммы 1. Основную роль здесь играет такое утверждение: если — непротиворечивое множество, а — произвольная формула, то хотя бы одно из множеств и

непротиворечиво. В самом деле, если оба множества и противоречивы, то и , но множество предполагалось непротиворечивым.

Если множество переменных конечно или счетно, то доказательство леммы легко завершить: множество всех формул тогда счетно, и просматривая их по очереди, мы можем добавлять к либо саму формулу, либо ее отрицание, сохраняя непротиворечивость. Получится, очевидно, полное множество. Чуть менее очевидна его непротиворечивость: оно было непротиворечиво на каждом шаге, но почему предельное множество (объединение возрастающей последовательности) будет непротиворечиво? Дело в том, что в выводе двух противоречащих друг другу формул может быть задействовано только конечное число формул из (по определению выводимости: вывод есть конечная последовательность формул). Поэтому все эти формулы должны появиться на некотором конечном шаге конструкции, а это невозможно (на всех шагах множество непротиворечиво).

Для случая произвольного набора переменных рассуждение можно завершить ссылкой на лемму Цорна: рассмотрим частично упорядоченное множество, элементами которого будут непротиворечивые множества формул, а порядком — отношение "быть подмножеством". Рассуждение предыдущего абзаца показывает, что всякая цепь в этом множестве имеет верхнюю границу (объединение линейно упорядоченного по включению семейства непротиворечивых множеств является непротиворечивым множеством). Следовательно, для любого непротиворечивого множества найдется содержащее его максимальное непротиворечивое множество. А оно обязано быть полным (иначе его можно расширить, добавив или ).

Лемма 1 доказана.

Доказательство леммы 2. Пусть — непротиворечивое полное множество. Тогда для каждой переменной (из множества ) ровно одна из формул и выводима из . Если первая, будем считать переменную истинной, если вторая — ложной. Тем самым появляется некоторый набор значений переменных, и надо только проверить, что любая формула из при таких значениях переменных истинна. Это делается так: индукцией по построению формулы мы доказываем, что

Базис индукции (когда — переменная) обеспечивается определением истинности переменных. Для шага индукции используется та же лемма, что и при доказательстве полноты с помощью разбора случаев. Пусть, например, имеет вид . Тогда есть четыре возможности для истинности и . В одном из них (когда и истинны на ) по предположению индукции мы имеем и , откуда , то есть . В другом ( истинна, ложна) предположение индукции дает и , откуда , то есть . Аналогично разбираются и все остальные случаи и логические связки. Лемма 2 доказана, и тем самым завершено доказательство теоремы 20.

Мы доказали, что всякое непротиворечивое множество формул совместно. Отсюда легко следует, что всякая тавтология является теоремой. В самом деле, если — тавтология, то множество несовместно, поэтому из

выводится противоречие, поэтому , и по закону снятия двойного отрицания .

Кроме того, теорема о полноте во второй формулировке имеет такое очевидное следствие:

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

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

Как мы знаем, несовместность равносильна противоречивости, а вывод противоречия по определению может использовать лишь конечное число формул.

Поскольку в формулировке теоремы компактности нет упоминания об исчислении высказываний (речь идет лишь об истинности формул, а не о выводимости), возникает вопрос, нельзя ли ее доказать непосредственно.

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

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

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

То же самое рассуждение годится и для несчетного множества переменных, но тогда возникает несчетное произведение двухточечных пространств, которое является топологическим пространством (но не метрическим); надо заметить, что это пространство компактно по теореме Тихонова, после чего наше рассуждение проходит.

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

Теорема 22 (лемма Кенига).

Любое бесконечное дерево имеет бесконечную ветвь.

Говоря о бесконечности дерева, мы имеем в виду, что соответствующее множество бесконечно. Отсюда следует, что оно содержит слова сколь угодно большой длины. Пусть — счетное множество переменных, которые принимают значения или . Для каждого рассмотрим формулу , которая утверждает, что слово принадлежит дереву (это возможно, так как любая булева функция выразима формулой). Поскольку — дерево, влечет при . Любое конечное множество формул вида равносильно, таким образом, одной формуле с максимальным и потому совместно. Следовательно, и множество всех формул совместно, и выполняющий набор определяет бесконечную ветвь.

(Конечно, мы "бьем из пушек по воробьям": достаточно индукцией по строить слово длины , которое имеет бесконечное число продолжений в дереве .)

Обычно утверждение леммы Кенига формулируют так: если колония бактерий, возникшая из одной бактерии, никогда не вымирает полностью, то существует бесконечная последовательность бактерий, каждая следующая из которых получается при делении предыдущей. [Аналогичная формулировка про людей осложняется возможностью клонирования, наличием двух полов и проблемами политкорректности.]


Содержание раздела