Foundations: Existence of uncountable ordinals. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T15:18:25Z http://mathoverflow.net/feeds/question/74938 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74938/foundations-existence-of-uncountable-ordinals Foundations: Existence of uncountable ordinals. Toby Bartels 2011-09-08T21:03:09Z 2011-09-08T21:37:18Z <p>This isn't really a research question, but at least it's research-level mathematics. I'm talking with some other people about the first uncountable ordinal, and I want some facts to inform this discussion. Specifically, what useful or interesting foundations of mathematics do or don't allow one to prove the existence of an uncountable ordinal?</p> <p>If you don't have a better interpretation, then for "useful", you can probably take "capable of encoding most if not all rigorous applied mathematics"; for "interesting", you can probably take "popular for study by researchers in foundations". For "existence of an uncountable ordinal", you could take "existence of a well-ordered uncountable set", "existence of a set whose elements are precisely the countable ordinals", etc.</p> <p>Hopefully there is a body of known results or obvious corollaries of such, since it could be a matter of some work to apply this question to foundational system X, and I don't expect anybody to do that.</p> http://mathoverflow.net/questions/74938/foundations-existence-of-uncountable-ordinals/74939#74939 Answer by Michael Hardy for Foundations: Existence of uncountable ordinals. Michael Hardy 2011-09-08T21:36:49Z 2011-09-08T21:36:49Z <p>The number of <em>countable</em> ordinals is $\aleph_1$. The <em>set</em> of all countable ordinals is the smallest uncountable ordinal $\omega_1$. So is there such a set, or is that a proper class? Suppose you look at the set of all sets of rank less than $\omega_1$. In ZF, that actually is a set, not a proper class. If I'm not mistaken, it is a model of all of the axioms of ZF except the power set axiom. Within that model, the set of countable ordinals is a proper class. Are all of them countable within that model? I.e., each of them has an enumeration, and the question is whether such an enumeration is one of the sets in that model. I'm rusty on some of this, but if I have all of this right, then this shows you cannot get uncountability in ZF minus the power-set axiom. Does this mean you <em>need</em> the power-set axiom for that? I don't think so, you might be able to add some weaker axiom or other axiom that would give you that. In fact, if you just add a new axiom that says there is a set containing every countable ordinal as a member, I think that's quite a bit weaker than the power-set axiom.</p> http://mathoverflow.net/questions/74938/foundations-existence-of-uncountable-ordinals/74940#74940 Answer by Andreas Blass for Foundations: Existence of uncountable ordinals. Andreas Blass 2011-09-08T21:37:18Z 2011-09-08T21:37:18Z <p>For the existence of an uncountable set with a definable well-ordering, it suffices to have <code>$\mathcal P(\mathcal P(\mathbb N))$</code>, where $\mathcal P$ means the power set. Any countable order-type is represented by a well-ordering of $\mathbb N$, and can therefore be coded by a subset of $\mathbb N$. Call two such codes equivalent if the well-orderings they code are isomorphic. Then the equivalence classes are elements of <code>$\mathcal P(\mathcal P(\mathbb N))$</code>, they correspond naturally to the countable ordinals, and so they constitute an uncountable well-ordered set. (If you want the well-ordering itself to be a set, rather than given by a definition, and if you want it to be literally a set of ordered pairs, with ordered pairs defined in the usual Kuratowski fashion, then you'll need some more assumptions to ensure the existence of the relevant ordered pairs, etc. But if you're willing to settle for some other coding of ordered pairs, then <code>$\mathcal P(\mathcal P(\mathbb N))$</code> seems to suffice.)</p> <p>In particular, the existence of an uncountable well-ordered set is well within the power of Zermelo set theory (like ZF but without the axiom of replacement). If, on the other hand, you want the set of countable ordinals and if you use von Neumann's (nowadays standard) representation of ordinals by sets, then Zermelo set theory is not enough. One natural model of Zermelo set theory is the collection of sets of rank smaller than <code>$\omega+\omega$</code>; this contains plenty of uncountable well-ordered sets, but its ordinals are just those below <code>$\omega+\omega$</code>. (The moral of this story is that, in Zermelo set theory and related systems, ordinals should not be defined using the von Neumann representation but rather as isomorphism classes of well-orderings.)</p>