Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
МЛиТА 4 - 5.doc
Скачиваний:
20
Добавлен:
12.11.2018
Размер:
877 Кб
Скачать
☆

4.5. Компактность и полнота языка первого порядка

Теорема компактности для счётных языков была доказана Куртом Гёделем в 1930 году. Анатолий Иванович Мальцев доказал её для произвольных языков первого порядка в 1936 году. Мы будем следовать доказательству Генкина (1949 г.).

Напомним, что теории – это множества предложений. Множество предложений  языка L называется конечно выполнимым, если каждое конечное подмножество из  имеет модель. Множество  – полное, если для каждого предложения  либо   , либо   .

Лемма 1. Для каждого конечно выполнимого множества предложений языка первого порядка существует полное конечно выполнимое множество предложений .

Доказательство. Пусть B = {Q : Q   и Q – конечно выполнимо}. Легко видеть, что (B, ) удовлетворяет лемме Куратовского-Цорна. Значит, существует максимальное конечно выполнимое . Для каждого предложения  либо , либо конечно выполнимо. В противном случае существуют конечные такие, что и не имеют моделей, хотя будет иметь некоторую модель А в силу конечной выполнимости . Для этой модели либо A |= , либо A |= . Противоречие показывает, что либо , либо . Следовательно, – полное.

Лемма 2. Если – конечно выполнимое множество предложений языка L с одной свободной переменной x, а с – новый символ константы (не принадлежащий L), то {(x(x)) (c)} – конечно выполнимо в языке L {с}.

Доказательство. Новое предложение (x(x))  (c) называется предложением Генкина, а константа с – константой Генкина. Предположим, что   {(x(x))  (c)} не является конечно выполнимым. Тогда существует конечное , такое, что F  {(x(x))  (c)} не имеет модели. Пусть А – модель языка L, удовлетворяющая F. Так как константа с не принадлежит L, то мы можем интерпретировать её произвольным образом. Если A |= x(x), то существует b  А, для которого A |= . В этом случае, сопоставляя символу с элемент b, мы расширим модель на L  {c}. Получим A |= (c), а вместе с тем A |= x(x)  (c). Если же x(x) ложно в модели А, то символу c можно сопоставить любой элемент из А. Во всех случаях модель А будет удовлетворять F  {(x(x))  (c)}.

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

((x(x)) (c)) .

Лемма 3. Если – конечно выполнимое множество предложений языка L, то существуют такие и , что  является конечно выполнимым множеством Генкина предложений языка L.

Доказательство. Для любого множества  предложений языка L положим: * =   {x(x)  (c) : (x) – формула языка L с одной свободной переменной}. Язык теории * содержит новый символ константы c для каждой формулы (x). Применяя к конечным подмножествам теории * лемму 2, получим конечную выполнимость множества *. Далее положим: 0 =  и для всех m  . Тогда множество будет множеством Генкина. Оно конечно выполнимо как объединение цепи конечно выполнимых множеств.

Каноническая модель теории

Пусть  – множество предложений языка L. Канонической моделью А теории  называется модель, построенная следующим образом:

  1. обозначим через Y – множество всех термов языка L, не содержащих переменных;

  2. для t1, t2  Y определим t1  t2, если и только если (t1 = t2)  ;

  3. предполагая, что  – отношение эквивалентности, обозначим через [t] класс эквивалентности терма t  Y;

  4. универсум модели А определим как множество классов эквивалентности относительно отношения ;

  5. для любого символа константы положим сА = [с];

  6. для любой n-арной операции f положим fA([t1], …, [tn]) = [f(t1, …, tn)];

  7. для любого символа предиката R положим:

([t1], …, [tn])  RA, если R(t1, …, tn)  .

Лемма 4. Если – конечно выполнимое полное множество Генкина предложений языка L, то каноническая модель А для определена корректно, и для каждого предложения языка L верно, что

A |= тогда и только тогда, когда .

Доказательство состоит из проверки того, что  – отношение эквивалентности, перестановочное с символами операций и отношений. Сформулированное свойство доказывается по индукции.

Теорема (о компактности). Для произвольных языка L и множества предложений языка L, если каждое конечное подмножество из имеет модель, то имеет модель.

Доказательство. По лемме 3 существует конечно выполнимое множество Генкина:   . Возьмём его пополнение , существующее по лемме 1. Рассмотрим каноническую модель полученной теории. Ограничение этой теории на  будет искомой моделью на .

Лемма 5. Мощность множества формул языка L равна max (|L|, ||).

Теорема (Лёвенгейма-Скулема). Если теория Т языка L имеет модель, то она имеет некоторую модель мощности, не большей max (|L|, ||).

Доказательство. Каноническая модель пополнения множества Генкина Т, построенного для Т, имеет мощность  max (|L|, ||).

Из этой теоремы, в частности, вытекает, что существуют счетные модели теории множеств. Имеет место и теорема Лёвенгейма-Скулема о существовании моделей большой мощности. Она утверждает, что для любой модели А языка L существует содержащая её модель B произвольной мощности B  max (|A|, |L|). В частности, существуют несчетные модели теории натуральных чисел.

Полнота теории первого порядка

Кроме исчисления предикатов существуют другие формальные теории, связанные с языком первого порядка. Мы рассмотрим исчисление предикатов. Наиболее простая из них – исчисление ММ. Логические аксиомы в этой системе – предложения , истинные в любой модели языка первого порядка L. Правило вывода одно – Modus Ponens. Мы будем опираться далее на равносильность этой формальной теории исчислению предикатов, которая в действительности вытекает из теоремы Гёделя о полноте исчисления предикатов.

Теорема о полноте теории первого порядка. Пусть заданы произвольные множества предложений и предложение языка L. Вывод существует тогда и только тогда, когда каждая модель теории удовлетворяет предложению .

Доказательство. В случае   и A |=  утверждение A |=  доказывается очевидным образом с помощью индукции по длине вывода   (теорема о корректности). Пусть, наоборот, каждая модель A |=  удовлетворяет . Так как всякая модель  является моделью для , то множество предложений   {} не имеет моделей. По теореме компактности существует такое конечное подмножество {1, …, n}  , что {1, …, n, } не имеет моделей. Отсюда  (1 & … & n & ) – тавтология исчисления ММ. Значит, имеет место логическая аксиома: 1  (2  (…  (n  ) …))), из которой будет вытекать вывод:  .