Теорема Лёвенгейма — Скулема


Теорема Лёвенгейма — Скулема — теорема теории моделей о том, что если множество предложений в счётном языке первого порядка имеет бесконечную модель, то оно имеет счётную модель. Эквивалентная формулировка: каждая бесконечная модель счётной сигнатуры имеет счётную элементарную подмодель.

Это утверждение впервые сформулировано в работе Леопольда Лёвенгейма 1915 года, доказано Туральфом Скулемом в 1920 году.

Теорема часто называется теоремой Лёвенгейма — Скулема о понижении мощности (англ. downward Löwenheim — Skolem theorem), чтобы отличать её от похожего утверждения, называемого теоремой Лёвенгейма — Скулема о повышении мощности: если множество предложений счётного языка первого порядка имеет бесконечную модель, то оно имеет модель произвольной бесконечной мощности (англ. upward Löwenheim — Skolem theorem).

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

Индуктивно определим как подструктуру, сгенерированную множеством

Так как количество формул счётно, каждая из подструктур счётна. Заметим также, что их объединение удовлетворяет критерию Тарского — Вота и, следовательно, является элементарной подструктурой , что и завершает доказательство.