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

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

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

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

Эта теорема появилась в работе Лёвенгейма 1915-го года; она также часто называется теоремой Лёвенгейма — Сколема о понижении мощности (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{N}_{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}, что и завершает доказательство.

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

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

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

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

Примеры

Связанные темы

  • Теорема о компактности
  • Критерий Тарского — Вота
  • Элементарная эквивалентность
  • Парадокс Сколема



Wikimedia Foundation. 2010.

Нужна курсовая?

Полезное


Смотреть что такое "Теорема Лёвенгейма — Сколема" в других словарях:

  • Теорема Лёвенгейма-Сколема — …   Википедия

  • Парадокс Сколема — представляет собой рассуждение, связанное с использованием теоремы Лёвенгейма Сколема для аксиоматической теории множеств. В отличие от парадокса Рассела, парадокса Кантора, парадокса Бурали Форти, где при помощи логически верных выводов… …   Википедия

  • Теория моделей — Теория моделей  раздел математической логики, который занимается изучением связи между формальными языками и их интерпретациями, или моделями. Название теория моделей было впервые предложено Тарским в 1954 году. Основное развитие теория …   Википедия

  • Моделей теория — Теория моделей  это раздел математической логики, который занимается изучением связи между формальными языками и их интерпретациями, или моделями. Название теория моделей было впервые предложено Тарским в 1954 году. Основное развитие теория… …   Википедия

  • История математики — История науки …   Википедия

  • Математика Древнего Востока — История науки По тематике Математика Естественные науки …   Википедия

  • Логика первого порядка — (исчисление предикатов)  формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций и предикатов. Расширяет логику высказываний. В свою очередь является частным случаем логики высшего порядка. Содержание 1 …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»