Cantor's diagonal argument

Cantor's diagonal argument is a method for showing the uncountability of the set of real numbers. It is a proof by contradiction - one assumes that, towards contradiction, there is a bijection from the natural numbers to the real numbers, and then one constructs a real number not in the range of this function, which contradicts surjectivity. It may be rephrased as the assertion that every function from the naturals to the reals is non-surjective, and in that sense it could be considered a direct proof instead.

First, for a real number \(r\), let \(r[n]\) be the \(n\)th digit after the decimal place, in the "lexicographically maximal" decimal expansion of \(r\). For example, \(\pi[0] = 1\) and \(\pi[1] = 4\). Then the proof goes like so: assume \(f: \mathbb{N} \to \mathbb{R}\) is a supposed function enumerating the entirety of the real numbers. Let \(r\) be the real number with whole part 0. Then \(r[n] = 0\) if \(f(n)[n] \neq 0\), and else \(r[n] = 1\). Now, since \(f\) is surjective, there is some \(m\) so that \(f(m) = r\). Then, if \(f(m)[m] \neq 0\), we have \(r[m] = 0\), and if \(f(m)[m] = 0\), we have \(r[m] = 1\). That is, \(r\) and \(f(m)\) disagree on the \(m\)th decimal place after the decimal point, and therefore they can not be the same real number.

The proof is known as the "diagonal argument" because of a common visual representation. Namely, one writes out the decimal expansions of all the supposed real numbers on a grid, so that \(f(n)[m]\) is equal to the entry at the \(m+1\)st column and \(n+1\)st row, and then constructs a new real number by "inverting" the decimal expansion of the diagonal.

The conclusion can be strengthened to show that just the real interval \([0,1]\) is uncountable.

P(N)

A similar argument can be used to show the uncountability of the powerset of the natural numbers, \(\mathcal{P}(\mathbb{N})\). Note that, by using binary expansions and characteristic functions, one can see that \([0,1]\) has the same size as \(\mathcal{P}(\mathbb{N})\), with \(0\) corresponding to \(\emptyset\) and \(1\) corresponding to \(\mathbb{N}\). However, the application of the method of diagonalization to \(\mathcal{P}(\mathbb{N})\) has some merit in its own right.

Assume \(f: \mathbb{N} \to \mathcal{P}(\mathbb{N})\) is a supposed function enumerating the entirety of the powerset of the natural numbers. We define a set \(X\) like so: \(n \in X\) iff \(n \notin f(n)\). Now, since \(f\) is surjective, there is some \(m\) so that \(f(m) = X\). Then, we have \(m \in X\) iff \(m \notin f(m)\) iff \(m \notin X\). This is impossible!

And this can be generalized to show that, for every set \(X\), we have \(2^{|X|} > |X|\).

The general form of diagonalization-type arguments is similar to the barber paradox, or, more precisely, Russel's paradox.