The Journal of Symbolic Logic

Research Article

Correction to A note on the Entscheidungsproblem

Alonzo Church

Princeton University

In A note on the Entscheidungsproblem the author gave a proof of the unsolvability of the general case of the Entscheidungsproblem of the engere Funktionenkalkül. This proof, however, contains an error, in order to correct which it is necessary to modify the “additional axioms” of the system L so that they contain no free variables (either free individual variables or free propositional function variables).

The additional axioms of L other than x=y→[F(x)F(y)] contain no free propositional function variables, and hence it is sufficient to replace each one by an expression obtained from it by quantifying all the individual variables by means of universal quantifiers initially placed—thus, in particular, x = x is replaced by (x)[x=x]. Moreover the axiom x=y→[F(x)F(y)] may be replaced by the following set of axioms:

and similar axioms for each of the functions b 1, b 2, …, bk .

(Received August 13 1936)