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

Теорема Лёвенгейма — Скулема
Названо в честь	Леопольд Лёвенгейм и Туральф Скулем
Дата открытия (изобретения)	1915

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

• Теорема Лёвенгейма — Скулема, слабый вариант — непротиворечивая теория первого порядка в не более чем счётном языке имеет счётную модель.^[1]
• Теорема Лёвенгейма — Скулема, сильный вариант (подмодельный вариант)
  • счётная версия — каждая бесконечная модель теории первого порядка в не более чем счётном языке имеет счётную элементарную подмодель.^[2]
  • несчётная версия — каждая бесконечная модель теории первого порядка в языке ${\displaystyle \Sigma }$ имеет элементарную подмодель мощности меньшей или равной ${\displaystyle \max(\aleph _{0},|\Sigma |)}$.^[3][4]
• Теорема Лёвенгейма — Скулема о повышении мощности — каждая нормальная бесконечная модель мощности ${\displaystyle \kappa }$ имеет нормальное элементарное расширение любой мощности, больше ${\displaystyle \kappa }$.^[3]

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

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

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

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

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

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

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

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

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

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

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

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

Счётная или конечная сигнатура

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

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

Это утверждение обозначается LS. Данная теорема уже не может быть доказана в ZF, она требует дополнительно аксиому зависимого выбора. Более того, сильная теорема Лёвенгейма — Скулема для счётной сигнатуры в ZF эквивалентна аксиоме зависимого выбора, то есть ${\displaystyle \operatorname {LS} \Leftrightarrow \operatorname {DC} }$.^[4]

Набросок доказательства. Пусть структура ${\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}}}$, что и завершает доказательство.

Теорема Лёвенгейма — Скулема о понижении мощности в счётном варианте эквивалентна над ZF следующему утверждению: если ${\displaystyle M}$ некоторая бесконечная модель теории над счётной или конечной сигнатурой, ${\displaystyle B}$ её не более чем счётное подмножество, то существует счётная элементарная подмодель ${\displaystyle M}$, содержащая ${\displaystyle B}$.^[2]

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

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

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

Произвольная сигнатура

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

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

Случай конечной сигнатуры уже рассматривался выше: там в качестве ${\displaystyle \kappa }$ просто берётся ${\displaystyle \aleph _{0}}$. Иногда, чтобы оба случая покрыть одним утверждением, разрешают сигнатуру любой мощности, а про элементарную подмодель говорят, что она имеет мощность меньшую или равную ${\displaystyle \max {\aleph _{0},\kappa }}$.^[3]

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

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

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

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

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

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

Любая бесконечная нормальная модель мощности ${\displaystyle \kappa }$ теории первого порядка с равенством имеет нормальное элементарное расширение любой мощности большей ${\displaystyle \kappa }$.^[3]

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

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

См. также

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

Примечания

Литература

• Беклимишев Л. Д., Кузнецов С. Л., Яворская Т. Л. Обязательный спецкурс кафедры математической логики и теории алгоритмов  (рус.). https://homepage.mi-ras.ru/~sk/ (21 мая 2016). Дата обращения: 20 апреля 2024.
• Jane I. What Did Löwenheim Prove? (англ.) // Philosophia Mathematica : журнал. — 2005. — 1 February (vol. 11, iss. 13). — P. 91-106. — doi:10.1093/philmat/nki004.
• Smullyan R. M, Fitting M. Set Theory and the Continuum Problem. — Clarendon Press, 1996. — 288 с.
• Karagila A. Downward Löwenheim-Scolem Theorem and Choice Principles (англ.). https://aragila.org (31 марта 2014). Дата обращения: 20 апреля 2024.
• Găină D. Downward Löwenheim–Skolem Theorem and interpolation in logics with constructors (англ.) // Journal of Logic and Computation. — 2017. — September (vol. 27, no. 6). — P. 1717–1752. — doi:10.1093/logcom/exv018.
• Espindola C. L¨owenheim-Skolem theorems and Choice principles (англ.). Дата обращения: 24 апреля 2024.

Эта страница в последний раз была отредактирована 3 мая 2024 в 13:59.