Goodstein Function in Terms of Fast-Growing Function Hierarchies

start value

for the GS

maximum number ofGS elements to be computed

GS( n 0 ) = { n 0 , n 1 , n 2 , … Note: elements greater than 6 10 are displayed as realswith precision 1 in scientific form to increase readability	GS[0,8,6,1000000,1]
GF( n 0 ) numeric,or in terms of the Löb-Wainer hierarchy of functions	GFLW[0]
GF( n 0 ) numeric,or in terms of the Hardy function H α (1)-1with ordinal index α given by	GFH[0]

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.

Details

The hereditary representation of an integer

n>0

, 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

b+1

in the complete base

representation of

(see [2]).

Example 1: The complete base 2 representation of 266 is

266=

2+1

Example 2:

(266)=

3+1

The Goodstein sequence [2,5] for

GS(n)

, is defined by

GS[n]=

, where

k≥1

and

=n,

and

k+1

=

k+1

(

)-1if

0if

Example 3:

GS(3)

is 3,3,3,2,1,0,0,0,…

The Goodstein function [2]

GF:→

is defined as the smallest index

for which

. Hence

GF(n)

measures the effective length of

GS(n)

, that is,

GF(n)

is the number of terms needed to reach 0 in the sequence

GS(n)

Example 4:

GF(3)=6

The explosive growth of

can be seen by taking

n=4

GF(4)=3×

402653211

-2

. Compare this to the Shannon number

120

≈

399

, a lower bound for the number of possible chess games, or with the estimated number of elementary particles in the universe,

300

(see [2]). The number of digits of

GF(5)

is larger than the value

GF(4)

. Eventually,

dominates every recursive function that

can prove to be total. The Löb–Wainer [3] and Hardy [4] function hierarchies are used to characterize provable total functions in

. 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

[m]

denote the change-of-base function replacing each

by the ordinal

in the complete base

representation of

Example 5:

[266]=

ω+1

+ω

Chichon [1] showed that

GF[n]=

[n+1]

[1]-1

Caicedo [2] showed that for

+…+

with

>…>

and

(

)

, one can write GF in terms of the Löb–Wainer functions as follows:

GF(n)=

(

(…(

(3))…))-2.

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.