2
$\begingroup$

I know that the standard way of proving that the set of all countable ordinals is uncountable is by stating that if the set is countable, then it incurs Burali-Forti paradox.

Is there other ways of proving this?

  • 0
    Not Russell's paradox so much as Burali-Forti's paradox, but they're closely related.2012-10-18
  • 0
    Some proofs are given in this question: [Uncountability of countable ordinals](http://math.stackexchange.com/questions/71726/uncountability-of-countable-ordinals). (And you might want to have a look at linked questions, too.)2012-10-18
  • 0
    I think this question already has an answer at https://math.stackexchange.com/questions/38468/no-uncountable-ordinals-without-the-axiom-of-choice.2017-10-26
  • 0
    This question has nothing to do with the axiom of choice, so I've removed that tag.2017-11-12

3 Answers 3

9

The set of all countable ordinals is the supremum of all countable ordinals, which is simply their unions. If $\omega_1$ were countable, $\omega_1+1$ would be countable too and hence $\omega_1+1<\omega_1$. Hence $\omega_1\in\omega_1+1\in\omega_1$, which shows that the set $\{\omega_1,\omega_1+1\}$ has no $\in$-minimum, which is impossible since the ordinals are well-ordered by $\in$.

  • 0
    Wait, how is $\omega_1+1 \leq \omega$? Isn't $\omega$ the first infinite countable ordinal?2012-10-18
  • 0
    @DOT Yes. But this is a proof by contradiction. Since the set of all countable ordinals is the supremum of all countable ordinals, and $\omega_1$ being countable implies $\omega_1+1$ we have $\omega_1+1<\omega_1$, which is by definition of the ordering on ordinals $\omega_1+1\in\omega_1$.2012-10-18
  • 0
    @CarlMummert Thank you.2012-10-18
  • 0
    I think that the contradiction has nothing to with the the fact those are ordinals; rather with the fact that the axiom of regularity fails.2012-10-18
  • 1
    @Asaf But the proof works even when the axiom of regularity fails.2012-10-18
  • 0
    True, but even if it fails, all the ordinals appear in an inner model where the axiom of regularity holds. It's a dirty trick, but you see it often in choice context. You show that if something were to fail, it would fail in an inner model of choice. The same can be applied to regularity. (The common between these two axioms is that the theory of ZF with and without either is equiconsistent)2012-10-18
  • 0
    @Asaf It seems to me that this is simply a more complicated way of saying that the ordinals belong to the class of well-founded sets. Adding a relative consistency proof on top doesn't really help in showing that $\omega_1$ is uncountable.2012-10-18
  • 0
    @Michael: Yes, this is a very complicated way of saying that the ordinals are sets on which $\in$ is well-founded. :-)2012-10-18
  • 0
    Asaf, the point is that we only need a weak theory to make sense of this argument, a theory that does not require foundation, and that needs not be strong enough to even make sense of inner models or the well-founded universe.2012-10-18
  • 0
    The problem with your argument is that it's not a well known theorem that uncountable ordinal numbers exist without assuming the axiom of choice.2017-10-26
  • 1
    @Timothy There is a [theorem by Hartog](https://en.wikipedia.org/wiki/Hartogs_number), provable without AC, that for every set there is an ordinal such that there is no injection from the form into the latter. In particular, uncountable ordinals exist.2017-10-26
  • 0
    @Michaek Greinecker Is this answer considered a good answer because experts can figure out from reading it how to write a complete proof of what this question asked them to prove even though the answer itself doesn't give a complete proof?2017-10-26
  • 1
    @Timothy I obviously didn't vote on my own answer. But every textbook discussing ordinals without the axiom of choice will contain the result. More importantly, my argument actually proves the existence of uncountable ordinals. If you have questions understanding the proof, feel free to ask.2017-10-26
  • 0
    You're probably right that the proof is good enough but I'm not sure if this is the correct reason. A lot of people including me will be able to figure out how to write a complete proof after they read your answer, because I thought of my own proof by myself that I didn't need your answer to think of and wrote it as another answer to this question.2017-11-03
2

I think that all proofs will be similar in some way to the Burali-Forti paradox. Here is a proof that is slightly different than other proofs on this site, so maybe someone will find it useful. Note that the Axiom of Regularity is not used anywhere.

Definition: An ordinal is a transitive set well-ordered by $\in$.

Fact: The class of ordinals is transitive and well-ordered by $\in$.

Definition: $\omega_1$ is the class of countable ordinals.

Fact: $\omega_1$ is a set.

To see that $\omega_1$ is an ordinal using the above facts, it remains to observe that every element of a countable ordinal is a subset of that ordinal and is therefore countable also.

Now suppose toward a contradiction that $\omega_1$ is countable. Then $\omega_1 \in \omega_1$ by definition. This contradicts the fact that the class of ordinals is well-ordered by $\in$.

1

In Principia Mathematica, Whitehead & Russell presented Burali-Forti's paradox in a form that can dispense with the axiom of infinity. They eventually dispelled the paradox by showing that in higher types there are greater ordinals than any to be found in lower types.

The paradox:

Let $\alpha$ be any ordinal number, then the ordinal number for $0_r, 1_s, 2_r, 3_r, ... \alpha$ in order of magnitude is $\alpha + \overset{.}{1}$; thus $\alpha +\overset{.}{1}$ exists, and is greater than $\alpha$. But $\alpha$ is similar to the segment of series of ordinals consisting of the predecessors of $\alpha$, and is therefore less than the ordinal of all ordinals. Hence the ordinal of all ordinals is greater than every ordinal, including itself, which is absurd.

In order to dispel the paradox, it is only necessary to make the types explicit. Let $N$ be the series of all ordinals arranged in order of magnitude; when we say "$P$ is well-ordered $\Rightarrow$ $P$ is less than $N$," we mean, by $N$, a series two types above $P$, i.e. $N$'s terms belong to the type of $P$'s ordinal number ($t‘N_0r‘P$). In other words:

$P$ is well-ordered $\Rightarrow$ $P \lt N(P,P)$

Whence $N(P,P)$ is well-ordered $\Rightarrow N(P,P)\lt N\{N(P,P),N(P,P)\}$

Thus, N is no longer less than itself, and the paradox disappears.

Source: Whitehead & Russell, Principia Mathematica V.3. ✳256. Merchant Books, 1913

  • 0
    Note to self: I have yet been able to come up with a W-O series in which some terms, except for the first one, do not have immediate predecessors.2014-12-29
  • 0
    Let $P, Q \in \Omega$ and $P$ has no last term, then $P⤉Q \in \Omega$, and $Q$'s first term has no immediate predecessor in $P⤉Q$.2014-12-30