<p>I'm posting my comment as an answer, at the request of the OP.</p>

<p><a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#ah" rel="nofollow">Arithmetic Hierarchy</a> AH is a class of decision problems defined as below:</p>

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

<ul>
<li>$Δ_i = R^ {\Sigma_{i-1}}$.</li>
<li>$\Sigma_i = RE ^{\Sigma_{i-1}}$.</li>
<li>$\Pi_i = coRE ^{\Sigma_{i-1}}$.</li>
</ul>

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

CC BY-SA 2.5
2011-04-01T18:08:34.817Z
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 http://en.wikipedia.org/wiki/Turing_jump for more details.
Steven Stadnicki
CC BY-SA 2.5
2011-04-01T16:15:00.950Z
2011-04-01T16:15:00.950Z
Sadeq Dousti
<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/3203/are-there-languages-that-are-not-in-re-nor-co-re">Are there languages that are not in RE nor CO-RE?</a>  </p>
</blockquote>



<p>Let <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:A#all" rel="nofollow noreferrer">$ALL$</a> 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!).</p>

CC BY-SA 2.5
2011-04-01T15:18:48.893Z
I'm not really sure, but I think [AH](http://qwiki.stanford.edu/index.php/Complexity_Zoo:A#ah) is a subset of ALL. So, if AH does not collapse, $ALL\setminus(RE \cup co-RE)$ is nonempty.
Sadeq Dousti
CC BY-SA 2.5
2011-04-01T15:39:34.320Z
Complexity Zoo: "Each level of AH strictly contains the levels below it." That should answer your question.
Robin Kothari
CC BY-SA 2.5
2011-04-01T15:45:39.550Z
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
CC BY-SA 2.5
2011-04-01T16:04:13.567Z
"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
CC BY-SA 2.5
2011-04-01T20:41:35.533Z
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
CC BY-SA 2.5
2011-04-01T21:27:42.600Z
@Kaveh: This is a duplicate of http://cstheory.stackexchange.com/questions/3203/are-there-languages-that-are-not-in-re-nor-co-re.
Tsuyoshi Ito
CC BY-SA 2.5
2011-04-01T21:36:43.420Z
@Tsuyoshi, thanks. I will make it closed as duplicate (though I sincerely think this is *really* not research-level, see [Computability theory](http://en.wikipedia.org/wiki/Computability_theory)).
Kaveh
CC BY-SA 2.5
2011-04-01T23:16:14.883Z
You are both correct. Upon having the AH mentioned I realized this is well below research-level (my background in computability is of undergraduate level). Unfortunately, I was searching for recognizable and unrecognizable and that duplicate didn't come up.
chazisop
<computability>
Is $ALL\setminus(RE \cup co-RE)$ empty?
chazisop
# Is $ALL\setminus(RE \cup co-RE)$ empty?

(Asked by: username_0 on 2011-04-01)

> **Possible Duplicate:**  
> [Are there languages that are not in RE nor CO-RE?](https://cstheory.stackexchange.com/questions/3203/are-there-languages-that-are-not-in-re-nor-co-re)

Let [$ALL$](http://qwiki.stanford.edu/index.php/Complexity_Zoo:A#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!).

**Tags:** computability
> **Comments:**
> **username_1**: I'm not really sure, but I think [AH](http://qwiki.stanford.edu/index.php/Complexity_Zoo:A#ah) is a subset of ALL. So, if AH does not collapse, $ALL\setminus(RE \cup co-RE)$ is nonempty.  
> **username_2**: Complexity Zoo: "Each level of AH strictly contains the levels below it." That should answer your question.  
> **username_0**: 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?  
> **username_3**: "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.  
> **username_4**: 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.  
> **username_5**: @Kaveh: This is a duplicate of http://cstheory.stackexchange.com/questions/3203/are-there-languages-that-are-not-in-re-nor-co-re.  
> **username_4**: @Tsuyoshi, thanks. I will make it closed as duplicate (though I sincerely think this is *really* not research-level, see [Computability theory](http://en.wikipedia.org/wiki/Computability_theory)).  
> **username_0**: You are both correct. Upon having the AH mentioned I realized this is well below research-level (my background in computability is of undergraduate level). Unfortunately, I was searching for recognizable and unrecognizable and that duplicate didn't come up.  

---

## 1 answers

### Answer by username_1 on 2011-04-01. Score: 3 | Accepted answer

I'm posting my comment as an answer, at the request of the OP.

[Arithmetic Hierarchy](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#ah) 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.

> **Comments:**
> **username_6**: 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 http://en.wikipedia.org/wiki/Turing_jump for more details.  

---

