Goodstein Function in Terms of Fast-Growing Function Hierarchies

Goodstein's theorem (GT) is a natural independence phenomenon. GT is the combinatorial statement that for each integer , the associated Goodstein sequence (GS) eventually reaches zero. This statement is true but unprovable in Peano arithmetic (PA). For each integer , the Goodstein function (GF) computes the exact length of the GS associated with , that is, the number of terms needed to reach zero. The statement "GF is total" is true but unprovable in PA. In this Demonstration, the user can generate Goodstein sequences and values of the Goodstein function. For small , GF is computed numerically; for higher , GF is computed in terms of two different function hierarchies, the Löb–Wainer hierarchy and the Hardy hierarchy. Both hierarchies are fast-growing families of functions indexed by transfinite ordinals. Hence, you can develop an idea of the explosive growth of GF well beyond the framework controlled by PA. Eventually, GF dominates every Hardy and Löb–Wainer function and is therefore not provably total in PA.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

The hereditary representation of an integer , also known as the complete base representation [2], represents as a sum of powers of a base , followed by expressing each of the exponents as a sum of powers of , etc., until the process stops. The change-of-base function takes a natural number and changes the base to in the complete base representation of (see [2]).
Example 1: The complete base 2 representation of 266 is .
Example 2: .
The Goodstein sequence [2,5] for , , is defined by , where and and
.
Example 3: is 3,3,3,2,1,0,0,0,…
The Goodstein function [2] is defined as the smallest index for which . Hence measures the effective length of , that is, is the number of terms needed to reach 0 in the sequence .
Example 4: .
The explosive growth of GF can be seen by taking : . Compare this to the Shannon number , a lower bound for the number of possible chess games, or with the estimated number of elementary particles in the universe, (see [2]). The number of digits of is larger than the value . Eventually, GF dominates every recursive function that PA can prove to be total. The Löb–Wainer [3] and Hardy [4] function hierarchies are used to characterize provable total functions in PA. The Hardy hierarchy of fast-growing recursive functions is indexed by transfinite ordinals and generalizes the Ackermann function, which occurs (in a slight variant) as (see [4] for more details). The Löb–Wainer fast-growing hierarchy of recursive functions is indexed by transfinite ordinals as well (see [3] for more details). Here denotes the first ordinal solving Cantor's equation .
Now, let denote the change-of-base function replacing each by the ordinal in the complete base representation of .
Example 5: .
Chichon [1] showed that .
Caicedo [2] showed that for with and , one can write GF in terms of the Löb–Wainer functions as follows:
Hence GF eventually dominates every Hardy and Löb–Wainer function and therefore is not provably total in PA. Hence, the Goodstein theorem is a true but unprovable statement in PA and one of the prime examples of a natural independence phenomenon.
References
[1] E. A. Chichon, "A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods," Proc. of the AMS, 87(4), 1983 pp. 704–706.
[2] A. E. Caicedo, "Goodstein's Function," Rev. Col. de Matemáticas, 41(2), 2007 pp. 381–391.
[3] M. H. Löb and S. S. Wainer, "Hierarchies of Number Theoretic Functions I, II: A Correction," Arch. Math. Logik Grundlagenforschung 14, 1970 pp. 198–199.
[4] G. H. Hardy, "A Theorem Concerning the Infinite Cardinal Numbers," Quarterly J. of Mathematics 35, 1904.
[5] R. Goodstein, "On the Restricted Ordinal Theorem," J. of Symbolic Logic, 9(2), 1944 pp. 33–41.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.