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.

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

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
@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
add comment

4 Answers 4

up vote 9 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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$)?

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.