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

Question

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

Answer 1

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$.