A: Goodstein’s argument over the natural numbers

For any given natural number m, we can express the Goodstein sequence G(m) for m in a form where each term of the sequence is expressed in it’s hereditary representation:

[1]     G(m) \equiv \left\{g_{1}(m)_{[2]},\ g_{2}(m)_{[3]},\ g_{3}(m)_{[4]}, \ldots \right\}

where the first term g_{1}(m)_{[2]} denotes the unique hereditary representation ofthe natural number m in the natural number base [2]:

e. g. g_{1}(9)_{[2]} \equiv 1.2^{(1.2^{1.2^{0}}+1.2^{0})} + 0.2^{(1.2^{1.2^{0}}+0.2^{0})} + 0.2^{1.2^{0}} + 1.2^{0}

and if n > 1 then g_{(n)}(m)_{[n+1]} is defined recursively from g_{(n-1)}(m)_{[n]} as below.

B: The recursive definition of Goodstein’s Sequence over the natural numbers

For n > 1 let the (n-1)^{th} term g_{(n-1)}(m) of the Goodstein natural number sequence G(m) be expressed syntactically by its hereditary representation as:

[2]     g_{(n-1)}(m)_{[n]} \equiv \sum_{i=0}^{l} a_{i}.n^{i_{[n]}}

where:

(a) 0 \leq a_{i} < n over 0 \leq i \leq l

(b) a_{l} \neq 0

and for each 0 \leq i \leq l the exponent i too is expressed syntactically by its hereditary representation i_{[n]} in the base [n]; as also are all of its exponents and, in turn, all of their exponents, etc.

We then define the n^{th} term of G(m) as:

[3]     g_{n}(m) = \sum_{i=0}^{l} (a_{i}.(n+1)^{i_{[n\ \hookrightarrow\ (n+1)]}} )-1

C: The hereditary representation of g_{n}(m)

Now we note that:

(a) if a_{0} \neq 0 then the hereditary representation of g_{n}(m) is:

[4]          g_{n}(m)_{[n+1]} \equiv \sum_{i=1}^{l} (a_{i}.(n+1)^{i_{[n\ \hookrightarrow\ (n+1)]}} ) + (a_{0}-1)

(b) whilst if a_{i} = 0 for all 0 \leq i < k, then the hereditary representation of g_{n}(m) is:

[5]          g_{n}(m)_{[n+1]} \equiv \sum_{i=k+1}^{l} (a_{i}.(n+1)^{i_{[n\ \hookrightarrow\ (n+1)]}} ) + {c_{k}}_{[n+1]}

where:

c_{k} = a_{k}.(n+1)^{k_{[n\ \hookrightarrow\ (n+1)]}} - 1

= (a_{k} - 1).(n+1)^{k_{[n\ \hookrightarrow\ (n+1)]}} + \left\{(n+1)^{k_{[n\ \hookrightarrow\ (n+1)]}} - 1\right\}

= (a_{k}-1).(n+1)^{k_{[n\ \hookrightarrow\ (n+1)]}} + n\left\{(n+1)^{k_{[n\ \hookrightarrow\ (n+1)]}-1} + (n+1)^{k_{[n\ \hookrightarrow\ (n+1)]}-2} \ldots +1\right\}

and so its hereditary representation in the base (n+1) is given by:

{c_{k}}_{[n+1]} \equiv (a_{k}-1).(n+1)^{k_{1[n+1]}} + n\left\{(n+1)^{k_{2[n+1]}} + (n+1)^{k_{3[n+1]}} \ldots +1\right\}

where k_{1[n+1]} \equiv k_{[n\ \hookrightarrow\ (n+1)]} and k_{1} > k_{2} > k_{3} > \ldots \geq 1.

D: Goodstein’s argument in arithmetic

For n > 1 we then consider the difference:

d_{(n-1)} = \left\{g_{(n-1)}(m)_{[n]}- g_{n}(m)_{[n+1]}\right\}

Now:

(a) if a_{0} \neq 0 we have:

[6]          d_{(n-1)} = \sum_{i=0}^{l} (a_{i}.n^{i_{[n]}}) - \sum_{i=1}^{l} (a_{i}.(n+1)^{i_{[n\ \hookrightarrow\ (n+1)]}} ) - (a_{0}-1)

(b) whilst if a_{i}=0 for all 0 \leq i < k we have:

[7]          d_{(n-1)} = \sum_{i=k}^{l} (a_{i}.n^{i_{[n]}}) - \sum_{i=(k+1)}^{l} (a_{i}.(n+1)^{i_{[n\ \hookrightarrow\ (n+1)]}} ) \\- (a_{k} - 1).(n+1)^{k_{1[n+1]}} - n\left\{(n+1)^{k_{2[n+1]}} + (n+1)^{k_{3[n+1]}} + \ldots +1 \right\}

