Complements of recursively enumerable subsets.

Question

Let $A,B \subseteq \mathbb{N}$. If $A$ and $B$ are recursively enumerable, can we say anything about expressions like $A^c \cup B$, $A^c \cap B$, etc.?

Answer 1

A,B are recursively enumerable. That makes them $\Sigma_1^0$ sets. $A^c, B^c$ are $\Pi_1^0$ sets.

What this means is that the set $A$ can be expressed as $ \{ n\ |\ (\exists \vec{m})\ \psi_A(\vec{m},n) \} $, where $\psi_A$ is recursive. $B$ may be expressed identically, using the formula $ (\exists\ \vec{m})\ \psi_B(\vec{m},n)$ instead of $\psi_A$.

Note: I am using $\exists \vec{m}$ to denote a quantifier block.

$A^c$ can therefore be defined by $(\forall\ \vec{m}) \neg \psi_A(\vec{m},n)$.

If we take $A^c \cup B$ then it can be defined as $(\exists \vec{m_1})\ (\forall \vec{m_2}) \neg \psi_A(\vec{m_1},n)\ \lor\ \psi_B(\vec{m_2},n)$. This makes it $\Sigma_2^0$. But notice that the order of quantifiers does not matter in this one instance. So that makes it $\Pi_2^0$, as well. Therefore, it is a $\Delta^0_2$ set.

The same holds for $A \cap B^c$. One can place it in $\Delta^0_2$.

Not sure if this is the answer you were looking for.

Answer 2

These are the boolean combination of c.e. sets.

A 2-c.e. set $C$ is a set which has a computable approximation $C(x,s)$ such that for all $x$, $C(x) = \lim_{s \rightarrow \infty} C(x,s)$ and the approximation for any $x$ can change at most 2 times. That is $\{s : C(x,s) \neq C(x,s - 1)\}$ has size 2.

If $A$ and $B$ are c.e. sets, then $C = A \cap (\omega - B)$ is a 2-c.e. set. The 2-c.e. approximation of $A \cap (\omega - B)$ is the following: $C(x,s) = 1$ if and only if such that $A(x,s) = 1$ and $B(x,s) = 0$. Observe there can be at most 2 change, which occurs when $x$ appears first in $A$ and then latter in $B$ (so needs to be removed from C).

As you may be aware, the c.e. sets fall into the arithmetical hierarchy at $\Sigma_1^0$. This means that it is definable by a computable formula with a single existential quantifier. From the description of the 2-c.e. set above, $A \cap (\omega - B)$ is a $\Sigma_1^0 \wedge \Pi_1^0$ set. The 2-c.e. sets are exactly those sets definable by $\Sigma_1^0 \wedge \Pi_1^0$ formulas.

Generalizing, for each $n$, one can define the n-c.e.sets by the existence of computable approximation that changes at most $n$ times. They are also particular boolean combinations of c.e. sets. They can also be defined by boolean combination of $\Sigma_1^0$ formulas. Within the hierarchy, they lie below the $\Delta_2^0$ sets. $\Delta_2^0$ sets are also all limit computable sets.

It is simple exercise in a diagonalization argument to show that there exist a 2-c.e. set which is not c.e. (Observe that c.e. is the same as 1-c.e.). In general there are $n + 1$ c.e. sets that are not n-c.e. By using a finite injury argument, you can show that there are Turing degrees that contain $(n + 1)$ c.e. sets but no $n$-c.e. sets.