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:
Are there many more irrational numbers than rational?

I read this article where it mentioned

Countably infinite means you can set up a one-to-one correspondence between the set in question and the set of natural numbers. It can be shown that no such relationship can be established between the set of real numbers and the natural numbers, thus the set of real numbers is not "countable", but it is infinite.

I am not sure why the real numbers cannot be put in a one to one correspondence with the natural numbers. Can anybody explain?

share|improve this question

marked as duplicate by Ross Millikan, Belgi, MJD, Chris Eagle, Norbert Oct 8 '12 at 9:29

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.

This has been asked thoroughly on this site. –  Asaf Karagila Oct 7 '12 at 22:18

3 Answers 3

Look up "Cantor's diagonal proof" anywhere! (didn't see the earlier article before sending, which presents the proof...)

share|improve this answer

This is a very standard result that can be found in almost all textbooks which provide an introduction to (un)countability. The most common proof uses Cantor's diagonal argument, which is echoed below.

Suppose $\mathbb{R}$ is countable. Then we can enumerate its elements as follows: $$\mathbb{R} = \{ x_1, x_2, x_3, \cdots \}$$ (If $f : \mathbb{R} \to \mathbb{N}$ is a bijection then we can take $x_i = f^{-1}(i)$.)

Each $x_i$ has a unique decimal expansion in which infinite strings of $0$s are taken if there is any ambiguity. So write $$\begin{align}x_1 &= n_1 + 0.d_{11}d_{12}d_{13} \cdots \\ x_2 &= n_2 + 0.d_{21}d_{22}d_{23} \cdots \\ x_3 &= n_3 + 0.d_{31}d_{32}d_{33} \cdots \\ &\ \vdots\end{align}$$ where $n_i \in \mathbb{Z}$ for each $i$ and $d_{ij} \in \{ 0, 1, \cdots, 9 \}$.

Construct $x \in \mathbb{R}$ as follows. Let $$x = 0.d_1d_2d_3\cdots$$ where $d_i = 0$ if $d_{ii} \ne 0$ and $d_i = 1$ if $d_{ii}=0$. Then in particular $d_i \ne d_{ii}$ for any $i$. Since $x \in \mathbb{R}$ and $\mathbb{R}$ is supposed to be countable, we must have $x=x_i$ for some $i$, but that would mean that $d_i = d_{ii}$... contradiction!

share|improve this answer

I see two people giving the famous diagonal argument that Cantor wrote three years after he proved uncountability of the reals by a different method. That different method is nice: http://en.wikipedia.org/wiki/Cantor's_first_uncountability_proof.

share|improve this answer

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