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

Теорема Лёвенгейма — Скулема
Названо в честь	Леопольд Лёвенгейм и Туральф Скулем
Изучается в	теория моделей
Дата открытия (изобретения)	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}$. Однако если теория всё же имеет хоть какую-то бесконечную нормальную модель, то эту модель можно расширять до какой угодно мощности. Объединив теорему о повышении мощности с теоремой о понижении мощности, можно увидеть, что для теории, имеющей бесконечную модель, есть модели для любой бесконечной мощности, большей мощности сигнатуры.

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

См. также

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

Примечания

1. Беклимишев, с. 46.
2. Karagila, с. 1.
3. Беклимишев, с. 48.
4. Karagila, с. 2.
5. Găină, 2017, с. 1717.
6. Jane, 2005, с. 93.
7. Smullyan, 1996, с. 133.
8. Espindola, с. 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.