◄ Index                                                                                                                                      ◄ Main essay

 

How definitive is the standard interpretation of Goodstein’s argument?

Bhupinder Singh Anand[1]

(A .pdf  file of this essay before the current update is available at http://arXiv.org/abs/math/0311103)

Goodstein's argument is, essentially, that the hereditary representation, m<b>, of any given natural number m in the natural number base b, can be mirrored in Cantor Arithmetic, and used to well-define a finite, decreasing, sequence of transfinite ordinals, each of which is not smaller than the ordinal corresponding to the corresponding member of Goodstein's sequence of natural numbers, G(m). The standard interpretation of this argument is, first, that G(m) must, therefore, converge; and, second, that this conclusion - Goodstein’s Theorem - is unprovable in Peano Arithmetic, but true under the standard interpretation of the Arithmetic. We argue, however, that, even assuming Goodstein’s Theorem is, indeed, unprovable in PA, its truth must, nevertheless, be an intuitionistically unobjectionable consequence of some constructive interpretation of Goodstein's reasoning. We consider such an interpretation, and construct a Goodstein functional sequence to highlight why the standard interpretation of Goodstein's argument ought not to be accepted as a definitive property of the natural numbers.

Contents

 

1.    Introduction

 

2.    Notation and Definitions

 

3.    The Goodstein operations

 

4.    Goodstein’s argument

 

5.    Goodstein’s Theorem

 

5.1  Example: m = 1

5.2  Example: m = 2

5.3  Example: m = 3

 

6.    Some Goodstein sequence lemmas

 

7.    Three Goodstein sequence theorems

 

8.    Goodstein’s implicit Thesis

 

9.    A Goodstein functional sequence

 

10.   Formal mathematical objects

 

11.   Conclusion

 

References and Web resources

1.  Introduction

Goodstein’s argument [Gd44] is, essentially, that the hereditary representation, m<b>, in Peano Arithmetic[2], of any given natural number m in the natural number base b, can be mirrored in Cantor’s (ordinal) Arithmetic[3], and used to yield a finite[4], decreasing, sequence of transfinite ordinals, each of which is not smaller[5] than the ordinal corresponding to the corresponding member of Goodstein’s sequence of natural numbers, G(m).

The standard interpretation of this argument is, first, that G(m) must, therefore, converge (Goodstein’s Theorem); second, that this number-theoretic proposition is unprovable in any formal system of Peano Arithmetic, but expresses a truth, under the standard interpretation of the Arithmetic, that appeals necessarily to transfinite reasoning (Kirby-Paris Theorem [KB82]); and, third, that Goodstein’s Theorem is, in a sense, a proposition that, under such interpretation, expresses a more natural independence phenomenon than Gödel’s Theorem on formally unprovable, but interpretatively true, sentences of any formal system of Peano Arithmetic.

However, we note, first, that Gödel’s reasoning can be carried out in a weak Arithmetic such as Robinson's system Q [Ro50], which does not admit mathematical induction. The truth of the unprovable Gödel sentence could, thus, be reasonably argued as being even more intuitive than the truth, under the standard interpretation, of any number-theoretic assertion of Peano Arithmetic that necessarily appeals to mathematical induction. Moreover, both truths are, classically, accepted as constructive, and intuitionistically unobjectionable.

We note, further, that Goodstein’s Theorem involves a non-constructive - hence, non-verifiable - concept of mathematical truth[6] that is, prima facie, of a higher order of intuition, in a manner of speaking, than that required to see that Gödel’s formally unprovable sentence is a true number-theoretic assertion of Peano Arithmetic under its standard interpretation [Go31a].[7]

If, therefore, the proof of Goodstein's Theorem is to be considered as having established, both, an unprovable proposition of Peano Arithmetic that is true under its standard interpretation, and a more natural independence phenomenon than Gödel’s, then, such truth, too, must, reasonably, be a consequence of some constructive, and intuitionistically unobjectionable, interpretation of Goodstein's reasoning.

In §8 we argue that such an interpretation does, indeed, exist - as an implicit thesis - in Goodstein’s argument. In §9 and §10 we, consequently, construct, and consider, a Goodstein functional sequence that highlights why the standard interpretations of this argument ought not to be considered as definitive, and why we must consider the possibility that Goodstein’s argument validly constructs a non-terminating sequence of decreasing ordinals which is not definable in ZFC.

2.  Notation and Definitions

Ordinal number notation: We denote the ordinal number corresponding to the natural number m by [m].

Hereditary representation m<b> of a natural number m in base b: The hereditary representation of the natural number m in the natural number base b[8], which we denote by m<b>[9], is its syntactic expression as a sum of powers of the natural number base b, followed by expression of each of the exponents as a sum of powers of b, etc., until the process stops.

The rank of a hereditary representation: The rank of a hereditary representation is the highest power of the natural number base that has a non-zero co-efficient in the representation.

Goodstein Sequence: Let m<b>'' be the non-negative integer which results if we syntactically replace each b by (b+1) in the hereditary representation m<b> of a natural number m in base b. Starting at the hereditary representation of the natural number m in base 2, we formally define the Goodstein sequence, G(m), for m, as:

{m<2>, (m<2>''[10]-1)<3>, ((m<2>''-1)<3>''-1)<4>, (((m<2>''-1)<3>''-1)<4>''-1)<5>, ...},

which we express in an abbreviated form as:

{G(1, m), G(2, m), G(3, m), G(4, m), ...}.

Goodstein’s Theorem: For all natural numbers m, there exists a natural number n such that the nth term, G(n, m), of the Goodstein sequence, G(m), is 0.

3.  The Goodstein operations

We note that each natural number m has a unique hereditary representation, of some finite rank l, in any given natural number base b. Without loss of generality, we may express this syntactically as:

m<b> =[11] ,

where:

(a)  0 ≤ ai < b over 0 ≤ i ≤ l;

(b)  al ≠ 0;

(c)  for each 0 ≤ i ≤ l, the exponent i, too, is expressed syntactically by its hereditary representation, i<b>, in the base b; so, also, are all of its exponents, and, in turn, all of their exponents, etc.

3.1  Partial Goodstein operation

We define the partial Goodstein operation[12], on the hereditary representation of a natural number m in the natural number base b, by:

The natural number m<b>'' is derived from m under a partial Goodstein operation by syntactically replacing b by b+1 in the hereditary representation m<b> of m in the base b.

We can express this, also without loss of generality, as:

m<b>'' =

which is the same as:

m<b>'' = ,

where (i<b>)" is derived from i by, similarly, syntactically replacing b by b+1 in the hereditary representation i<b> of i in the base b.

3.2  Complete Goodstein operation

We, then, define the result of a complete Goodstein operation, on the hereditary representation of a natural number m in the natural number base b, as the hereditary representation (m<b>''-1)<b+1>.

4.  Goodstein’s argument

In his 1944 paper, Goodstein, essentially, considers, for any given natural number m, the sequence, G(m), of natural numbers of Peano Arithmetic:

{m<2>, (m<2>''-1)<3>, ((m<2>''-1)<3>''-1)<4>, (((m<2>''-1)<3>''-1)<4>''-1)<5>, ...},

and the parallel sequence, O[m<μ>], of ordinal numbers of Cantor Arithmetic:

{[m<2|μ>], [(m<2>''-1)<3|μ>], [((m<2>''-1)<3>''-1)<4|μ>], [(((m<2>''-1)<3>''-1)<4>''-1)<5|μ>], ...},

where [m<b|μ>] is the ordinal number obtained from the hereditary representation m<b> of m in the base b by syntactically replacing all natural numbers in m<b> by their corresponding ordinals, other terms by their corresponding[13] set-theoretical terms, and then syntactically replacing the ordinal [b] by the ordinal [μ].

Now, by properties of ordinal addition, multiplication and exponentiation ([Me64], p189), we have, for any given m<b>, the ordinal inequality, [m<b|ω>][14] > [m], where [m] denotes the ordinal corresponding to the natural number m, and ω denotes Cantor’s first infinite ordinal.

Further, by arithmetical properties that are characteristic of transfinite ordinals such as ω - but not necessarily shared by the sequence O[m<μ>] if [μ] is a finite ordinal - it can be shown that O[m<ω>] is a decreasing sequence of transfinite ordinals, each of whose members is not smaller than the ordinal corresponding to the corresponding member of the sequence of natural numbers, G(m).

Since, in Cantor Arithmetic, the ordinals are well-ordered, and there are no infinite, decreasing, sequences of ordinals, Goodstein concludes that O[m<ω>] is a finite sequence of transfinite ordinals.

5.  Goodstein’s Theorem

Now, assuming that a set theory, such as ZFC, can be treated as a consistent extension of a first order Peano Arithmetic, such as standard PA,[15] the standard interpretation of Goodstein’s argument is, then:

Goodstein’s Theorem: For all natural numbers m, there exists a natural number n such that the nth term, G(n, m), of the Goodstein sequence, G(m), is 0.

We note that this interpretation of Goodstein’s argument is supported by the following examples.

5.1  Example: m = 1

12 = 1.20;

12'' = 1.30;

(12'' - 1)3 = 0.30;

Hence G(1) is {1, 0}.

5.2  Example: m = 2

22 = 1.21 + 0.20;

22'' = 1.31 + 0.30;

(22'' - 1)3 = 2.30;

(22'' - 1)3'' = 2.40;

((22'' - 1)3'' - 1)4 = 1.40;

((22'' - 1)3'' - 1)4'' = 1.50;

(((22'' - 1)3'' - 1)4'' - 1)5 = 0.50;

Hence G(2) is {2, 2, 1, 0}.

5.3  Example: m = 3

32 = 1.21 + 1.20;

32'' = 1.31 + 1.30;

(32'' - 1)3 = 1.31 + 0.30 

(32'' - 1)3'' = 1.41 + 0.40;

((32'' - 1)3'' - 1)4 = 3.40;

((32'' - 1)3'' - 1)4'' = 3.50;

(((32'' - 1)3'' - 1)4'' - 1)5 = 2.50;

(((32'' - 1)3'' - 1)4'' - 1)5'' = 2.60;

((((32'' - 1)3'' - 1)4'' - 1)5'' - 1)6 = 1.60;

((((32'' - 1)3'' - 1)4'' - 1)5'' - 1)6'' = 1.70;

(((((32'' - 1)3'' - 1)4'' - 1)5'' - 1)6'' - 1)7 = 0.70;

Hence G(3) is {3, 3, 3, 2, 1, 0}.

6.  Some Goodstein sequence lemmas

However, we now argue that, to the extent that standard interpretations of Goodstein’s argument use, but ignore the significance of, the fact that arithmetical properties of the sequence O[m<μ>], in the case where [μ] is a finite ordinal, are not necessarily shared by the sequence O[m<ω>], in the case where [ω] is an infinite ordinal, and vice versa, such interpretations cannot be considered definitive.

In order to highlight the significance of the above distinction, we introduce some general properties of sequences generated by iterated application of the complete Goodstein operation on the hereditary representation of the natural number m in a natural number base b.

6.1  The first Goodstein sequence lemma

We note, firstly, that, if:

G(1, m) = ,

where:

(a)  0 ≤ ai < 2 over 0 ≤ i ≤ l;

(b)  al ≠ 0;

(c)  for each 0 ≤ i ≤ l, the exponent i, too, is expressed syntactically by its hereditary representation, i<2>, in the base 2; so, also, are all of its exponents, and, in turn, all of their exponents, etc.

then:

G(1, m)'' = ,

and, so:

G(1, m)''- G(1, m)   = ,

= .

Now, if m > 3, then l ≥ 2. Hence:

G(1, m)''- G(1, m)   ≥ 3l''- 2l,

≥ 33- 22,

> 1.

It follows that:

Lemma 1: If there exists a natural number n such that the nth term, G(n, m), of the Goodstein sequence, G(m), is 0, then, for all m > 3, there is some k < n such that G(k, m) < G((k-1), m).

6.2  The second Goodstein sequence lemma

Next, since the base of the k’th term of a Goodstein sequence is (k+1), we have that:

G(k, m) = ,

where:

(a)  0 ≤ ai < (k+1) over 0 ≤ i ≤ l;

(b)  al ≠ 0;

(c)  for each 0 ≤ i ≤ l, the exponent i, too, is expressed syntactically by its hereditary representation, i<k+1>, in the base (k+1); so, also, are all of its exponents, and, in turn, all of their exponents, etc.

If, now, 0 ≤ j < l, and aj ≠ 0, then:

G(k, m) ≥ al(k+1)l+aj(k+1)j.

We, thus, have that:

G(k, m)''-1   ≥ al(k+2)l''+aj(k+2)j''-1,

≥ al(k+1)l+aj(k+1)j.

It follows that:

Lemma 2: If the hereditary representation of the kth term, G(k, m), of the Goodstein sequence, G(m), contains more than one non-zero term, then G((k+1), m) ≥ G(k, m).

6.3  The third Goodstein sequence lemma

We consider, then, the case:

G(k, m) = ,

where 1 < al < (k+1), and ai = 0 for 0 ≤ i < l.

Since all the terms in the above summation, except the first, are 0, we have that:

(G(k, m)''-1)-G(k, m) = al((k+2)l''-(k+1)l)-1.

It follows that:

Lemma 3: If the leading term in the hereditary representation of the kth term, G(k, m), of the Goodstein sequence, G(m), is of the form , where 1 < al < (k+1), then G((k+1), m) > G(k, m) if l ≥ 1, and G((k+1), m) < G(k, m) if l = 0.

6.4  The fourth Goodstein sequence lemma

We consider, now, the case:

G(k, m) = ,

where al = 1, (k+1) ≤ l, and ai = 0 for 0 ≤ i < l.

Since l'' > l, we have that:

(G(k, m)''-1)-G(k, m) = (k+2)l''-(k+1)l-1,

> 0.

It follows that:

Lemma 4: If the first term in the hereditary representation of the kth term, G(k, m), of the Goodstein sequence, G(m), is of the form 1.(k + 1), where (k+1) ≤ l, then G((k+1), m) > G(k, m).

6.5  The fifth Goodstein sequence lemma

We consider, next, the case:

G(k, m) = ,

where al = 1, (k+1) > l, and ai = 0 for 0 ≤ i < l.

Since, now, l'' = l, we have that:

(G(k, m)''-1)-G(k, m) = (k+2)l-(k+1)l-1.

It follows that:

Lemma 5: If the leading term in the hereditary representation of the kth term, G(k, m), of the Goodstein sequence, G(m), is of the form 1.(k + 1),where (k+1) > l, then:

(i)      G((k+1), m) > G(k, m) if l >1;

(ii)     G((k+1), m) = G(k, m) if l =1;

(iii)    G((k+1), m) < G(k, m) if l = 0.

6.6  The sixth Goodstein sequence lemma

Now, if G(n, m) = 0 for some natural numbers m and n, then:

If n > 1, the hereditary representation of G(n, m) in the base (n+1) is 0.(n+1)0 ;

If n > 2, the hereditary representation of G((n-1), m) in the base n is 1.(n)0 ;

If n > 3, the hereditary representation of G((n-2), m) in the base (n-1) is 2.(n-1)0 ;

If n > 5, the hereditary representation of G((n-3), m) in the base (n-2) is 3.(n-2)0 ;

...

If n > (2r-1), the hereditary representation of G((n-r), m) in the base (n-r+1) is r.(n-r+1)0.

It follows that, for some natural number n1 > 1, we must have either n = (2n1+1), or n = 2n1.

Now, if n = (2n1+1), then the hereditary representation of (G((n-n1), m)+1) in the base (n-n1+1) is n1.(n-n1+1)0+1.(n-n1+1)0, i.e., (n1+1).(n1+2)0.

However, since (n1+1).(n1+2)0 is not the result of any partial Goodstein operation, we cannot have n = (2n1+1).

Hence, n = 2n1, and the hereditary representation of G((n-n1), m) in the base (n-n1+1) is n1.(n-n1+1)0, i.e., n1.(n1+1)0.

We thus have:

Lemma 6: If the nth term, G(n, m), of the Goodstein sequence, G(m), is 0, then n = 2n1, and the hereditary representation of G((n1-1), m) in the base n1 is 1.n11+0.n10.

Corollary 6.1: If the nth term, G(n, m), of the Goodstein sequence, G(m), is 0, then n = 2n1, and, for n1 ≤ k ≤ n, we have that G(k, m) = (n-k).   

6.7  The seventh Goodstein sequence lemma

Arguing as before, we now have that:

If n1 > 2, the hereditary representation of G((n1-1), m) in the base n1 is 1.n11+0.n10;

If n1 > 3, the hereditary representation of G((n1-2), m) in the base (n1-1) is 1.(n1-1)1+1.(n1-1)0;

If n1 > 4, the hereditary representation of G((n1-3), m) in the base (n1-2) is 1.(n1-2)1+2.(n1-2)0;

If n1 > 6, the hereditary representation of G((n1-4), m) in the base (n1-3) is 1.(n1-3)1+3.(n1-3)0;

...

If n1 > 2r, the hereditary representation of G((n1-r), m) in the base (n1-r+1) is 1.(n1-r+1)1+(r-1).(n1-r+1)0 .

We thus have that (n1-1) too, must be even, and, if (n1-1) = 2n2, then:

If n2 > 3, the hereditary representation of G((n2-1), m) in the base n2 is 2.n21+0.n20.

We thus have:

Lemma 7: If the nth term, G(n, m), of the Goodstein sequence, G(m), is 0, then n = 2(2n2+1), where the hereditary representation of G((n2-1), m) in the base n2 is 2.n21+0.n20.

Corollary 7.1: If the nth term, G(n, m), of the Goodstein sequence, G(m), is 0, then n = 2(2n2+1), and, for n2 ≤ k < 2n2, we have that G(k, m) = G((k+1), m).   

7.  Three Goodstein sequence theorems

It follows from the above lemmas that:

First Goodstein sequence theorem[16]: If the nth term, G(n, m), of the Goodstein sequence, G(m), is 0, then n = 2(2n2+1) for some natural number n2, and:

(i)      G(k, m) = (n-k) for (2.n2+1) ≤ k ≤ n;

(ii)     G(k, m) = G((k+1), m) for n2 ≤ k < 2.n2;

(iii)    G(k, m) < G((k+1), m) for 1 ≤ k < n2.

Thus, any sequence generated by the iterated application of the complete Goodstein operation on the hereditary representation of any natural number in any natural number base cannot oscillate. We thus conclude that:

Second Goodstein sequence theorem: For any given natural number m, the Goodstein sequence, G(m), of natural numbers converges if, and only if, it is bounded finitely in Peano Arithmetic.

We note, next, that, for all natural numbers k > 1, if L(k) is the sequence of finite natural numbers generated by iterated application of the complete Goodstein operation on the hereditary representation of kk in the base k:

<kk, (kk)''-1, ((kk)''-1)''-1, (((kk)''-1)''-1)''-1, ...>,

then:

kk<k> = 1.kk+0.k(k-1)+0.k(k-2)+ ... +0.k0

((kk<k>)''-1)<k+1>       =  1.(k+1)(k+1)+0.(k+1)(k-1)+0.(k+1)(k-2) + ... +0.(k+1)0-1.(k+1)0

=  k.(k+1)k+k.(k+1)(k-1)+k.(k+1)(k-2)+ ... +k.(k+1)0.

Thus, L(k) is a sequence of natural numbers, each of whose members is such that the rank of the hereditary representation of any successor-member is less than the base of the representation; in other words, the complete Goodstein operation leaves the exponents in the hereditary representation of any successor-member unchanged (as in Goodstein’s argument with transfinite ordinals).

Now, we note that a complete Goodstein operation on any number of the form:

,

where 1 ≤ al, l < k, and ai = 0 for 0 ≤ i < l,

(i)   either, yields, if al > 1, a number of the same rank, l, but with a reduced co-efficient of the highest power of the base, such as:

(k+1)i),

