Extenze teorií

Definice: Extenze teorie T$vjazyceL$ je libovolná teorie $T^{\prime }$ v jazyce $L^{\prime }\supseteq L$ taková, že množina důsledků $T$ je podmnožinou množiny důsledků $T^{\prime }$, tj.

$${\mathrm{Csq}}_L(T)\subseteq {\mathrm{Csq}}_{L^{\prime }}(T^{\prime })$$

Definice: $T^{\prime }$ je ekvivalentní $T$ (mají stejnou sílu) právě když

$${\mathrm{Csq}}_L(T^{\prime })={\mathrm{Csq}}_L(T).$$

Sílu teorií tedy porovnáváme inkluzí jejich důsledků.

Pozorování: Semanticky je $T^{\prime }$ extenzí $T$ tehdy, když každý model $T^{\prime }$ redukovaný na jazyk $L$ je modelem $T$ říkáme o ní, že je konzervativní, pokud navíc každý model $T$ lze rozšířit na model $T^{\prime }$.

---

Skolemizace

Definice: Skolemizace je proces odstranění existenčních kvantifikátorů nahrazením každé podformule $(\exists x)\phi (x)$ vhodnými novými Skolemovými funkcemi či konstantami, čímž vznikne otevřená teorie ekvivalentní s původní.

Lemma: Pro každou $L$-sentenci

$$\varphi =(\forall x_1\dots \forall x_n)(\exists y)\psi (x_1,\dots ,x_n,y)$$

a její Skolemovu variantu

$${\varphi }^S=(\forall x_1\dots \forall x_n)\psi (x_1,\dots ,x_n,f(x_1,\dots ,x_n))$$

platí, že $L$-redukt každého modelu ${\varphi }^S$ je modelem $\varphi$ a naopak každý model $\varphi$ lze expandovat na model ${\varphi }^S$.

Věta: (Skolemova) Každá teorie má otevřenou konzervativní extenzi – existuje tedy ekvivalentní otevřená teorie, která je konzervativní extenzí původní.