# Confusion related to countably infinite sets [duplicate]

Possible Duplicate:
Are there many more irrational numbers than rational?

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?

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

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

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!