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

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

Это утверждение впервые сформулировано в работе Леопольда Лёвенгейма 1915 года, доказано Туральфом Скулемом в 1920 году.

Теорема часто называется теоремой Лёвенгейма — Скулема о понижении мощности (англ. downward Löwenheim — Skolem theorem), чтобы отличать её от похожего утверждения, называемого теоремой Лёвенгейма — Скулема о повышении мощности: если множество предложений счётного языка первого порядка имеет бесконечную модель, то оно имеет модель произвольной бесконечной мощности (англ. upward Löwenheim — Skolem theorem).

Набросок доказательства

Пусть структура N {displaystyle {mathfrak {N}}} является моделью множества формул счётного языка L {displaystyle {mathcal {L}}} . Построим цепочку подструктур M n {displaystyle {mathfrak {M}}_{n}} , 1 ⩽ n < ∞ {displaystyle 1leqslant n<infty } . Для каждой формулы φ ( x ) ∈ L {displaystyle varphi (x)in {mathcal {L}}} такой, что N ⊨ ∃ x φ ( x ) {displaystyle {mathfrak {N}}models exists x,varphi (x)} , обозначим через b φ ( x ) {displaystyle b_{varphi (x)}} произвольный элемент модели, для которого N ⊨ φ ( b φ ) {displaystyle {mathfrak {N}}models varphi (b_{varphi })} . Пусть M 1 {displaystyle {mathfrak {M}}_{1}} — подструктура N {displaystyle {mathfrak {N}}} , сгенерированная множеством

{ b φ ( x ) ∣ N ⊨ ∃ x φ ( x ) } . {displaystyle {b_{varphi (x)}mid {mathfrak {N}}models exists x,varphi (x)}.}

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

{ b φ ( x , a ¯ ) ∣ N ⊨ ∃ x φ ( x , a ¯ ) , a ¯ ∈ M n } . {displaystyle {b_{varphi (x,;{ar {a}})}mid {mathfrak {N}}models exists x,varphi (x,;{ar {a}}),;{ar {a}}in {mathfrak {M}}_{n}}.}

Так как количество формул счётно, каждая из подструктур M n {displaystyle {mathfrak {M}}_{n}} счётна. Заметим также, что их объединение удовлетворяет критерию Тарского — Вота и, следовательно, является элементарной подструктурой N {displaystyle {mathfrak {N}}} , что и завершает доказательство.

Языки произвольной мощности

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

• Понижение мощности. Каждая структура сигнатуры мощности κ {displaystyle kappa } имеет элементарную подструктуру мощности λ ⩽ κ {displaystyle lambda leqslant kappa } .
• Повышение мощности. Если множество предложений языка L {displaystyle {mathcal {L}}} имеет бесконечную модель, то оно имеет модель любой мощности λ ⩾ | L | + ℵ 0 {displaystyle lambda geqslant |{mathcal {L}}|+aleph _{0}} .

Примеры