Paper review: The Tower of Hanoi

I first read Hugh Woodin’s Tower of Hanoi years ago early in my undergraduate. I remember getting bogged down by the math, and finding it more difficult to keep hold of the main thread as I got further into the paper. A few years later, I read the paper again upon starting grad school, and was pleasantly surprised to find it an easier read. No longer slowed down by technical obscurities, ideas that remained concealed before now seemed clearer, and the paper was much more enjoyable as a result. One of my reasons for starting this blog was to condense those years into a single exercise — to try and elicit the key ideas in papers involving technically challenging or dense mathematical material, where (I think) often those technical details can overshadow what is really being said. The Tower of Hanoi, then, seemed like a natural place to start. 

The paper is motivated by concerns about inconsistency in our mathematical theories. Inconsistency, of course, is bad – an inconsistent theory can prove anything at all. Gödel’s second incompleteness theorem tells us that any reasonably powerful mathematical theory cannot prove its own consistency. So, if we adopt one of those theories, then that theory can never assure us of its own consistency. Should we believe nonetheless that our theory is consistent? We surely want to. The Tower of Hanoi argues that we can never be certain of our theory’s consistency – we’re forced to accept the lingering possibility that our theory is inconsistent.

The idea driving the argument is this. First, we define a fast growing function \text{Exp}_k(n) (it’s defined inductively on k). For large k, and a given n, the value of \text{Exp}_k(n) is enormous (but still finite). Next, we produce a formula in the language of set theory that implicitly defines a property of finite sequences (the property itself doesn’t matter here). Then, if we can show that there exists a sequence of length n with that property, the (outrageously large but finite) number \text{Exp}_{2020}(n) does not exist.

This is bad. After all, \text{Exp}_{2020}(n) is just a finite number, and we want arbitrarily large sets in our mathematics. But allowing arbitrarily large sets is inconsistent with the non-existence of \text{Exp}_{2020}(n) – it says both that every number exists, and that there is a number that doesn’t exist. In an ideal world, for each suitable n, we’d want to prove that there can be no such sequence of length n with that property, thus ruling our forever the possibility of inconsistency these sequences pose. But that standard is out of reach. If arbitrarily large sets exist, then there is no proof of length less than n that there’s no sequence of length n with that property (i.e., that the corresponding bad sequence doesn’t exist). So there might be such a sequence after all.

The small comfort is supposed to be that if there is, any proof of its existence is longer than our given n – choose a massive n, like 10^{24}, that far exceeds the number of written pages in human history. Now, our conclusion reads: there might exist one of these bad sequences, but if there does, a proof of its existence would be longer than the number of pages ever written in human history. Thus, while we can’t rule it out entirely, a proof of inconsistency is way way way beyond the reach of humans’ current experience.

The paper draws an analogy between this situation and the Tower of Hanoi, which is where the paper gets its name. The Tower of Hanoi is a game in which there are three rods, and a number of discs placed on one of the rods, so that the discs are stacked on top of each other in decreasing size.

The Tower of Hanoi

The idea is to transfer all the discs to one of the other two rods so that they are stacked on the new rod exactly how they were stacked on the original rod. The rules say that you can only move one disc at a time, and you can only place a disc on a rod if there is no smaller disc below it. If there are n discs, the minimum number of moves required to win the game is 2^n - 1. So the larger the number of discs, the more moves it takes to win the game.

Legend has it that the great God Bramah once placed 64 discs of pure gold upon one of these rods at the great temple in Benares. The priests at the temple worked tirelessly to transfer the discs from one rod to another according to the rules. If the priests could complete the game, then the universe and everything in it would vanish forever.

Here is the analogy: an inconsistency in mathematics is bad, bad news. The world vanishing is bad, bad news. There’s a way we can find an inconsistency in mathematics — by giving a short enough proof that one of our bad sequences exists. There’s a way we can make the world vanish — by winning the game. There might be a way to show one of our bad sequences exists, but in our universe of sets, if there is, it’s out of practical reach. The proof is infeasibly long. There might be a way to win the game, but if there is, it’s out of current practical reach. The number of moves it takes to win the game is:

2^{64}-1=18 \hspace{3pt} 446 \hspace{3pt} 744 \hspace{3pt} 073 \hspace{3pt} 709 \hspace{3pt} 551 \hspace{3pt} 615.

If a priest moved one disc per second from the beginning of 2020 for 100 ordinary calendar years, they would make 3 155 673 600 moves — 10 orders of magnitude short of the minimum number of moves required to win. 

So whilst we’ll never be able to prove that our bad sequences don’t exist, and the world won’t disappear, we are forced to accept the possibility nonetheless.

One option at this point might be to try and give some sort of plausibility argument that our bad sequences don’t exist. But the paper concludes by arguing that there isn’t even any evidence that our bad sequences don’t exist, so that option isn’t available after all. “Evidence” here can be a number of formalized notions – it’s perhaps easiest to think of it as proof length. The idea is to construct a sentence \Omega_a with the property “there is no evidence of order a or more that the corresponding bad sequence doesn’t exist”. There are then two cases.

Very roughly, the first is the nonstandard case, where a is a nonstandard number. Then (under a bunch of extra technical conditions) its a theorem that if ZFC is consistent, then so is \Omega_a. Here, it looks like the consistency of \Omega_a is supposed to function as evidence for its truth, in much the same way that the consistency of large cardinal axioms is sometimes said to function as evidence for their truth. The latter argument is a very interesting one, but is far from obvious, and I think there’s a lot of room to push back there.

The second case is the standard case, where a is something like 10^{24}. Here the idea is that a bad sequence itself (i.e. a corresponding proof of inconsistency of length less than 10^{24}), and a feasible verification of that proof, both count as evidence for the truth of \Omega_{10^{24}}.

If we accept the idea that there is no evidence that our bad sequences don’t exist, we are led to two possibilities. One: we are committed to our universe of arbitrarily large sets. In this case, the nonstandard analysis goes through, \Omega_a is true, and the philosophical ramifications for our universe are weird. We are allowed arbitrarily large finite models of mathematics, so have everything available that we usually do, but we are also forced to accept that there is a nonstandard model that thinks \Omega_a is true. That is, we are forced to accept that there is a corresponding bad sequence. The second possibility: we give up our universe of arbitrarily large sets. But there are very few, if any, mathematicians who would want a universe like that.

The comparison with the Tower of Hanoi is cute, but despite all this, I don’t think there’s any need to worry. The possibility that mathematics is inconsistent bothers very few mathematicians. The claim that there is not even any evidence that there is no inconsistency in mathematics I think deserves to be taken more seriously. However, there’s a few ways to push back: what’s the right way to think of “evidence” in this context? Is the consistency of \Omega_a really evidence for its truth? Does this still hold in the context of nonstandard models? If \Omega_a‘s consistency is evidence for its truth, in what sense is that supposed to resemble the same argument for large cardinal axioms?

Perhaps answering these questions would offer some clarification, but for me, buying the evidence claim requires a lot more.

One thought on “Paper review: The Tower of Hanoi

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: