In mathematical logic, Goodstein's theorem is a statement about the natural numbers, made by Reuben Goodstein, which states that every Goodstein sequence eventually terminates at 0. Kirby & Paris 1982 showed that it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second order arithmetic). This was the third "natural" example of a true statement that is unprovable in Peano arithmetic (after Gerhard Gentzen's 1943 direct proof of the unprovability of ε_{0}induction in Peano arithmetic and the Paris–Harrington theorem). Earlier statements of this type had either been, except for Gentzen, extremely complicated, adhoc constructions (such as the statements generated by the construction given in Gödel's incompleteness theorem) or concerned metamathematics or combinatorial results (Kirby & Paris 1982).
Laurie Kirby and Jeff Paris gave an interpretation of the Goodstein's theorem as a hydra game: the "Hydra" 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. The Kirby–Paris interpretation of the theorem says 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, very long time.
Contents
Hereditary basen notation
Goodstein sequences are defined in terms of a concept called "hereditary basen notation". This notation is very similar to usual basen positional notation, but the usual notation does not suffice for the purposes of Goodstein's theorem.
In ordinary basen notation, where n is a natural number greater than 1, an arbitrary natural number m is written as a sum of multiples of powers of n:
where each coefficient a_{i} satisfies , and . For example, in base 2,
Thus the base 2 representation of 35 is 2^{5} + 2^{1} + 2^{0}. (This expression could be written in binary notation as 100011.) Similarly, one can write 100 in base 3:
Note that the exponents themselves are not written in basen notation. For example, the expressions above include 2^{5} and 3^{4}.
Full article ▸
