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$?


Equivalently: $\overline{L_1}$ is RE iff there is some $\overline{L_2}$ that is $R$ so that $\overline{L_1}=\{u | \exists v : <u,v>\in \overline{L_2}\}$ is RE.

  • $\Rightarrow$

Take $\overline{L_2}=\{<u,v> | v\text{ represents an execution accepting u in the MT accepting }\overline{L_1}\}$. It's R because you just simulate the MT following v and it'll either work or not. And it vefiries the property $\overline{L_1}=\{u | \exists v : <u,v>\in \overline{L_2}\}$ because a word is accepted iff some execution accepts.

You could also take $\overline{L_2}=\{<u,n> | u\text{ is accepted by an execution of size} n\}$.

  • $\Leftarrow$

Enumerate all $v$, for each, test is $<u,v>\in\overline{L_2}$ and if it is, accept. If the word is in $\overline{L_1}$ then some $v$ will work so it'll be accepted. So $\overline{L_1}$ is indeed RE.

Your property says is that being RE is the same thing as being the projection of a R set.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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