The diagonalization argument

Some examples of self-referential proofs in mathematics

In mathematics, the diagonalization argument is often used to prove that an object cannot exist. It doesn’t really have an exact formal definition but it is easy to see its idea by looking at some examples.

If x ∈ X and f(x) make sense to you, you should understand everything inside this post. Otherwise pretty much everything.

Cantor’s diagonal argument

The person who first used this argument in a way that featured some sort of a diagonal was Georg Cantor. He stated that there exist no bijections between infinite sequences of 0’s and 1’s (binary sequences) and natural numbers. In other words, there is no way for us to enumerate ALL infinite binary sequences. Don’t believe him? Then you are basically (classically) saying there exists such an enumeration. So take it and accordingly write each sequence in a row and place those rows vertically one after another. Now take the diagonal. The process should look kind of like the image below.

Let’s construct a new sequence s by taking the diagonal and switching 0s and 1s. In the above case, we get

s = 1 0 1 1 1 0 1 0 0 1 1 …

According to you, this sequence has to be enumerated by some index i, so that s_i is our s. It’s important to notice that s_i[i] (the i-th term of the sequence s_i) lies on our diagonal. So, what is s_i[i]?

• If s_i[i] is 0, then s[i] by definition switched it to 1, so s[i] is 1. But as we have by assumption s_i = s, it also follows that s_i[i] = s[i] = 1.
• If s_i[i] is 1, then again by definition s[i] is 0, so as s_i = s, it follows that s_i[i] = s[i] = 0.

What? That makes no sense… that’s a contradiction. Exactly! So what have we learned? We learned that one does not simply question Cantor.

Imagine blue squares/circles as zeros and orange squares/circles as ones. The red circle can’t be defined and thus makes the horizontal placement of the inverted diagonal impossible.

That’s how Cantor proved that there is a larger infinity (the set of infinite binary sequences) than the countable infinity (natural numbers). Now we’re going to prove that for every infinity there exists a larger infinity. Here’s an expansion on what exactly this means.

Formally, we are going to prove that for any set X there exists no bijection between X and the set of all subsets of X. Again assume such bijection exists and name it e. Then define

Of course, S is a subset of X, so S = e(s) for some s in X. We think over whether s is in S and see that in any case there is a contradiction:

• if s ∈ S, then by definition s ∉ e(s) = S,
• if s ∉ S, then again by definition s ∈ e(s) = S.

So our bijection doesn’t exist.

The argument was a bit harder to follow now that we didn’t have a clear image of the whole process. But that’s kind of the point of the diagonalization argument. It’s hard because it twists the assumption about an object, so it ends up using itself in a contradictory way.

Russell’s paradox

The story here also begins with Cantor, as he tried to introduce a new concept that has become integral in mathematics. A concept we already used here - a set. It might not seem that way, but it had some issues. Bertrand Russell in 1901 noticed that if we define the set containing all sets that don’t contain themselves

we arrive at a contradiction. That is we can’t answer the question of whether R contains itself (R ∈ R).

• if R contains itself, then by definition of R, R doesn’t contain itself,
• if R doesn’t contain itself, it should contain itself by its definition.

So what exactly caused the contradiction here? We haven’t assumed anything. Or have we? To ask whether R ∈ R, R has to be a set. So the way to salvage set theory is to not recognize R as a set. And as it turned out, that kind of worked out (if mathematics is non-contradictory by itself, set theory is safe). If you wish to learn more about how set theory is now formalized, ZFC is the word.

Halting problem

Let’s look at something that limits our computer capabilities (and Ethereum). In 1936 Alan Turing proved the Halting problem, which states that no algorithm exists to decide whether a given program terminates (its execution ends in a finite amount of time). This again seems like a bizarre theorem, so diagonalization has to be involved somehow. We know the drill. Assume there is such an algorithm A that takes an input (X, Y) and determines whether algorithm X ran on its input Y terminates. Then we define another algorithm B that takes an input W and does the following:

• if A ran on (W, W) returns True, then we go in a sort of a run forever loop,
• if A ran on (W, W) returns False, then we terminate the execution.

We can now ask, what we get if we run A on input (B, B). Let’s separate two cases:

• if A ran on (B, B) returns True, then B halts on B, which can only happen if A ran on (B, B) returned False,
• if A ran on (B, B) returns False, then B doesn’t halt on B, which means A ran on (B, B) returned True.

Again we see that in each case we get a contradiction. So algorithm B can’t exist, which means that algorithm A can’t exist.

This may have been difficult to understand as we’ve not been entirely precise. We considered inputs and algorithms to be the same. That is not formally the case. Formally, we must encode algorithms as input strings (their code).

Halting problem in Python

Gödel’s incompleteness theorems

We can’t end this post without mentioning Kurt Gödel’s incompleteness theorems. Unfortunately, they are too involved to explain properly, so we’ll just intuitively try to understand the important part of the first one.

It states that in non-contradictory mathematics based on a reasonably large amount of axioms, there will always be a sentence that cannot be proved or disproved. This is called the Gödel sentence and it states:

using the given axioms, I cannot be proven true.

We can’t prove this sentence true, as that would lead to a contradiction. But that means it is indeed true, so it can’t be proved false. In this way, mathematics will always be incomplete.

The second one states that under the same constraints, mathematics cannot prove itself to be non-contradictory. So, if our math is correct, we’ll never know it for sure.

Reasonably large really means we’re being reasonable. Formally it means that we have to be able to construct an algorithm that tells us if a given axiom is inside the set of axioms.

Conclusion

Diagonalization is widely used in mathematics and established some very fundamental theorems. The self-referential way it proves things bends your mind into understanding why what you’re assuming to be true really can’t be possible. In math, that’s pretty valuable.