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.