# Is there a language in $RE \setminus R$ which is not $RE$-complete?

If any recursively enumerable language can be reduced by a mapping reduction to a language $L$, then $L$ is called $RE$ complete. In that case, $L$ must be in $RE\setminus R$. But are there languages in $RE\setminus R$ which are not $RE$ complete? Can anyone give an example of such a language? I'm sure this is well known, but it's not well known to me, and google doesn't help.

-
Yes, this is extremely well known, and covered in any reasonable recursion theory textbook at the graduate level. The usual construction makes a nonrecursive r.e. set that is not only intermediate in many-one degree, it's also intermediate in Turing degree. The construction, due independently to Friedberg and Muchnik, uses a priority argument. Soare's book or Rogers' book has all the details. – Carl Mummert Apr 9 '11 at 2:17
If by a mapping reduction from $A$ to $B$ you mean a recursive function $f$ such that $a \in A$ iff $f(a) \in B$, then it's somewhat easier than a priority argument. For these reductions, Post solved this problem using "simple sets" (r.e. sets whose complements contain no infinite r.e. sets). However, priority arguments are really beautiful and handle much more general sorts of reductions. – Henry Cohn Apr 9 '11 at 13:23
"Mapping reduction" is a (nonstandard) term that Sipser's computability textbook uses to refer to many-one reductions. It's a fine book but not focused at all on classical computability theory. – Carl Mummert Apr 9 '11 at 15:24
As Carl said, the construction by Friedberg and Muchnik uses a priority argument. It may be worth adding that they (indepedently) invented the priority method for just this problem (known as Post's problem). So in a sense, this question was at the root of much of the last half-century's development of recursion theory. – Andreas Blass Apr 9 '11 at 22:49