patternMinor
Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable?
Viewed 0 times
implysubseteqcriteriaaremakewillthatunrecognizablethere
Problem
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)
(recognizable means recursively enumerable, in case you use different terminology)
Solution
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.
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.
Context
StackExchange Computer Science Q#37934, answer score: 3
Revisions (0)
No revisions yet.