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

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

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

Див. також

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

Джерела

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.