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

I am not asking which order types PA proves are well ordered. That would be all up to $\epsilon_0$. Rather I mean, assuming a stronger ambient theory such as Zermelo set theory, which ordinals have the order type of some relation on $\mathbb{N}$ that is defined by a formula of PA (not requiring that PA prove the relation is a well ordering).

share|improve this question
3  
Woohoo! Three answers at once. –  Joel David Hamkins Nov 1 '12 at 17:24
add comment

3 Answers

up vote 7 down vote accepted

These are the recursive ordinals. The same well-order-types can be realized by recursive relations as by hyperarithmetical relations. PA-definable, i.e., arithmetical, falls nicely between these two. (I think you can go considerably lower, say to PTime-computable relations, and still have the same order-types.)

share|improve this answer
    
Is this too well know to need a reference when I invoke it in an article? Or can you suggest a reference? –  Colin McLarty Nov 1 '12 at 18:17
    
It's pretty well-known, but I guess you might as well give a reference. I think it's in Rogers's "Theory of recursive functions and effective computability", but I'm away from Michigan and can't just pull the book off my shelf and check. The result is probably originally due to Kleene, but I don't have a reference for that. –  Andreas Blass Nov 1 '12 at 19:14
add comment

The answer is the ordinal $\omega_1^{ck}$, named after Church and Kleene, which is defined to be the supremum of the ordinals coded by a computable relation on $\mathbb{N}$. It happens also to be the supremum of the order types of the relations coded by any arithmetic relation, that is, by any relation definable in the language of arithmetic.

share|improve this answer
add comment

The computable ordinals---that is, the ordinals below $\omega_1^{CK}$---are, by definition, represented by computable relations, all of which can be represented by formulas in PA, and indeed, even by fairly simple formulas. As Andreas points out, allowing arithmetic formulas instead of computable ones does not change the class of ordinals.

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.