ABSTRACT
In fact (1) is not recursively satisfiable if satis
fies the conditions of theorem 2. Let A(x, y, z) be $he
formula of ttf which theorem 2 shows that (x)(Ey)(z)A(x, y, z)
is provable in *y but not recursively satisfiable. Let aQ
be the number of the formula (y)(Ez) - A(b, y, z) . Let
f be the function purporting to satisfy (1). If it does,
then
(2)
is verifiable, where s(aQ, n) is the number of
Now clearly whose num
ber is i8 provable, for it is equivalent to Therefore by (2)
(3)
(4)
is false, then its negation is provable; and by existential
generalization, (3) is provable. Therefore (4) is true for every m . Since this argument holds for every n , it
follows that
is verifiable, contrary to the assertion of theorem 2 that (x)(Ey)(z)A(x, y, z) is not recursively satisfiable.