Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
@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 E. Caicedo Nov 15 '10 at 1:59
@Andres Caicedo: Thanks. I'll fix it. – Arturo Magidin Nov 15 '10 at 3:49
up vote 2 down vote accepted

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.
  • Find a way to turn this partial order into a linear order while keeping the relevant properties.

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

share|cite|improve this answer
That was a pretty good hint, in that I got the answer, but it still took some thinking. – anon Nov 16 '10 at 0:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.