Введение
Существование и кардинальность моделей логических теорий
В математической логике теорема Лёвенхайма — Сколема — это теорема о существовании и кардинальности моделей, названная в честь Леопольда Лёвенхайма и Торальфа Сколема. Точная формулировка приведена ниже. Она подразумевает, что если счётная теория первого порядка имеет бесконечную модель, то для любого бесконечного кардинального числа κ она имеет модель мощности κ, и что ни одна теория первого порядка с бесконечной моделью не может иметь единственную модель с точностью до изоморфизма. Следовательно, теории первого порядка не способны контролировать кардинальность своих бесконечных моделей. Теорема Лёвенхайма — Сколема (в направлении вниз) является одним из двух ключевых свойств, наряду с теоремой о компактности, которые используются в теореме Линдстрёма для характеризации логики первого порядка. В общем случае, теорема Лёвенхайма — Сколема не выполняется в более сильных логиках, таких как логика второго порядка.
In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem. The precise formulation is given below. It implies that if a countable first order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ, and that no first order theory with an infinite model can have a unique model up to isomorphism. As a consequence, first order theories are unable to control the cardinality of their infinite models. The (downward) Löwenheim–Skolem theorem is one of the two key properties, along with the compactness theorem, that are used in Lindström's theorem to characterize first order logic. In general, the Löwenheim–Skolem theorem does not hold in stronger logics such as second order logic.
Обсуждение
Ниже мы подробно рассмотрим общую концепцию подписей и структур.
Подписи
Подпись состоит из множества символов функций Sfunc, множества символов отношений Srel и функции, представляющей арность символов функций и отношений. (Нульарный символ функции называется символом константы.) В контексте логики первого порядка подпись иногда называют языком. Она называется счетной, если множество символов функций и отношений в ней счетно, и в общем случае кардинальность подписи равна кардинальности множества всех символов, которые она содержит. Теория первого порядка состоит из фиксированной подписи и фиксированного множества предложений (формул без свободных переменных) в этой подписи. Теории часто задаются путем предоставления списка аксиом, порождающих теорию, или путем предоставления структуры и принятия теории, состоящей из предложений, удовлетворяемых этой структурой.
Последствия
Заявление, сделанное во введении, непосредственно вытекает из рассмотрения M как бесконечной модели теории. Доказательство верхней части теоремы также демонстрирует, что теория, имеющая произвольно большие конечные модели, должна иметь бесконечную модель; иногда это рассматривается как часть самой теоремы.
Верхняя часть
Сначала сигнатура расширяется добавлением нового константного символа для каждого элемента из M. Полная теория M для расширенной сигнатуры σ' называется элементарной диаграммой M. На следующем шаге к сигнатуре добавляется κ новых константных символов, и к элементарной диаграмме M добавляются предложения c ≠ c' для любых двух различных новых константных символов c и c'. Используя теорему о компактности, легко убедиться, что полученная теория является непротиворечивой. Поскольку кардинальность любой её модели должна быть не меньше κ, нисходящая часть этой теоремы гарантирует существование модели N, имеющей кардинальность ровно κ. Она содержит изоморфную копию M как элементарную подструктуру.
В других логиках
Хотя (классическая) теорема Лёвенхейма — Сколема тесно связана с логикой первого порядка, её аналоги справедливы и для других логик. Например, любая непротиворечивая теория в логике второго порядка имеет модель, меньшую, чем первый суперкомпактный кардинал (если он существует). Минимальный размер, при котором в логике применима теорема типа (вниз) Лёвенхейма — Сколема, известен как число Лёвенхейма и может использоваться для характеристики мощности этой логики. Более того, если мы переходим за пределы логики первого порядка, нам приходится отказываться от одного из трёх: счётной компактности, теоремы Лёвенхейма — Сколема вниз или свойств абстрактной логики.