Löwenheim-Skolem lause

Löwenheim-Skolem-lause on malliteorialause , jonka mukaan jos ensimmäisen asteen laskettavan kielen lausejoukolla on ääretön malli, niin sillä on laskettava malli. Vastaava muotoilu: jokaisella laskettavan allekirjoituksen äärettömällä mallilla on laskettava alkeisalimalli.

Tämä lausunto esitettiin ensimmäisen kerran Leopold Löwenheimin teoksessa vuonna 1915 , ja Turalf Skolem todisti vuonna 1920 .

Lausetta kutsutaan usein alaspäin laskevaksi Löwenheim-Skolem- lauseeksi , jotta se erottuisi samankaltaisesta lauseesta nimeltä Löwenheim-Skolem tehonlisäyslause : jos ensimmäisen asteen laskettavan kielen lausejoukolla on ääretön malli, niin sillä on mielivaltainen malli. ääretön teho ( englanniksi ylöspäin Löwenheim - Skolem -lause ).

Luonnos todisteesta

Olkoon rakenne malli kaavojen joukosta laskettavalla kielellä . Muodostetaan alirakenteiden ketju , . Jokaiselle kaavalle sellainen, että , merkitään mielivaltaisella elementillä mallista, jolle . Antaa olla joukon luoma alirakenne ${\mathfrak N}$ ${\mathcal L}$ ${\mathfrak {M}}_{n}$ $1\leqslant n<\infty$ $\varphi (x)\in {\mathcal {L}}$ ${\mathfrak {N}}\mallit \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))\mallit \exists x\,\varphi (x)\right\}.

Määritellään induktiivisesti joukon generoima alirakenne ${\mathfrak {M}}_{{n+1}}$

\left\{b_{\varphi (x,\;{\bar {a)))}\mid {\mathfrak {N))\mallit \exists x\,\varphi (x,\;{\ palkki {a)))\;{\bar {a}}\in {\mathfrak {M}}_{n}\right\}.

Koska kaavojen määrä on laskettavissa, jokainen alirakenne on laskettavissa. Huomaa myös, että heidän liittonsa täyttää Tarski-Wota-kriteerin ja on siksi alkeisrakenne , joka täydentää todisteen. ${\mathfrak {M}}_{n}$ ${\mathfrak {N}}$

Mielivaltaisen kardinaalisuuden kielet

Löwenheim-Skolem-lauseet mielivaltaisen kardinaalisuuden kielille on muotoiltu seuraavasti:

Virta pois päältä . Jokaisella teho-allekirjoitusrakenteella on alkeellinen tehoalirakenne . $\kappa$ $\lambda \leqslant \kappa$
Tehon lisääminen . Jos kielen lausejoukolla on ääretön malli, niin sillä on malli minkä tahansa kardinaalisuudesta . $\mathcal{L}$ $\lambda \geqslant |{\mathcal {L}}|+\aleph _{0}$

Esimerkkejä

Katso myös

Skolemin paradoksi