# Proof: is the language $L_1=\{\langle M\rangle\mid\emptyset \subseteq L(M)\}$ (un)-decidable?

I want to show that $$L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\}$$ is decidable/undecidable - without rice theorem (just for the case that I can apply it).

Every language contain the $$\emptyset$$ as a subset. So my guess is that the language is decidable.

Therefore, let us assume that $$L_1$$ is decidable. Lets say that $$N$$ is the TM which decides $$L_1$$.

N = "with input $$$$:"

1. ...

How can I prove that $$N$$ is a decider for $$L_1$$?

• 1. output "true". – Hendrik Jan Jul 19 '20 at 0:22

Your language $$L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\}$$ is trivially decidable by a Turing machine $$T$$ that just checks whether $$\langle M \rangle$$ is a valid description of a Turing Machine. If it is, $$T$$ accepts. Otherwise $$T$$ rejects.
Notice that, for any Turing machine $$M$$, $$L(M)$$ is a set (by definition) and therefore $$\emptyset \subseteq L(M)$$ is always true.