where cl = (al-1), and 0 < ci < (k+1) over 0 ≤ i < l;

(ii)  or, yields, if al = 1, a number of reduced rank, such as:

(k+1)i),

where 0 < ci < (k+1) over 0 ≤ i < (l-1).

In either case, it can be shown, inductively, that iterated application of the complete Goodstein operation must eventually reduce the rank of some member of the sequence to 0. By lemma 3, the sequence must, therefore, terminate with 0.

It follows that:

Lemma 8: For any natural number k, the sequence, L(k), defined as:

{kk, (kk)k''-1, ((kk)k''-1)(k+1)''-1, (((kk)k''-1)(k+1)''-1)(k+2)''-1, ...},

is a finite sequence that terminates with 0.

We, thus, have that:

Third Goodstein sequence theorem: For any given natural number m, the Goodstein sequence, G(m), of natural numbers:

{m, m<2>''-1, (m<2>''-1)<3>''-1, ((m<2>''-1)<3>''-1)<4>''-1, ...},

converges finitely if, and only if, there is some natural number k such that the sequence L(k) of finite natural numbers:

{kk, (kk)k''-1, ((kk)k''-1)(k+1)''-1, (((kk)k''-1)(k+1)''-1)(k+2)''-1, ...},

generated by the iterated application of the complete Goodstein operation on the hereditary representation of kk in the base k, is such that, for any n such that G(n, m) ≠ 0, L(n, k) > G(n, m), and L(k) converges finitely.

