The set-theoretical argument for Goodstein’s Theorem meets William Gasarch’s criteria [1] of an argument that prima facie defies belief.

We shall show that the disbelief is justified, since Goodstein’s argument can be carried out completely over the structure \mathbb{N} of the natural numbers—without appealing to any properties of transfinite ordinal sequences—to yield the following:

Theorem 1: If G(m) is a Goodstein Sequence over the natural numbers then, for any natural number x, the first x terms of the Goodstein Functional Sequence G(m)_{[x]} formed by replacing the base syntactically in the hereditary representation of each term of G(m) by x form a monotonically decreasing sequence of natural numbers.

Proof: Follows immediately from (iii) below. \Box

Now, we shall argue that since we can show that the first order Peano Arithmetic PA cannot admit a model that contains a non-successor element \infty such that, for any given natural number n, we can have \infty > n, we cannot conclude from the above argument that every Goodstein sequence over the natural numbers must terminate finitely.

However Goodstein’s argument is that since any model of a first order Ordinal Arithmetic would admit a non-successor element \omega such that, for any given finite ordinal n_{o}, we have \omega > n_{o}, we can conclude from the above argument—when interpreted in the Arithmetic—that every Goodstein sequence over the finite ordinals must terminate finitely.

Moreover, since we can set up a 1-1 correspondence between the natural numbers and the finite ordinals, Goodstein concludes that every Goodstein sequence over the natural numbers must also terminate finitely.

We shall argue that Goodstein’s argument is a curious case of proving a Theorem involving the set-theoretical membership-based relation `>_{o}‘ over the structure of the ordinals below \epsilon_{o} and—ignoring Thoraf Skolem’s cautionary remarks [2] about unrestrictedly corresponding putative mathematical relations and entities across domains of different axiom systems—invalidly postulating that a corresponding theorem involving the natural number inequality relation `>‘ must therefore hold over the structure of the natural numbers.

Some properties of Goodstein’s sequence over the natural numbers

We note that, for any natural number m, R. L. Goodstein [3] uses the properties of the hereditary representation of m to construct a sequence G(m) \equiv \{g_{1}(m),\ g_{2}(m), \ldots\} of natural numbers by an unusual, but valid, algorithm.

Hereditary representation: The representation of a number as a sum of powers of a base b, followed by expression of each of the exponents as a sum of powers of b, etc., until the process stops.

For example, we may express the hereditary representations of 266 in base 2 and base 3 as follows:

226_{[2]} \equiv 2^{8_{[2]}}+2^{3_{[2]}}+2 \equiv 2^{2^{(2^{2^{0}}+2^{0})}}+2^{2^{2^{0}}+2^{2^{0}}}+2^{2^{0}}

226_{[3]} \equiv 2.3^{4_{[3]}}+2.3^{3_{[3]}}+3^{2_{[3]}}+1 \equiv 2.3^{(3^{3^{0}}+3^{0})}+2.3^{3^{3^{0}}}+3^{2.3^{0}}+3^{0}

For the moment we shall ignore the peculiar manner of constructing the individual members of the Goodstein sequence, since these are not germane to understanding the essence of Goodstein’s argument. We need simply accept for now that G(m) is well-defined over the structure \mathbb{N} of the natural numbers, and has the following properties:

(i) For any given natural number k > 0 we can construct a hereditary representation—denoted by g_{k}(m)_{[k+1]} [4]—of the k^{th} term g_{k}(m) of the Goodstein sequence G(m) in the base [k+1];

Example: The hereditary representations of the first two terms of G(226) are [5]:

g_{1}(226)_{[2]} \equiv 2^{2^{2+1}}+2^{2+1}+2

g_{2}(226)_{[3]} \equiv 3^{3^{3+1}}+3^{3+1}+2

(ii) We can define a Goodstein Functional Sequence G(m)_{[x]} \equiv \{g_{k}(m)_{[(k+1)\ \hookrightarrow\ x]} [6] : k > 0\} over \mathbb{N} by replacing the base [k+1] in g_{k}(m)_{[k+1]} with the variable x for each k > 0;

Example:

g_{1}(226)_{[2\ \hookrightarrow\ x]} \equiv x^{x^{x+1}}+x^{x+1}+x

g_{2}(226)_{[3\ \hookrightarrow\ x]} \equiv x^{x^{x+1}}+x^{x+1}+2

