There are two results famously associated with Cantor's celebrated diagonal argument. The first is the proof that the reals are uncountable.
This clearly illustrates the namesake of the diagonal argument in this case. However, I am told that the proof of Cantor's theorem also involves a diagonal argument. Given a set $S$, suppose there exists a bijection $f:S\longrightarrow\ P(S)$ from $S$ to its powerset. The construction of the set
$$B=\{b\in S\mid b\notin f(b)\}$$
is said to be a diagonal argument due to the dual occurrence of $b$ in $b\notin f(b)$. Now I am not exactly sure why this is called a diagonal argument. Is there a geometric representation of this argument like the picture above? Or is it simply an analogy to the first proof using the idea of constructing a witness to show $f$ is not surjective?
Best Answer
Diagonalization is a common method in mathematics. Essentially it means "write it in an infinite matrix and then walk along a coordinate line which approaches infinity on both axes".
The "Cantor diagonal argument" says write the numbers in a matrix, and take the $n$-th number's $n$-th digit, and change it.
The Cantor theorem is a form of diagonalization because what you actually do is write the function in matrix form:
$$\begin{array}{|c|c|c|c|c} &x_1 & x_2 & x_3 & \ldots\\ \hline f(x_1)\\ \hline f(x_2)\\ \hline f(x_3)\\ \hline \vdots \end{array}$$
Now we write $1$ into the blank cells if $x_i\in f(x_j)$, and $0$ otherwise. The proof takes the set of all $x\in X$ such that $x\notin f(x)$, That is walk along the diagonal and take the coordinates which give $0$. This defines a subset of $X$ which is not in the range of $f$, much like the diagonal argument gives a number which is not in the enumeration.
Similar, but different arguments are given when showing the real numbers can be defined as Cauchy sequences of rationals up to some equivalence, and that this is a complete space. We take a Cauchy sequence of Cauchy sequences and we take the $k$-th element of the $k$-th sequence.
Of course this is not exactly what we do, but it is close enough. We need to toy with $\epsilon-\delta$ and define the diagonal we are going to walk on (for the $k$-th element we want to take some $x^k_j$ for $j$ large enough so and so...)