Cardinality of the Irrationals [duplicate]

Possible Duplicate:
Proof that the irrational numbers are uncountable

We previously proved that $\mathbb{Q}$, the set of rational numbers, is countable and $\mathbb{R}$, the set of real numbers, is uncountable. What can you say, then, about the cardinality of the irrational numbers?

I would say that the cardinality of irrational numbers is uncountable. That would be because the set $\mathbb{Q}$ is a subset of $\mathbb{R}$. The irrationals is also a subset of $\mathbb{R}$. Basically, my thought is that the continuum is composed of irrationals and rationals (only two subsets of reals). Because we can prove that the rationals are countable by Cantor's proof, then the remaining subsets of $\mathbb{R}$, the irrationals, has to be uncountable for $\mathbb{R}$ to be uncountable. My concern is how to go about the prove this (rigorous, intro level).

-

marked as duplicate by Chris Eagle, Davide Giraudo, Sasha, anon, JavaManOct 12 '11 at 22:15

@Chris: I partly disagree that this is a duplicate. Saying that a set is uncountable does not imply what cardinality it might have. I vote to keep open, please the next one to support closing cancel my vote. –  Asaf Karagila Oct 12 '11 at 21:49
@Asaf: Sorry, I wouldn't have voted right away if I looked at your comment under that of Chris - but technically isn't the question here only on how to show the irrationals are uncountable? You went above and beyond the original query. –  anon Oct 12 '11 at 22:05

Claim: Suppose $A,B$ are two countable sets which are disjoint, then $A\cup B$ is countable.

Proof: Fix $f\colon A\to\mathbb N$, and $g\colon B\to\mathbb N$ two bijections given by the fact that these sets are countable. Now define $h\colon A\cup B\to\mathbb N$ by: $$h(x)=\begin{cases}2\cdot f(x) & x\in A\\ 2\cdot g(x)+1 & x\in B\end{cases}$$

Since $A\cap B=\varnothing$ this function is well defined, and it is easy to see that it is in fact a bijection.

Claim: $|\mathbb R\setminus\mathbb Q|>\aleph_0$.

Proof: Suppose not, then $\mathbb R=(\mathbb R\setminus\mathbb Q)\cup\mathbb Q$ and by the previous claim it is a union of two disjoint countable sets, and therefore $|\mathbb R|=\aleph_0$. Contradiction.

Note, however, that this does not mean at all that $|\mathbb R\setminus\mathbb Q|=|\mathbb R|$. It just proves that the irrationals are uncountable.

The proof that the irrationals are of the same cardinality of the continuum is harder. If we want to use Cantor-Bernstein's theorem we need to find an injection from $\mathbb R$ into the irrationals.

This can be done using continued fractions, the proof is not trivial and quite long, or in a somewhat more general way as discussed here: Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?

Lastly, assuming the axiom of choice the result is obvious since $|\mathbb R|=|\mathbb R\setminus\mathbb Q|+\aleph_0=\max\{|\mathbb R\setminus\mathbb Q|,\aleph_0\}$, and we do know that $|\mathbb R\setminus\mathbb Q|>\aleph_0$ and thus we have the equality.

(It is not true without the axiom of choice that addition of cardinals is the same as taking the maximum of the two.)

-

Hint: The rationals are countable so they can be counted as $q_1,q_2,q_3,\dots$ and if the irrationals are also countable they can be counted as $r_1,r_2,r_3,\dots$ - so then what are you counting if you combine the two sequences (say, alternate them: $q_1,r_1,q_2,r_2,q_3,r_3,\dots$)?

-

If $A$ and $B$ are countable sets, one knows that the union $A\cup B$ is again countable.

A consequence of this principle is that the complement of a countable subset in an uncountable set must be uncountable (else, you'd get an easy contradiction). That's exactly your situation since the irrationals are the complement of $\Bbb Q$ in $\Bbb R$.

-

Your idea sounds pretty rigorous to me. The union of rationals and irrationals yields the reals, thus if both sets are countable $R$ is countable (if you haven't proved a union of two countable sets is countable in class, think about how you can show this by a simple injection into $N$), which is a contradiction.

-