WikiSort.ru - Не сортированное

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

Это утверждение впервые сформулировано в работе Леопольда Лёвенгейма 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 \{b_{\varphi (x)}\mid {\mathfrak {N}}\models \exists x\,\varphi (x)\}.}$

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

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

Так как количество формул счётно, каждая из подструктур ${\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 года.