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

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

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

Доведення

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

Нехай структура ${\displaystyle {\mathfrak {N}}}$ є моделлю множини формул зліченної мови ${\displaystyle {\mathcal {L}}}$. Побудуємо послідовність підструктур ${\displaystyle {\mathfrak {M}}_{n}}$ ${\displaystyle 1\leqslant n<\infty }$. Для кожної формули ${\displaystyle \varphi (x)\in {\mathcal {L}}}$ такої, що ${\displaystyle {\mathfrak {N}}\models \exists x\varphi (x)}$, позначимо через ${\displaystyle b_{varphi(x)}}$ довільний елемент моделі, для якого ${\displaystyle {\mathfrak {N}}\models \varphi (b_{\varphi })}$. Хай ${\displaystyle {\mathfrak {M}}_{1}}$ підструктура ${\displaystyle {\mathfrak {N}}}$, що згенерована множиною

${\displaystyle \{b_{\varphi (x)}\mid {\mathfrak {N}}\models \exists x\varphi (x)\}}$

Індуктивно визначимо ${\displaystyle {\mathfrak {M}}_{n+1}}$ як підструктуру, що згенерована множиною

${\displaystyle \{b_{\varphi (x,\;{\bar {a}})}\mid {\mathfrak {N}}\models \exists x\varphi (x,\;{\bar {a}}),\;{\bar {a}}\in {\mathfrak {M}}_{n}\}}$

Оскільки кількість формул зліченна, кожна з підструктур ${\displaystyle {\mathfrak {M}}_{n}}$ зліченна. Помітимо також, що їх об'єднання задовольняє критерій Тарського — Вота, а отже, є елементарною підструктурою ${\displaystyle {\mathfrak {N}}}$, що і завершує доказ.

Див. також

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