Given some unrecognizable language $L$, is it possible for its complement $\\ove
ID: 652927 • Letter: G
Question
Given some unrecognizable language $L$, is it possible for its complement $overline{L}$ to also be unrecognizable?
If some other language $S$ and its complement $overline{S}$ are both recognizable, then $S$ and $overline{S}$ are decidable. If $overline{S}$ is unrecognizable, then then $S$ is undecidable but still recognizable. Why do we ignore the idea that $S$ and $overline{S}$ may both be unrecognizable? This implies that $exists! s in S cup overline{S} = Sigma^*$ on which no machine halts, otherwise I don't see why we cannot have $x,y in Sigma^*$ and $x eq y$ such that no machine halts on $x$ or $y$, where $x in S$ and $y in overline{S}$.
Perhaps I am making a false assumption somewhere?
Explanation / Answer
I'll write "corecognizable" as a shortcut for "complement of recognizable". There are countably many recognizable languages and countably many corecognizable languages. Therefore, there are uncountably many languages which are neither recognizable nor corecognizable.