Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Not Russell's paradox so much as Burali-Forti's paradox, but they're closely related. –  Zhen Lin Oct 18 '12 at 9:43
    
Some proofs are given in this question: Uncountability of countable ordinals. (And you might want to have a look at linked questions, too.) –  Martin Sleziak Oct 18 '12 at 10:20
add comment

2 Answers

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$.

share|improve this answer
    
Wait, how is $\omega_1+1 \leq \omega$? Isn't $\omega$ the first infinite countable ordinal? –  DOT Oct 18 '12 at 10:20
    
@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$. –  Michael Greinecker Oct 18 '12 at 10:28
    
@CarlMummert Thank you. –  Michael Greinecker Oct 18 '12 at 11:25
    
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. –  Asaf Karagila Oct 18 '12 at 13:30
1  
@Asaf But the proof works even when the axiom of regularity fails. –  Michael Greinecker Oct 18 '12 at 19:50
show 4 more comments

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$.

share|improve this answer
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.