Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

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

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

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

\{b_{\phi(x)} \mid \mathfrak{N} \models \exists x \phi(x)\}

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

\{b_{\phi(x,\bar{a})}  \mid \mathfrak{N} \models \exists x \phi(x, \bar{a}), \bar{a} \in \mathfrak{M}_n\}

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

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

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

Понижение мощности. Каждая структура сигнатуры мощности \kappa имеет элементарную подструктуру мощности мощности \lambda \leq \kappa.

Повышение мощности. Если множество предложений языка \mathcal{L} имеет бесконечную модель, то оно имеет модель любой мощности \lambda \geq |\mathcal{L}|+\aleph_0.

Примеры Править

Связанные темы Править


cs:Löwenheim-Skolemova větapl:Twierdzenie Löwenheima-Skolema

Викия-сеть

Случайная вики