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.
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.]
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).