(iii) We can show that some member of Goodstein’s sequence G(m) terminates finitely (i.e., evaluates to 0) if, and only if, there is some natural number z such that for any given natural number k > 0:

If g_{k}(m)_{[(k+1)\ \hookrightarrow\ z]} > 0 in G(m)_{[z]}, then g_{k}(m)_{[(k+1)\ \hookrightarrow\ z]} > g_{k+1}(m)_{[(k+2)\ \hookrightarrow\ z]}.

Terminate finitely: By Goodstein’s algorithm, after a 0 all subsequent members of the sequence necessarily remain 0, and the sequence is said in such a case to terminate finitely at its first 0 value.

We shall show that the proof of (iii)—which depends, of course, on the peculiar nature of Goodstein’s algorithm—is merely tedious, but straightforward. The main point to note is that the proof appeals only to the usual properties of the natural numbers.

The question arises: Are we free to postulate the existence of such a natural number z, and conclude—as Goodstein’s argument does—that some member of G(m) must evaluate to 0 in \mathbb{N}?

Though it sounds absurd, the following theorem shows that this is precisely the freedom that the ordinal-based argument for Goodstein’s Theorem claims (albeit implicitly)!

Theorem 2: Goodstein’s ordinal sequence G_{o}(m_{o}) over the finite ordinals terminates with respect to the ordinal inequality `>_{o}‘ in any sound interpretation of a first order Ordinal Arithmetic even if Goodstein’s natural number sequence G(m) over the natural numbers does not terminate with respect to the natural number inequality `>‘ in any sound interpretation of PA.

Proof: Assume that Goodstein’s natural number sequence G(m) \equiv \{g_{k}(m)_{[(k+1)}: k > 0\} over the natural numbers does not terminate with respect to the natural number inequality `>‘ in any sound interpretation of PA.

Let n_{max} be the largest term amongst the first n terms of G(m). It is tedious but straightforward to show that, by our assumption, n_{max} is a monotonically increasing function of n. Hence there is no natural number z such that g_{k}(m)_{[(k+1)\ \hookrightarrow\ z]} > g_{k+1}(m)_{[(k+2)\ \hookrightarrow\ z]} for all k > 0.

Consider next Goodstein’s ordinal number sequence G_{o}(m_{o}) \equiv \{g_{k}(m_{o}): k > 0\} over the finite ordinals. There is now the axiomatically postulated transfinite ordinal \omega such that g_{k}(m_{o})_{[(k+1)\ \hookrightarrow\ \omega]} >_{o} g_{k+1}(m_{o})_{[(k+2)\ \hookrightarrow\ \omega]} for all k > 0.

Since there are no infinite descending sequences of ordinals under the ordinal inequality `>_{o}‘, Goodstein’s ordinal number sequence G_{o}(m_{o}) must terminate finitely with respect to the ordinal inequality `>_{o}‘ in any sound interpretation of a first order Ordinal Arithmetic. \Box

Since the finite ordinals can be meta-mathematically put into a 1-1 correspondence with the natural numbers, it follows that:

Corollary: The relationship of `terminating finitely’ with respect to the ordinal inequality `>_{o}‘ over an infinite set Z_{0} of ordinals containing a transfinite ordinal in any sound interpretation of a first order Ordinal Arithmetic cannot be corresponded to the relationship of `terminating finitely’ with respect to the natural number inequality `>‘ over an infinite set N of natural numbers in any sound interpretation of PA.

NOTES

Return to 1: William Gasarch. 2010. Theorems that you simply don’t believe. Computational Complexity blog, Thursday, March 11, 2010.

Return to 2: Thoralf Skolem. 1922. Some remarks on axiomatized set theory. Text of an address delivered in Helsinki before the Fifth Congress of Scandinavian Mathematicians, 4-7 August 1922. In Jean van Heijenoort. 1967. Ed. From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931. Harvard University Press, Cambridge, Massachusetts.

Return to 3: R. L. Goodstein. 1944. On the Restricted Ordinal Theorem. Journal of Symbolic Logic 9, 33-41.

Return to 4: Strictly speaking the denotation should be: (g_{k}(m))_{[k+1]}.

Return to 5: For ease of expression we express `a^{0}‘ as `1‘, and `a^{b^{0}}‘ as `a‘ unless indicated to the contrary.

Return to 6: We prefer this notation to that of the usual `base bumping’ function as it makes the argument more transparent.

Author’s working archives & abstracts of investigations

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand