3
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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$? $\endgroup$ – Yuval Filmus Nov 12 '13 at 18:06
  • $\begingroup$ What Yuval wrote is almost a complete proof that the statement isn't true; just give an example of any undecidable subset of $B$. $\endgroup$ – G. Bach Nov 12 '13 at 21:42
  • $\begingroup$ See also this related question. $\endgroup$ – Raphael Nov 13 '13 at 22:00
  • $\begingroup$ @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 ? $\endgroup$ – Out Of Bounds Nov 12 '14 at 15:40
  • $\begingroup$ @Wick Every language is a subset of $\Sigma^*$, which is decidable. $\endgroup$ – Yuval Filmus Nov 12 '14 at 15:57
10
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Jen Stone Nov 12 '13 at 18:22
  • $\begingroup$ 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^*$. $\endgroup$ – Shaull Nov 12 '13 at 18:32
  • $\begingroup$ 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? $\endgroup$ – Smajl Sep 17 '14 at 10:29
  • $\begingroup$ Nope, same idea, take the empty language, which is contained in every language, but is decidable. Or take any finite language, etc. $\endgroup$ – Shaull Sep 17 '14 at 10:40
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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