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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Необхідні визначення[ред.ред. код]

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

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

Підструктурою σ-структури 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 (англ.)