Godel teljességi tétele

Gödel tétele a predikátumszámítás teljességéről a matematikai logika egyik alapvető tétele : egyértelmű kapcsolatot teremt egy állítás logikai igazsága és az elsőrendű logikában való levezethetősége között . Ezt a tételt Kurt Gödel bizonyította először 1929 -ben .

A képlet akkor és csak akkor származtatható az elsőrendű predikátumszámításban, ha érvényes (bármilyen értelmezésben igaz minden helyettesítésre ).

Más szóval, ha az állítmányszámítás azonosan igaz formulája, akkor az predikátumkalkulusban bizonyítható. [egy] $\Phi$ $\Phi$

Bizonyítás

Az azonos igazságból azt kapjuk, hogy a halmaznak nincs modellje . A modell létezési tételéből következik, ami ellentmondásos, vagyis az állítmányszámítási tétel. A következtetés szabályával azt kapjuk, hogy bizonyítható. [egy] $\Phi$ $\{\neg \Phi \}$ $\{\neg \Phi \}$ $\neg \Phi \vdash$ ${\frac {\Gamma ,\neg \Phi \vdash }{\Gamma \vdash \Phi ))$ $\Phi$

Lásd még

Jegyzetek

↑ 1 2 Ershov, 1987 , p. 139.

Irodalom

Ershov Yu.L. , Palyutin E.A. Matematikai logika. — M .: Nauka, 1987. — 336 p.