Brandon Doherty, Department of Pure Mathematics, University of Waterloo
"Goodstein sequences and the Hydra game"
Gödel's incompleteness theorem proves the existence of certain statements about the natural numbers that can be neither proven nor disproven using basic first-order arithmetic. The kinds of statements constructed in the standard proof of the incompleteness theorem, however, are extremely technical, and not very interesting in and of themselves.
This raises the question: are there any natural, interesting statements about the natural numbers that are neither provable nor disprovable in first-order arithmetic? In 1982, Kirby and Paris provided examples of easily understandable theorems which are true, and can be stated in the language of first-order arithmetic, but cannot be proven. One of these states that every one of a class of sequences known as Goodstein sequences, which initially grow extremely quickly, eventually decays to zero and terminates. The other states that a graph-theoretic game involving rooted trees, known as the Hydra game, eventually terminates regardless of the player's strategy.
MC 5479