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.

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.

share|improve this question
    
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
1  
@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

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
@Miha Habič: is there some other type of example, or some other property, that you are looking for? –  Carl Mummert Jun 20 '13 at 12:37
    
I guess I really can't avoid checking out the intermediate degree construction. Would you agree with Quinn's (now deleted) assertion that all the "naturally" occurring examples seem to turn out to be complete for their particular arithmetic complexity? It seems weird that anything we can think of is the most complicated thing we could have thought of. –  Miha Habič Jun 23 '13 at 11:17
    
@Miha Habič: it is a well known phenomenon among computability theorists that there aren't "natural" examples of intermediate sets. The well known "natural" examples are all complete at their level, and constructions that generate incomplete sets are always (in practice) noncanonical in the sense that that the construction itself has seemingly arbitrary choices, so it can make infinitely many examples, none of which seems better than any other. It is a somewhat mysterious phenomenon. –  Carl Mummert Jun 25 '13 at 1:50

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'$.

share|improve this answer

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.