Goodstein's theorem

<p>In <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>, Goodstein's theorem is a statement about the <a href="/facts/Natural_number/u65og8JE">natural numbers</a>, proved by <a href="/facts/Reuben_Goodstein/7sSAxMPt">Reuben Goodstein</a> in 1944, which states that every Goodstein sequence (as defined below) eventually terminates at 0. Laurence Kirby and <a href="/facts/Jeff_Paris_(mathematician)/LuPfTlYh">Jeff Paris</a> showed that it is <a href="/facts/Independence_(mathematical_logic)/xW9tCrGB">unprovable</a> in <a href="/facts/Peano_axioms/DhhDnNug">Peano arithmetic</a> (but it can be proven in stronger systems, such as <a href="/facts/Second-order_arithmetic/abBxQsaH">second-order arithmetic</a> or <a href="/facts/Zermelo-Fraenkel_set_theory/UYIsPbXw">Zermelo-Fraenkel set theory</a>). This was the third example of a true statement about natural numbers that is unprovable in Peano arithmetic, after the examples provided by <a href="/facts/G%C3%B6del%27s_incompleteness_theorem/du8PRu8g">Gödel's incompleteness theorem</a> and <a href="/facts/Gerhard_Gentzen/9ujN0ssI">Gerhard Gentzen</a>'s 1943 direct proof of the unprovability of <a href="/facts/Epsilon_numbers_(mathematics)/t7w8KgA9">ε0</a>-induction in Peano arithmetic. The <a href="/facts/Paris%E2%80%93Harrington_theorem/YcvXywQb">Paris–Harrington theorem</a> gave another example.
</p><p>Kirby and Paris introduced a graph-theoretic <a href="/facts/Hydra_game/W2SvUUpk">hydra game</a> with behavior similar to that of Goodstein sequences: the "Hydra" (named for the mythological multi-headed <a href="/facts/Hydra_of_Lerna/CQcBcyIq">Hydra of Lerna</a>) is a rooted tree, and a move consists of cutting off one of its "heads" (a branch of the tree), to which the hydra responds by growing a finite number of new heads according to certain rules.  Kirby and Paris proved that the Hydra will eventually be killed, regardless of the strategy that Hercules uses to chop off its heads, though this may take a very long time. Just like for Goodstein sequences, Kirby and Paris showed that it cannot be proven in Peano arithmetic alone.
</p>

Goodstein's theorem open-in-new

Goodstein's theorem