Goodstein Sequences: The Power of a Detour via Infinity

Originating authors are Michèle Artigue, Ferdinando Arzarello and Susanna Epp.
Studying the evolution of a natural phenomenon often leads to studying numerical sequences , especially their long-term behavior and whether they eventually converge. Polynomial, exponential, and logarithmic sequences are frequently encountered in secondary school, but certain other sequences with very simple definitions exhibit much more complex behavior. Examples include the chaotic sequences that arise in the study of dynamical systems (see [1]) and the Syracuse sequence (or 3n + 1 sequence), introduced by Luther Collatz in 1937. The Syracuse sequence has challenged mathematicians for decades. Despite the huge number of values that have been computed, it is currently unknown whether the sequence is infinite or is finite and always ends in 1 (see [2]).

The sequences considered in this vignette were introduced by the British logician R. L. Goodstein in 1944 (see [3]) and exhibit a different kind of unusual behavior. Their initial values increase so rapidly that we are led to believe that they tend to infinity, but, amazingly, they always end by decreasing and ultimately reach zero. Proving this result requires a generalization of the well-ordering principle for the integers (see [4]) to transfinite numbers, but the basic idea is not hard to understand. To explain it, like Hodgson, (see [5]) we first introduce a related sequence, called a weak Goodstein sequence, which is simpler but closely related to a Goodstein sequence.

1. Weak Goodstein Sequences

As in Hodgson, we illustrate the definition of a weak Goodstein sequence by starting with the number 266. Like all positive integers, it has a unique decomposition into a sum of powers with base 2 (see [6]): 266 = 2^8 + 2^3 +2^1. The weak Goodstein sequence with initial term u_0 = 266 is defined as follows: To obtain u_1 copy the base 2 representation for u_0 but change each base 2 to base 3, subtract 1, and rewrite the resulting number in base 3. Thus u_1 = 3^8 + 3^3 + 3^1 - 1 = 3^8 + 3^3 + 2 = 6,590. To determine u_2 start with the representation for u_1, change each base 3 to base 4, subtract 1, and rewrite the resulting number in base 4. Thus u_2 = 4^8 + 4^3 + 2 - 1 = 4^8 + 4^3 + 1 = 65,601. Continue generating terms of the sequence, as long as no term equals zero, by replacing the integer in the base of the previous term by the next larger integer, subtracting 1, and rewriting the result using the new base.

u_0 &= 2^8 + 2^3 + 2^1 = 266
u_1 &= 3^8 + 3^3 + 3^1 - 1 = 3^8 + 3^3 + 2 = 6,590
u_2 &= 4^8 + 4^3 + 2 - 1 = 4^8 + 4^3 + 1 = 65,601
u_3 &= 5^8 + 5^3 + 1 - 1 = 5^8 + 5^3 = 390,750
u_4 &= 6^8 + 6^3 - 1 = 6^8 + 5 . 6^2 + 6^2 - 1 = 6^8 + 5 . 6^2 + 5 . 6 + 6 - 1\\ = 6^8 + 5 . 6^2 + 5 . 6^1 + 5 = 1,679,831
u_5 &= 7^8 + 5 . 7^2 + 5 . 7^1 + 5 - 1 = 7^8 + 5 . 7^2 + 5 . 7^1 + 4 = 5,765,085
u_6 &= 8^8 + 5 . 8^2 + 5 . 8^1 + 4 - 1 = 8^8 + 5 . 8^2 + 5 . 8^1 + 3 = 16,777,579
u_7 &= 9^8 + 5 . 9^2 + 5 . 9^1 + 3 - 1 = 9^8 + 5 . 9^2 + 5 . 9^1 + 2 = 43,047,173
u_8 &= 10^8 + 5 . 10^2 + 5 . 10^1 + 2 - 1 = 10^8 + 5 . 10^2 + 5 . 10^1 + 1 = 100,000,551
u_9 &= 11^8 + 5 . 11^2 + 5 . 11^1 + 1 - 1 = 11^8 + 5 . 11^2 + 5 . 11^1 = 214,359,541
u_{10} &= 12^8 + 5 . 12^2 + 5 . 12^1 - 1 = 12^8 + 5 . 12^2 + 4 . 12^1 + 12 - 1\\ = 12^8 + 5 . 12^2 + 4 . 12^1 + 11 = 429,982,475

Table 1: Initial terms of a weak Goodstein sequence.

