◄ Index
◄
Main essay
How definitive is the standard interpretation of
Goodstein’s argument?
Bhupinder
Singh Anand[1]
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.
1. Introduction
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
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''