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

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

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

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

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

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

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

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

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

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

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

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

Примеры

См. также

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

В статье не хватает ссылок на источники (см. рекомендации по поиску ). Информация должна быть проверяема , иначе она может быть удалена. Вы можете статью, добавив ссылки на авторитетные источники в виде сносок . ( 26 октября 2017 )