# 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

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

-

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!

-

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.

-