# Determine if for given some $L$, $S_L={L(M) : <M>\in L}$ then for any $L$, if $S_L=RE$ then $L\in R$ is True or False and explain

Determine if for given some $$L$$, $$S_L=\{\ L(M) | \in L \}$$ then for any $$L$$, if $$S_L=RE$$ then $$L\in R$$. Correct or Incorrect and explain why.

I think the claim is incorrect, and I'm trying to explain it with cardinals. I know that for each language we have $$\aleph0$$ turing machines and $$|RE|$$ is also $$\aleph0$$ but I know that is countable, actually, I don't know how to make the connection if $$S_L=RE$$ then is somehow is not counable.

Edit: I am looking to solve it with cardinals.

The statement is incorrect*. Consider that

$$RE = \{L(M) \mid M \text{ is a turing machine} \}$$

Thus

$$\{ \langle M \rangle \mid M \text{ is a turing machine}\} \subseteq L \implies S_L =\{\ L(M) \mid \langle M \rangle \in L \} = RE$$

Therefore if I set

$$L = \{ \langle M \rangle \mid M \text{ is a turing machine}\} \cup \{ \#\langle M \rangle \mid M \text{ is a TM that always halts}\}$$

where # is some character that does not occur in turing machine encodings, we have $$S_L = RE$$ but $$L \not\in R$$ as the halting problem could be reduced to it.

* when assuming that $$M$$ in $$S_L$$ ranges over all turing machines. Otherwise the statement is ambiguous.

• This is correct except for the incorrect statement that $S_L=RE\iff \{\langle M\rangle \mid M\text{ is a turing machine}\}\subseteq L$. Only one direction is correct, which is $\{\langle M\rangle \mid M\text{ is a turing machine}\}\subseteq L \implies S_L=RE$, which is the direction you actually use Jul 28 '21 at 11:30
• @nirshahar Thanks for the hint. But can you actually come up with any $L$ for which the other direction actually doesn't hold? Jul 28 '21 at 11:36
• Yes, for example $L_{M_0}:=\{\langle M\rangle \mid M \text{ is a TM}\} \setminus \{\langle M_0\rangle \}$ for any TM $M_0$ of your choice. Note that $\exists M: \langle M\rangle \in L \land L(M)=L(M_0)$ Jul 28 '21 at 11:39
• @nirshahar Oh, of course, yes. Thanks, I wasn't thinking straight. Jul 28 '21 at 11:43
• Thanks for this solution, But actually, I am trying to prove it with cardinal numbers reason, as I started to prove it to show that is not countable. Jul 28 '21 at 11:57