FOM: Recursion theory question

Harvey Friedman friedman at
Sat Feb 16 16:58:14 EST 2002

The following is well known.

THEOREM. "The set of all n such that there exists e < n with phi_e(0) = n"
is of Turing degree 0'.

Normally, one easily proves that this is effectively simple, and quotes
Donald Martin's theorem that every effectively simple set is of Turing
degree 0', whose usual proof is to use Donald Martin's theorem about DNR.
However, there is a simple direct proof of this Theorem that does not
involve this interesting machinery. This is also probably well known.

But now what about

CONJECTURE. "The set of all n such that there exists e < n such that n is
the largest element of W_e" is of Turing degree 0'.

Is this well known, or at least known? If not, then can you prove this? I
am confident that an expert in recursion theory can do this.

More information about the FOM mailing list