Godelova věta o úplnosti

Gödelův teorém o úplnosti predikátového počtu je jedním ze základních teorémů matematické logiky : zakládá jednoznačný vztah mezi logickou pravdivostí výroku a jeho odvoditelností v logice prvního řádu . Tuto větu poprvé dokázal Kurt Gödel v roce 1929 .

Formule je odvoditelná v predikátovém počtu prvního řádu tehdy a pouze tehdy, když je platná (platí v jakékoli interpretaci pro jakoukoli substituci ).

Jinými slovy, pokud je shodně pravdivá formule predikátového počtu, pak je v predikátovém počtu prokazatelná. [jeden] $\Phi$ $\Phi$

Důkaz

Ze stejné pravdy dostáváme, že sada nemá žádný model . Z modelové existenční věty vyplývá, která je rozporuplná, tedy věta o predikátovém počtu. Pravidlem dedukce získáme, že je to prokazatelné. [jeden] $\Phi$ $\{\neg \Phi \}$ $\{\neg \Phi \}$ $\neg \Phi \vdash$ ${\frac {\Gamma ,\neg \Phi \vdash }{\Gamma \vdash \Phi ))$ $\Phi$

Viz také

Poznámky

↑ 1 2 Ershov, 1987 , str. 139.

Literatura

Ershov Yu.L. , Paljutin E.A. Matematická logika. — M .: Nauka, 1987. — 336 s.