is the empty language L = ∅ a subset of every languages?

Question

I need to show false the following claim

Every language L which is a subset of $A_{TM}$ ($L \subseteq A_{TM}$) is undecidable.

For this, I wish to use the empty language L = ∅ (I know is decidable).

Is it correct that the empty language L = ∅ is a subset of every languages (and also of $A_{TM}$)?

Answer 1

Yes. Remember that $A\subseteq B$ just means "every element of $A$ is also an element of $B$." In case $A=\emptyset$, this is trivially true ("vacuously true") regardless of what $B$ is.

It may also help to think in terms of counterexamples: $A\subseteq B$ is the "default" situation, and is only false if there is a counterexample: some $x\in A$ with $x\not\in B$. Since there are no $x\in \emptyset$ in the first place, there are never any counterexamples to $\emptyset\subseteq B$ (again, regardless of what $B$ is).

---

It's worth mentioning that there are less trivial solutions to this problem as well. For example, fix some $a\in A_{TM}$. The padding lemma then builds us a computable infinite set $A\subseteq A_{TM}$ of "equivalent versions" of $a$ (not everything "equivalent to" $a$ shows up in $A$, but infinitely many things do).

And even more is true - $A_{TM}$ is computably enumerable, and we have the following general fact:

Every infinite computably enumerable set has an infinite computable subset.

This is a good exercise. HINT: think about the fact that any computably enumerable set which we can enumerate "in order" is computable.