Imagine you’re tasked with killing a hydra. As usual, the hydra is defeated when all of its heads are cut off, and whenever a head is cut off, the hydra grows new ones.

However, this mathematical hydra is much more frightening than a “traditional” one. It’s got a tree-like structure – heads growing out of its heads – and it can regrow entire groups of heads at once! Can you still win?

Also, this post is the first one with interactivity! Feel free to report bugs on the GitHub issues page.

For the purposes of our game, a hydra is a rooted tree. The root, on the left, is the body, and the leaves are the heads. Intermediate nodes are part of the necks of the hydra, and cannot (yet) be cut off.

You can cut off one head at a time, and when you do, the hydra may grow more heads, according to the following rules:

• If the head is connected directly to the root, then the hydra does nothing.
• Otherwise, look at the parent node (the one directly underneath the one you just cut off). The hydra grows two new copies of that node and all its children, attaching them to the grandparent as appropriate.

This is hard to convey through text, so let’s walk through an example. Let’s start with a pretty simple hydra, and cut off one of the heads. (Purple indicates newly-grown heads.)

We used to have two heads, and four nodes total, but now we have three, and seven nodes. That’s not good. Let’s try chopping off another one.

This increases the total number of heads, but now, we can cut off the three smallest heads, one at a time, without incident.

We’ve made some visible progress now. Cutting off one of the remaining heads will reveal three more, but we can extinguish them easily.

Repeating this process on the last head will kill the hydra.

We managed to defeat this hydra, but it was a pretty small one. What about something a bit larger? Let’s add one more head to that neck.

This time, you can try to kill it yourself: the illustration below is interactive!

Reset

Depending on how persistent you are, you might not be surprised to learn that you can indeed kill this hydra, though it’ll take tens of thousands of moves to do so (29528 moves by my count). In fact, you can kill any hydra, though I’ll make no guarantees about how long it will take.

But what may be surprising is that you can’t avoid killing the hydra, even if you try. No matter how large the hydra, or what order you cut off its heads, you will always defeat it in a finite number of moves.

And even better, this holds true even for faster-regenerating hydras. What if, instead of growing back two copies of the subtree, the hydra grows back three copies? Or a hundred? What if, on the \(N\)th turn of the game, it grows back \(N\) copies? \(N^2\)? \(N!\)? What if the hydra just gets to pick how many copies to regrow, as many as it wants?

It doesn’t matter.

You always win.

The proof here relies on ordinal numbers. If you’re not familiar, there’s a good video from Vsauce about them. The key property to know is that the ordinals are “well-ordered”; that is, there is no infinitely long descending sequence¹.

We assign an ordinal number to each hydra, in such a way that cutting off a head produces a hydra with a strictly smaller ordinal. As we play the hydra game, the sequence of hydras we encounter produces a corresponding sequence of ordinals. Since the ordinal sequence is strictly decreasing, it must eventually terminate, and so the hydra sequence must terminate as well. The only way that the hydra sequence can terminate is if we have no more heads to cut off; i.e., we’ve defeated the hydra.

The assignment is done by assigning values to the nodes, and accumulating down to the root:

• A head is assigned \(0\). Similarly, a trivial (dead) hydra is assigned \(0\).
• If a node has children with ordinals \(\alpha_1, \alpha_2, \ldots, \alpha_n\), then we assign the ordinal \(\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}\).²

What happens when we cut off a head?

• If it’s directly attached to the body, then it contributes a term of \(\omega^0 = 1\) to the whole ordinal. Killing this head removes this term, decreasing the ordinal.
• Otherwise, consider the ordinal of that head’s parent and grandparent. Before we cut off the head, the ordinal of the parent must have been of the form \(\alpha + 1\). This means the ordinal of the grandparent has a term \(\omega^{\alpha + 1}\). When we cut off the head, the parent ordinal decreases to \(\alpha\), but there’s now two more copies of it. This replaces the \(\omega^{\alpha + 1}\) term in the grandparent with \(3 \omega^\alpha\), which is strictly smaller. And because the rest of the tree remains unchanged, this means the ordinal assigned to the hydra as a whole also decreases.

To illustrate this process, let’s look the ordinals that correspond to the hydras we saw earlier. It may help to read them in reverse order.

We can also see why the hydra’s regeneration speed doesn’t matter. No matter how large \(N\) is, as long as it’s finite, \(\omega^{\alpha + 1}\) will be strictly larger than \(N \omega^{\alpha}\).

One way to think about this is that a neck that forks at height \(k+1\) is literally infinitely worse than a neck that forks at height \(k\). By cutting off a head, you simplify it at height \(k+1\), at the expense of introducing some forking at height \(k\), which isn’t as bad.

A last interesting fact: this proof relied on ordinal numbers, which have a whole lot of infinities (\(\omega\)s) tied up in them. But everything in this hydra game is finite; from an initial hydra, there’s only finitely many hydras we can encounter, each of which has only finitely many heads. Is there a proof that avoids any mention of infinity?

In 1982, Laurence Kirby and Jeff Paris proved that there isn’t, in the following sense: any proof technique strong enough to prove the hydra’s eventual demise is strong enough to prove the consistency of Peano arithmetic. In particular, it’s impossible to prove the hydra theorem from within Peano arithmetic.

1. In fact, the ordinals are the prototype of every well-founded set, and this is what makes them important. ↩
2. Without loss of generality, we can relabel the subhydras so that the ordinals are non-strictly descending. This avoids problems coming from the non-commutativity of ordinal addition. ↩