Language decidability and Post's theorem

Question

I have the following exercise on decidability:

Show that the language $L$ is decidable if and only if there exist decidable languages $A$ and $B$ such that $L=\{x\;|\;(\exists y)[\langle x, y\rangle\in A]\}=\{x\;|\;(\forall y)[\langle x, y\rangle\in B]\}$.

There is a hint to use Post's theorem. Any suggestion how to show this?

Answer 1

If you already know that "Post's theorem" implies decidable = $\Delta^0_1$, then the whole proof becomes a 1-liner: The RHS conditions say precisely that $L$ is both $\Sigma^0_1$ and $\Pi^0_1$, i.e. that $L$ is $\Delta^0_1$. In the event you haven't proved that, the following shows why it's true.

($\Longleftarrow$) Given decidable $A, B$, suppose $L$ is such that $$\begin{align} L &= \{x\mid(\exists y)[\langle x, y\rangle\in A]\} \tag{$\Sigma$}\\ &= \{x\mid(\forall y)[\langle x, y\rangle\in B]\} \tag{$\Pi$}. \end{align}$$ The identity ($\Sigma$) shows that $L$ is $\Sigma^0_1$ (alias, semi-decidable, alias recursively enumerable). The identity ($\Pi$) shows that $L$ is $\Pi^0_1$ (hence its complement is semi-decidable, alias recursively enumerable). Therefore $L$ is $\Delta^0_1$, which is the same thing as decidable (alias recursive).

To see more explicitly why this is so, we can write $L^c$, the complement of $L$, in terms of $B$ in a $\Sigma^0_1$ way: $$\begin{align} L^c &= \{x\mid \neg(\forall y)[\langle x, y\rangle\in B]\} \\ &= \{x\mid (\exists y)[\langle x, y\rangle\notin B]\} \\ &= \{x\mid (\exists y)[\langle x, y\rangle\in B^c]\} \\ \end{align}$$ Because $B$ is decidable, so is $B^c$. Thus, just like $L$, the complement $L^c$ of $L$ is the projection of a decidable relation. To enumerate $x$ into $L^c$ involves an unbounded search through all $(x,y)$ until one is found that's in $B^c$.

An algorithm for deciding membership in $L$ is as follows. There are, in principle, procedures decide_A(x,y) and decide_not_B(x,y) which decide membership of $\langle x,y \rangle$ in $A$ and $B^c$ respectively. So here's a procedure for deciding membership in $L$:

def decide_L(x):
    y = 0
    while True:
        if decide_A(x,y):
            return True        # x is in L
        if decide_not_B(x,y):
            return False       $ x is in complement of L
        y = y + 1

This procedure will always terminate, because for each $x$, some $y$ will be found such that one of the two procedures it calls will return True with arguments $x,y$.

Note: Actually, these "procedures" are all "functions", in the programming language sense, as they return values.

($\Longrightarrow$) If $L$ is decidable, then both $L$ and $L^c$ are semi-decidable, so there are decidable $A, C$ such that: $$\begin{align} L &= \{x\mid(\exists y)[\langle x, y\rangle\in A]\} \\ L^c &= \{x\mid(\exists y)[\langle x, y\rangle\in C]\}. \end{align}$$ Then $B = C^c$ is decidable, and $$\begin{align} L^c &= \{x\mid(\exists y)[\langle x, y\rangle\in C]\} \\ &= \{x\mid(\exists y)[\langle x, y\rangle\notin B]\} \\ &= \{x\mid(\exists y)\neg[\langle x, y\rangle\in B]\} \\ &= \{x\mid \neg(\forall y)[\langle x, y\rangle\in B]\}. \end{align}$$

Therefore, $L = \{x\mid (\forall y)[\langle x, y\rangle\in B]\}$.