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 used Zorn's Lemma to cook up a proof that $\mathbb{R}$ is countable, and now I can't find a flaw in it. Can anyone help? Here it is...

Denote by $\mathcal{A}$ the set of countable subsets of $\mathbb{R}$, partially ordered under inclusion, and consider any chain in $\mathcal{A}$: $$A_0 \subseteq A_1 \subseteq A_2 \subseteq \dots$$ Now let $A = \cup_{k \ge 0} A_k$. Then $A \in \mathcal{A}$, the countable union of countable sets.

It follows that every chain in $\mathcal{A}$ has an upper bound. So by Zorn's Lemma, $\mathcal{A}$ contains an element $X$ maximal under inclusion.

Suppose now that there is $a \in \mathbb{R}$ not in $X$. Then $X' = X \cup \{ a \}$ is countable, for if $f: X \to \mathbb{Z}^{+}$ is a bijection, then $f': X' \to \mathbb{Z}^{+}$, $$f'(a) = 1 \quad \text{and} \quad f'(x) = f(x) + 1,$$ is a bijection. But then $X' \in \mathcal{A}$ strictly contains the maximal element $X$, a contradiction. So $a \in X$, and hence $X = \mathbb{R} \in \mathcal{A}$.

share|improve this question
5  
Line 6 assumes that the chain is countable. A chain of countable sets needs not be countable in length, and its union does not need to be countable. See this. –  Andres Caicedo Mar 12 at 5:50
    
Fantastic, thanks. If you add it as an answer I'll definitely accept it. –  Joshua Ciappara Mar 12 at 6:19

1 Answer 1

up vote 6 down vote accepted

Line 6 assumes that the chain is countable. A chain of countable sets needs not be countable in length, and its union does not need to be countable. For instance, $\omega_1$, the first uncountable ordinal, is the (well-ordered) union of a chain of countable sets.

share|improve this answer

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.