3
$\begingroup$

Let $A \subseteq B$, and A is unrecognizable. I know in general that doesn't mean B is unrecognizable. However, are there some limitations we could put on A and B that would make it true? The only thing I could come up with was A=B. Plus, we could say B is unrecognizable as part of our assumptions, but that's not really helpful.

(recognizable means recursively enumerable, in case you use different terminology)

$\endgroup$
2
  • 3
    $\begingroup$ You can transfer the condition on $B$ to a condition on $B\setminus A$. Specifically, if $B\setminus A$ is decidable, then $B$ is unrecognizable (as otherwise you could decide $A$ as well). $\endgroup$
    – Shaull
    Feb 3 '15 at 21:41
  • $\begingroup$ @Shaull Make an answer? $\endgroup$ Feb 4 '15 at 5:01
3
$\begingroup$

The condition about $B$ can be transformed into a condition about $B\setminus A$, as follows. If $B\setminus A$ is decidable, then $B$ is unrecognizable. Indeed, if you could recognize $B$, you could determine whether a word $w$ is in $B\setminus A$. If it is, then it's not in $A$, otherwise it is. So $A$ would be recognizable as well.

Note, however, that the converse does not work - there are sets $C,D$ such that $C\cap D=\emptyset$, both $C$ and $D$ are not recognizable, and $C\cup D$ is unrecognizable as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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