# Proving that a class of languages is a subset of RE for Rice Theorem

Consider language $L = \{<M> |L(M) \subseteq L(0(0\cup1)^*) \}$ where $<M>$ is a valid encoding of a turing machine.

I know that the language is applicable for Rice Theorem. Now, I understand that in this case the language group in $RE$ is:

$C = \{L\subseteq \Sigma^*|L\subseteq L(0(0\cup1)^*)\}$

However, I'm not sure how to prove that each of these languages is in the $RE$ class. Note That an alphabet wasn't given in the exercise so I guess that there can be other letters. I thought at first it had something to do with the languages being subests of a regular language, but then again $\Sigma^*$ is a regular language and all other languages are its subsets.

• $L\in \Sigma^*$ means that $L$ is a word, not a language. You probably mean $L\subseteq \Sigma^*$. – chi Dec 31 '17 at 17:29
• Also note that the sub-languages $L$ of $0(0\cup 1)^*$ are uncountably many, so surely some of them are not RE. I think you are not applying Rice correctly -- you probably should consider the recognizable sub-languages, only. – chi Dec 31 '17 at 17:31

You missed a tiny detail when defining $C$: all those languages are RE by assumption; no other language can be an $L(M)$!

Let us again look at the language you want to say something about:

$\qquad L = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \subseteq L\bigl(\, 0(0\cup1)^* \,\bigr) \}$.

We see that $L \subseteq \Sigma^*$ for some alphabet $\Sigma$ that depends on the TM encoding $\langle \_ \rangle$.

Now recall the statement of Rice's theorem: the index set

$\qquad \Phi(X) = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \in X \}$

of a language class $X$ is undecidable if $\emptyset \subsetneq X \subsetneq \mathrm{RE}$.

Now, it is obvious (read: very easy to prove -- your exercise) that $L = \Phi(C)$ with

$\qquad C = \{ Y \in \mathrm{RE} \mid Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$;

the requirement $\emptyset \subsetneq C \subsetneq \mathrm{RE}$ is likewise trivial.

We don't get to "just say" anything; we have to prove all three conditions -- $L = \Phi(C)$, $\emptyset \subsetneq C$, and $C \subsetneq \mathrm{RE}$ -- but it so happens that all three proofs are very easy here since $L$ has been defined in a very suitable way. For other languages, the proofs can be more intricate (or impossible; then Rice's theorem does not apply).

Side note: If we consider

$\qquad C' = \{ Y \in \Sigma^* \mid Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$

then we also get $\Phi(C') = L$! While there are non-RE $X$ in $C'$ (a simple if non-constructive argument is that there are uncountably many such $X$), $\Phi$ "ignores" them. However, $C'$ does not fulfill the conditions of Rice's theorem so we can not use it.

• I think I get it now from your answer and Chi's comment. You can say that this language is equal to the language with C as the enumerable subsets of the given set because if you remove the un-enumerable subsets it does't affect any other TM's in the set (doesn't exclude them) so the sets are equal. – Eloo Jan 2 '18 at 18:40
• @Eloo I have no idea what you're getting at there; I think you're making things more complicated than they are. But if it makes sense to you now, great. – Raphael Jan 2 '18 at 19:12