Löwenheimova-Skolemova věta

Löwenheim-Skolemův teorém je teorém teorie modelu , že pokud má množina vět v spočetném jazyce prvního řádu nekonečný model, pak má spočetný model . Ekvivalentní formulace: každý nekonečný model počitatelného podpisu má počitatelný elementární podmodel.

Toto tvrzení bylo poprvé uvedeno v díle Leopolda Löwenheima v roce 1915 , což dokázal Turalf Skolem v roce 1920 .

Věta se často nazývá sestupná Löwenheimova-Skolemova věta , aby se odlišila od podobného tvrzení zvaného Löwenheimova-Skolemova věta o nárůstu moci : pokud má množina vět spočítatelného jazyka prvního řádu nekonečný model, pak má libovolný model. nekonečná moc ( angl . upward Löwenheim - Skolemova věta ).

Náčrt důkazu

Nechť struktura je modelem množiny vzorců v počitatelném jazyce . Vytvořme řetězec podstruktur , . Pro každý vzorec takový, že označíme libovolným prvkem modelu, pro který . Nechť je podstruktura generovaná množinou ${\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}}$

\left\{b_{\varphi (x)}\mid {\mathfrak {N))\models \exists x\,\varphi (x)\right\}.

Definujme induktivně jako podstrukturu generovanou množinou ${\mathfrak {M}}_{{n+1}}$

\left\{b_{\varphi (x,\;{\bar {a)))}\mid {\mathfrak {N))\models \exists x\,\varphi (x,\;{\ takt {a)))\;{\bar {a}}\v {\mathfrak {M}}_{n}\right\}.

Vzhledem k tomu, že počet vzorců je spočetný, každá z podstruktur je spočetná. Všimněte si také, že jejich spojení splňuje kritérium Tarski-Wota , a proto je základní podstrukturou , která doplňuje důkaz. ${\mathfrak {M}}_{n}$ ${\mathfrak {N}}$

Jazyky svévolné mohutnosti

Löwenheim-Skolemovy teorémy pro jazyky libovolné mohutnosti jsou formulovány takto:

Vypnout . Každá struktura podpisu moci má základní podstrukturu moci . $\kappa$ $\lambda \leqslant \kappa$
Zvyšování výkonu . Pokud má množina vět v jazyce nekonečný model, pak má model jakékoli mohutnosti . $\mathcal{L}$ $\lambda \geqslant |{\mathcal {L}}|+\aleph _{0}$

Příklady

Viz také

Skolemův paradox