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

  • $\begingroup$ How is this question appropriate for this forum? It might be better suited for the math forum. $\endgroup$ Nov 19, 2012 at 13:37
  • 4
    $\begingroup$ 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. $\endgroup$ Nov 19, 2012 at 14:01
  • 5
    $\begingroup$ @AndrejBauer: I disagree. Diagonalization is a key concept in complexity theory. $\endgroup$
    – A.Schulz
    Nov 19, 2012 at 14:02
  • 1
    $\begingroup$ Ok, I stand corrected. $\endgroup$ Nov 19, 2012 at 14:25

2 Answers 2


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.

  • $\begingroup$ Instead of taking the diagonal elements why you are adding 5 to the diagonal elements? $\endgroup$
    – user5507
    Nov 21, 2012 at 2:30
  • $\begingroup$ 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? $\endgroup$ Nov 21, 2012 at 4:35
  • $\begingroup$ 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. $\endgroup$ Nov 21, 2012 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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