WOLFRAM|DEMONSTRATIONS PROJECT

Goodstein Function in Terms of Fast-Growing Function Hierarchies

​
start value
n
0
for the GS
0
maximum number ofGS elements to be computed
6
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
n
, the associated Goodstein sequence (GS) eventually reaches zero. This statement is true but unprovable in Peano arithmetic (PA). For each integer
n
, the Goodstein function (GF) computes the exact length of the GS associated with
n
, 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
n
, GF is computed numerically; for higher
n
, 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.