1
$\begingroup$

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:
enter image description here

$\endgroup$

3 Answers 3

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.