# does the language 𝐿 = {< 𝑀1 >, < 𝑀2 >: 𝐿(𝑀1 ) ⊆ 𝐿(𝑀2)} is in co-RE?

i was asked to determine if its in RE and if its in co-RE. well i think its easy to say the language is not in RE but i was wondering if this language is in co-RE. so the question is if $$\overline{L}$$= {< 𝑀1 >, < 𝑀2 >: $$\ 𝐿(𝑀1 )\not\subseteq\ 𝐿(𝑀2)$$} is in RE? my intuition is that if there is a word in 𝐿(𝑀1 ) which is not in 𝐿(𝑀2 ), we can eventually get to this word and try to run it on both machines.

• Since $\bar L$ includes any string that is not in $L$, it includes the string $\langle M1 \rangle$ so your definition of $\bar L$ is not correct. What you could do is prove that $L \notin R$ and $L \in RE$ which would mean that $\bar L \notin RE$ and hence $L \notin$ co-RE – user137481 Jan 15 at 23:34