Proof: We note, firstly, that, if there is a convergent sequence L(k) as defined above, then G(m) is a finitely bounded sequence and so, by the preceding lemmas, it must converge to 0.

Secondly, if G(m) converges finitely in n terms, and the largest member of the sequence is p, we can take k = max(n, p). By lemma 8, L(2q, k) = 0 for some q.

Since, by the first Goodstein sequence theorem, the largest term in L(k) is L(q, k) = q, and we also have that q > kk, it follows that q > n. Hence, for any n such that G(n, m) =/= 0, we have that L(n, k) > G(n, m).

8.  Goodstein’s implicit Thesis

We can now express Goodstein’s argument constructively in Peano Arithmetic as:

The Goodstein Thesis: For any given natural numbers m and k, and partial sequences {G(n, m): 1≤ n ≤ k}, i.e.:

{m2, (m2''-1)3, ((m2''-1)3''-1)4, (((m2''-1)3''-1)4''-1)5, ...}k,

and {R(n, G(n, m)(n+1)|u(k)): 1≤ n ≤ k}, defined as.:

{ (m2)2|u(k), (m2''-1)3|u(k), ((m2''-1)3''-1)4|u(k), (((m2''-1)3''-1)4''-1)5|u(k), ...}k,

where:

(i)   u(k) is the base of the largest term in the partial sequence {G(n, m): 1≤ n ≤ k},

