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

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_, 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_, 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_ 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_[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_'' be the non-negative integer which results if we syntactically replace each b by (b+1) in the hereditary representation m_ 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 n^th 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_ =[11] ,

where:

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

(b) a_l ≠ 0;

(c) for each 0 ≤ i ≤ l, the exponent i, too, is expressed syntactically by its hereditary representation, i_, 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_'' is derived from m under a partial Goodstein operation by syntactically replacing b by b+1 in the hereditary representation m_ of m in the base b.

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

m_'' =

which is the same as:

m_'' = ,

where (i_)" is derived from i by, similarly, syntactically replacing b by b+1 in the hereditary representation i_ 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_''-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_ of m in the base b by syntactically replacing all natural numbers in m_ 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_, 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 n^th 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

1₂ = 1.2⁰;

1₂'' = 1.3⁰;

(1₂'' - 1)₃ = 0.3⁰;

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

5.2 Example: m = 2

2₂ = 1.2¹ + 0.2⁰;

2₂'' = 1.3¹ + 0.3⁰;

(2₂'' - 1)₃ = 2.3⁰;

(2₂'' - 1)₃'' = 2.4⁰;

((2₂'' - 1)₃'' - 1)₄ = 1.4⁰;

((2₂'' - 1)₃'' - 1)₄'' = 1.5⁰;

(((2₂'' - 1)₃'' - 1)₄'' - 1)₅ = 0.5⁰;

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

5.3 Example: m = 3

3₂ = 1.2¹ + 1.2⁰;

3₂'' = 1.3¹ + 1.3⁰;

(3₂'' - 1)₃ = 1.3¹ + 0.3⁰

(3₂'' - 1)₃'' = 1.4¹ + 0.4⁰;

((3₂'' - 1)₃'' - 1)₄ = 3.4⁰;

((3₂'' - 1)₃'' - 1)₄'' = 3.5⁰;

(((3₂'' - 1)₃'' - 1)₄'' - 1)₅ = 2.5⁰;

(((3₂'' - 1)₃'' - 1)₄'' - 1)₅'' = 2.6⁰;

((((3₂'' - 1)₃'' - 1)₄'' - 1)₅'' - 1)₆ = 1.6⁰;

((((3₂'' - 1)₃'' - 1)₄'' - 1)₅'' - 1)₆'' = 1.7⁰;

(((((3₂'' - 1)₃'' - 1)₄'' - 1)₅'' - 1)₆'' - 1)₇ = 0.7⁰;

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 ≤ a_i < 2 over 0 ≤ i ≤ l;

(b) a_l ≠ 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) ≥ 3^l''- 2^l,

≥ 3³- 2²,

> 1.

It follows that:

Lemma 1: If there exists a natural number n such that the n^th 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 ≤ a_i < (k+1) over 0 ≤ i ≤ l;

(b) a_l ≠ 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 a_j ≠ 0, then:

G(k, m) ≥ a_l(k+1)^l+a_j(k+1)^j.

We, thus, have that:

G(k, m)''-1 ≥ a_l(k+2)^l''+a_j(k+2)^j''-1,

≥ a_l(k+1)^l+a_j(k+1)^j.

It follows that:

Lemma 2: If the hereditary representation of the k^th 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 < a_l < (k+1), and a_i = 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) = a_l((k+2)^l''-(k+1)^l)-1.

It follows that:

Lemma 3: If the leading term in the hereditary representation of the k^th term, G(k, m), of the Goodstein sequence, G(m), is of the form , where 1 < a_l < (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 a_l = 1, (k+1) ≤ l, and a_i = 0 for 0 ≤ i < l.

Since l''