# Posts's Theorem

Published May 19, 2022  -  By Marco Garosi

Post’s Theorem, named after Emil Post, is a theorem in the computability theory that gives a characterization of recursive sets. Indeed it states that a set is recursive if and only if it and its complement (namely $\bar{A} = \N \setminus A$) are recursively enumerable (r.e.).

## Theorem

We can rewrite formally what we’ve just said:

$A \text{ recursive } \iff A \in \text{r.e. } \land \bar{A} \in \text{r.e.}$

Post's Theorem

### Proof

Let $A \subseteq \N \land \bar{A} = \N \setminus A$.

Similarly to what we do to prove Rice’s Theorem, we have to prove the double implication.

#### Left to right, $\implies$

Let’s assume that $A$ is recursive. Then it must have a characteristic function $f_A$, which is total and recursive.

Let’s define:

$\Psi(x) = \begin{cases} 1 &\text{if } f_A(x) = 1 \text{ } (x \in A) \\ \uparrow &\text{otherwise} \end{cases}$

Function $\Psi$ is partial (it does not always halt) and recursive; it is the semicharacteristic function of $A$.

You can construct an analogous function for $\bar{A}$. In fact, you could define $f_{\bar{A}} = 1 - f_A$.

Since $A$ and $\bar{A}$ have a semicharacteristic, partial recursive function $\Psi$, they are recursively enumerable (r.e.).

#### Right to left, $\impliedby$

Let’s assume that $A$ and $\bar{A}$ not be r.e., with semicharacteristic functions $\Psi_A$ and $\Psi_{\bar{A}}$. Hence we can define:

$f_A = \begin{cases} 1 &\text{if } \Psi_A(x) \downarrow \\ 0 &\text{if } \Psi_{\bar{A}}(x) \downarrow \end{cases}$

Since $A$ and $\bar{A}$ are complementary, then $x \in A \lor x \in \bar{A}$. So, function $f_A$ always returns a value, as long as $\Psi_A$ and $\Psi_{\bar{A}}$ are run in parallel on interleaving (one instruction of $\Psi_A$ and one of $\Psi_{\bar{A}}$). Running them in such a way prevents one function diverging from blocking the other — no blockings are created.

Function $f_A$, then, is total recursive; $A$ is thus recursive by definition. $\square$

Share on: