Goodstein's Theorem and Peano Arithmetic

This is the second part of a post series on Goodstein's theorem. For the first part, see here.

We saw last post that Goodstein sequences are certain sequences of positive integers defined using base representations. Despite their simple definition, they grow extraordinarily large. However, Goodstein's Theorem states that no matter how large the starting value is, the sequence will eventually terminate at 0 after some finite number of steps. Before discussing the proof to this remarkable theorem, we move in a completely different direction and define the axioms of Peano arithmetic.

Increasing standards of rigor were a hallmark of late 19th and early 20th century mathematics. With this movement came a need to precisely define the basic building blocks with which a given branch of mathematics worked. This was even true for simple arithmetic! By 1890, the mathematician Giuseppe Peano had published a formulation of the axioms (fundamental assumptions) of arithmetic, which are used nearly unchanged to this day. Written in simple english, the axioms state the following about the collection N of natural numbers (nonnegative integers), a function S known as the successor function, a function + known as addition, and a function * known as multiplication:

1) There exists a natural number called 0 in N
2) For every natural number n in N there is a successor S(n) in N (commonly written
n + 1)
3) There is no natural number whose successor is 0
4) For any two natural numbers m and n in N, if S(m) = S(n), then m = n
5) For any natural number n, n + 0 = n
6) For any natural numbers n and m, n + S(m) = S(m + n)
7) For any natural number n, n*0 = 0
8) For any natural numbers n and m, n*S(m) = n*m + n
9) For any "well-behaved" property P, if P(0) holds and for each n in N, P(n) implies
P(n + 1), then P is true for every natural number in N

