FOM: HA and Post's Problem

[Stephen G Simpson]

Reply to van Oosten, Fri, 15 Sep 2000.

Your main point is well taken.  As you observed, one can carry out in
HA Post's construction of a simple set S, and one can show in HA that
S is not creative, hence not many-one complete.  However, one cannot
show in HA that S is nonrecursive in the sense that I mentioned,
namely (forall e)(exists n)({e}(n) is undefined or unequal to 1 if n
is in S, 0 if n is not in S).  Indeed, as I remarked earlier, it is
consistent with HA that every nonrecursive (in this sense) r.e. set is
many-one complete.

I didn't understand your other point, about Turing reducibility.  You
said

 > if one formulates "W_a is T-reducible to W_b" in the usual way
 > which supposes the existence of a total function with the usual
 > properties, the statement $\forall a,b (W_a is T-reducible to W_b
 > --> W_a is recursive)$ is consistent; in particular, the relation
 > "is T-reducible to" is not provably reflexive.

but I don't get it.  There is certainly a very reasonable formulation
of "W_a is T-reducible to W_b" which is provably reflexive, so that
for instance K is T-reducible to itself, provably in HA.

-- Steve