- •4. Теории первого порядка
- •4.1. Термы и предикаты
- •4.2. Язык логики предикатов
- •Аксиомы кванторов
- •Аксиомы равенства
- •4.3. Семантика языка логики предикатов
- •4.4. Модели теории первого порядка
- •4.5. Компактность и полнота языка первого порядка
- •4.7. Метод резолюций Робинсона
- •4.6. Упрощение формул
- •5. Нечеткая логика
- •5.1. Нечеткие множества
- •5.2. Логические операции
- •X (a b), если и только если X a b.
- •5.3. Нечеткие отношения
- •5.4. Пропозициональная нечёткая логика
- •5.5. Вывод с нечёткими посылками
- •4. Теории первого порядка 26
- •5. Нечеткая логика 42
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. Канонической моделью А теории называется модель, построенная следующим образом:
-
обозначим через Y – множество всех термов языка L, не содержащих переменных;
-
для t1, t2 Y определим t1 t2, если и только если (t1 = t2) ;
-
предполагая, что – отношение эквивалентности, обозначим через [t] класс эквивалентности терма t Y;
-
универсум модели А определим как множество классов эквивалентности относительно отношения ;
-
для любого символа константы положим сА = [с];
-
для любой n-арной операции f положим fA([t1], …, [tn]) = [f(t1, …, tn)];
-
для любого символа предиката 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
) …))), из которой
будет вытекать вывод:
.
