0
$\begingroup$

Given three languages $L_1, L_2, L_3$ with $L_1$ and $L_3$ being semi-decidable and $L_1 \subseteq L_2, L_2 \subseteq L_3$. Can I deduce from these properties, that $L_2$ is also semi-decidable and how would I proof this?

Intuitionally it seems obvious that $L_2$ is also semi-decidable, but I didn't find a way to prove (or falsify) it.

So far I only found information about the closure of semi-decidability under $\cup$ and $\cap$. Can I use these properties in any way?

$\endgroup$

marked as duplicate by David Richerby, D.W., Thomas Klimpel, Rick Decker, Juho Aug 6 '15 at 7:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

No, because every language $L$ satisfies $$ \emptyset \subseteq L \subseteq \Sigma^* $$ and $\emptyset$ and $\Sigma^*$ are both semi-decidable.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.