Diagonalisation (Proof Technique)

Diagonalisation (more famously known as Cantor’s diagonal argument) is a proof technique that can be used to increase the cardinality of a set. More importantly, it can be used to show that a set is uncountable, by employing a proof by contradiction.

Procedure §

Increasing Cardinality Of A Finite Set §

Let $X$ be a finite set of numbers, which is initially thought to have cardinality/size $n$. This means there exists a bijection from the elements of the set to the natural numbers. More informally, we can count the elements of $X$, and represent them as $X=\{x_1,x_2,x_3,\dots x_n\}$. This usually involves applying a total ordering on the set.

Let $X=\{x|x\in \mathbb{N},x\text{ has}\le 3\text{ digits}\}$. (We already know there are 999 such numbers). However, let’s assume for now that there are only 3 such numbers, $X=\{420,157,123\}$. If we were to order them in ascending order, we get $X=\{123,157,420\}$. Now, divide each number into a set of their constituting digits, like so: $X=\{\{1,2,3\},\{1,5,7\},\{4,2,0\}\}$. Representing it as a matrix, we have:

$$X=\left[\begin{array}{cccc}& d_1& d_2& d_3\\ x_1:& 1& 2& 3\\ x_2:& 1& 5& 7\\ x_3:& 4& 2& 0\end{array}\right]$$

Then, we can construct a new number (that belongs in $X$), by constructing $y=y_1{y}_2{y}_3$ where $y_i\ne X_{i,i}$. More intuitively, we essentially look at the diagonal of this matrix, which is $\left[\begin{array}{ccc}1& 5& 0\end{array}\right]$, and make a new number such that the first digit is not 1, the second digit is not 5 and the 3rd digit is not 0. For example, $y=041$ is a new number that belongs in $X$, which means $X$ has at least cardinality of 4 (and we can keep increasing this by finding new $y$’s).

%%🖋 Edit in Excalidraw, and the dark exported image%%

Visual aid, not the 'proper' way of doing it.

The proper diagonal argument does not relate to matrices, nor lists, but to sequences. The matrix-like approach shown above is only a visual aid because (as you’ll see below), it starts to break down when we talk about numbers represented as infinite sequences.

Proving Uncountability Of An Infinite Set §

Now that we’ve done it for finite sets, we can apply this same procedure to infinite sets, to increase their cardinality from the natural numbers (being countable) to the real numbers (being uncountable).