Are the undecidable languages closed under complement? How can the answer be proved?
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ Prove the contrapositive: the complement of a decidable language is decidable. $\endgroup$– Yuval FilmusCommented Sep 4, 2017 at 10:10
-
2$\begingroup$ Try to prove a more general fact: For any self-inverse function $f : A \to A$, set $B \subseteq A$ is closed against $P$ if and only if $\overline{B} = A \setminus B$ is closed against $P$. $\endgroup$– RaphaelCommented Sep 4, 2017 at 10:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Suppose you could decide the complement. Wouldn't you then be able to decide the language itself?
answered Sep 4, 2017 at 10:33