# A non-r.e. language whose complement is not r.e.

What's an example of a language that is not recursively enumerable and whose complement is also not recursively enumerable?

• Any language that is neither $\Sigma^0_1$ nor $\Pi^0_1$. The set of indices of total computable functions, the set of indices of partial computable functions with a bounded range, etc. – Carl Mummert Dec 21 '13 at 1:56

A language is r.e. if and only if it is $\Sigma^0_1$, which is to say if it can be defined with a formula of the form $(\exists t)P(n,t)$ where $P$ is a computable predicate.

So languages whose definition requires several nested quantifiers will not be r.e., and their complement will not be r.e.

A few examples include:

• The second Turing jump of the empty set, $\emptyset''$. This set is $\Sigma^0_2$. By Post's theorem it is $\Sigma^0_2$ complete, and thus not at any lower level of the arithmetical hierarchy.

• The set of indices of total Turing machines. This set is $\Pi^0_2$. ("For all $n$ there is a $t$ such that $\phi_e(n)$ halts in $t$ steps".)

• The set of indices of partial computable functions that have a bounded range. This set is $\Sigma^0_2$. ("There is a $k$ such that for all $n$ and $t$, if $\phi_e(n)$ halts in $t$ steps then the result is less than $k$").

The usual way of proving that these cannot be defined with fewer quantifiers is to show that the truth predicate for that level of the arithmetical hierarchy can be many-one reduced to an instance of the problem at hand.

For example, if $\psi \equiv (\forall n)(\exists m)Q(n,m)$ is an arbitrary $\Pi^0_2$ sentence, where $Q$ is a computable predicate, we can make an index for a partial computable function $g(n) = (\mu m)Q(n,m)$. Then $g$ is total if and only if $\psi$ holds, and an index for $g$ can be computed uniformly from a Godel number for $\psi$.

• Thanks very much. Does $(\mu m)\psi(m)$ here mean the smallest $m$ for which $\psi(m)$ holds? – MJD Dec 21 '13 at 17:37
• Yes, $(\mu m)\psi(m)$ is the smallest $m$ for which $\psi(m)$ holds, if there is any such $m$, and $(\mu m)\psi(m)$ is undefined (diverges as a computation) otherwise. So $\mu$ is an unbounded search operator. – Carl Mummert Dec 21 '13 at 18:32
• Thanks again. I'm glad that the answer turned out to be something I wouldn't have been able to figure out by myself. – MJD Dec 21 '13 at 21:36