Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
How is this question appropriate for this forum? It might be better suited for the math forum. –  Andrej Bauer Nov 19 '12 at 13:37
2  
Diagonalization comes up a lot in theoretical computer science (eg, proofs for both time hierarchy theorems). While Cantor's proof may be slightly off-topic, diagonalization certainly isn't. –  Nicholas Mancuso Nov 19 '12 at 14:01
4  
@AndrejBauer: I disagree. Diagonalization is a key concept in complexity theory. –  A.Schulz Nov 19 '12 at 14:02
    
Ok, I stand corrected. –  Andrej Bauer Nov 19 '12 at 14:25

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
Instead of taking the diagonal elements why you are adding 5 to the diagonal elements? –  user5507 Nov 21 '12 at 2:30
    
The important part is that $r' \neq r_i$ for each $i$. What we need is for $r'$ to differ in some digit. So, for example, if $r_4$ were 0.6652, then by setting the next digit of $r'$ to 7 we have $r' = 0.6657$ which makes it clearly different from $r_4$ by at least 0.0004. Does that make sense? –  William Macrae Nov 21 '12 at 4:35
    
The values r_1 ... must be between 0.0<=r<1.0. Otherwise, and as written here, the diagonal itself (0.110...) cannot be an entry, no matter the ordering. –  Andrew Dalke Nov 21 '12 at 9:27

Perhaps you will find my blog post "On a proof of Cantor's theorem" illuminating. In short, the right way to prove Cantor's theorem is to first prove Lawvere's fixed point theorem, which is more computer-sciency in nature than Cantor's theorem.

Given two sets $A$ and $B$, let $B^A$ denote the set of all functions from $A$ to $B$.

Theorem (Lawvere): Suppose $e : A \to B^A$ is a surjective map. Then every map $f : B \to B$ has a fixed point, i.e., $x \in B$ such that $f(x) = x$.

Proof. Consider the map $s:A \to B$ defined by $s(x)=f(e(x)(x))$. Because $e$ is onto, there is $y \in A$ such that $e(y)=s$. Then we have $e(y)(y)=s(y)=f(e(y)(y))$, therefore $e(y)(y)$ is a fixed point of $f$. QED.

Corollary (Cantor): There is no onto map from a set $A$ onto its powerset $\mathcal{P}(A)$.

Proof. First note that $\mathcal{P}(A)$ is isomorphic to $2^A$ where $2 = \lbrace 0, 1 \rbrace$. That is, the subsets of $A$ correspond to their characteristic functions $A \to \lbrace 0, 1 \rbrace$. Suppose $e : A \to 2^A$ is onto. By Lawvere's theorem every map $2 \to 2$ has a fixed point. But this is not the case for the map $f(x) = 1 - x$. Therefore no such $e$ can exist. QED.

The usual proof of uncountability of reals (using decimal expansions) is of the same form too. There is a map $f : \lbrace 0, 1, \ldots, 9\rbrace \to \lbrace 0, 1, \ldots, 9\rbrace$ on the decimal digits which has no fixed point, therefore there can be no onto map $\mathbb{N} \to \lbrace 0, 1, \ldots, 9\rbrace^\mathbb{N}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.