# Showing an equivalent definition of $CO-RE$

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.