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

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

• Теорема Лёвенгейма — Скулема, слабый вариант — непротиворечивая теория первого порядка в не более чем счётном языке имеет счётную модель.Шаблон:Sfn
• Теорема Лёвенгейма — Скулема, сильный вариант (подмодельный вариант)
  • счётная версия — каждая бесконечная модель теории первого порядка в не более чем счётном языке имеет счётную элементарную подмодель.Шаблон:Sfn
  • несчётная версия — каждая бесконечная модель теории первого порядка в языке $\mathrm{\Sigma }$ имеет элементарную подмодель мощности меньшей или равной $\max ({\mathrm{\aleph }}_0,|\mathrm{\Sigma }|)$.Шаблон:SfnШаблон:Sfn
• Теорема Лёвенгейма — Скулема о повышении мощности — каждая нормальная бесконечная модель мощности $\kappa$ имеет нормальное элементарное расширение любой мощности, больше $\kappa$.Шаблон:Sfn

Шаблон:Якорь Для отличия первых трёх теорем от последней теоремы используется также название теорема Лёвенгейма — Скулема о понижении мощности. Оно может использоваться как для сильного вариантаШаблон:Sfn, так и для слабого Шаблон:Sfn. Теорему Лёвенгейма — Скулема о повышении мощности также иногда называют теоремой Лёвенгейма — Скулема — Мальцева'.

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

Шаблон:Якорь Слабая теорема Лёвенгейма — Скулема

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

Любая непротиворечивая теория первого порядка со счётной или конечной сигнатурой имеет счётную модель.Шаблон:Sfn

Данная теорема не требует аксиомы выбора и может быть доказана в ZF.Шаблон:Sfn Её можно доказать при помощи обычного доказательства Хенкина существования модели, наблюдая за мощностью получаемой модели и следя за тем, чтобы нигде не использовалась аксиома выбора.

Стоит понимать, что в приведённой формулировке под словом модель понимается не обязательно нормальная модель. Нормальной счётной модели у такой теории может не быть. К примеру, если в теории есть теорема $\mathrm{\forall }x\mathrm{\forall }yx=y$, то любая её модель будет иметь мощность $1$. Для нормальных моделей слабая теорема Лёвенгейма — Скулема модифицируется так:

Любая непротиворечивая теория первого порядка с равенством со счётной или конечной сигнатурой имеет счётную или конечную нормальную модель.

Эта версия теоремы также может быть доказана в ZF; для её доказательства достаточно взять счётную модель из утверждения выше и факторизовать её по отношению равенства.

Из слабой теоремы Лёвенгейма — Скулема следует такое контринтуитивное на первый взгляд утверждение, как существование счётной модели ZF (в случае её непротиворечивости). Это утверждение называется парадоксом Скулема.

Шаблон:Якорь Сильная теорема Лёвенгельма — Скулема

Сильная версия теоремы Лёвенгейма — Скулема о понижении мощности встречается в двух вариантах: для не более чем счётной сигнатуры и для любой сигнатуры. Первый вариант частный случай второго.

Шаблон:Якорь Счётная или конечная сигнатура

Сильная версия теоремы Лёвенгейма — Скулема для счётной или конечной сигнатуры утверждает следующее:

У любой бесконечной модели теории первого порядка над счётной или конечной сигнатурой есть счётная элементарная подмодель.

Это утверждение обозначается LS. Данная теорема уже не может быть доказана в ZF, она требует дополнительно аксиому зависимого выбора. Более того, сильная теорема Лёвенгейма — Скулема для счётной сигнатуры в ZF эквивалентна аксиоме зависимого выбора, то есть $\mathrm{LS}\iff \mathrm{DC}$.Шаблон:Sfn

Набросок доказательства. Пусть структура $𝔑$ является моделью множества формул счётного языка $ℒ$. Построим цепочку подструктур ${𝔐}_n$, $1⩽n<\mathrm{\infty }$. Для каждой формулы $\phi (x)\in ℒ$ такой, что $𝔑\models \mathrm{\exists }x\phi (x)$, обозначим через $b_{\phi (x)}$ произвольный элемент модели, для которого $𝔑\models \phi (b_{\phi })$. Пусть ${𝔐}_1$ — подструктура $𝔑$, сгенерированная множеством

$\{b_{\phi (x)}\mid 𝔑\models \mathrm{\exists }x\phi (x)\}.$

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