(ii)  and R(n, G(n, m)(n+1)|u(k)) is the natural number obtained from the hereditary representation of G(n, m) in the base (n+1) by syntactically replacing the base (n+1) by the base u(k),

we have that:

Lt [u(k)] < ω.

Now, by the first Goodstein sequence theorem, there is no natural number base u(k) for which we have that:

R(n, G(n, m)(n+1)|u(k)) < R((n+1), G((n+1), m)(n+2)|u(k))

Thus Goodstein’s argument appeals to properties of sequences of transfinite ordinals in Cantor Arithmetic that do not correspond to any arithmetical properties of their corresponding sequences of natural numbers in Peano Arithmetic.

It follows we cannot, prima facie, conclude that, by simply replacing a constructive natural number base, u(k), by the non-constructive ordinal base, ω, Goodstein’s argument establishes Goodstein’s Theorem as a true assertion of Peano Arithmetic, under its standard interpretation, in a constructive, and intuitionistically unobjectionable, way.

Such a conclusion must, therefore, implicitly appeal to some non-constructive, and counter-intuitive, assumption that needs to be expressed explicitly.

9.  A Goodstein functional sequence

The above point is illustrated better if we define the sequence of functions, {R(n, G(n, m)(n+1)|x)}, i.e.:

{(m2)2|x, (m2''-1)3|x, ((m2''-1)3''-1)4|x, (((m2''-1)3''-1)4''-1)5|x, ...},

