FOM: HA and Post's Problem; correction

[jvoosten@math.uu.nl]

I made a mistake in my posting of Friday. I apologize for this;
it doesn't affect the argument, though.

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

The mistake is: "one can show that the complement of S is infinite".
One can't show $\forall x\exists y>x.\neg (y\in S)$, but one can show
$\forall x\neg\neg\exists y>x.\neg (y\in S)$. This is enough.

Jaap van Oosten
Lecturer, Dept of Mathematics
Utrecht University,
The Netherlands