$\{b_{\phi (x,\overline{a})}\mid 𝔑\models \mathrm{\exists }x\phi (x,\overline{a}),\overline{a}\in {𝔐}_n\}.$

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

Теорема Лёвенгейма — Скулема о понижении мощности в счётном варианте эквивалентна над ZF следующему утверждению: если $M$ некоторая бесконечная модель теории над счётной или конечной сигнатурой, $B$ её не более чем счётное подмножество, то существует счётная элементарная подмодель $M$, содержащая $B$.Шаблон:Sfn

Для случая нормальных моделей теорема может быть переформулирована следующим образом:

У любой бесконечной нормальной модели теории первого порядка с равенством над счётной или конечной сигнатурой есть счётная или конечная элементарная подмодель.

Эта формулировка также эквивалентна над ZF приведённой выше формулировке.

Шаблон:Якорь Произвольная сигнатура

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

У любой бесконечной модели теории первого порядка, сигнатура которой имеет бесконечную мощность $\kappa$, есть элементарная подмодель мощности меньшей или равной $\kappa$.

Случай конечной сигнатуры уже рассматривался выше: там в качестве $\kappa$ просто берётся ${\mathrm{\aleph }}_0$. Иногда, чтобы оба случая покрыть одним утверждением, разрешают сигнатуру любой мощности, а про элементарную подмодель говорят, что она имеет мощность меньшую или равную $\max {\mathrm{\aleph }}_0,\kappa$.Шаблон:Sfn

Данная теорема в полном объёме требует для доказательства аксиому выбора. Более точно: пусть $\mu$ — некоторый бесконечный кардинал. Обозначим за $\mathrm{LS}(\mu )$ следующее утверждение:

Для каждой бесконечной модели некоторой теории первого порядка, мощность сигнатуры которой меньше или равна $\mu$, существует элементарная подмодель, мощность которой меньше или равна $\mu$.

За ${\mathrm{AC}}_{\mu }$ обозначим аксиому выбора для семейств мощности $\mu$, за ${\mathrm{AC}}_{WO}$ — аксиому выбора для вполнеупорядочиваемых семейств, за $\mathrm{DC}$ — аксиому зависимого выбора. Тогда над ZF верны следующие эквивалентности:

• для любого алефа $\mu$ утверждение $\mathrm{LS}(\mu )$ эквивалентно конъюнкции $\mathrm{DC}$ и ${\mathrm{AC}}_{\mu }$Шаблон:Sfn;
• утверждение «для любого алефа $\mu$ выполняется $\mathrm{LS}(\mu )$» эквивалентно ${\mathrm{AC}}_{WO}$;
• утверждение «для любого бесконечного кардинала $\mu$ выполняется $\mathrm{LS}(\mu )$» эквивалентно полной аксиоме выбора.Шаблон:Sfn

Шаблон:Якорь Теорема Лёвенгейма — Скулема о повышении мощности

Теорема Лёвенгейма — Скулема о повышении мощности утверждает следующее:

Любая бесконечная нормальная модель мощности $\kappa$ теории первого порядка с равенством имеет нормальное элементарное расширение любой мощности большей $\kappa$.Шаблон:Sfn

Требование бесконечности изначальной модели здесь существенно: вновь пример теории с теоремой $\mathrm{\forall }x\mathrm{\forall }yx=y$. Такая теория будет иметь нормальную модель только мощности $1$. Однако если теория всё же имеет хоть какую-то бесконечную нормальную модель, то эту модель можно расширять до какой угодно мощности. Объединив теорему о повышении мощности с теоремой о понижении мощности, можно увидеть, что для теории, имеющей бесконечную модель, есть модели для любой бесконечной мощности, большей мощности сигнатуры.

Теорема Лёвенгейма — Скулема формулируется именно для нормальных моделей. Для произвольных (не обязательно нормальных) моделей утверждение тривиально: любую модель (даже конечную) можно повысить до любой большей мощности; достаточно просто один любой элемент скопировать нужное число раз и все его копии объявить равными относительно интерпретации предиката равенства. Так как модель не нормальная, от предиката равенства не требуется, чтобы он выполнялся только для равных элементов в модели.

См. также

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

Литература

• Шаблон:Cite web
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Cite web
• Шаблон:Статья
• Шаблон:Cite web