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

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

Это утверждение впервые сформулировано в работе Леопольда Лёвенгейма 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{N}_{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$.

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

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