Is $ALL\setminus(RE \cup co-RE)$ empty? Possible Duplicate:
  Are there languages that are not in RE nor CO-RE?  




Let $ALL$ be the language of all decision problems. My question is, is there a language that is neither recognizable or complement-recognizable? If such a language exists, I believe it would be very interesting to study it (if it is possible!).
I'm posting my comment as an answer, at the request of the OP.

Arithmetic Hierarchy AH is a class of decision problems defined as below:

Let $Δ_0 = \Sigma_0 = \Pi_0 = R$. Then for $i&gt;0$, let


$Δ_i = R^ {\Sigma_{i-1}}$.
$\Sigma_i = RE ^{\Sigma_{i-1}}$.
$\Pi_i = coRE ^{\Sigma_{i-1}}$.


Obviously, AH $\subseteq$ ALL. On the other hand, "each level of AH strictly contains the levels below it." (As pointed by Robin Kothari in a comment above). Therefore, $ALL\setminus(RE \cup coRE)$ is nonempty.