HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable?

Submitted by: @import:stackexchange-cs··
0
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)

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.

Context

StackExchange Computer Science Q#37934, answer score: 3

Revisions (0)

No revisions yet.