Löwenheim-Skolem tétel

A Löwenheim-Skolem tétel egy modellelméleti tétel , miszerint ha egy elsőrendű megszámlálható nyelv mondathalmazának van végtelen modellje, akkor van megszámlálható modellje. Egyenértékű megfogalmazás: egy megszámlálható aláírás minden végtelen modelljének van megszámlálható elemi részmodellje.

Ezt az állítást először Leopold Löwenheim 1915 -ös munkájában fogalmazta meg, amit Turalf Skolem 1920 - ban bizonyított .

A tételt gyakran nevezik lefelé irányuló Löwenheim-Skolem tételnek , hogy megkülönböztesse a Löwenheim-Skolem hatványnövekedési tételnek nevezett hasonló állítástól : ha egy elsőrendű megszámlálható nyelv mondathalmazának van végtelen modellje, akkor tetszőleges modellje van. végtelen hatalom ( angol felfelé Löwenheim - Skolem tétel ).

A bizonyítás vázlata

Legyen a struktúra egy megszámlálható nyelv képlethalmazának modellje . Szerkesszünk egy alstruktúrák láncát , . Minden olyan képletnél jelölje a modell tetszőleges elemét, amelyre . Legyen a halmaz által generált részstruktúra ${\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\}.

Induktívan definiáljuk a halmaz által generált részstruktúrát ${\mathfrak {M}}_{{n+1}}$

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

Mivel a képletek száma megszámlálható, minden részstruktúra megszámlálható. Vegye figyelembe azt is, hogy uniójuk eleget tesz a Tarski-Wota kritériumnak , és ezért elemi alstruktúrája a -nak , amely kiegészíti a bizonyítást. ${\mathfrak {M}}_{n}$ ${\mathfrak {N}}$

Tetszőleges kardinalitású nyelvek

A Löwenheim-Skolem tételek tetszőleges számú nyelvekre a következőképpen vannak megfogalmazva:

Áramtalanítás . Minden hatalom aláírási struktúrának van egy elemi hatalom alstruktúrája . $\kappa$ $\lambda \leqslant \kappa$
Növekvő teljesítmény . Ha egy nyelv mondatainak végtelen modellje van, akkor tetszőleges kardinalitású modellje van . $\mathcal{L}$ $\lambda \geqslant |{\mathcal {L}}|+\aleph _{0}$

Példák

Lásd még

Skolem paradoxona