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

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?

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.

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.

share|improve this question
    
I think you at least need the power set axiom. –  Quinn Culver Sep 8 '11 at 21:11
1  
You might want to see this on math.SE math.stackexchange.com/questions/4778/… and perhaps also possibly this could be a question of interest for you as well. math.stackexchange.com/questions/46833/… –  Asaf Karagila Sep 9 '11 at 5:59
    
Thanks, Asaf. It looks like I shouldn't neglect math.stackexchange! –  Toby Bartels Sep 12 '11 at 16:24
add comment

2 Answers

up vote 13 down vote accepted

For the existence of an uncountable set with a definable well-ordering, it suffices to have $\mathcal P(\mathcal P(\mathbb N))$, 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 $\mathcal P(\mathcal P(\mathbb N))$, 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 $\mathcal P(\mathcal P(\mathbb N))$ seems to suffice.)

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 $\omega+\omega$; this contains plenty of uncountable well-ordered sets, but its ordinals are just those below $\omega+\omega$. (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.)

share|improve this answer
2  
To avoid a possible confusion: Some people omit the axiom schema of separation from the ZF axioms, since it can be deduced from replacement. When deleting replacement, to produce Zermelo set theory, these people should restore the separation axioms. –  Andreas Blass Sep 8 '11 at 22:43
    
Thanks, Andreas; this is exactly what I need! –  Toby Bartels Sep 12 '11 at 16:26
add comment

The number of countable ordinals is $\aleph_1$. The set 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 need 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.

share|improve this answer
5  
$V_{\omega_1}$ does satisfy the powerset axiom, as does any $V_\alpha$ for a limit ordinal $\alpha$. That's because taking a powerset only increases rank by 1. However, $V_{\omega_1}$ fails to satisfy the replacement axiom since there are plenty of very, very large sets in $V_{\omega_1}$, but so few ordinals... –  François G. Dorais Sep 8 '11 at 22:08
3  
@Michael: Your statement about satisfying the ZF axioms except for power set would become correct if the set $V_{\omega_1}$ of sets of countable rank were replaced with the set $H(\omega_1)$ of sets whose transitive closures are countable. $H(\omega_1)$ contains the same ordinals as $V_{\omega_1}$, namely the countable ordinals, but in other respects $H(\omega_1)$ is much smaller than $V_{\omega_1}$. –  Andreas Blass Sep 8 '11 at 22:50
    
Thanks again, Andreas, this is a useful model to have. –  Toby Bartels Sep 12 '11 at 16:27
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.