Is it always enough to prove that a subset $L'$ of a language $L$ is unprovable in order to prove that $L$ is undecidable?

Question

Given a language $L$, I sometimes try to find a subset of $L' \subseteq L$ which I can prove is undecidable. I conclude that if a subset of $L$ is undecidable, then $L$ must be undecidable as well. Is this correct for arbitrary languages $L$ and $L' \subseteq L$?

What if someone said: $L'$ could be empty (we don't know due to the undecidability of $L'$), and we cannot conclude anything about $L$ from $L' = \varnothing$, therefore the proof is insufficient. Is this a valid point?

---

For example, in order to prove that the language $$L = \left\{ w : M_w \text{ halts on a a finite set of inputs} \right\}$$ is undecidable ($M_w$ is a turing machine constructed from $w$), I use the fact that $L \text{ is undecidable} \iff L^c \text{ is undecidable}$. $L^c$ can be described as $$L^c = \left\{ w : M_w \text{ halts on an infinite set of inputs} \right\}$$ and $$L' = \left\{ w : M_w \text{ halts on all inputs } \Sigma^* \right\}$$ can be considered a subset of $L^c$. Using reduction, I can then prove that $L'$ is undecidable. If my assumption about subsets is correct, then $L^c$ must be undecidable as well, and therefore $L$ is undecidable.

(I know that the undecidability of the above language can be proven simpler, but I need an example for the use of subsets.)

Answer 1

No, your conclusion is not correct. The fact that $L'\subseteq L$ is undecidable do not imply anything about $L$. Indeed, consider $L=\Sigma^*$ for some finite alphabet $\Sigma$. Then, $L$ is decidable.

Now consider $L'\subset L$ such that $w\in L'$ iff $w$ is the description of a halting Turing machine written with characters from $\Sigma$. Then, $L'$ is, of course, undecidable.

Answer 2

$L'$ can not be empty and undecidable at the same time.

However, the objection stands: given $L' \subseteq L$, knowing that $L'$ is (un-)decidable does not imply anything about $L$.

Indeed, if the complement of $L'$ is infinite, there are uncountably many languages larger than $L'$, so most of those are undecidable (and not even RE).

There are also languages larger than $L'$ which are cofinite, i.e. the complement of a finite set. Those are decidable.

In general, trying to reason about the decidability of sublanguages or superlanguages is not useful. You have to write a reduction function (and prove it such) to achieve (un-)decidability results. If inclusion were enough, probably no one would bother with reduction :-)