Теорема Льовенгейма — Сколема
Теорема Льовенгейма — Сколема, також теорема Левенгайма — Скулема[1] або теорема Левенгайма — Сколема[2][3] — твердження з теорії моделей про те, що якщо множина пропозицій у зліченній мові першого порядку має нескінченну модель, то вона має зліченну модель. Еквівалентне формулювання: кожна нескінченна модель зліченної сигнатури має зліченну елементарну підмодель.
Ця теорема з'явилася в роботі Ловенгейма 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 (підвищення потужності)
Доведення
Нижче подано доведення найважливішого часткового випадку про існування зліченної елементарної підмоделі для нескінченної моделі зі зліченною сигнатурою.
Нехай структура є моделлю множини формул зліченної мови . Побудуємо послідовність підструктур . Для кожної формули такої, що , позначимо через довільний елемент моделі, для якого . Хай підструктура , що згенерована множиною
Індуктивно визначимо як підструктуру, що згенерована множиною
Оскільки кількість формул зліченна, кожна з підструктур зліченна. Помітимо також, що їх об'єднання задовольняє критерій Тарського — Вота, а отже, є елементарною підструктурою , що і завершує доказ.