Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.?

share|improve this question
    
They are not necessarily r.e. or co-r.e. There is a hierarchy that goes up from recursive, and they are low down in that hierarchy. –  André Nicolas Feb 9 '13 at 2:17
    
Whats the name of the hierarchy? –  goblin Feb 9 '13 at 2:33
    
It is the arithmetical hierarchy. –  André Nicolas Feb 9 '13 at 2:54
    
Can Godel's incompleteness theorems be "circumvented" by allowing theories to have complexity in the arithmetical hierarchy? –  goblin Feb 9 '13 at 3:11
    
If you mean by using say a $\Sigma_2^0$ set of axioms? We still get incompleteness, it will just be pushed one level upwards. –  André Nicolas Feb 9 '13 at 3:18

2 Answers 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.

share|improve this answer

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.

share|improve this answer
    
It's more or less what I was looking for. What does the superscript on the $\Delta$ mean? –  goblin Feb 9 '13 at 3:28
    
These sets are not $\Delta_1^0$. $A$ and $B^c$ are $\Sigma_1^0$ and $\Pi_1^0$. Hence they belong to the next level, i.e. $\Sigma_2^0$ and $\Pi_2^0$. Hence they are $\Delta_2^0$. –  William Feb 9 '13 at 9:21
    
You are right. I fixed it. –  Sriram S Feb 9 '13 at 15:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.