# Guest Post: Ordinals and Hydras, by Brian Lawrence

A few days ago, the hydra game came up in discussion with Brian Lawrence; we'd both run into a somewhat mystifying analysis of the game via ordinals.  Brian and I came up with a much more down-to-earth analysis (which experts will recognize as the same as the usual one); Brian decided to write it up, and I asked him if I could post his write-up here.

Guest post by Brian Lawrence:

I've read in a number of places about the Hydra game, which one plays by applying a certain type of move to a rooted tree.  The theorem (surprising at first) is that the Hydra game always terminates: there is no infinite sequence of legal moves.  The theorem is used in mathematical logic as an example of a result that can only be proven in a sufficiently strong proof system.  I'm not an expert in logic, so I won't say any more about that.  Instead, I'd like to give a straightforward proof of the Hydra theorem.

The game is based on the mythical Hydra, a many-headed monster.  In myth, every time you cut off one of the Hydra's heads, it would grow two more.

Our Hydra is a (finite) rooted tree.  One performs a sequence of moves; each move is as follows.  Choose a leaf $x_0$ of the rooted tree, and remove it.  Then, let $x_1$ be the parent node of $x_0,$ and $x_2$ the parent node of $x_1$ (assuming it exists).  Let $S$ be the subtree consisting of $x_1$ and all its descendants, after $x_0$ has been removed.  When you remove $x_0,$ the Hydra chooses a $N > 0,$ and attaches $N$ new copies of $S$ as children of $x_2.$  If $x_0$ doesn't have a grandparent, the Hydra doesn't get to add anything to the tree.  (Note that the Hydra can choose a different $N$ at every step.)  The game ends when only a single vertex (the root) remains.

One move of the hydra game.

There's a link to a Java version at the bottom of this page.  (The in-website applet doesn't work for me, but the downloadable version does.)

Here's the remarkable fact: no matter how we choose which leaves to cut off, and no matter how large the Hydra chooses its positive integers $N,$ the game is guaranteed to terminate after finitely many steps.

Let's define the "depth" of a rooted tree to be the length of the longest path from root to leaf.  If a tree has only one vertex, it has depth $0;$ if all leaves are adjacent to the root, the tree has depth $1;$ and so forth.  I'll prove the theorem by induction on the depth, starting with the case of depth $2.$  (The theorem is trivial for trees of depth $0$ and $1.$)

For any rooted tree, call an "immediate subtree" the subtree consisting of $x$ and all its descendants, where $x$ is a neighbor of the root.

Now suppose we have a tree $T$ of depth at most $2.$  Its immediate subtrees have depth at most $1.$  For every integer $r \geq 0,$ call $T_r$ the tree of depth at most $1$ where the root has $r$ children.

The tree $T_4$

(The depth of $T_0$ is $0.$)  To describe our tree $T,$ we just have to describe its immediate subtrees; in fact, if $a_r$ is the number of immediate subtrees isomorphic to $T_r,$ then our tree $T$ is determined completely by the tuple $(a_0, a_1, a_2, \ldots).$

The tree corresponding to the tuple $(0, 2, 1, 1, 0, 0, \ldots)$.

Let $\mathcal{I}_2$ be the set of tuples $(a_0, a_1, a_2, \ldots)$ of nonnegative integers, such that all but finitely many $a_r$ are nonzero.  We impose the lexicographic total ordering on $\mathcal{I}_2:$ given $a = (a_0, a_1, a_2, \ldots)$ and $b =(b_0, b_1, b_2, \ldots)$ in $\mathcal{I}_2,$ take the largest $r$ such that $a_r \neq b_r,$ and define $a > b$ if and only if $a_r > b_r.$

We have described a bijection between trees of depth at most $2$ and tuples in $\mathcal{I}_2.$  The theorem (for depth $2$) now follows from the following two lemmas, which are left as an exercise to the reader.

Lemma. Any legal move changes a tuple $a \in \mathcal{I}_2$ to another tuple $b$ such that $b < a$ for our total ordering.

Lemma. The set $\mathcal{I}_2$ is well-ordered: it contains no infinite descending chain.

