4
$\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.

Improve this question
$\endgroup$
5
  • 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, 2013 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, 2013 at 21:42
  • $\begingroup$ See also this related question. $\endgroup$
    – Raphael ♦
    Nov 13, 2013 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$
    – user22295
    Nov 12, 2014 at 15:40
  • 2
    $\begingroup$ @Wick Every language is a subset of $\Sigma^*$, which is decidable. $\endgroup$
    – Yuval Filmus
    Nov 12, 2014 at 15:57

3 Answers 3

Reset to default
14
$\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).

Improve this answer
$\endgroup$
4
  • $\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, 2013 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, 2013 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, 2014 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, 2014 at 10:40
2
$\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...

Improve this answer
$\endgroup$
0
$\begingroup$

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$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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