As you can see the terms of the sequence quickly become very large, so you might wonder if all such sequences increase as rapidly. But they do not. For instance, if u_0 = 1, then u_1 = 1 - 1 = 0. If u_0 = 2 = 2^1, then u_1 = 3^1 - 1 = 2, u_2 = 2 - 1 = 1 and u_3 = 1 - 1 = 0 (because the base for u_2 is 4 and the base for u_3 is 5). You can check similarly that if u_0 = 3, then the terms of the sequence never become larger than 3 and reach 0 in five steps (see [7]). However as soon as the decomposition for the initial value includes a higher power of 2 than 2^1, the initial increase in the terms is very rapid (as illustrated for u_0 = 266), which leads to the belief that the sequence tends to infinity. How can the fact of merely subtracting 1 at each step counteract the enormous increase in the terms that is obtained by continually adding 1 to the base?

And yet … let us look more carefully at the expressions in the table above. Even though successive terms of the sequence with first term 266 increase rapidly, the exponents for the representations in successive bases tend to decrease. For instance, the exponent 1 in u_0 is no longer present in u_1. Similarly, the exponent 3 in u_3 is replaced by a 2 in u_4. And by u_9, it is reduced to 1, at which point the coefficient by which it is multiplied begins to decrease. Ultimately, the exponent 8 in u_{10} is reduced to a 7, and the 7 continues to be reduced in further steps. It is this characteristic, common to all the Goodstein sequences, which will allow us to show that they converge to zero. To see this, we need to bring in, as promised, the transfinite ordinal numbers.

2. Transfinite Ordinal Numbers and Well Orderings

Ordinals:
In ordinary language, ordinal numbers are used to indicate position in a list: first, second, third, etc. Indeed, the positive integers can be used to arrange the elements of any finite set in this way. The idea of transfinite ordinal number extends the notion of ordinal number. It is due to the mathematician Georg Cantor, who developed it in a series of articles at the end of the 19th century. Because the set of integers is finite, if we imagine starting with 0 and counting successive integers we would never finish. We can, however, imagine that there is a “number” \omega , that is the first number greater than every integer. Because infinitely many integers are smaller than , we call a “transfinite” ordinal number. It has a successor \omega +1, which is followed by \omega + 2, and so forth. The smallest ordinal greater than all ordinals of the form \omega + n, is denoted \omega + \omega or \omega . 2 (see [8]) and the smallest ordinal greater than all ordinals of the form \omega . n + m (where m is an ordinal less than \omega . n) is denoted \omega ^2. The smallest ordinal greater than all ordinals of the form \omega ^n + m (where m is an ordinal less than \omega ^n) is denoted \omega^{\omega}.


Rendered by QuickLaTeX.com

Then \omega^{\omega} is followed by \omega^{\omega} + 1, \omega^{\omega} + 2, … , \omega^{2 \omega} , \omega^{2 \omega} + 1, …, \omega^{2 \omega} + \omega, … , \omega^{3 \omega}, …, \omega^{\omega^{\omega}}, etc., and we define \varepsilon_0 to be the smallest ordinal greater than all the sums of iterated powers of \omega and allow the process to continue indefinitely. In fact, all the ordinals considered thus far constitute only the beginning of the chain of ordinals because they form a countable set, that is, they can be matched up, one-for-one with the positive integers.

Ordinals and well ordering:
A significant difference between transfinite ordinals and nonnegative integers is that each integer greater than 0 has an immediate predecessor whereas ordinals such as \omega, \omega . 2 and \omega^{\omega} do not. However, like the set of integers, the extended set of ordinal numbers is “well ordered” in the sense that every nonempty set of ordinals has a least element. This property is the reason we can deduce the fact that there cannot be an infinitely long strictly decreasing sequence of ordinal numbers. For suppose that such an infinite sequence exists. Let us denote it by u_0, u_1, u_2, …, and let S be the set of all its terms. Given that S is nonempty, it has a least element \alpha, and so \alpha = u_k for some integer k. But since the sequence is strictly decreasing, u_{k+1} < u_k = \alpha and so \alpha is not the least element of S, which contradicts the supposition.
We now show how to use the ordinal numbers to prove the result about weak Goodstein sequences.

3. Proving That a Weak Goodstein Sequence Converges to Zero

To each weak Goodstein sequence {u_n}, we associate a strictly decreasing sequence of ordinals {\alpha_n} by replacing the base in every term of u_n by \omega. Because the initial base of a weak Goodstein sequence is 2 and because the base increases by 1 in each step, the decomposition of u_n has base (n+2). Thus for the sequence associated to 266, the initial terms of {\alpa_n} are shown in Table 2:


Rendered by QuickLaTeX.com

Table 2: The sequence of ordinals corresponding to a weak Goodstein sequence.

