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)

Improve this question
$\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, 2015 at 21:41
  • $\begingroup$ @Shaull Make an answer? $\endgroup$
    – Yuval Filmus
    Feb 4, 2015 at 5:01

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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