FOM: HA and Post's Problem

[jvoosten@math.uu.nl]

> 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,

Sure. I only pointed out that there is another, equally natural,
definition of "non-recursive" for which the statement "every non-recursive
set is many-one complete" IS inconsistent with HA.

> 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. 

OK. The point here is: suppose, for a set X of natural numbers X one defines
"s is an X-information sequence" if s codes a finite sequence of pairs
<a,b> such that b=0 <=> a\in X.

Let T(s,e,x,y) be the primitive recursive predicate: y codes a computation
(with oracle questions!) on machine e with input x, such that for every 
"oracle question" the program calls for, the required information is in s, 
and the computation uses that information.

Suppose that one defines "X is Turing reducible to Y" as:
There is e, such that for all x there is a y and an s such that s is a
Y-information sequence and T(s,e,x,y), and x\in X <==> U(y)=0
(where U(y) is the output of computation y)

This is an absolutely natural definition, I think. But now, since in HA
it is consistent that every total function is recursive, it is consistent
that "X is Turing reducible to Y" implies that the required s can be
obtained recursively in x. Hence X is recursive.

To be precise: HA+CT |- "X is Turing reducible to Y"--> X is recursive
for this definition of "X is Turing reducible to Y" (CT is the axiom
scheme asserting that every total relation contains a total recursive
function). So HA does not prove "K is Turing reducible to K" for this
definition.

Jaap van Oosten