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

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

Набросок доказательства

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

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

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

Языки произвольной мощности

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

Понижение мощности. Каждая структура сигнатуры мощности имеет элементарную подструктуру мощности .

Повышение мощности. Если множество предложений языка имеет бесконечную модель, то оно имеет модель любой мощности .

Примеры

Связанные темы

• Теорема о компактности
• Критерий Тарского — Вота
• Элементарная эквивалентность
• Парадокс Скулема