Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

It's well known that Kleene's O is $\Pi^1_1$-complete. Does the same thing go for the first-order theory of arithmetic? (I'm talking specifically without set quantifiers---the theory of arithmetic in the language of $PA$, not $ACA_0$) Is the theory of arithmetic lower than $\Pi^1_1$?

Either way, where would one find this fact proved? Who discovered it?

Thanks very much. I know it's a basic question, but I can't find the answer anywhere.

share|improve this question
add comment

2 Answers

If I understand the question you're asking, the theory of arithmetic in the language of PA is of degree $$0^{(\omega)}=\lbrace \langle x, y\rangle: x\in 0^{(y)}\rbrace,$$ the $\omega$th jump of $\emptyset$. To see why, just convince yourself that we can use one jump to tell whether a $\Sigma^0_1$ statement is true; two jumps to tell whether a $\Sigma^0_2$ statement is true; etc. (Actually, this just shows that the true theory of arithmetic is computable in $0^{(\omega)}$; this is, though, enough for your question. The other direction can be proved by coding Turing machines into the language of arithmetic, via Kleene's T predicate. That's definitely one of those "do-it-once-and-then-never-again" type of proofs.)

This is considerably smaller than the degree of Kleene's $\mathcal{O}$. To get an idea of just how much smaller it is, note that we can continue taking jumps past $\omega$: in fact, as long as $\alpha$ is a computable well-ordering, then $0^{(\alpha)}$ makes sense. Now, there are lots of computable ordinals: basically, any countable ordinal you can think of is computable (including the quite large proof-theoretic ordinals). Certainly, $\omega$ is very very small compared to $\omega_1^{CK}$, the first noncomputable ordinal. But each of these sets $0^{(\alpha)}$ for $\alpha$ computable is $\Delta^1_1$, that is, both $\Pi^1_1$ and $\Sigma^1_1$, and hence Kleene's $\mathcal{O}$ is much larger. See Sacks' book, "Higher Recursion Theory," for details on this and more.

As to who proved it, I believe that Kleene's paper which introduced the arithmetical hierarchy proved that the set of (Goedel numbers of) true $\Sigma^0_n$ sentences had degree $0^{(n)}$; I don't know whether he then explicitly observed the fact that the whole theory has degree $0^{(\omega)}$, but that follows immediately.

EDIT: Actually, the question of attribution might be a bit more subtle than that. The paper by Kleene which introduces the arithmetical hierarchy, "Recursive predicates and quantifiers" (http://www.jstor.org/stable/1990131?seq=1), was written in 1943; but I don't believe arbitrary Turing degrees (including the higher jumps) were treated explicitly until later (certainly no earlier than 1944, when Emil Post first posed his Problem, and no later than Kleene-Post 1954). By that time, though, the proof would certainly have been considered trivial from Kleene's work. The upshot is, I'm not sure when the statement "the true theory of $\mathbb{N}$ in the language of PA has degree $0^{(\omega)}$" was first explicitly stated.

FURTHER EDIT: Technically, my answer requires a bit of hyperarithmetic theory, which is maybe undesirable. Here's another way to show that the true theory of arithmetic is strictly weaker than Kleene's $\mathcal{O}$; this approach concludes that the theory is $\Delta^1_1$, which is still a bad upper bound, but enough to conclude that it's weaker than $\mathcal{O}$.

Given an arithmetic formula $\phi$, we can computably-in-$\phi$ come up with a game, $G_\phi$, in which player I tries to show $\phi$ is false and player II tries to show $\phi$ is true. This is described more in detail and generality in Vaananen's "Games and Models" (http://www.maths.manchester.ac.uk/logic/mathlogaps/workshop/ManchesterVaananen.pdf; it's what Vaananen calls the "semantic game"), where he calls it the "semantic game," and in other sources, where it's generally called "game semantics" for first-order logic. Basically, we first put $\phi$ into prenex normal form (which you should convince yourself we can do computably), and strip away the quantifiers one by one, with player I choosing values for each universally-quantified variable, and player II choosing values for each existentially-quantified variable. At the end of the game, a quantifier-free expression with no free variables is left; and player I wins iff that expression is false.

Now, player I has a winning strategy iff $\phi$ is false, and player II has a winning strategy iff $\phi$ is true. But saying that one player or another has a winning strategy is $\Sigma^1_1$: "there is a strategy (=real) such that no finite play (=finite sequence of naturals=natural) defeats it." So the set of Goedel numbers of true arithmetic statements is $\Sigma^1_1$, and the set of Goedel numbers of false arithmetic statements is also $\Sigma^1_1$. That's it!

[Note that the conclusion that "X wins the game" is $\Sigma^1_1$ relied on the fact that the game in question was clopen, i.e., guaranteed to end in finitely many moves; in particular, the semantic game has only as many moves as there are quantifiers in $\phi$. For a more complicated game, this would fail, and in fact open games - the simplest kind of game which can go on indefinitely - in which player II/Closed/Defender wins do not necessarily have winning strategies for II which are $\Delta^1_1$ in the game itself.]

share|improve this answer
    
Thanks for your comprehensive answer :) –  Anonymous May 29 '13 at 12:03
    
If this answers your question, you can accept by clicking the check mark to the left of the answer. –  Noah S Jun 5 '13 at 4:58
add comment

The theory of arithmetic is $\Delta^1_1$, thus it cannot be $\Pi^1_1$-complete (since $\Delta^1_1$ is a strict subset of $\Pi^1_1$ and these classes are closed under recursive preimages).

share|improve this answer
add comment

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.