# 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. – dan 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.86677915,"math_prob":0.99081933,"size":760,"snap":"2020-24-2020-29","text_gpt3_token_len":206,"char_repetition_ratio":0.12698413,"word_repetition_ratio":0.0,"special_character_ratio":0.2736842,"punctuation_ratio":0.096551724,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9992961,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-06-02T05:00:08Z\",\"WARC-Record-ID\":\"<urn:uuid:74777237-566b-43a0-bcc9-bfa51e491822>\",\"Content-Length\":\"141157\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d04495c9-59ab-4d19-8232-697a4ab1c02c>\",\"WARC-Concurrent-To\":\"<urn:uuid:4bb5abb6-e7b8-41ea-9f0f-ff0e47622405>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/112875/a-condition-for-emptyset-neq-s-subset-re-under-which-l-s-notin-re\",\"WARC-Payload-Digest\":\"sha1:IAV7AJ7UJOC7ESFAUTLKA6OR4MZXFQBD\",\"WARC-Block-Digest\":\"sha1:6VFMZGLYFKWFCXOYWAKABSAPEB43WG6N\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-24/CC-MAIN-2020-24_segments_1590347422803.50_warc_CC-MAIN-20200602033630-20200602063630-00528.warc.gz\"}"}