as the Goodstein functional sequence of m.

If mn(x) is the n’th term of this functional sequence, we, then, have:

(i) mn(x) - mn+1(x) = 1 if mn(x) has a constant term c, where x > c > 0,

and:

(ii) mn(x) - mn+1(x) ≥ (x-2)x(a-1) if the lowest power of x in mn(x) is cxa, where c and a are constants such that a > 0, and x > c > 0.

Hence, for all natural numbers n ≥ 1, u > 2:

N{mn(u)} is a finite, decreasing, sequence of natural numbers.

Now, if the Goodstein sequence for m, i.e., G(m), terminates after l terms, then, clearly:

 mn(l) ≥ G(n, m) for all n ≥ 1.

However, if G(m) does not terminate, then, for any u > 2, there can be no decreasing, sequence of natural numbers, N{mn(u)}, such that:

mn(u) ≥ G(n, m) for all n ≥ 1.

Nevertheless, in either case, treating [mn(x)] as a function over the ordinals, there is always a decreasing sequence of transfinite ordinals, W{[mn(ω)]}, such that:

[mn(ω)] ≥ [G(n, m)] for all n ≥ 1,

where [G(n, m)] is the ordinal corresponding to the natural number G(n, m).

10.  Formal mathematical objects

Now, as noted above, Goodstein’s argument does not directly address this issue of the upper bound of a Goodstein sequence in Peano Arithmetic. Instead, it indirectly, and implicitly, concludes the existence of such a bound by assuming that there is a finite, recursively well-defined, decreasing sequence, {W[n, G(n, m)n|ω]}[17], of transfinite ordinals in Cantor Arithmetic, such that, for any n such that G(n, m) ≠ 0, we have that W[n, G(n, m)n|ω] ≥ [G(n, m)], where W[n, G(n, m)n|ω] is the ordinal obtained by replacing the base (n+1) in the nth term of the Goodstein sequence, G(m), by ω, i.e., by the first infinite ordinal.

