# Computational power of arithmetically complex sets

When learning basic computability theory we are usually given as examples of arithmetic sets sets which are complete for their level of the arithmetic hierarchy (like the halting set, the set of indices of total functions etc.). Our teachers are of course quick to point out that not all sets are complete in this way. However, one could still be led to believe that arithmetically complex sets have quite a lot of computational power. Surely this cannot be the case.

Can you give me an example of an arithmetic set $A$ of some (precise) complexity $\Sigma^0_n$ (or $\Pi^0_n$ or whatever) such that $A$ does not compute all the sets of lower complexity? Can you give me one where $A$ does not compute the halting problem?

I should point out that a friend (who likes models of PA) has already given me an example by constructing a particular model of PA whose standard system contains a completion of PA but omits the halting problem. While this example is perfectly fine, it feels like the problem should have a much more elementary solution.

-
I'm skeptical about your friend's model of PA because the halting set can be defined using a pretty weak fragment of PA. What is a model's 'standard system'? – Quinn Culver Jun 14 '13 at 6:33
@QuinnCulver The standard system of a nonstandard model $M$ of PA is the set $\{A\cap\mathbb{N};A\text{ is definable over$M$}\}$. It can be shown that all computable sets are contained in the standard system of any model, but it follows from an omitting types argument that there is a model whose standard system doesn't contain the halting set. – Miha Habič Jun 14 '13 at 10:49
But isn't $\Sigma^{0}_{1}$ comprehension part of PA, so that the halting set is in every model? – Quinn Culver Jun 15 '13 at 1:48
@QuinnCulver You need to be careful. Any model of PA can define the halting set, however its intersection with the standard part might not be the halting set as defined in the standard model. A nonstandard model might believe that a computation of a machine coded by a standard number halts by some nonstandard time. – Miha Habič Jun 15 '13 at 8:42
@Quinn Culver: in general the standard system of a model of PA is only a model of $\text{WKL}_0$, not of $\text{ACA}_0$. The collection of sets is called a "Scott set" in the literature. Here, crucially, PA is a theory of first-order arithmetic, not second-order arithmetic. – Carl Mummert Jun 18 '13 at 12:22

If you take the usual construction of a Turing incomplete real between $0$ and $0'$, via the Kleene-Post method, the real $\xi$ that is constructed is automatically $\Delta^0_2$, and in particular $\Sigma^0_2$, although $\xi$ does not compute $0'$ by construction. In the construction, we can also ensure $\xi$ is not $\Sigma^0_1$, so that the complexity is strictly $\Delta^0_2$.
In practice, every type of real made by a priority construction can additionally be made $\Sigma^0_n$ for sufficiently high $n$, where $n$ is large enough to cover all the oracles needed to make the construction effective. So the literature can be mined for other examples of oddly behaved arithmetical sets.
Any set $C$ which is c.e. and low relative to some low c.e. set $B$ will be $\Sigma^{0}_{2}$ but not above $\emptyset'$ because $C < _{T} C' \leq_{T} B' \leq_{T} \emptyset'$.