As constructed, each term of {\alpha_n} is greater than the corresponding term of {u_n}, but whereas {u_n} is increasing, {\alpha_n} is decreasing. The reason is that in the decomposition of u_n with base n + 2, either the unit term of u_n is nonzero or it is not. Passing from each term to the next is thus made in one of two ways:

  • If the unit term of u_n is nonzero, then because one subtracts 1 at each step, the unit term of u_{n+1} is one less than the unit term of u_n. (In Table 2, this happens in going from u_1 to u_2, from u_2 to u_3, from u_4 to u_5, and from u_5 to u_6.)
  • If the unit term of u_n is zero, when one rewrites the decomposition in the new base, one has to break down the term of the decomposition having the smallest exponent. (In Table 2, this happens in going from u_0 to u_1, from u_3 to u_4, and from u_9 to u_{10}. See Table 1 for the detailed computations.) (see [9])

Observe that in both cases the new term of {\alpha_n} is strictly less than the preceding one.

Now because the ordinals are well ordered, there does not exist an infinite strictly decreasing sequence of ordinals, and so there must exist an integer m for which \alpha_m = 0. Moreover, because u_n \leqslant \alpha_n for all n, u_m must also equal 0. In other words, the terms of {u_n} reach 0 in a finite number of steps, although the number of steps may be extremely large.
We invite the reader to write the terms of {u_n} and {\alpha_n} starting with u_0 = 5. For what value of n is \alpha_n = \omega ? What is the value of u_n then, and what are the following terms for each of the two sequences? (see [10]).
We are now ready to examine Goodstein sequences proper. They are defined slightly differently from weak Goodstein sequences and the nature of their increase is much more spectacular. Nonetheless, surprisingly, the strategy for proving that they eventually decrease to zero is similar to what we have just done.

4. Goodstein Sequences

Consider again the base-2 representation for 266: 2^8 + 2^3 + 2^1. Now write the exponents using only base 2: 3 = 2^1 + 1 and 8 = 2^3 = 2^{2^1 +1}. As a result, the entire expression for 266 can be written entirely without using any number larger than base 2. Let {m_n} be the Goodstein sequence that starts with m_0 = 266. To construct m_1, replace all occurrences of 2 by 3, subtract 1, and rewrite the result without using any number larger than base 3. Then continue process iteratively to obtain successive terms of {m_n}, as shown in Table 3. (See [11]).

m_0 = 2^{2^{2+1}} + 2^{2+1} + 2^1
m_1 = 3^{3^{3+1}} + 3^{3+1} +3^1 - 1 = 3^{3^{3+1}} + 3^{3+1} + 2\\ = 443 426 488 243 037 769 948 249 630 619 149 892 886 \approx 10^{38}
m_2 = 4^{4^{4+1}} + +4^{4+1} +1 \approx 10^{616}
m_3 = 5^{5^{5+1}} + 5^{5+1} \approx 10^{10921}
m_4 = 6^{6^{6+1}} + 6^{6+1} -1 = 6^{6^{6+1}} + 5.6^6 + 5.6^5 + 5. 6^4 +5.6^3 + 5.6^2 +5.6^1 + 5\\ \approx10^{217832}
m_5 = 7^{7^{7+1}} + 5.7^7 + 5.7^5 + 5. 7^4 +5.7^3 + 5.7^2 +5.7^1 + 4\\ \approx 10^{4 871 822}

Table 3.

As you see, the growth in the size of the terms is spectacular, and yet this sequence, like all Goodstein sequences, eventually starts decreasing and finally converges to 0. The proof is very similar to the proof for a weak Goodstein sequence. As in that case, a sequence {\beta_n} is associated to the sequence {m_n} by replacing each occurrence of each base by \omega. The first few terms of {\beta_n} are as follows:

\beta_0 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1} + \omega^1
\beta_1 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1} + 2
\beta_2 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1} + 1
\beta_3 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1}
\beta_4 = \omega^{\omega^{\omega +1}} + 5. \omega^{\omega} + 5 . \omega^{5} + 5 . \omega^{4} + 5 . \omega^{3} + 5 . \omega^{2} + 5 . \omega^{1} + 5
\beta_5 = \omega^{\omega^{\omega +1}} + 5. \omega^{\omega} + 5 . \omega^{5} + 5 . \omega^{4} + 5 . \omega^{3} + 5 . \omega^{2} + 5 . \omega^{1} + 4

The sequence {\beta_n} of ordinal numbers is strictly decreasing, which implies that it has a least element, and, because terms continue to be computed as long as they are nonzero, the least element of the sequence is 0. Similar reasoning can be used for all the Goodstein sequences.

