Cardinality of the Irrationals

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

Solutions Collecting From Web of "Cardinality of the Irrationals"

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.