Let A and B be languages with A ⊆ B, and B is Turing-recognizable. Can A be not Turing-recognizable? If so, is there any example?
This is something that confuses many students. The point here is that being subset of another language does not imply much about their difficulty of computation. You can always consider the trivial language $\emptyset$ and $\Sigma^*$ and any other language is between them w.r.t. set inclusion.
Therefore just knowing that a language contains or is contained in a easy to compute language doesn't say anything about the difficulty of computing it.
When a Turing-recognizable language $X$ is not decidable, it implies that it is not co-Turing-recognizable (in other words: $X^c$ is not recognizable). Since $X^c$ is a perfectly valid subset of $\Sigma^*$, this supports the fact that for a language $A \subseteq B$ where $B$ is Turing-recognizable, $A$ may very well not be.
Your discussion successfully confused me :(
"Can A be not Turing-recognizable?"
I feel A is always Turing-recognizable. Here is my thinking,
Since B is Turing Recognizable => There is some TM which accepts all the words of language B => There is a TM which accepts (all the words of language A + some other words) => There is a TM which accepts all the words of language A => A is Turing Recognizable.
Is this wrong? Can there be any case where A is Non-TRL while B is TRL. Kindly help
In this case A couldn't be Turing-recognizable. Take this as an example:
language B is the union of a language t.r (C) and a language not t.r(A). you can create a turing machine that recognizes B. A is not t.r and A ⊆ B.
is that right? i dont know if it is..so.. =)