The first two axioms simply say that you can start from 0 and count upwards forever through the natural numbers. The third says that there is no natural number below 0 (this is of course false for larger sets of numbers such as integers, but Peano's axioms are only for properties of the natural numbers). The fourth shows that the successor of a natural number is unique. The fifth through eighth axioms state the common properties of addition and multiplication. The ninth axiom is actually a large collection of axioms (an axiom schema) in disguise, called the "axiom schema of induction."

The idea of induction may be familiar to readers who recall their high school mathematics: one often wishes to prove that a given property holds for every natural number. To do so, it is sufficient to show that it is true in the "base case," that is, true for 0, and that the statement being true for a number means that it is also true for the next. Then since the property is true for 0, it is true for 1. Since it is true for 1, it is true for 2, and so on. The figure above illustrates the idea of induction, where each "statement" is that the given property is true for some number. The final axiom simply codifies the fact this type of reasoning works; we get that the property is true for all natural numbers. In this context, a "well-behaved" property is one expressible in the semantics of the variety of logic being used (first-order logic in this case).

Remarkably, the above assumptions are all that is needed to perform arithmetic. In principle, though formalizing complicated proofs would be quite lengthy, true statements such as "17 is prime" and "every number is the sum of four squares" become theorems in Peano arithmetic. All of these proofs would take the form of a chain of statements beginning from axioms and concluding with the desired result, such as "17 is prime," rendered appropriately in the formal mathematical language. The progression from each statement to the next would also follow a collection of well-defined deductive rules. In principle, almost all theorems concerning natural numbers could be proven this way, beginning from just a small collection of axioms! However, Peano arithmetic still runs afoul of a result that vexes many axiom systems of first-order logic: Gödel's Incompleteness Theorem.

Gödel's (First) Incompleteness Theorem, originally proven by the mathematician Kurt Gödel in 1931, dashed the hopes of those who imagined that formal logical systems would provide a complete description of mathematics. It states, informally, that for any first-order logical system powerful enough to encode arithmetic (Peano arithmetic is of course such a system), there exist statements in the language of the system that are neither provable nor refutable from the axioms. Further, there are explicit sentences in the logical system that are true (under the intended interpretation of the theory, more on this later) but unprovable. The above diagram illustrates the situation: there will always be things we know to be true or false that are beyond the reach of the axioms to formally prove or refute.

Some questions may spring to mind at this unintuitive result. What is the distinction between "true" and "provable"? How do we define "true" in mathematics if not as the end result of a proof? What do these unprovable statements look like, and what do they say?

The answer to the first of these depends on there being something "we mean by" the term "natural numbers". In other words, there is an intended interpretation of what natural numbers should be that the logical system fails to completely capture. Consequently, there are statements that we know to be true using methods outside the formal system but are unprovable within it. Bringing in additional assumptions does not simply resolve the incompleteness theorem, however. For each outside axiom added, the theorem guarantees the existence of a new unprovable statement. And if the system ever does become complete by the addition of more axioms, it also becomes inconsistent, that is, able to prove a contradiction (and loses all validity as a mathematical system).

As for the final question, the first known unprovable statements were those constructed in the proof of Gödel's theorem; these are known as Gödel sentences. They are highly contrived for the proof, however, and do not have any intuitive meaning. In the years following the original proof, the concern remained whether, for example, any statement that "naturally" arises in the study of natural numbers would be unprovable and unrefutable from the axioms of Peano arithmetic. Amazingly, such statements exist! In fact, a great example is Goodstein's Theorem. No proof exists, beginning from the Peano axioms, that has it as a conclusion. To read more about how it can be proven and why it is not a theorem of Peano arithmetic, see the next post.

Sources: https://www.cs.toronto.edu/~sacook/csc438h/notes/page96.pdf, https://plato.stanford.edu/entries/goedel-incompleteness/

Goodstein Sequences and Hereditary Base Notation

In mathematics, Goodstein sequences are certain sequences of natural numbers. Though they are fairly easy to define, their properties have important consequences in logic. Before investigating these, however, we give the definition. It depends on the concept of expressing numbers in different bases (well-known examples in addition to normal base-10 representations include binary, base 2, and hexadecimal, base 16). Recall that when writing a number, such as 4291, what we mean is 4 thousands plus 2 hundreds plus 9 tens, plus 1 one, alternatively expressed as

4291 = 4*10³ + 2*10² + 9*10¹ + 1.

This decomposition uses 10 as a base. Note that the numbers multiplying the powers of 10 always vary between 0 and 9. Base 2, for example, could be used just as easily, with only digits 0 and 1 as coefficients. Expressing 4291 as powers of 2 yields

4291 = 1*4096 + 0*2048 + 0*1024 + 0*512 + 0*256 + 1*128 + 1*64 + 0*32 + 0*16 + 0*8 + 0*4 + 1*2 + 1*1
= 1*2¹² + 0*2¹¹ + 0*2¹⁰ + 0*2⁹ + 0*2⁸ + 1*2⁷ + 1*2⁶ + 0*2⁵ + 0*2⁴ + 0*2³ + 0*2² + 1*2¹ + 1.

Therefore, 4291 is typically expressed in binary as the sequence of coefficients 1000011000011. However, for our purposes, it is more convenient to explicitly express the powers of the base involved, although it will simplify matters to drop those terms with coefficient 0 since they have no contribution to the sum. The equation above then becomes

4291 = 1*2¹² + 1*2⁷ + 1*2⁶ + 1*2¹ + 1.

The system described above is known as ordinary base notation, but the definition of Goodstein sequences requires a slightly modified version, hereditary base notation. This involves taking the exponents themselves and subjecting them to the same base decomposition as the original number. Since 12 = 1*2³ + 1*2², 7 = 1*2² + 1*2¹ + 1, and 6 = 1*2² + 1*2¹, the integer 4291 now becomes

4291 = 1*2^{1*23 + 1*22} + 1*2^{1*22 + 1*21 + 1} + 1*2^{1*22 + 1*21} + 1*2¹ + 1.

This expression is quite complicated, but the process is not quite finished yet! The exponents 2 and 3 within the exponents are not yet in base-2: 3 = 1*2¹ + 1 and 2 = 1*2¹. Making the necessary replacements finally gives 4291 in hereditary base-2 notation:

4291 = 1*2^{1*21*21 + 1 + 1*21*21} + 1*2^{1*21*21 + 1*21 + 1} + 1*2^{1*21*21 + 1*21} + 1*2¹ + 1.

In the general case, there may be many iterations of this process, which motivates the name "hereditary"; a base-2 decomposition is applied to the original integer and then the exponents that result, and then their exponents, and so on. The end result has only 2's as bases of exponents and only 1's as coefficients. The interested reader can verify that this type of process may be repeated for any positive integer in any base (using as coefficients positive integers less than the base), and that for a fixed number and base, the representation thus obtained is unique. The stage is now set for the definition of Goodstein sequence.

A Goodstein sequence is simply a sequence of nonnegative numbers. We may choose any number 1, 2, 3,... to begin the sequence. Next, whatever this number is, we express it in hereditary base-2 notation, just as we did with the example 4291 above. To generate the next member of the sequence, simply change every 2 in the hereditary base-2 representation to a 3, and then subtract 1 from the resulting number. This is the second member of the sequence. After that, express this second number in hereditary base-3 notation, change the 3's to 4's, and subtract one to get the third, and so on. We denote the nth member of the Goldstein sequence beginning with m by G_m(n). The first few sequences G_m die out quickly: if the seed is 1 (whose hereditary base-2 representation is just 1), there are no 2's to change to 3's so we simply subtract 1 to find G₁(2) = 0. If a sequence reaches 0, we end it there, so that the sequence

G₁ = {1,0}.

G₂ is scarcely more interesting: G₂(1) = 2 = 1*2¹ so changing the single 2 to a 3 and subtracting 1 yields G₂(2) = 1*3¹ - 1 = 2. Recall that coefficients 0-2 are allowed in hereditary base-3 notation so 2 in this notation is simply 2. There are no 3's to change to 4's, so we subtract 1 to get G₂(3) = 1. There are no 4's to change to 5's, so G₂(4) = 0 and the sequence is finished:

G₂ = {2,2,1,0}.

Beginning with 3 leads to a sequence nearly identical: the reader may try calculating the sequence. The end result is G₃ = {3,3,3,2,1,0}. However, at m = 4, new behavior emerges. 4 = 1*2^1*21, so both 2's must be replaced by 3's to get: G₄(2) = 1*3^1*31 - 1 = 27-1 = 26. In hereditary base-3, 26 = 2*3² + 2*3¹ + 2 so G₄(3) = 2*4² + 2*4¹ + 2 - 1 = 41. For the next step, we get G₄(4) = 2*5² + 2*5¹ + 1 - 1 = 60. Note that the units digit is reduced by one in each step even as the sequence increases. When it hits zero, as in this step, the coefficient of the penultimate coefficient is decreased by one: G₄(5) = 2*6² + 2*6¹ - 1 = 83 = 2*6² + 1*6¹ + 5. However, the new units digit becomes one less than the base, namely 5, so it takes more steps for this to reach zero than previously. After another five steps, we arrive at G₄(10) = 2*11² + 1*11 = 253. When changing to base 12 at the next step, we obtain G₄(11) = 2*12² + 11 = 299. The units digit again decreases for the next 11 steps, until G₄(22) = 2*23² = 1058.

The next step starts to indicate why Goodstein sequences can increase for so long: G₄(23) = 2*24² - 1 = 1151 = 1*24² + 23*24¹ + 23. Since the base is 24, we get two new coefficients of 23. Each time the units digit reaches zero, the value at which it has to start the next time doubles. The square term in the base representation does not vanish until the base reaches 402653184. And at this point the sequence has barely begun. The largest value it reaches is 3*2^402653210 - 1 at base 3*2^402653209, after which the sequence remains stable for a while before finally declining to zero. This maximum value is so astronomically large that if the digits of the number were printed at a typical font size, front and back, it would fill a stack of paper over 10 feet tall! And this is just G₄. Goodstein sequences with higher initial values increase much, much faster.

If we start with 18, for instance, since 18 = 1*2^1*21*21 + 1*2¹, replacing all the 2's with 3's gives G₁₈(2) = 1*3^1*31*31 + 1*3¹ - 1 = 7625597484989. The third term is G₁₈(3) = 1*4^1*41*41 + 2 - 1, which is about 10¹⁵⁴. The values this sequence reaches quickly become difficult to even write down. However, Reuben Goodstein himself, after whom the sequences are named, proved in 1944 a statement that became known as Goodstein's Theorem. His remarkable result showed that no matter how incalculably large the sequences become, they always terminate at 0. That is, after some finite, though possibly immense, series of steps, each sequence stops increasing eventually and decreases to 0.

The theorem's proof has significance beyond demonstrating this surprising fact about Goodstein sequences. For more, see the next post.

Source: https://www.jstor.org/stable/2268019, http://mathworld.wolfram.com/GoodsteinSequence.html