Ordinary integer arithmetic is often called Peano arithmetic because the 19th century Italian mathematician Giuseppe Peano first formulated its axioms. What is most notable about the elegant proof given above is that it goes outside Peano arithmetic to prove a theorem that can be stated entirely within Peano arithmetic. In other words, it uses a general theory of sets that includes transfinite ordinals to prove a theorem about nonnegative integers, namely that every Goodstein sequence converges to 0. It is natural to ask whether the convergence of Goodstein sequences can be proved without using transfinite ordinals. The answer is no! This was proved in 1982, approximately 40 years after the sequences were introduced, by Laurie Kirby and Jeff Paris (see [12]). They showed that if convergence could be proved using only the well-ordering principle for the integers (i.e., within Peano arithmetic), then the theorem about Goodstein sequences could be reduced to a theorem of Gentzen (1936), from which the consistency of Peano arithmetic could be deduced. But we know from the Gödel incompleteness theorem (1931) that the consistency of Peano arithmetic cannot be proved using only Peano arithmetic. It is therefore useless for mathematicians to waste their energy in trying to find such a proof!

On the other hand, which may seem surprising, the fact that the weak Goodstein sequences converge to 0 can be proved within Peano arithmetic. The reason is essentially that the terms of the associated sequence of ordinals are all less than \omega^{\omega}. A proof was given by E. A. Cichon who introduced the weak Goodstein sequences in 1983 (see [13]). To each term u_n of a weak Goodstein sequence, one can correspond the m-tuplet of the coefficients of the decomposition in base n + 2 and show that the m-tuplets satisfy a strictly decreasing lexicographic well ordering.

5. Goodstein Sequences and the Hydra Game

In their article, Kirby and Paris mention another process, the Hydra Game, with many similarities to the Goodstein sequences. The game (see [14]) gets its name from a description in Greek mythology of combat between Hercules and a many-headed beast: the Learnaean Hydra. Each time one of the hydra’s heads was cut off, two new ones grew in its place. In the game, the hydra is modeled by a tree, and the heads of the hydra correspond to the terminal vertices, or leaves, of the tree. If Hercules cuts a head that is not directly connected to the root of the tree, the edge leading to the head is eliminated, but the hydra grows new heads from the branch node located two levels below the head that was cut off. This can be realized in various ways. For instance, in the example given by Kirby and Paris and used again by Hodgson (see [4]), if a head is cut off in step n of the game, the hydra generates n copies of the part of the tree above the branch node from which the head was removed. In the diagram below, the part that is cut off is shown with a dotted line, the part that is regenerated is shown in red, and the part that is newly grown is shown in blue.

It is possible to prove that whatever the initial configuration of the hydra’s heads and whatever the strategy employed by Hercules, Hercules will always succeed in cutting all of them off, although it may take him an extraordinarily long time to finish. As for the convergence of the Goodstein sequences, the proof is based on the relationship between successive trees and a strictly decreasing sequence of ordinals. As you might guess from the diagrams shown above, the tree becomes wider and wider, but its height eventually decreases. Ultimately Hercules is able to eliminate all the heads that lie more than one level above the root, and at that point (as illustrated in step 3) he can cut off the remaining heads one by one without generating any new ones.

6. Lessons from These Examples

The examples in this vignette are interesting for several reasons. First they show that mathematical logic is relevant to more than metamathematics, that theorems such as Gödel’s incompleteness theorem and objects such as the transfinite ordinals are needed for the study of ordinary mathematical objects such as sequences of integers and mathematical trees. By showing that a property of integers can be proved within the general theory of sets but not within Peano arithmetic, the examples also draw our attention to the theoretical and linguistic framework within which proofs occur. In this case they show that Peano arithmetic is weaker than the general theory of sets.

Another lesson from these examples is the value of approaching a more difficult problem (the convergence of general Goodstein sequences) by modifying it into a more accessible one (the convergence of weak Goodstein sequences). In addition, the examples show how a generic example – a sequence whose initial value is 266 – can illustrate all the important features of the general case. The examples are also instructive because they illustrate the limits of our intuition. Sequences that appear to tend to infinity do not in fact do so; they ultimately start decreasing and converge to 0 in a finite number of steps. Finally, the examples enable us to see both the power and the limits of technology because technology gives us a concrete sense for the rapid increase in the terms of the sequence, but it is of limited use when faced with the numerical explosion generated by the sequence definition.

References

