Теорема Льовенгейма — Сколема — твердження з теорії моделей про те, що якщо множина пропозицій у зліченній мові першого порядку має нескінченну модель, то вона має зліченну модель. Еквівалентне формулювання: кожна нескінченна модель зліченної сигнатури має зліченну елементарну підмодель.
Ця теорема з'явилася в роботі Ловенгейма 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 (підвищення потужності)
Доведення
Нижче подано доведення найважливішого часткового випадку про існування зліченної елементарної підмоделі для нескінченної моделі зі зліченною сигнатурою.
Нехай структура є моделлю множини формул зліченної мови . Побудуємо послідовність підструктур . Для кожної формули такої, що , позначимо через довільний елемент моделі, для якого . Хай підструктура , що згенерована множиною
Індуктивно визначимо як підструктуру, що згенерована множиною
Оскільки кількість формул зліченна, кожна з підструктур зліченна. Помітимо також, що їх об'єднання задовольняє , а отже, є елементарною підструктурою , що і завершує доказ.
Див. також
Джерела
- 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, (англ.)
- Hodges, Wilfrid (1993), Model theory, Cambridge: Cambridge Univ. Pr., (англ.)
- Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Berlin, New York: Springer, (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет