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.
[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.
![[Snapshot]](HTMLImages/index.en/thumbnail_1.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_2.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_3.gif)
Embed Interactive Demonstration 
Browse all topics
