# If a Language is Non-Recognizable then what about its complement?

Is the complement of a Non-Recognizable language

1. Recognizable
2. Non-Recognizable
3. May be Recognizable, May be Non-recognizable. I.e cant comment.

A mathematical proof would be of great help since im unable to think of any way to prove this.

I did some research on this and found below examples. Im specifying complement using a "!"

1. !A(TM) is a non-recognizable language while A(TM) is a recognizable language.
2. EQ(TM) is a non-recognizable language and !EQ(TM) is also non-recognizable language

The above two would mean that we simply cant comment on the Recognizability of the complement of non-recognizable language. But I feel that there should be some way to prove (or disprove) this.

Assuming that you can prove statement 1 and 2 above, you have just presented a proof. You're trying to show that there exists a language which is non-recognizable such that its complement is recognizable. You then prove that $!A(TM)$ has this property. Then you want to show that there exists a non-recognizable language whose complement is also non-recognizable and then you show that $EQ(TM)$ has this property.
• Just a note: point 1 is a direct consequence of the easy lemma: $L$ is decidable if and only if $L$ and $\bar{L}$ are recognizable. Point 2 can be proved using a Turing reduction from $EQ_{TM}$ to $\overline{A_{TM}}$ and from $\overline{EQ_{TM}}$ to $\overline{A_{TM}}$ – Vor Oct 19 '12 at 20:01