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.
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
More information about the FOM
mailing list