# A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$

I read some computation theory lecture notes and after citing and proving the proposition: $$\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$$ it says that $$\emptyset\in S$$ is not a sufficient condition, i.e $$L_S \notin RE$$ doesn't yield $$\emptyset \in S$$, by giving the counter example $$L_{\Sigma ^*}:= \{\langle M\rangle : L(M) = \Sigma^*\}\notin RE$$ . However it says that there is a necessary and sufficient condition under which $$L_S\notin RE$$. I searched in Sipser's book for this condition but couldn't find it. I would really appreciate a reference for this condition.

Edit : given the answer by @dkaeae , I wish to know what is the stronger property one can deduce about a non-trivial $$S\subset RE$$ in case $$L_S \notin RE$$.

• It seems that you mean $\emptyset\in S$ is not a necessary condition from your contexts. – xskxzr Aug 19 '19 at 12:24
• Added the definition of $L_{\Sigma^*}$. I thought I had a counter example for cases in which $\emptyset \notin S$ and $L_S \in RE$ and thus $\emptyset \in S$ is a necessary condition, but it seems I have a problem with this counter examples so I have to rethink. – user5721565 Aug 19 '19 at 14:56
• The condition $\emptyset\in S$ cannot derive $L_S\notin \mathrm{RE}$. For example, if $S$ is the set of all languages, to which $\emptyset$ belongs certainly, then $L_S$ is the set of descriptions of all TMs, which certainly belongs to RE. – xskxzr Aug 20 '19 at 2:39
• I deleted my answer because evidently I completely messed up decidable and RE... (It happens.) – dkaeae Aug 22 '19 at 7:46