What ordinals are definable relations in Peano Arithmetic? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T20:40:15Z http://mathoverflow.net/feeds/question/111176 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111176/what-ordinals-are-definable-relations-in-peano-arithmetic What ordinals are definable relations in Peano Arithmetic? Colin McLarty 2012-11-01T16:56:11Z 2012-11-01T17:22:44Z <p>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).</p> http://mathoverflow.net/questions/111176/what-ordinals-are-definable-relations-in-peano-arithmetic/111181#111181 Answer by Andreas Blass for What ordinals are definable relations in Peano Arithmetic? Andreas Blass 2012-11-01T17:21:26Z 2012-11-01T17:21:26Z <p>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.)</p> http://mathoverflow.net/questions/111176/what-ordinals-are-definable-relations-in-peano-arithmetic/111182#111182 Answer by Joel David Hamkins for What ordinals are definable relations in Peano Arithmetic? Joel David Hamkins 2012-11-01T17:22:30Z 2012-11-01T17:22:30Z <p>The answer is the ordinal <a href="http://en.wikipedia.org/wiki/Church%E2%80%93Kleene_ordinal" rel="nofollow">$\omega_1^{ck}$, named after Church and Kleene</a>, 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. </p> http://mathoverflow.net/questions/111176/what-ordinals-are-definable-relations-in-peano-arithmetic/111183#111183 Answer by Henry Towsner for What ordinals are definable relations in Peano Arithmetic? Henry Towsner 2012-11-01T17:22:44Z 2012-11-01T17:22:44Z <p>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.</p>