# Hint on Kleene's O

I figured out this order on $\omega^2$: elements of different columns are ordered by their column number; within column $m$, the order is $0 \gt 1 \gt 2 \gt \cdots \gt n$, where $n$ is the first such that $P(m,n)$ is true; then $0 \lt n+1 \lt n+2 \lt \cdots$. The column is an infinite descending sequence if there is no such $n$. This order is well-founded iff for all $m$ there is an $n$ such that $P(m,n)$ is true.

So I can reduce any $\Pi_{2}^{0}$ sentence to a computable ordering which is well-founded iff the sentence is true. I don't see how to do this for $\Sigma_{2}^{0}$.

Now Wikipedia tells me Kleene's $O$ is $\Pi_{1}^{1}$ complete, so I'm still a long way away from what I should be able to do. Rather than being told what the full reduction is, if instead I could just get a hint for the $\Sigma_{2}^{0}$ case, then maybe I can pretend to myself that I figured "most" of it out on my own?

-
@anon: if I got the subindex/exponent wrong in the $\Pi$ and $\Sigma$, I apologize. You can edit them appropriately. – Arturo Magidin Nov 15 '10 at 1:50
@Arturo: It should be $\Sigma^0_2$, $\Pi^0_2$. – Andrés Caicedo Nov 15 '10 at 1:59
@Andres Caicedo: Thanks. I'll fix it. – Arturo Magidin Nov 15 '10 at 3:49

The "usual proof" I know for $\Sigma^0_2$ is the same as for general $\Pi^1_1$ formulas. For $\Sigma^0_2$ formulas in particular, this is one possible method:
• Take the negation of your original formula to get a $\Pi^0_2$ formula. Construct a partial order on a subset of $\omega$ such that the partial order has an infinite descending sequence if and only if the original formula is false.
This is intentionally just a hint. The usual method by which these things are proved is not particularly obvious because it relies on a clever relationship between computable linear orders and computable subtrees of $\omega^{<\omega}$ (this relationship goes by the name "Kleene-Brouwer order").