Аксиоматическая система исчисления предикатов

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

где  — последовательность простых чисел.

Эта теорема может быть доказана и в более общей мощностной формулировке: если множество  формул имеет бесконечную модель и мощность множества всех букв, из которых составлены формулы из  , равна  , то для любой бесконечной мощности  существует модель множества  мощности  .
Укажем два следствия этой теоремы:
1) если  — множество формул мощности  , имеющее бесконечную модель, то  имеет бесконечные модели любых мощностей, превышающих  ;
2) всякое конечное множество или счетное непротиворечивое множество формул либо имеет только конечные модели, либо имеет бесконечные модели любых мощностей.
Теорема Лёвенгейма–Сколема дает ряд поразительных следствий двух типов: одни из них гласят, что некоторая теория имеет неожиданно обширные модели, другие — что теория имеет неожиданно узкие модели. Дальнейшее развитие эта мысль получит в следующей лекции.