Is every subset of a decidable set, also decidable?

Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable?

I believe it would be true because all the subsets of B should also be decidable making A decidable. I'm not sure if my thought process is right or if there's a easier more intuitive way to explain this.

• Try proving your claim more formally. What happens for example when $B = \{0,1\}^*$? How would a machine for $B$ be helpful for deciding an arbitrary subset $A \subseteq B$? Nov 12 '13 at 18:06
• What Yuval wrote is almost a complete proof that the statement isn't true; just give an example of any undecidable subset of $B$. Nov 12 '13 at 21:42
– Raphael
Nov 13 '13 at 22:00
• @YuvalFilmus I saw a solution to this question and it says that any undecidable language is a subset of a decidable language ? How is that ?
– user22295
Nov 12 '14 at 15:40
• @Wick Every language is a subset of $\Sigma^*$, which is decidable. Nov 12 '14 at 15:57

This is a common misconception: complexity is not a measure of size. That is, it's not that "bigger" language are harder. Intuitively, a language becomes harder when it's harder to describe it (TMs being a form of description). For example, as @Yuval Filmus points out in the comments, the language whose description is "everything" is very easy to decide.

Similarly, the converse is not true - that is, smaller languages are not "harder" as well. For example, the language "nothing" is also easily decidable.

So the containment relation does not preserve hardness. Indeed - that's why we use the relatively complicated notion of reductions between languages, rather than showing containment.

So the simple answer to your question is that it's false, and an example, as in the comments, is $\Sigma^*$, which is decidable, but contains an undecidable language (indeed, every undecidable language).

• this may be dumb but I understand how {0,1}* is decidable, can create a machine to simulate, what would a subset be of that that is undecidable Nov 12 '13 at 18:22
• Perhaps the concrete 0 and 1 confuse you. Think of any alphabet $\Sigma$, and take an undecidable language $L$ over $\Sigma$ (pick your favorite undecidable language). Now, consider the language $\Sigma^*$. You have that $L\subseteq \Sigma^*$. Nov 12 '13 at 18:32
• I am just curious. Does is work the other way around? If I have an undecidable problem B, does it hold that every $A \subseteq B$ is also undecidable? Sep 17 '14 at 10:29
• Nope, same idea, take the empty language, which is contained in every language, but is decidable. Or take any finite language, etc. Sep 17 '14 at 10:40

Definitely not. Just think about that the universal set of input is a decidable language, but there are infinite subsets of it are undecidable...

Its not true.

Proof : Let $$A=\Sigma^*$$,we know that $$A$$ is decidable. Now lets take a look at

$$\Sigma^*\cap A_{TM}=A_{TM}$$ Since $$\Sigma^*$$ is the Set which contains all languagues it also contains $$A_{TM}$$. But $$A_{TM}$$ is known to be undecidable. Therefore its not true for all languagues that every subset of a decidable languague is decidable . $$\blacksquare$$