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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Примеры[править | править вики-текст]

Связанные темы[править | править вики-текст]