# The hydra game

Today I lectured about the Hydra game by Laurence Kirby and Jeff Paris (Accessible Independence Results for Peano Arithmetic, Kirby and Paris, Bull. London Math. Soc. 1982; 14: 285-293). For the occasion I implemented the game in Java. I am publishing the code for anyone who wants to play, or use it for teaching.

A hydra is a finite tree, with a root at the bottom. The object of the game is to cut down the hydra to its root. At each step, you can cut off one of the heads, after which the hydra grows new heads according to the following rules:

• If you cut off a head growing out of the root, the hydra does not grow any new heads.
• Suppose you cut off a head like this:
Delete the head and its neck. Descend down by 1 from the node at which the neck was attached. Look at the subtree growing from the connection through which you just descended. Pick a natural number, say 3, and grow that many copies of that subtree, like this:

My program grows $n$ copies at step $n$ of the game, which is one possible variant of the game. There are spoilers ahead, so before you read on you should play the game with the Hydra applet (your browser must support Java) and try to win. Is it possible to win? How should you play to win?

Here is a surprising fact:

Theorem 1: You cannot lose!

The proof uses ordinal numbers. To each hydra we assign an ordinal number:

• A head gets the number $0$.
• Suppose a node $x$ has sub-hydras $H_1, \ldots, H_n$ growing from it. To each sub-hydra we assign its ordinal recursively and order the ordinals in descending order: $\alpha_1 \geq \alpha_2 \geq \ldots \geq \alpha_n$. The ordinal assigned to the node $x$ is $\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$. For example, the ordinal corresponding to the hydra from the first picture above is $\omega^{\omega^3 + 1} + 1$. The hydra in the second picture gets the ordinal $\omega^{\omega^2 \cdot 4 + 1} + 1$.
• By chopping off a head we strictly decrease the ordinal. Because there are no infinite strictly descending sequences of ordinals, the hydra will eventually die, no matter how you chop off heads.

But Theorem 1 is not the punchline. The punchline is this:

Theorem 2 (Kirby and Paris): Any proof technique that proves Theorem 1 is strong enough to prove that Peano arithmetic is consistent.

Consistency of Peano arithmetic is Hilbert's second problem, which was solved by Gentzen in 1936.

The program is written in Java and is available freely under the BSD License. You may:

• Get the source code from the GitHub hydra repository.
• Download a JAR file hydra.jar, suitable for running on your computer as a stand-alone application, for which you need Java Runtime Environment (JDK will do as well, of course). It should run when you double-click on it (you may have to convince your computer this is not a security risk).
• Try the game online (you may have to convince your browser that this is not a security risk).

[...] cierto namero de cabezas y con otros la hidra se mantendrÃ¡ tal cual quede despuÃ©s del corte. En esta web podÃ©is ver tanto la explicacion del juego como el enlace a un applet de java donde podais jugar [...]

John A.

Hi,

Cool game. But I think it has a bug. You don't seem to eliminate a head attached to the root when picked, so that those "root heads" get replicated when you subsequently pick a non root head to eliminate.

If I have this to start: [sourcecode gutter="false"] O Y X \ / /
O /
| / O </pre> And eliminate the X, and then the Y, it's as if I never eliminated the X at all.

Or perhaps I don't understand the game...

John.

I think there's something you don't understand. If you first cut off X (assuming in your picture that X grows from the root), then X disappears, of course. After that, if you cut of Y, X will not magically reappear. Which bit of the text is unclear to you?

Thanks for the game, but i haven't successful yet

Peter

The ordinals you provide for the two pictures have lost all the formatting for exponentiation, and thus are very confusing. Also, there's a small error:

first pic: Ï‰^(Ï‰^3 + 1) + 1 2nd pic: Ï‰^((Ï‰^2)*4 + 1) + 1

Your error was that the four was on the wrong side of the Ï‰^2.

@Peter: I see them fine on my Firefox, what platform are you using? I fixed the problem with multiplication by 4 from the wrong side, thank you for spotting it.