However, in the absence of a constructive proof, or meta-proof[18], to the contrary, we must admit the possibility that some Goodstein sequence of natural numbers in Peano Arithmetic does not converge. The latter would be the case if Goodstein’s assumption - that we can recursively define an ordinal sequence, {W[n, G(n, m)n|ω]}, which is a well-defined, formal, mathematical object in Cantor Arithmetic - is invalid. Consequently, Goodstein’s argument - that the ordinal sequence {W[n, G(n, m)n|ω]} is a well-defined, finite[19], decreasing, set in Cantor Arithmetic - would be vacuously true.

In other words, we must allow for the possibility that Goodstein’s argument validly constructs a non-terminating sequence of decreasing ordinals which is not definable in ZFC.

It follows that, if we admit such a possibility, then we cannot treat the standard interpretations of Goodstein’s argument as establishing Goodstein’s Theorem definitively.

We can express the above reservation more precisely. Goodstein’s argument ignores the possibility that the recursively defined ordinal sequence, {W[n, m(n+1)|ω]}, may not be a formal mathematical object in Cantor Arithmetic (i.e., in a set theory such as, say, ZFC), in the following sense:

Definition 1(i): A primitive mathematical object is any symbol for an individual constant, predicate letter, or a function letter (cf. [Me64], p46; also p1, p10), which is defined as a primitive symbol of a formal mathematical language.

Definition 1(ii): A formal mathematical object is any symbol for an individual constant, predicate letter, or a function letter that is either a primitive mathematical object, or that can be introduced through definition (cf. [Me64], p82) into a formal mathematical language without inviting inconsistency[20].

