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

Напомним, что теории – это множества предложений. Множество предложений å языка L называется конечно выполнимым, если каждое конечное подмножество из å имеет модель. Множество å – полное, если для каждого предложения q либо q Î å, либо Øq Î å.

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

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

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

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

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

(($xq(x)) ® q(c)) Î å .

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

Доказательство. Для любого множества å предложений языка L положим: å* = å È {$xq(x) ® q(c_q) : q(x) – формула языка L с одной свободной переменной}. Язык теории å* содержит новый символ константы c_q для каждой формулы q(x). Применяя к конечным подмножествам теории å* лемму 2, получим конечную выполнимость множества å*. Далее положим: å₀ = å и  для всех m Î w. Тогда мно

жество  будет множеством Генкина. Оно конечно выполнимо как объединение цепи конечно выполнимых множеств.

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

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

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

2) для  t₁, t₂ Î Y определим t₁ ~ t₂, если и только если (t₁ = t₂) Î å;

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

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

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

6) для любой n-арной операции f положим f^A([t₁], …, [t_n]) = [f(t₁, …, t_n)];

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

([t₁], …, [t_n]) Î R^A, если R(t₁, …, t_n) Î å.

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

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

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

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

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

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

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

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

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

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

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

предикатов, которая в действительности вытекает из теоремы Гёделя о полноте исчисления предикатов.

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

Доказательство. В случае å q и A |= å утверждение A |= q доказывается очевидным образом с помощью индукции по длине вывода å q (теорема о корректности). Пусть, наоборот, каждая модель A |= å удовлетворяет  q.  Так как всякая модель å является моделью для q, то множество предложений å È {Øq} не имеет моделей. По теореме компактности существует такое конечное подмножество {q₁, …, q_n} Í å, что {q₁, …, q_n, Øq} не имеет моделей. Отсюда Ø (q₁ & … & q_n & Øq) – тавтология исчисления ММ. Значит, имеет место логическая аксиома: q₁ ® (q₂ ® (… ® (q_n ® q) …))), из которой будет вытекать вывод: å q.