Further:

(c) if in equation (6) we replace the base [n] by the base [z] in the term:

[8]          \sum_{i=0}^{l} a_{i}.n^{i_{[n]}}

and the base [n+1] also by the base [z] in the term:

[9]          \sum_{i=k+1}^{l} (a_{i}.(n+1)^{i_{[n\ \hookrightarrow\ (n+1)]}} ) + (a_{0}-1)

then we have:

[10]          d^{\prime}_{(n-1)} = \sum_{i=0}^{l} (a_{i}.z^{i_{[n\ \hookrightarrow\ z]}}) - \sum_{i=1}^{l} (a_{i}.z^{i_{[n\ \hookrightarrow\ z]}}) - (a_{0}-1)

= 1

since (i_{[n\ \hookrightarrow\ (n+1)]})_{[(n+1)\ \hookrightarrow\ z]} \equiv i_{[n\ \hookrightarrow\ z]};

(d) whilst if in equation (7}) we replace the bases similarly, then we have:

[11]          d^{\prime}_{(n-1)} = \sum_{i=k}^{l} (a_{i}.z^{i_{[n\ \hookrightarrow\ z]}}) - \sum_{i=(k+1)}^{l} (a_{i}.z^{i_{[n\ \hookrightarrow\ z]}}) \\- (a_{k}-1).z^{k_{1[(n+1)\ \hookrightarrow\ z]}} - n\left\{z^{k_{2[(n+1)\ \hookrightarrow\ z]}} + z^{k_{3[(n+1)\ \hookrightarrow\ z]}} + \ldots +1\right\}

= a_{k}.z^{k_{[n\ \hookrightarrow\ z]}} - (a_{k} - 1).z^{k_{1[(n+1)\ \hookrightarrow\ z]}}) - n(z^{k_{2[(n+1)\ \hookrightarrow\ z]}} + z^{k_{3[(n+1)\ \hookrightarrow\ z]}} + \ldots +1)

= z^{k_{1[(n+1)\ \hookrightarrow\ z]}}-n(z^{k_{2[(n+1)\ \hookrightarrow\ z]}} + z^{k_{3[(n+1)\ \hookrightarrow\ z]}} + \ldots +1)

where k_{1[(n+1)\ \hookrightarrow\ z]} \equiv k_{[n\ \hookrightarrow\ z]},

and k_{1[(n+1)\ \hookrightarrow\ z]} > k_{2[(n+1)\ \hookrightarrow\ z]} > k_{3[(n+1)\ \hookrightarrow\ z]} > \ldots \geq 1.

We consider now the sequence:

G(m)_{[z]} \equiv (g_{1}(m)_{[2\ \hookrightarrow\ z]},\ g_{2}(m)_{[3\ \hookrightarrow\ z]},\ g_{3}(m)_{[4\ \hookrightarrow\ z]}, \ldots )

obtained from Goodstein’s sequence by replacing the base [n+1] in each of the terms g_{n}(m)_{[n+1]} by the base [z] for all n \geq 1.

Clearly if z > n for all non-zero terms of the Goodstein sequence, then d^{\prime}_{(n-1)} > 0 in each of the cases—equation (10) and equation (11).

(Since we then have:

d^{\prime}_{(n-1)} \geq (z^{k} - (z-1)(z^{(k-1)}+z^{(k-2)}+z^{(k-3)}+\ldots+1))=1

in equation (11).)

The sequence G(m)_{[z]} is thus a descending sequence of natural numbers, and must terminate finitely in \mathbb{N} if z > n.

Since g_{n}(m)_{[(n+1)\ \hookrightarrow\ z]} \geq g_{n}(m)_{[n+1]} if z > n, Goodstein’s sequence G(m) too must terminate finitely in \mathbb{N} if z > n.

Obviously, since we can always find a z > n for all non-zero terms of the Goodstein sequence if it terminates finitely in \mathbb{N}, the condition that we can always find some z > n for all non-zero terms of any Goodstein sequence is equivalent to the assumption that any Goodstein sequence terminates finitely in \mathbb{N}.

E: Goodstein’s argument over the ordinal numbers

We shall see next how Goodstein mirrors the above argument over the ordinals and curiously concludes the Theorem that, since we now have \omega > n_{o} for any finite ordinal n_{o}, therefore any Goodstein sequence over the natural numbers must terminate finitely since a corresponding Goodstein sequence of transfinite ordinals cannot be an infinitely descending sequence of ordinals!

Bhupinder Singh Anand

Advertisements