Русская Википедия:Теорема Лёвенгейма — Скулема

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

Теорема часто называется теоремой Лёвенгейма — Скулема о понижении мощности (Шаблон:Lang-en), чтобы отличать её от похожего утверждения, называемого теоремой Лёвенгейма — Скулема о повышении мощности: если множество предложений счётного языка первого порядка имеет бесконечную модель, то оно имеет модель произвольной бесконечной мощности (Шаблон:Lang-en).

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

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

<math>\left\{b_{\varphi(x)} \mid \mathfrak{N} \models \exists x \,\varphi(x)\right\}.</math>

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

<math>\left\{b_{\varphi(x,\;\bar{a})} \mid \mathfrak{N} \models \exists x \,\varphi(x,\;\bar{a}),\;\bar{a} \in \mathfrak{M}_n\right\}.</math>

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

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

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

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

См. также

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