[Solved]: Cantor's diagonal method in simple terms?

Problem Detail: 

Could anyone please explain Cantor's diagonalization principle in simple terms?

Asked By : user5507

Answered By : William Macrae

Here's the standard application explained in the simplest terms I can:

Theorem: There are more real numbers than there are integers.

Lemma: A real number has a decimal representation (that might not terminate), and all decimal representations create real numbers.

Proof of Theorem: Suppose there are as many integers as reals. Then we can list the reals in some order,

$r_1 = 3.141592...$

$r_2 = 2.718281...$

$r_3 = 1.000000...$

and so on for each $r_i$ where $i$ is an integer

There is a contradiction because I can construct a real that is not in the above list. Let $r' = 0.d_1d_2d_3d_4\ldots$ where $d_1$ is not equal to the 1st digit after the decimal of $r_1$, $d_2$ is not equal to the 2nd digit after the decimal of $r_2$, and so forth. For example, I could add 5 and take it mod 10. In the example this gives $r' = 0.665\ldots$. The contradiction is that $r'$ is not in the list, because for any $i$ I know that $r'$ and $r_i$ differ by at least $4*10^{-i}$ (since they differ in $d_i$).

The fact that the reals cannot be enumerated as such shows that they are larger than the integers. But, the important result of Cantor is simply that they cannot be enumerated.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6753