Hey Andrej,

I just wrote up another similar application of ordinal arithmetic: a method of surfing the internet without getting infinitely sidetracked following links. Kind of like this hydra, except with webpages and links instead of hydra-heads. Here it is: http://www.xamuel.com/internet-surfing-ordinals/

[...] In the late 70s a series of sentences such that Peano arithmetic cannot prove and cannot prove were discovered. They have in common that, unlike Goedel's examples, they are not coding logical notions. Instead, they are genuine mathematical statements of the kind that a person working in combinatorics would find interesting. The example I gave is Goodstein's theorem (an undergraduate student of mine at Caltech wrote a nice paper on this a few years ago, "The termite and the tower."). There are others. A nice one is about a game, Hercules and the Hydra. [...]

Bo

You said a head gets the number 0 but in your examples is seems to be 1.

@Bo: I think it's ok. The head itself gets a 0, but because it is growing out of a lower node, we turn that into $\omega^0 = 1$. So, the only way to get $0$ is to have just one head without any necks, in other words the root. For example, if we had one head growing out of the root we would assign $0$ to the head, and then $\omega^0 = 1$ to the whole thing.

Scott

I can't get the java applet to work in Opera or Firefox, and the program didn't work as a standalone either. (I followed the command-line instructions and got a "class not found" type of error. I do have the JRE installed.) Any chance you can help? I'd like to use it for a talk I'm giving in two days.

Scott

It works for me under Chrome 17.0. on MacOS. At a minimum you'd have to tell me what OS you're using, which version of Opera/Firefox you're using, can you run any other applets on the internet, what version of JRE you installed, and what version of Java your browser is using.

Scott

I got it to work. Note for other Ubuntu users--make sure you have the icedtea6-plugin installed for the web applet to work.

[...] objects of the world so that the subtraction always stops, but that this is hard to prove. See this note by Andrej Bauer on “The hydra game” for a discussion of such [...]

Brendan Long

The .jar file seems to be missing a manifest. I had to run it like this:

java -cp ~/Downloads/hydra.jar hydra.HydraWindow


The META-INF/MANIFEST.MF should have a line like:

Main-Class: hydra.HydraWindow


[…] The applet was created by Andrej Bauer. It is free and open source, available under the BSD license. You can dowload it from his cool website on the Hydra game here: http://math.andrej.com/2008/02/0… […]

Andrew K

Thanks, Andrej, and thanks, Brendan - your instructions work for me (on OSX)

Jeremiah

I'm not sure I understand this. It starts with size 9 by default, I changed it to 3 (I body with 2 heads) to make an original hydra. If I click on one head, instead of making 2 extra heads grow in it's place (making it 3 heads and one body) like the hydra thing goes, it switches to 1 head and 1 body. Also, why does it have multiple bodies if you start at 9? I thought the hydra always had 1 body, and heads never grew heads. Very confused.

Is there a rigorous definition for what constitutes a rigorous definition?

Thanks for A2A, Héctor. Probably not, because it's a purely colloquial and, actually, silly expression. I'm not a logician, so I maybe wrong but I believe the only basis definitions in maths are incorporated set theory and logic. Even numbers, be it…

[…] this is the same as the relation on http://math.andrej.com/2008/02/02/the-hydra-game/ and I expect has smaller […]

[…] than basic graph theory (it is nicely summed up in the article pointed out by @anorton, i.e. here, if you are wondering what the mysterious symbol ?? means, check out the ordinal numbers at […]

[…] The Hydra Game http://math.andrej.com/2008/02/02/the-hydra-game/ […]

[…] for large numbers, we encounter a mythical monster – the Hydra. We will though deal with a well known, more abstract version of […]

Write your comment using Markdown. Use $⋯$ for inline and $$⋯$$ for display LaTeX formulas, and <pre>⋯</pre> for display code. Your E-mail address is only used to compute your Gravatar and is not stored anywhere. Comments are moderated through pull requests.

Name

E-mail

Website

Comment