# Is $ALL\setminus(RE \cup co-RE)$ empty? [duplicate]

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 not really sure, but I think AH is a subset of ALL. So, if AH does not collapse, $ALL\setminus(RE \cup co-RE)$ is nonempty. – M.S. Dousti Apr 1 '11 at 15:18
• Complexity Zoo: "Each level of AH strictly contains the levels below it." That should answer your question. – Robin Kothari Apr 1 '11 at 15:39
• Robin, Sadeq, thank you for your comments and your links. I know of the polynomial hierarchy and I've heard of the arithmetical hierarchy, which turns out to be exactly what I was looking for. Can you post your comment as an answer, so that I can accept it? If not, should I just close the question? – chazisop Apr 1 '11 at 15:45
• "Given a computable predicate $P$, decide whether $P(x)$ is both 'true' and 'false' infinitely many times for positive integers $x$." Neither the positive nor negative result can be verified in a finite amount of time. – mjqxxxx Apr 1 '11 at 16:04
• chazisop, this is not a research-level question (the answer can be found in the first chapters of almost any computability textbook or on Wikipedia). I am therefore closing the question as off-topic. – Kaveh Apr 1 '11 at 20:41

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

• It's also worth noting that AH doesn't exhaust ALL either - the AH consists essentially of the (union of) the finite jumps of the recursive degree 0, and the operation can be iterated through countable ordinals beyond $\omega$. See en.wikipedia.org/wiki/Turing_jump for more details. – Steven Stadnicki Apr 1 '11 at 18:08