↑ arvau

Wikipedia / Goodstein's theorem

In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence (as defined below) eventually terminates at 0. Laurence Kirby and Jeff Paris showed in 1982 that Goodstein's theorem is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second-order arithmetic or Zermelo–Fraenkel set theory). This was the third example of a true statement about natural numbers that is unprovable in Peano arithmetic, after the examples provided by Gödel's incompleteness theorem and Gerhard Gentzen's 1943 direct proof of the unprovability of ε0-induction in Peano arithmetic. The Paris–Harrington theorem gave another example.

Kirby and Paris also introduced a graph-theoretic hydra game with behavior similar to that of Goodstein sequences: the "Hydra" (named for the mythological multi-headed Hydra of Lerna) is a rooted tree, and a move by "Hercules" 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.

Hereditary base-n notation

Goodstein sequences are defined in terms of a concept called "hereditary base-n notation". This notation is very similar to usual base-n positional notation for natural numbers, but the usual notation does not suffice for the purposes of Goodstein's theorem.

To achieve the ordinary base-n 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 ai satisfies , and .

For example, the base-3 notation of 100:

Here, the exponents of n themselves are not written in base-n notation, as is seen in the case 34, above.

To convert a base-n notation to a hereditary base-n notation, first rewrite all of the exponents as a sum of powers of n (with the limitation on the coefficients ). Then rewrite any exponent inside the exponents again in base-n notation (with the same limitation on the coefficients), and continue in this way until every number appearing in the expression (except the bases themselves) is written in base-n notation.

For example, 100 in hereditary base-3 notation is

Goodstein sequences

The Goodstein sequence of a number , is , is obtained by writing of the Goodstein sequence of is computed by:

  • taking the hereditary base-(,

  • replacing each occurrence of the base () with , then

  • subtracting one.

and on the index .

terminates at the sixth step (the column labeled "Hereditary notation" shows how the value is calculated): starts as follows (): a Woodall number

increases much more rapidly and starts as follows:In spite of this rapid growth, Goodstein's theorem states that every Goodstein sequence eventually terminates at 0, no matter what the starting value is.

Proof of Goodstein's theorem

of ordinal numbers in Cantor normal form because.. By infinite regress, which guarantees termination.

with the first infinite ordinal number.

. Addition, multiplication and exponentiation of ordinal numbers are well defined.

:

after applying the first, base-changing operation in generating the next element of the Goodstein sequence, but before the second minus 1.

. Now we apply the minus 1.

is not an ordinal.

is strictly decreasing. As the standard order < on ordinals is well-founded.

While this proof of Goodstein's theorem is fairly easy, the Kirby–Paris theorem, which shows that Goodstein's theorem is not a theorem of Peano arithmetic, is technical and considerably more difficult. It makes use of countable nonstandard models of Peano arithmetic.

Extended Goodstein's theorem

be as follows:

  • .

  • .

  • Subtract one.

The extended version is in fact the one considered in Goodstein's original paper, where Goodstein proved that it is equivalent to the restricted ordinal theorem (i.e. the claim that transfinite induction below ε0 is valid), and gave a finitist).

The extended Goodstein's theorem without any restriction on the sequence bn is not formalizable in Peano arithmetic (PA), since such an arbitrary infinite sequence cannot be represented in PA. This seems to be what kept Goodstein from claiming back in 1944 that the extended Goodstein's theorem is unprovable in PA due to Gödel's second incompleteness theorem and Gentzen's proof of the consistency of PA using ε0-induction. However, inspection of Gentzen's proof shows that it only needs the fact that there is no primitive recursive strictly decreasing infinite sequence of ordinals, so limiting bn to primitive recursive sequences would have allowed Goodstein to prove an unprovability result. Furthermore, with the relatively elementary technique of the Grzegorczyk hierarchy, thus giving an alternative proof to the same result Kirby and Paris proved.

Sequence length as a function of the starting value

The Goodstein function is the length of the Goodstein sequence that starts with n. (This is a total function in the Hardy hierarchy in the fast-growing hierarchy of Löb and Wainer:

  • Kirby and Paris (1982) proved that

  • .)

  • Cichon (1983) showed that

  • is the result of putting n in hereditary base-2 notation and then replacing all 2s with ω (as was done in the proof of Goodstein's theorem).

  • then

  • .

Some examples:(For Ackermann function and Graham's number bounds see .)

Application to computable functions

Goodstein's theorem can be used to construct a total computable function that Peano arithmetic cannot prove to be total. The Goodstein sequence of a number can be effectively enumerated by a Turing machine; thus the function that maps n to the number of steps required for the Goodstein sequence of n to terminate is computable by a particular Turing machine. This machine merely enumerates the Goodstein sequence of n and, when the sequence reaches 0, returns the length of the sequence. Because every Goodstein sequence eventually terminates, this function is total. But because Peano arithmetic does not prove that every Goodstein sequence terminates, Peano arithmetic does not prove that this Turing machine computes a total function.

See also

Notes

References

Bibliography