FOM: HA and Post's Problem

[jvoosten@math.uu.nl]

This is a reaction to Simpson's messages
of August 7 and August 11.
Simpson shows that the statement "every
non-recursive set is many-one complete"
is consistent with HA (intuitionistic
first-order arithmetic). He goes on to conclude
that "the Friedberg/Muchnik solution of
post's Problem is inherently nonconstructive".

It should be pointed out that while Simpson's proof
is correct, the statement depends on which of several
(intuitionistically) inequivalent formulations of 
"non-recursive" one takes.

Suppose that we define "W_a is not recursive" as:
$\neg\exists f\forall x(fx defined and (fx=0 <--> x\in W_a))$
(This is essentially weaker than Simpson's formulation)

Then the statement
 $\forall a(W_a is not recursive --> W_a is m-complete)$
IS inconsistent with HA.
This is because Post's simple construction (1944) of a simple
set S can be carried out in HA; one can show that the complement
of S is infinite, since S is the image of a partial recursive
function F which satisfies F(x)>2x (if F(x) is defined). Moreover
S intersects every infinite r.e. set.
Hence, S is non-recursive in the sense given above, and S is
not creative.
If K is m-reducible to S, S would be creative; contradiction.
(K is the halting set) 

I believe that about Turing reducibility, nothing interesting
can be said as far as provability in HA is concerned; because,
by realizability, HA is consistent with "every total function
is recursive". So 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.