Try finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R

Question

"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.

Answer 1

Let $\widetilde{L}\not\in\mbox{RE}$ have alphabet $\widetilde{\Sigma}$. We define $\Sigma:=\{0,1\}\times\widetilde{\Sigma}$. Then for $i\in\{0,1\}$ we define $\widetilde{L_i}:=\{(i,c_1)(i,c_2)...(i,c_n):c_1c_2...c_n\in\widetilde{L}\}\not\in\mbox{RE}$. We can consider the languages $L_1:=\widetilde{L_0}$, $L_2:=(\{0\}\times\widetilde{\Sigma})^*$ and $L_3:=L_2\cup\widetilde{L_1}$ which have alphabet $\Sigma$. We get $L_1\subseteq L_2\subseteq L_3$ and $L_1,L_3\not\in\mbox{RE}$, but $L_2\in\mbox{R}$.

Answer 2

Let $H$ be a suitably chosen non-RE set and let $R$ be recursive. Then $$H\cap R \subsetneq R\subsetneq H\cup R.$$