This argument is the basis for Georg Cantor's theory that there are degrees of infinity, i.e. the infinity that represents the set of Natural numbers is not the same as the infinity that represents the set of Real numbers.
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 alephnull _{0} and larger infinite sets i.e. those without a onetoone correspondence with the infinitude of Natural numbers are denoted _{1}, _{2}, _{3} these are called transfinite numbers.
Now to Cantor's proof that there is not a onetoone 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} ⇒ 1, a_{2} ⇒ 2, a_{3} ⇒ 3, a_{4} ⇒ 4, a_{n} ⇒ n.
a_{1} = 0.890328754907861…
a_{2} = 0.528520654035861…
a_{3} = 0.247815759367324…
a_{4} = 0.082489564213887…
a_{5} = 0.420985387691245…
a_{6} = 0.143249526570604…
………………………………
a_{n} = 0.n_{1}n_{2}n_{3}n_{4}n_{5}n_{6}n_{7}n_{8}…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_{1} so c ≠ a_{1}. The second digit must differ from the second digit of a_{2} so c ≠ a_{2}. 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
