Consider the sets N = {0, 1, 2, �} of natural numbers and the set E = {0, 2, 4, �} of even numbers. Common sense would suggest that the set N is bigger than the set E because only half of the natural numbers are even. But if we were to list the members of each set then it can be seen that for every member of set N there is a corresponding member of set E.

0	1	2	3	4	5	6	7	8	9	10	11	...
↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓
0	2	4	6	8	10	12	14	16	18	20	22	...

It can be further proven that many other infinite sets share the same cardinality as the set of Natural numbers. Cantor denoted the infinity of elements in these sets with the cardinal number aleph-null ₀ and larger infinite sets i.e. those without a one-to-one correspondence with the infinitude of Natural numbers are denoted ₁, ₂, ₃ these are called transfinite numbers.

Now to Cantor's proof that there is not a one-to-one correspondence of the set of Real numbers with the infinitude of Natural numbers.

Consider a list of Real numbers between 0 and 1 where each number corresponds to a member of the set of Natural numbers i.e. a₁ ⇒ 1, a₂ ⇒ 2, a₃ ⇒ 3, a₄ ⇒ 4, a_n ⇒ n.

a₁ = 0.890328754907861�
a₂ = 0.528520654035861�
a₃ = 0.247815759367324�
a₄ = 0.082489564213887�
a₅ = 0.420985387691245�
a₆ = 0.143249526570604�
������������
a_n = 0.n₁n₂n₃n₄n₅n₆n₇n₈�n_n�

We might then create a new number composed of the diagonal digits that are coloured red:

b = 0.827489� n_n�

If we were to then add 1 to each digit in this number to create yet another new number e.g.

c = 0.938590�(n_n+1)�

We would have created a number that could not possibly be in the original list as it would differ in at least one digit to any number in the original list.

The first digit must differ from the first digit of a₁ so c ≠ a₁. The second digit must differ from the second digit of a₂ so c ≠ a₂. The nth digit must differ from the nth digit of a_n so c ≠ a_n and so on for all the numbers in the list.

For further information see PlanetMath.org an excellent resource for all mathematical information and the following page which is specifically about Cantor's Diagonal Argument http://planetmath.org/encyclopedia/CantorsDiagonalArgument.html