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

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

Ця теорема з'явилася в роботі Ловенгейма 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}}$, що і завершує доказ.

Див. також

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

Література

Українською

• Безущак О., Ганюшкін О. (2023). Математична логіка : навч. посіб (PDF). Київ: Видавничо-поліграфічний центр "Київський університет". с. 143. ISBN 978-966-933-248-6.
• Безущак О., Ганюшкін О. (2023). Теорія моделей : навч. посіб (PDF). Київ: Видавничо-поліграфічний центр "Київський університет". с. 206.
• Олійник А.С., Сущанський В.І. (2013). Математична логіка. Київ: Видавничо-поліграфічний центр "Київський університет". с. 171. ISBN 978-966-439-650-6.
• Дрозд Ю. А. (2005). Основи математичної логіки (PDF). Київ: ВПЦ "Київський університет". с. 96. (укр.)

Англійською

• 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.
• Poizat, Bruno (2000). A Course in Model Theory: An Introduction to Contemporary Mathematical Logic. Berlin, New York: Springer. ISBN 978-0-387-98655-5.
• Hodges, Wilfrid (1993). Model theory. Cambridge: Cambridge Univ. Pr. ISBN 978-0-521-30442-9.