# turing recognisable = complement of co-recognisable

Define: RE = {L : L is recognizable by a TM}, R = {L : L is decidable by a TM}, and coRE = {L : L-complement is recognizable by a TM}.
The question is: Does the complement of coRE equal RE?
I know that the answer is false, but I'm not sure why my proof is wrong:

Let $$A=\{ \overline{L'} \in \Sigma^* \mid L' \in \mathsf{RE} \}$$ (notice that I renamed the variable used in the definition of the set to avoid confusion). It is false that $$L \in A \iff L \in \mathsf{RE}$$.

To see this consider the language $$H$$ of the halting problem, which is well-known not to be decidable. $$H \in \mathsf{RE}$$ since you can simply simulate a Turing Machine until it halts (possibly never) and then accept. However $$H \not\in A$$. Indeed, $$H \in A \iff \overline{H} \in \mathsf{RE}$$ but $$\overline{H}$$ is not recognizable (otherwise both $$H$$ and $$\overline{H}$$ would be recognizable, which would imply that $$H$$ is decidable).

I'm assuming you mean $$L \in P(\Sigma^*)$$ instead of $$L \in \Sigma^*$$. Remember that by $$\{x \in D | \varphi(x)\}$$ we simply denote $$\{x | x \in D \land \psi(x)\}$$ and $$\overline{\{x | \varphi(x)\}} = \{x | \neg \varphi(x)\}$$.

The mistake is in the second equivalence of your proof, you assert that $$L \in \overline{\{L \in P(\Sigma^*) | \overline{L} \in \texttt{RE}\}} \iff L \in \{\overline{L} \in P(\Sigma^*) | L \in \texttt{RE}\}$$ which is equivalent to $$\neg(L \in P(\Sigma^*) \land \overline{L} \in \texttt{RE}) \iff \overline{L} \in P(\Sigma^*) \land L \in \texttt{RE}$$ but this is invalid (try applying DeMorgan's laws to the lhs).

The third equivalence isn't valid either, it's not the case that $$L \in \{\overline{L} \in P(\Sigma^*) | L \in \texttt{RE}\} \iff L \in \texttt{RE} = \{L \in P(\Sigma^*) | L \in \texttt{RE}\}.$$

Note that a language $$L$$ is a subset of $$\Sigma^*$$ and not an element in $$\Sigma^*$$, and here we're considering classes of languages. So I assumed that you meant $$L$$ is a language over $$\Sigma$$.

It looks like you have complemented the set $$\{ L \subseteq \Sigma^*: \overline{L}\in \text{RE} \}$$ incorrectly. Specifically, you assumed that: $$\overline{\{ L \subseteq \Sigma^*: \overline{L}\in \text{RE} \}} = \{ \overline{L}\subseteq \Sigma^*: L\in \text{RE}\}$$

but this is incorrect as you should complement the set $$\{ L \subseteq \Sigma^*: \overline{L}\in \text{RE} \}$$ as follows: $$\overline{\{ L \subseteq \Sigma^*: \overline{L}\in \text{RE} \}} = \{ L \subseteq \Sigma^*: \overline{L}\notin \text{RE} \}$$

In general, if we have a condition $$c$$ and a set $$A$$ given by $$A = \{ x: \text{x satisfies c}\}$$, then $$\overline{A} = \{ x: \text{x does not satisfy c}\}$$.

Note that:

• $$\{ \overline{L}\subseteq \Sigma^*: L\in \text{RE}\}$$ is the class of languages whose complement is in $$\text{RE}$$, and thus it is actually $$\text{coRE}$$. So you also have another mistake in the last equivalence, not only in the middle one.
• $$\{ L \subseteq \Sigma^*: \overline{L}\notin \text{RE} \}$$ is the class of languages whose complement is not in $$\text{RE}$$, and thus it is actually $$\overline{\text{coRE}}$$, which is the class you've started with, and that makes sense...