Definition 1(iii): A mathematical object is any symbol that is either a primitive mathematical object, or a formal mathematical object.

Definition 1(iv): A set is the range of any function whose function letter is a formal mathematical object.

Consideration of formal mathematical objects in more detail would lie outside the immediate scope of this investigation (whose limited aim is to establish that, prima facie, there are sufficient grounds for arguing that the standard interpretations of Goodstein’s argument ought not to be accepted as definitive).

Nevertheless, we note that, in Anand [An02b], we consider the existence of a primitive recursive number-theoretic relation that is intuitively decidable constructively, but which cannot be introduced through definition as a formal mathematical object into any formal system of Peano Arithmetic, PA, without inviting inconsistency. Ipso facto, such a relation cannot be introduced through definition as a formal mathematical object into any Axiomatic Set Theory, such as ZFC, in which the axioms of PA interpret as theorems. Hence, it is not a formal mathematical object, and the range of its characteristic function is not a recursively enumerable set.

Since recursive number-theoretic functions and relations are classically accepted as amongst the most basic building blocks for defining constructive, and intuitionistically unobjectionable, mathematical objects, we cannot, prima facie, accept Goodstein’s argument as sufficient for establishing the recursively defined, and admittedly non-constructive, ordinal sequence, {W[n, G(n, m)n|ω]}, as a formal mathematical object in Cantor Arithmetic.

11.  Conclusion

Goodstein’s argument implicitly assumes that the recursively defined ordinal sequence, {W[n, m(n+1)|ω]}, is a formal mathematical object in Cantor Arithmetic. In other words, it implicitly assumes the existence of a well-defined set of transfinite ordinals, in Cantor Arithmetic, which has properties corresponding to the properties required of the number-theoretic sequence L(k) that is defined in the third Goodstein sequence theorem above.

Since, as argued in Anand [An02b], such an assumption need not necessarily hold, Goodstein’s Theorem can, reasonably, be viewed as a number-theoretic proposition whose truth in the standard interpretation of any formal system of Peano Arithmetic has simply been asserted as a non-verifiable consequence of a non-constructive argument.

We conclude that, in the absence of a constructive, and intuitionistically unobjectionable, proof, or meta-proof, that any given Goodstein sequence is bounded in Peano Arithmetic, the standard interpretation of Goodstein’s Theorem as a number-theoretic assertion that is consistent with any formal system of Peano Arithmetic, such as standard PA, ought not to be accepted as definitive.

References

[Go31a]  Gödel, Kurt. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York.

[Gd44]    Goodstein, R. L. 1944. On the Restricted Ordinal Theorem. J. Symb. Logic 9, 33-41, 1944.

[Ha47]    Hardy, G.H. 1947, 9th ed. Pure Mathematics. Cambridge, New York. 

[KP82]   Kirby, L. and Paris, J. 1982. Accessible independence results for Peano arithmetic. Bulletin of the London Math. Soc. 4, 1982, pp.285-293.

[La51]     Landau, E.G.H. 1951. Foundations of Analysis. Chelsea Publishing Co., New York. 

[Me64]   Mendelson, Elliott. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton. 

[Pe90]     Penrose, R. (1990, Vintage edition). The Emperor's New Mind: Concerning Computers, Minds and the Laws of Physics. Oxford University Press.

[Pe94]     Penrose, R. (1994). Shadows of the Mind: A Search for the Missing Science of Consciousness. Oxford University Press.

[Ro50]    Robinson, R. An essentially undecidable axiom system. In Proceedings of the International Congress of Mathematicians, Cambridge, MA, 1950. (Graves et al, editors). 1952. American Mathematical Society, Providence, RI, pp. 729-730.

[Ru53]    Rudin, Walter. 1953. Principles of Mathematical Analysis. McGraw Hill, New York.

[Ti61]      Titchmarsh, E. C. 1961. The Theory of Functions. Oxford University Press.

Web resources (not necessarily peer-reviewed) [21]

[An02a]  Anand, B. S. 2002. Reviewing Gödel's and Rosser's meta-reasoning of undecidability. (Web essay)

<Preprint: http://alixcomsi.com/Constructivity_consider.htm>

[An02b]  Anand, B. S. 2002. Some consequences of defining mathematical objects constructively and mathematical truth effectively. (Web essay)

<Preprint: http://alixcomsi.com/CTG_06_Consequences.htm>

[Bu03]    Burbanks, A. 2003. Fast-Growing Functions and Unprovable Theorems.

<http://www2.maths.bris.ac.uk/~maadb/research/seminars/online/fgfut/fgfut19.html>

[Go31]    Gödel, Kurt. 1931. On formally undecidable propositions of Principia Mathematica and related systems I.

<http://home.ddc.net/ygg/etext/godel/index.htm>

