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$
  • 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$ – Yuval Filmus 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.