Věty o kompaktnosti a úplnosti výrokové a predikátové logiky

Věta o korektnosti říká, že pokud existuje formální důkaz formule $\phi$ z teorie $T$, pak $\phi$ platí ve všech modelech $T$, tj.

$$T⊢\phi \Rightarrow T\models \phi .$$

Věta o úplnosti ve výrokové logice tvrdí, že každá tautologie (formule platná ve všech ohodnoceních) je formálně dokazatelná, tj.

$$\models \phi \Rightarrow ⊢\phi .$$

Gödelova věta o úplnosti predikátové logiky říká, že pro libovolnou teorii $T$ a uzavřenou formuli (větu) $\phi$ platí ekvivalence:

$$T\models \phi ⟺T{⊢}_H\phi$$

tj. pokud je $\phi$ pravdivá ve všech modelech $T$, existuje formální Hilbertovský důkaz $\phi$ z $T$, a naopak.

Věta o kompaktnosti říká, že teorie $T$ má model právě tehdy, když každá její konečná podteorie $T^{\prime }\subseteq T$ má model, tj.

$$T\text{ je splnitelnaˊ}\iff \forall T^{\prime }\subseteq T,|T^{\prime }|<\infty :T^{\prime }\text{ je splnitelnaˊ}.$$

Příklad použití kompaktnosti: Nechť $G$ je spočetně nekonečný graf a definujme teorii

$$T=\{p_u\leftrightarrow \neg p_v\mid \{u,v\}\in E(G)\}$$

v jazyce $\{p_v:v\in V(G)\}$. Každá konečná podteorie $T^{\prime }$ odpovídá konečnému podgrafu $G^{\prime }$, který je bipartitní, tedy $T^{\prime }$ má model. Kompaktnost zaručuje, že pak i $T$ má model, a $G$ je bipartitní.

Důsledky kompaktnosti:

1. Existence nestandardních modelů aritmetiky, tj. modelů obsahujících “nekonečné” elementy.
2. Löwenheim–Skolemova věta: každá spočetně axiomatizovatelná teorie s nekonečným modelem má model libovolné spočetné kardinály.