prove A is co-re

Question

Working on some cs theory and solving a problem on computationally [=recursively] enumerable languages:

A language $A\subseteq \{0,1\}^*$ is co-c.e. if and only if there is a decidable language $B\subseteq \{0,1\}^*$ such that, for all $x\in\{0,1\}^*$,

$x\in A \Leftrightarrow (\forall w\in \{0,1\}^*) \langle x,w\rangle\in B $

This is a two sided proof since it is "iff"

=> Since $B$ is decidable therefore there exists a TM call $M1$ s.t. it decides $B$ so we build a new machine as follows. $M2$ couples $M1$ s.t. it uses $M1$ as a witness to verify whether the given input tuple for some $w$ element of $\{0,1\}^\ast$: $\langle x,w\rangle$ is rejected if so accept else reject.

Now this side of the proof is trivial, but I feel like for the other side we are essentially trying to prove the halting problem?

<= There exists a TM $M1$ s.t. it computes comp($A$), now if we are enumerating for all $w$ in the tuple $\langle x,w\rangle$; since it is an infinite set there is no possible way to guarantee the constructed machine will halt or not. (Halting problem)?

Answer 1

Before I actually start answering your question, I will prove the following (see my comment):

A language $A \subseteq \{0, 1\}^\ast$ is recursively enumerable iff there exists a recursive language $B \subseteq \{0, 1\}^\ast$ sucht that for all $x \in \{0, 1\}^\ast$: $$ x \in A \iff \exists w \in \{0, 1\}^\ast. \langle x , w \rangle \in B.$$

For recursively enumerable (r.e / c.e.) I think the following definition is common:

A language $A \subseteq \{0,1 \}^\ast$ is recursively enumerable if there exists a Turing machine $M$ such that for all $x \in \{0, 1\}^\ast$: $$M( x) = \begin{cases}1, & x \in A\\ \bot, & \text{otherwise.}\end{cases}$$

only if: Let $M_A$ be this machine. Let $B = \{\langle x, w \rangle \mid M_A(x) = 1 \text{ after } |w| \text{ steps}\}$. $B$ is recursive as we only need to simulate $M_A$ for a finite number of steps to get an answer. $B$ has obviously the desired property.
if: Let $B \subseteq \{0, 1\}^\ast$ recursive such that $x \in A \iff \exists w \in \{0, 1\}^\ast. \langle x, w \rangle \in B$. Let $M_B$ the machine that decides $B$. We define $M_A$ as follows: For input $x \in \{0, 1\}^\ast$ simulate $M_B$ multiple (maybe infinite) times: In the $i$-th simulationon we use $\langle x, w_i \rangle$ as input, where $w_i$ is the $i$-th word in the canonical orderng of $\{0, 1\}^\ast$. If $M_B$ outputs $1$ in some round $i$, $M_A$ terminates with output $1$. Otherwise, $M_A$ will never stop simulating $M_B$ with new $w_i$s. Thus, $$M_A(x) = \begin{cases}1, & \exists w \in \{0, 1\}^\ast. \langle x, w \rangle \in B\\ \bot, & \text{otherwise}\end{cases} = \begin{cases}1, & x \in A\\ \bot, & \text{otherwise.}\end{cases}$$ Hence, $A$ is recursively enumerable.

---

Now to your question: It is simply negation the conditions: $A$ is co-recursively enumerable iff there exists $B'$ (which is the complement of the $B$ I used above) such that for all $x \in A$: $$x \in A \iff \forall w \in \{0, 1\}^\ast. \langle x, w \rangle \in B'.$$ You can probably find a more direct argument but following the same idea as me. This proof was just what I had in my head the whole time.

Answer 2

For $\Leftarrow$, we are given a TM $M$ which decides $B$. To prove that $A$ is co-ce we need to construct a TM $N$ which accepts the complement of $A$. Concretely, we can craft $N$ so that it diverges on each word of $A$, and accepts each word on its complement $\overline A$.

We make $N$ take its input $x$, and then try all the words $w$, checking whether $\langle x,w \rangle\in B$. We can do this $M$ decides $B$. As soon as we find some $w$ such that $\langle x,w \rangle\notin B$, we stop and accept. If we don't find any such $w$, we diverge.

So, $N$ indeed accepts the complement of $A$ ($L(N)=\overline A$), which is what we wanted.