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

Теорема Ловенгейма-Сколема — твердження з теорії моделей про те, що якщо множина пропозицій в зліченній мові першого порядку має нескінченну модель, то вона має зліченну модель. Еквівалентне формулювання: кожна нескінченна модель зліченної сигнатури має зліченну елементарну підмодель.

Ця теорема з'явилася в роботі Ловенгейма 1915-го року; вона також часто називається теоремою Ловенгейма-Сколема про пониження потужності, щоб відрізняти її від схожого твердження, званого теоремой Ловенгейма-Сколема про підвищення потужності: якщо множина пропозицій зліченної мови першого порядку має нескінченну модель, то вона має модель довільної нескінченної потужності.

Необхідні визначення

Для будь-якої мови логіки першого порядку сигнатурою називається об'єднання множин функційних символів і предикатних символів. Сигнатура називається зліченною якщо це об'єднання є зліченною множиною.

Для сигнатури σ, a σ-структурою M називається деяка множина (що теж позначається M) разом із інтерпретаціями функційних символів арності n функціями зMⁿ в M і предикатних символів арності n відповідними відношеннями тобто підмножинами Mⁿ.

Підструктурою σ-структури M є деяка підмножина N замкнута відносно інтерпретацій функційних символів σ разом із звуженням символів відношень на елементи множини N. Якщо при цьому в структурі N задовольняються ті самі формули мови першого порядку, що і в M то N називається елементарною підструктурою M, а M називається елементарним продовженням N.

Загальне твердження

Теореми Ловенгейма-Сколема для сигнатури довільної потужності формулюються так:

Для довільної сигнатури σ, довільної нескінченної σ-структури M і кожного кардинального числа κ ≥ |σ| існує σ-структура N така що |N| = κ і

• якщо κ < |M| тоді N є елементарною підструктурою структури M, (пониження потужності)
• якщо κ > |M| тоді N є елементарним продовженням структури M. (повишення потужності)

Доведення

Нижче подано доведення найважливішого часткового випадку про існування зліченної елементарної підмоделі для нескінченної моделі із зліченною сигнатурою.

Нехай структура $\mathfrak N$ є моделлю множини формул зліченної мови $\mathcal L$. Побудуємо лослідовність підструктур $\mathfrak{M}_n$ $1 \leqslant n < \infty$. Для кожної формули $\varphi(x)\in \mathcal{L}$ такої, що $\mathfrak{N} \models \exists x \varphi(x)$, позначимо через $b_{varphi(x)}$ довільний елемент моделі, для якого $\mathfrak{N} \models \varphi(b_\varphi)$. Хай $\mathfrak{M}_1$ підструктура $\mathfrak{N}$, що згенерована множиною

$\{b_{\varphi(x)} \mid \mathfrak{N} \models \exists x \varphi(x)\}$

Індуктивно визначимо $\mathfrak{M}_{n+1}$ як підструктуру, що згенерована множиною

$\{b_{\varphi(x,\;\bar{a})} \mid \mathfrak{N} \models \exists x \varphi(x,\;\bar{a}),\;\bar{a} \in \mathfrak{M}_n\}$

Оскільки кількість формул зліченна, кожна з підструктур $\mathfrak{M}_n$ зліченна. Помітимо також, що їх об'єднання задовольняє критерій Тарського — Вота, і отже є елементарною підструктурою $\mathfrak{N}$, що і завершує доказ.

Див. також

• Логіка першого порядку

Джерела

1. Badesa, Calixto (2004), The Birth of Model Theory: Löwenheim's Theorem in the Frame of the Theory of Relatives, Princeton, NJ: Princeton University Press, ISBN 978-0-691-05853-5(англ.)
2. Hodges, Wilfrid (1993), Model theory, Cambridge: Cambridge Univ. Pr., ISBN 978-0-521-30442-9 (англ.)
3. Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Berlin, New York: Springer, ISBN 978-0-387-98655-5 (англ.)