Теоремы Лёвенгейма — Скулема — несколько теорем теории моделей, утверждающих существование моделей разных мощностей для теорий первого порядка. Различаются следующие теоремы: Теорема Лёвенгейма — Скулема, слабый вариант — непротиворечивая теория первого порядка в не более чем счётном языке имеет счётную модель. Теорема Лёвенгейма — Скулема, сильный вариант (подмодельный вариант) счётная версия — каждая бесконечная модель теории первого порядка в не более чем счётном языке имеет счётную элементарную подмодель. несчётная версия — каждая бесконечная модель теории первого порядка в языке имеет элементарную подмодель мощности меньшей или равной . Теорема Лёвенгейма — Скулема о повышении мощности — каждая нормальная бесконечная модель мощности имеет нормальное элементарное расширение любой мощности, больше . Для отличия первых трёх теорем от последней теоремы используется также название теорема Лёвенгейма — Скулема о понижении мощности. Оно может использоваться как для сильного варианта, так и для слабого . Теорему Лёвенгейма — Скулема о повышении мощности также иногда называют теоремой Лёвенгейма — Скулема — Мальцева.
Это утверждение впервые сформулировано и доказано в работе Леопольда Лёвенгейма 1915 года. То, насколько доказательство Лёвенгельма корректно и какую именно версию слабую или сильную оно доказывает — дискуссионный вопрос. Общепринятое доказательство сильной версии теоремы было получено Туральфом Скулемом в 1920 году, слабой версии — в 1922 году.
Слабая теорема Лёвенгейма — Скулема Слабая версия теоремы Лёвенгейма — Скулема утверждает следующее: Любая непротиворечивая теория первого порядка со счётной или конечной сигнатурой имеет счётную модель. Данная теорема не требует аксиомы выбора и может быть доказана в ZF. Её можно доказать при помощи обычного доказательства Хенкина существования модели, наблюдая за мощностью получаемой модели и следя за тем, чтобы нигде не использовалась аксиома выбора.
Стоит понимать, что в приведённой формулировке под словом модель понимается не обязательно нормальная модель. Нормальной счётной модели у такой теории может не быть. К примеру, если в теории есть теорема , то любая её модель будет иметь мощность . Для нормальных моделей слабая теорема Лёвенгейма — Скулема модифицируется так: Любая непротиворечивая теория первого порядка с равенством со счётной или конечной сигнатурой имеет счётную или конечную нормальную модель. Эта версия теоремы также может быть доказана в ZF; для её доказательства достаточно взять счётную модель из утверждения выше и факторизовать её по отношению равенства.
Из слабой теоремы Лёвенгейма — Скулема следует такое контринтуитивное на первый взгляд утверждение, как существование счётной модели ZF (в случае её непротиворечивости). Это утверждение называется парадоксом Скулема.
Сильная теорема Лёвенгельма — Скулема Сильная версия теоремы Лёвенгейма — Скулема о понижении мощности встречается в двух вариантах: для не более чем счётной сигнатуры и для любой сигнатуры. Первый вариант частный случай второго.
Счётная или конечная сигнатура Сильная версия теоремы Лёвенгейма — Скулема для счётной или конечной сигнатуры утверждает следующее: У любой бесконечной модели теории первого порядка над счётной или конечной сигнатурой есть счётная элементарная подмодель. Это утверждение обозначается LS. Данная теорема уже не может быть доказана в ZF, она требует дополнительно аксиому зависимого выбора. Более того, сильная теорема Лёвенгейма — Скулема для счётной сигнатуры в ZF эквивалентна аксиоме зависимого выбора, то есть .Набросок доказательства. Пусть структура является моделью множества формул счётного языка . Построим цепочку подструктур , . Для каждой формулы такой, что , обозначим через произвольный элемент модели, для которого . Пусть — подструктура , сгенерированная множеством
Индуктивно определим как подструктуру, сгенерированную множеством
Так как количество формул счётно, каждая из подструктур счётна. Заметим также, что их объединение удовлетворяет критерию Тарского — Вота и, следовательно, является элементарной подструктурой , что и завершает доказательство.
Теорема Лёвенгейма — Скулема о понижении мощности в счётном варианте эквивалентна над ZF следующему утверждению: если некоторая бесконечная модель теории над счётной или конечной сигнатурой, её не более чем счётное подмножество, то существует счётная элементарная подмодель , содержащая .
Для случая нормальных моделей теорема может быть переформулирована следующим образом: У любой бесконечной нормальной модели теории первого порядка с равенством над счётной или конечной сигнатурой есть счётная или конечная элементарная подмодель. Эта формулировка также эквивалентна над ZF приведённой выше формулировке.
Произвольная сигнатура Сильная версия теоремы Лёвенгейма — Скулема для произвольной сигнатуры утверждает следующее: У любой бесконечной модели теории первого порядка, сигнатура которой имеет бесконечную мощность , есть элементарная подмодель мощности меньшей или равной . Случай конечной сигнатуры уже рассматривался выше: там в качестве просто берётся . Иногда, чтобы оба случая покрыть одним утверждением, разрешают сигнатуру любой мощности, а про элементарную подмодель говорят, что она имеет мощность меньшую или равную .
Данная теорема в полном объёме требует для доказательства аксиому выбора. Более точно: пусть — некоторый бесконечный кардинал. Обозначим за следующее утверждение: Для каждой бесконечной модели некоторой теории первого порядка, мощность сигнатуры которой меньше или равна , существует элементарная подмодель, мощность которой меньше или равна . За обозначим аксиому выбора для семейств мощности , за — аксиому выбора для вполнеупорядочиваемых семейств, за — аксиому зависимого выбора. Тогда над ZF' верны следующие эквивалентности: для любого алефа утверждение эквивалентно конъюнкции и ; утверждение «для любого алефа выполняется » эквивалентно ; утверждение «для любого бесконечного кардинала выполняется » эквивалентно полной аксиоме выбора.
Теорема Лёвенгейма — Скулема о повышении мощности Теорема Лёвенгейма — Скулема о повышении мощности утверждает следующее: Любая бесконечная нормальная модель мощности теории первого порядка с равенством имеет нормальное элементарное расширение любой мощности большей .
Требование бесконечности изначальной модели здесь существенно: вновь пример теории с теоремой . Такая теория будет иметь нормальную модель только мощности . Однако если теория всё же имеет хоть какую-то бесконечную нормальную модель, то эту модель можно расширять до какой угодно мощности. Объединив теорему о повышении мощности с теоремой о понижении мощности, можно увидеть, что для теории, имеющей бесконечную модель, есть модели для любой бесконечной мощности, большей мощности сигнатуры.
Теорема Лёвенгейма — Скулема формулируется именно для нормальных моделей. Для произвольных (не обязательно нормальных) моделей утверждение тривиально: любую модель (даже конечную) можно повысить до любой большей мощности; достаточно просто один любой элемент скопировать нужное число раз и все его копии объявить равными относительно интерпретации предиката равенства. Так как модель не нормальная, от предиката равенства не требуется, чтобы он выполнялся только для равных элементов в модели.
См. также Парадокс Скулема
Примечания
Литература
Категория:Математическая логика Лёвенгейма — Скулема Лёвенгейма — Скулема Категория:Основные теоремы Лёвенгейма — Скулема