[Ma99]   Mathworld. 1999. Goodstein's Theorem.

<http://mathworld.wolfram.com/GoodsteinsTheorem.html>

[Mi01]    Miller, Justin. 2001. On the Independence of Goodstein's Theorem.

<http://www.u.arizona.edu/~miller/thesis/index.html>

[Po01]    Podnieks, Karlis. 2001. Around Goedel's Theorem.

<http://www.ltn.lv/~podnieks/gt.html>

[Re03]    R.E.S. 2003. Long Linear Segments in Goodstein Sequences.

<http://r.s.home.mindspring.com/GoodsteinSequences/Goodstein.txt>

[Si87]      Simpson, S.G. 1987. Unprovable theorems and fast-growing functions. Contemporary Math. 65 1987, 359-394

<ftp.math.psu.edu:/pub/simpson>

[Wi03]    Wikipedia. 2003. Goodstein’s theorem.

◄ Index           ▲ Top of page


[1] The author is an independent scholar. E-mail: re@alixcomsi.com; anandb@vsnl.com. Postal address: 32, Agarwal House, D Road, Churchgate, Mumbai - 400 020, INDIA. Tel: +91 (22) 2281 3353. Fax: +91 (22) 2209 5091.

 

Updated: Wednesday, 30th May 2007, 1:30:49 AM IST, by re@alixcomsi.com.

 

[2] By Peano Arithmetic, we mean the arithmetic of the natural numbers that is definable in a formal number theory such as Mendelson’s theory S ([Me64], p102).

 

[3] By Cantor Arithmetic, we mean the arithmetic of the ordinal numbers that is definable in a formal set theory such as ZFC or NBG (cf. Mendelson [Me64], p189).

 

[4] We note that, for a sequence of ordinals to be termed as finite, it must be a well-defined set in Cantor Arithmetic ([Me64], p184).

 

[5] In the sense in which this relation is defined in Cantor Arithmetic.

 

[6] Necessarily so, according to a reasonable interpretation of the Kirby-Paris Theorem [KB82].

 

[7] This follows since, as Gödel pertinently notes in his seminal 1931 paper ([Go31a], p26), the truth of his unprovable sentence, under its standard interpretation, is meta-mathematically verifiable constructively, in an intuitionistically unobjectionable manner, in Peano Arithmetic. See, also, the reasoning in Anand [An02a].

 

[8] It is implicit here, and in what follows, that (the base) b > 1.

 

[9] We note that m and m<b> denote, but are different syntactical expressions of, the same natural number.

 

[10] Strictly speaking, m'' should always be expressed as m<b>'', to avoid ambiguity; however, where the base concerned in the (partial Goodstein) operation is obvious from the context, we sometimes denote m<b>'' by m'' for clarity and conciseness of expression. We note that m<b>''  is also, sometimes, denoted in the literature by B(b, m), where B is referred to as the Goodstein ‘bumping’, or “base-change”, function, and B(b, m) is the non-negative integer that results if we syntactically replace each b by (b+1) in the hereditary representation m<b> of the natural number m in base b.  

 

[11] Strictly speaking, this is a syntactical equivalence.

 

[12] We prefer to define these concepts as “operations”, rather than as “functions”, simply to avoid any implicit commitment to possible set-theoretic properties.

 

[13] We assume that such a correspondence exists, along the lines described, for instance, in Mendelson ([Me64], p192).

 

[14] We note that [m<b|ω>] is defined as the Cantor Normal Form of the hereditary representation mb.

 

[15] That a set theory, such as ZFC, cannot be unrestrictedly treated as a consistent extension of a first order Peano Arithmetic, such as standard PA, is also suggested by independent arguments offered in Anand [An02b].

 

[16] The characteristic structure of all terminating Goodstein sequences, expressed by this theorem, is investigated interestingly by R.E.S. [Re03], and visualised intriguingly in a striking computer-generated plot, of G(m), for m >= 4, at <http://r.s.home.mindspring.com/GoodsteinSequences/Goodstein.gif>.

 

[17] We note that this is the same as the sequence, W{mn(w)}, of the previous section.

 

[18] We note that such a meta-proof need not be provable in PA; in other words, the truth - or falsity - of Goodstein’s Theorem in the standard interpretation of PA does not depend on the existence of a PA proof sequence for the Theorem - or for its negation.

 

[19] As previously noted, for the sequence to be termed as finite, it must be a well-defined set in Cantor Arithmetic ([Me64], p184).

 

[20] We take Mendelson’s Corollary 1.15 ([Me64], p37), as the classical meta-definition of consistency.

 

[21] This investigation has liberally used the cited on-line resources, not necessarily peer-reviewed, that are freely available on the world-wide web.