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

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

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

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

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

Пусть структура ${\mathfrak {N}}$ является моделью множества формул счётного языка ${\mathcal {L}}$. Построим цепочку подструктур ${\mathfrak {M}}_{n}$, $1\leqslant n<\infty$. Для каждой формулы $\varphi (x)\in {\mathcal {L}}$ такой, что ${\mathfrak {N}}\models \exists x\,\varphi (x)$, обозначим через $b_{\varphi (x)}$ произвольный элемент модели, для которого ${\mathfrak {N}}\models \varphi (b_{\varphi })$. Пусть ${\mathfrak {M}}_{1}$ — подструктура ${\mathfrak {N}}$, сгенерированная множеством

$\{b_{\varphi (x)}\mid {\mathfrak {N}}\models \exists x\,\varphi (x)\}.$

Индуктивно определим ${\mathfrak {M}}_{n+1}$ как подструктуру, сгенерированную множеством

$\{b_{\varphi (x,\;{\bar {a}})}\mid {\mathfrak {N}}\models \exists x\,\varphi (x,\;{\bar {a}}),\;{\bar {a}}\in {\mathfrak {M}}_{n}\}.$

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

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

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

• Понижение мощности. Каждая структура сигнатуры мощности $\kappa$ имеет элементарную подструктуру мощности $\lambda \leqslant \kappa$.
• Повышение мощности. Если множество предложений языка ${\mathcal {L}}$ имеет бесконечную модель, то оно имеет модель любой мощности $\lambda \geqslant |{\mathcal {L}}|+\aleph _{0}$.

См. также

• Парадокс Скулема