Mathematica MathWorld Wolfram Science More »

HOME

TOPICS

LATEST

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.

Contributed by: Joachim Hertel

Show Initialization Code

(146 lines omitted)

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

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

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.

"Goodstein Function in Terms of Fast-Growing Function Hierarchies" from The Wolfram Demonstrations Project
http://demonstrations.wolfram.com/GoodsteinFunctionInTermsOfFastGrowingFunctionHierarchies/

Contributed by: Joachim Hertel

Mathematica 7 Just Released--Get Mathematica Player 7 Free--Download Now

Browse all topics

	Source page:
	Email	Name (optional)
	Occupation (optional)	Organization (optional)
	I use Mathematica often occasionally never
	Country (optional) Remember me
	Note: Please do not include anything you consider confidential or proprietary. Your message and contact information may be shared with the author of any specific Demonstration for which you give feedback, but will not otherwise be published or distributed. Privacy Policy »

Wolfram Research

Site Index

RSS

Atom