# For s set $S\subseteq RE$, so call feature of language $S=\emptyset$ vs. $S=\{\emptyset\}$

I'm trying to understand what's the difference between $$S=\emptyset$$ and $$S=\{\emptyset\}$$
The diffenition that I found for $$L_S=\{\langle M\rangle\ | L(M)\in S \}$$
I understood that $$S=\emptyset$$ and $$S=RE$$ are trivial and
$$S=\emptyset \Rightarrow L_\emptyset=\emptyset\in R$$
$$S=RE \Rightarrow L_{RE}=\Sigma^*\in R$$

But can't understand what's going with $$S=\emptyset$$ and $$S=\{\emptyset\}$$

## 1 Answer

Assume that all languages are over the alphabet $$\Sigma$$. What you have here is a bit of ambiguity in the meaning of $$\emptyset$$ (recall that the emptyset is defined w.r.t a universal set, and here $$\emptyset$$ is used w.r.t different universal sets). Indeed, $$S = \{ \emptyset\}$$ refers the set of languages containing only the empty language, that is, in this case, $$\emptyset\subseteq \Sigma^*$$. Also, $$S = \emptyset$$ refers to the empty set of languages, that is, in this case $$\emptyset\subseteq 2^{\Sigma^*}$$.

As you noted, if $$S = \emptyset$$, then $$L_S = \{ \langle M\rangle: L(M)\in \emptyset\} = \emptyset \in \text{R}$$. Now if $$S = \{ \emptyset\}$$, then $$L_S = \{ \langle M\rangle: L(M)\in \{\emptyset\}\} = \{ \langle M\rangle: L(M) = \emptyset\} = E_{TM}$$ which is known to be in $$\text{coRE}\setminus \text{R}$$.

• Thank you, I need to think a bit about it, just what do you mean by $E_{TM}$? – ChaosPredictor Jan 21 at 19:27
• The language of all TMs with empty language ($\{ \langle M\rangle: L(M)=\emptyset\}$) is know by the name $E_{TM}$ ($E$ stands form empty, and $TM$ stands for turing machine) – Bader Abu Radi Jan 21 at 19:33
• Sometimes they call it $EMPTY_{TM}$. I wrote it in case you want read about it. – Bader Abu Radi Jan 21 at 19:36
• I want to check that I understood it on the right way. $\{ \langle M\rangle: L(M)\in \emptyset\}$ stands for none of the languages of any TM will be accepted and because of it $M$ even don't need to be run on any input $x$, we can say straight away $L=\emptyset$. On the other hand $\{ \langle M\rangle: L(M) = \emptyset\}$ means that TM should be run on all the inputs and if it accept even one $x$, $M$ will be rejected – ChaosPredictor Jan 21 at 22:06
• You got it right. To be more precise: the language $\{ \langle M\rangle: L(M) \in \emptyset \}$ is the emptyset because for every TM $M$ the condition $L(M)\in \emptyset$ is not satisfied (the condition always evaluates to false). So a TM that decides the language immediately rejects all inputs (without even reading them). The language $\{ \langle M\rangle: L(M) = \emptyset \}$ is the language of all machines that do not accept any input ( they either reject or do no halt, on every input) - so you're right, a machine that accepts at least one input is not in the language. – Bader Abu Radi Jan 21 at 22:28