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

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

Ця теорема з'явилася в роботі Ловенгейма 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 (підвищення потужності)

Доведення

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

Нехай структура є моделлю множини формул зліченної мови . Побудуємо послідовність підструктур . Для кожної формули такої, що , позначимо через довільний елемент моделі, для якого . Хай підструктура , що згенерована множиною

Індуктивно визначимо як підструктуру, що згенерована множиною

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

Див. також

Джерела

  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 (англ.)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.