# 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". Jul 19 '20 at 0:22

## 2 Answers

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.

∅ Is the empty set symbol, not a valid string. Only valid strings may be contained in a language.

If you meant that L(M) = ∅ - It is not decidable: ETM Undecidability

If you meant that L(M) contains the empty string - it is also not decidable. Suppose D is a TM that decides it. Let F be a function that, given (M,w), Creates a Turing machine M' that ignores its input and emulates w on M and accepts if M accepts w. Now if M accepts w then M' accepts anything, including the empty string, and accepts nothing (including the empty string) otherwise. You would then be able to run M' on D to decide if M accepts w, a contradiction.

If you did mean your question literally, see this - https://math.stackexchange.com/questions/1464707/is-the-empty-set-in-every-language