[1] Elert, Glenn (1995-2007). The Chaos HypertextbookTM, Bodnar, M. & Ramsden P. Discrete Logistic Equation, Wolfram Demonstrations Project. Perrin, D. (2008). La suite logistique et le chaos.

[2] Lagarias, J. C. (2001) The Syracuse Problem. In Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer.

[3] Goodstein, R. L. (1944). On the Restricted Ordinal Theorem, Journal of Symbolic Logic, 9, 33-41.

[4] The well ordering principle for the integers states that if every element in a set S of integers is greater than some integer m, then S has a least element.

[5] Hodgson B. (2004). Herculean of Sisyphean tasks? EMS Newsletter, March 2004, pp. 11-16.

[6] Given an integer b > 0 with b \neq 1, every positive integer n has a unique decomposition in base b: n = d_m . {b^m} + d_{m-1} . b^{m-1} + ... + d_1 . b^1 + d_0, where all the d_i are integers between 0 and b - 1 and d_m \neq 0. Note that b^m < n < b^{m+1}. This is a generalization of the way we decompose numbers using base ten.

[7] If u_0 = 3 (= 2^1+ 1), then u_1= 3^1 + 1 - 1 = 3, u_2 = 4^1 - 1 = 3, u_3 = 3 - 1 = 2, u_4 = 2 - 1 = 1, and u^5 = 1 - 1 = 0. Starting with u_3, each successive term is one less than the previous term because in each case the base is larger than the previous term.

[8] We extend the sum and product operations from the integers to the transfinite ordinal numbers, noting, however, that commutativity of addition and multiplication are not preserved.

[9] In general, when the unit term of u_n is zero, then the smallest term of u_n has the form a . (b - 1)^k, where k is a positive integer and a < b - 1. Thus, because the base is increased by 1 and because 1 is subtracted from the result, the decomposition for u_{n+1} ends in a.b^k - 1 = (a - 1) . b^k + b^k - 1 = (a - 1) . b^k + (b - 1) . b^{k-2} + (b - 1) . b^{k-3} + ... + (b - 1) . b^1 + (b - 1).
So the coefficient of the smallest power of the base is reduced by 1 and the unit term becomes one less than the new base.

[10] The responses are as follows: \alpha_n = \omega when n = 29, and thus u_{29} = 31^1. To obtain u_{30}, replace the base 31 by the base 32 and subtract 1. Hence u_{30} = 32^1 - 1 = 31, and so \alpha_{30} = 31. Given that the base of u_{30} is 32 and that 31 < 32, starting from the subscript 30 the sequences {u_n} and {\alpha_n} have exactly the same terms. They form a decreasing arithmetic sequence with constant difference -1, from which it follows that u_{61} = \alpha_{61} = 0.

[11] The terms of {mn} shown in Table 3 were computed using http://www.wolframalpha.com.

[12] Kirby, L. and Paris, J. (1982). Accessible Independence Results for Peano Arithmetic, Bulletin of the London Mathematical Society, 14, 285-293.

[13] Cichon, E. A. (1983). A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods, Proc. Amer. Math. Soc., 87, 704-706.

[14] Bauer, A. Java applet for the Hydra Game. (If the applet fails to work in one browser, try it in another.)

This post is also available in: French, German, Portuguese (Brazil)

Free PDF    Send article as PDF   
This entry was posted in Mathematics Within the Last 100 Years. Bookmark the permalink.

  1. Volker Schroeter says:

    Excellent maths challenge; certainly there are some extension students (secondary) who will take an interest in this.

    However, may I suggest that the notation of the multiplication operator be changed to either comply with European standards or with ours. As it’s printed here, the multiplication can be and will be mistaken for a decimal point, with the consequence that the students will give up.

  2. I have two questions here
    1) I am not convinced that the least element αm of the sequence of ordinals that correspond to the (weak) Goodstein sequence should be zero. From the well ordering of the ordinals indeed there is a least element for the sequence αm , and for all k>m αk=αm. What is the argument that it should be 0, not another fixed ordinal? E.g. ω, so that in the next step the increase of the base by one, and the minus one cancel out given always the same natural number , corresponding to ω?
    The second question is
    2) The sequence αm seems to me that it can very well be constructed without the theory of ordinlas. E. g. we may use a variable x instead of ω, and polynomilas over x, instead of expressions of ω. Then well-order these polynomials (x^n<x^(n+1), nxn for every n , etc), in similar way as the ordinals (or in a appropriate symbolic lexicographic order, as tuples of naturals), and apply the same argument.
    Why then such a proof with well ordered polynomials would not be a proof within the Peano arithmetic?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>