Math people:

The title is the question. I am convinced that uncountable sets exist, thanks to Cantor's diagonal proof. It is not intuitively clear to me that uncountable ordinals or cardinals should exist. What axioms of set theory are needed to accept their existence? I think I have read here that the Axiom of Choice is not necessary. I am reluctant to accept as "true" any theorems that rely on the Axiom of Choice.

EDIT: This question may be a duplicate: I just found No uncountable ordinals without the axiom of choice? . I apologize if this is so.

  • 1
    $\begingroup$ It at least partly answers the question: $\mathsf{ZF}$ is sufficient, since it’s sufficient for the Hartogs’ number argument, but $\mathsf{ZF}$ minus the power set axiom is not. $\endgroup$ – Brian M. Scott May 26 '13 at 1:33
  • $\begingroup$ Duplicate of: this, and that, and also this, and of course the one linked in the question $\endgroup$ – Asaf Karagila May 26 '13 at 1:39
  • $\begingroup$ After giving more thought, I'm not sure if that's a complete duplicate of the above links (and I'd withdraw my vote to close if that was possible). This question can be read as a broader question than just the axiom of choice. True, it was particularly interested in the axiom of choice, but there are other axioms in $\sf ZFC$ that may or may not be used in that proof. Hence my answer below. $\endgroup$ – Asaf Karagila May 26 '13 at 1:55
  • $\begingroup$ What's the difference between the smallest uncountable ordinal, and a smallest uncountable ordinal? Those are the same. You don't need choice. There is a question I have answered on this site which describes the axioms of ZFC. I am writing from my phone right now, I'll find it when I wake up in a couple of hours. $\endgroup$ – Asaf Karagila May 26 '13 at 2:05
  • $\begingroup$ If there are uncoutnable ordinals, then there is a least uncountable ordinal. Courtesy of being well-ordered! $\endgroup$ – Asaf Karagila May 26 '13 at 2:13

As [1], [2], [3], and [4] may tell you, the axiom of choice is not needed to define $\omega_1$ (in particular [1] and [4]).

Two key axioms are the power set axiom and the replacement axiom schema. In [2] and [3] you can see why the axiom of power set is needed. It is consistent with $\sf ZF$ without the power set axiom that there are only countable ordinals. In particular the set of hereditarily countable sets satisfies that. In fact, it shows that without the power set axiom we cannot prove the existence of any uncountable sets.

But the replacement schema is also essential. We use it in order to map a certain subset of $\mathcal P(\omega\times\omega)$ onto ordinals, and we need the replacement schema to show that the result is a set. Indeed if we consider $\sf ZF$ without the replacement schema, then $V_{\omega+\omega}$ is a model of these axioms, and there are only countable ordinals in that model. It should be remarked that there may still be well-ordered of length $\omega_1$ in $V_{\omega+\omega}$ but the von Neumann ordinal, a transitive set ordered by $\in$ does not exist there. That is to say, it is consistent that the axiom of choice holds, and every set can be well-ordered, but the von Neumann ordinals don't exist beyond $\omega+\omega$. In such model we separate between ordinals as we think about today (von Neumann's definition), and as equivalence classes of order types (which are proper classes, of course).

Of course one uses the axiom of union all the time, as well extensionality. It should be remarked that regularity is not necessarily because we can always limit ourselves to the part of the well-founded sets, where it holds, at least if we have replacement.

The Links:

  1. How do we know an $ \aleph_1 $ exists at all?
  2. Uncountable ordinals without power set axiom
  3. Does the definition of countable ordinals require the power set axiom?
  4. No uncountable ordinals without the axiom of choice?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.