Question

Let $L_1$ be a language.

I would like t prove that $L_1\in CO-RE$ if and only if exists a language $L_2$ s.t. $L_1=\{ u\,\, |\,\, \forall_{v\in\Sigma^*} : <u,v>\in L_2 \}$ and $L_2\in R$.

I'm not quite sure on where do I start here from?

I've tried writing down what I know and trying to develop any ideas, but got stuck at the very begining.

Since $L_1\in CO-RE$ then $\overline{L_1} \in RE$. That is, exists a TM $M$ s.t. $M$ accepts any $u\in \overline{L_1}$ (that is $u\notin L_1$) and either rejects or loops forever for $u\in L_1$.

But I dont see how does this assist me to construct such a language $L_2$ that will both be in $R$ and assist me?

And even if I do succeed, how am I to show the other way around - that if such a language $L_2$ exists that satisfies the above conditions, $L_1\in CO-RE$?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top