Logik und Unentscheidbarkeit (II)

Satz: Das Gültigkeitsproblem der Prädikatenlogik ist unentscheidbar.

(Kurt Gödel, Alan Turing. http://thocp.net/biographies/papers/turing_oncomputablenumbers_1936.pdf)

Beweis:

• Halteproblem für TM ist unentscheidbar
• Halteproblem $\le$ Postsches Korrespondenzproblem (PCP)
• PCP $\le$ Gültigkeitsproblem

verwendet Reduktion A$\le$B : $\iff$
$\exists$TM-berechenbaresf : $\forall$x : x $\in$ A$\iff$f (x) $\in$ B.