We will construct recursively a well-ordered set $\mathcal{I}_d$ which classifies the isomorphism types of trees of depth at most $d.$  Specifically, we will construct $\mathcal{I}_{d+1}$ as a set of tuples of nonnegative integers, where instead of indexing by $\mathbb{N}$ we index by $\mathcal{I}_d.$  Precisely, $\mathcal{I}_{d+1}$ is the set of functions $a: \mathcal{I}_d \rightarrow \mathbb{N}$ (we notate such a function $i \mapsto a_i$) such that $a_i = 0$ for all but finitely many $i \in \mathcal{I}_d.$

Again, we impose on $\mathcal{I}_{d+1}$ the lexicographic total ordering: given any $a, b \in \mathcal{I}_{d+1},$ choose $i \in \mathcal{I}_d$ maximal such that $a(i) \neq b(i);$ and take $a > b$ if and only if $a(i) > b(i).$  (Only finitely many $i$ satisfy $a(i) \neq b(i),$ so there is no difficulty in choosing the maximal one.)

Just like before, there is a bijection between elements of $\mathcal{I}_{d+1}$ and isomorphism types of trees of depth at most $d+1:$ given a tree $T,$ produce the tuple which records for each $i \in \mathcal{I}_d$ the number of copies of $T_i$ that are immediate subtrees of $T.$

The result now follows from the following two lemmas, the first of which we again leave as an exercise.

Lemma. Any legal move changes a tuple $a \in \mathcal{I}_{d+1}$ to another tuple $b$ such that $b < a$ for our total ordering.

Lemma. The set $\mathcal{I}_{d+1}$ is well-ordered: it contains no infinite descending chain.

Proof. Suppose $a^{(1)} \geq a^{(2)} \geq a^{(3)} \geq \cdots$ is an infinite descending chain in $\mathcal{I}_{d+1}.$  We want to show that eventually the chain stabilizes: there exists $N$ such that $a^{(n)} = a^{(N)}$ for $n \geq N.$

$($A remark about notation: $a^{(N)} \in \mathcal{I}_{d+1}$ is a tuple in our infinite descending chain of tuples.  For $i \in \mathcal{I}_d,$ the $i$-th entry of this tuple is $a^{(N)}_i.)$

Let $j \in \mathcal{I}_d$ be an index; we say that the sequence $(a^{(n)})$ stabilizes to the right of index $j$ if there exists a positive integer $N$ such that
$$a^{(n)}_i = a^{(N)}_i$$
whenever $i \geq j$ and $n > N.$

Since $\mathcal{I}_d$ is well-ordered, we can choose $j$ minimal such that our sequence stabilizes to the right of $j;$ also choose $N$ as above, so that $(a^{(n)})_i = (a^{(N)})_i$ whenever $i \geq j$ and $n > N.$

The tuple $a^{(N)}$ has only finitely many nonzero entries.  If $a^{(N)}_k = 0$ for all $k < j$, then the sequence stabilizes at $a^{(N)}$ and we are done.  Otherwise, choose $k$ maximal such that $k < j$ and $a^{(N)}_k > 0.$   (There are only finitely many $k$ with $a^{(N)}_k > 0,$ so again there is no harm in choosing the maximum.)

I claim that in fact the sequence stabilizes to the right of index $k$, contradicting our choice of $j.$  Consider an index $i \geq k.$  If $i \geq j$ then we know $(a^{(n)})_i = (a^{(N)})_i$ for $n > N.$  If $k < i < j$ then $a^{(N)}_i = 0;$ and by the lexicographic ordering on $\mathcal{I}_{d+1}$ we know that $a^{(n)}_i = 0$ for $n > N$ as well.  So we only need to worry about $i = k.$  Again by lexicographic ordering, the sequence
$$a^{(N)}_k, a^{(N+1)}_k, a^{(N+2)}_k, \ldots$$
is a nonincreasing sequence of natural numbers.  Any such sequence in $\mathbb{N}$ eventually stabilizes.  So our sequence $(a^{(n)})$ stabilizes to the right of $k$ as well, contradicting our choice of $j.$ $\blacksquare$

In closing I'll just mention that the sets $\mathcal{I}_d$ are examples of ordinals; interpreting them as such gives rise to the proofs linked to at the very beginning of this post.