# FOM: HA and Post's Problem

Stephen G Simpson simpson at math.psu.edu
Tue Sep 19 19:34:49 EDT 2000

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.

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