# Goodstein’s theorem – Wikipedia

*by*Phil Tadros

Theorem about pure numbers

In mathematical logic, **Goodstein’s theorem** is an announcement in regards to the natural numbers, proved by Reuben Goodstein in 1944, which states that each **Goodstein sequence** (as outlined beneath) finally terminates at 0. Laurence Kirby and Jeff Paris^{[1]} confirmed that it’s unprovable in Peano arithmetic (however it may be confirmed in stronger techniques, reminiscent of second-order arithmetic). This was the third instance of a real assertion about pure numbers that’s unprovable in Peano arithmetic, after the examples supplied by Gödel’s incompleteness theorem and Gerhard Gentzen‘s 1943 direct proof of the unprovability of ε_{0}-induction in Peano arithmetic. The Paris–Harrington theorem gave one other instance.

Kirby and Paris launched a graph-theoretic hydra game with conduct just like that of Goodstein sequences: the “Hydra” (named for the mythological multi-headed Hydra of Lerna) is a rooted tree, and a transfer consists of reducing off one in all its “heads” (a department of the tree), to which the hydra responds by rising a finite variety of new heads in line with sure guidelines. Kirby and Paris proved that the Hydra will finally be killed, whatever the technique that Hercules makes use of to cut off its heads, although this will take a really very long time. Similar to for Goodstein sequences, Kirby and Paris confirmed that it can’t be confirmed in Peano arithmetic alone.^{[1]}

## Hereditary base-*n* notation[edit]

Goodstein sequences are outlined when it comes to an idea referred to as “hereditary base-*n* notation”. This notation is similar to traditional base-*n* positional notation, however the traditional notation doesn’t suffice for the needs of Goodstein’s theorem.

To attain the unusual base-*n* notation, the place *n* is a pure quantity higher than 1, an arbitrary pure quantity *m* is written as a sum of multiples of powers of *n*:

- ${displaystyle m=a_{okay}n^{okay}+a_{k-1}n^{k-1}+cdots +a_{0},}$

the place every coefficient *a _{i}* satisfies 0 ≤

*a*<

_{i}*n*, and

*a*≠ 0. For instance, to realize the bottom 2 notation, one writes

_{okay}- ${displaystyle 35=32+2+1=2^{5}+2^{1}+2^{0}.}$

Thus the base-2 illustration of 35 is 100011, which implies 2^{5} + 2 + 1. Equally, 100 represented in base-3 is 10201:

- ${displaystyle 100=81+18+1=3^{4}+2cdot 3^{2}+3^{0}.}$

Word that the exponents themselves are usually not written in base-*n* notation. For instance, the expressions above embody 2^{5} and three^{4}, and 5 > 2, 4 > 3.

To transform a base-n notation (which is a step in reaching base-*n* illustration) to a hereditary base-*n* notation, first rewrite all the exponents as a sum of powers of *n* (with the limitation on the coefficients 0 ≤ *a _{i}* <

*n*). Then rewrite any exponent contained in the exponents in base-

*n*notation (with the identical limitation on the coefficients), and proceed on this means till each quantity showing within the expression (besides the bases themselves) is written in base-

*n*notation.

For instance, whereas 35 in unusual base-2 notation is 2^{5} + 2 + 1, it’s written in hereditary base-2 notation as

- ${displaystyle 35=2^{2^{2^{1}}+1}+2^{1}+1,}$

utilizing the truth that 5 = 2^{21} + 1. Equally, 100 in hereditary base-3 notation is

- ${displaystyle 100=3^{3^{1}+1}+2cdot 3^{2}+1.}$

## Goodstein sequences[edit]

The **Goodstein sequence** *G*(*m*) of a quantity *m* is a sequence of pure numbers. The primary factor within the sequence *G*(*m*) is *m* itself. To get the second, *G*(*m*)(2), write *m* in hereditary base-2 notation, change all of the 2s to 3s, after which subtract 1 from the end result. On the whole, the (*n* + 1)-st time period, *G*(*m*)(*n* + 1), of the Goodstein sequence of *m* is as follows:

- Take the hereditary base-
*n*+ 1 illustration of*G*(*m*)(*n*). - Exchange every incidence of the base-
*n*+ 1 with*n*+ 2. - Subtract one. (Word that the following time period relies upon each on the earlier time period and on the index
*n*.) - Proceed till the result’s zero, at which level the sequence terminates.

Early Goodstein sequences terminate shortly. For instance, *G*(3) terminates on the sixth step:

Later Goodstein sequences enhance for a really massive variety of steps. For instance, *G*(4) OEIS: A056193 begins as follows:

Parts of *G*(4) proceed to extend for some time, however at base ${displaystyle 3cdot 2^{402,653,209}}$,

they attain the utmost of ${displaystyle 3cdot 2^{402,653,210}-1}$, keep there for the following ${displaystyle 3cdot 2^{402,653,209}}$ steps, after which start their descent.

Nevertheless, even *G*(4) would not give a good suggestion of simply *how* shortly the weather of a Goodstein sequence can enhance.

*G*(19) will increase rather more quickly and begins as follows:

Despite this speedy progress, Goodstein’s theorem states that **each Goodstein sequence finally terminates at 0**, it doesn’t matter what the beginning worth is.

## Proof of Goodstein’s theorem[edit]

Goodstein’s theorem will be proved (utilizing methods outdoors Peano arithmetic, see beneath) as follows: Given a Goodstein sequence *G*(*m*), we assemble a parallel sequence *P*(*m*) of ordinal numbers in Cantor normal form which is strictly lowering and terminates. A typical misunderstanding of this proof is to imagine that *G*(*m*) goes to 0 *as a result of* it’s dominated by *P*(*m*). Truly, the truth that *P*(*m*) dominates *G*(*m*) performs no position in any respect. The essential level is: *G*(*m*)(*okay*) exists if and provided that *P*(*m*)(*okay*) exists (parallelism), and comparability between two members of *G*(*m*) is preserved when evaluating corresponding entries of *P*(*m*).^{[2]} Then if *P*(*m*) terminates, so does *G*(*m*). By infinite regress, *G*(*m*) should attain 0, which ensures termination.

We outline a operate ${displaystyle f=f(u,okay)}$ which computes the hereditary base *okay* illustration of *u* after which replaces every incidence of the bottom *okay* with the primary infinite ordinal number ω. For instance, ${displaystyle f(100,3)=f(3^{3^{1}+1}+2cdot 3^{2}+1,3)=omega ^{omega ^{1}+1}+omega ^{2}cdot 2+1=omega ^{omega +1}+omega ^{2}cdot 2+1}$.

Every time period *P*(*m*)(*n*) of the sequence *P*(*m*) is then outlined as *f*(*G*(*m*)(*n*),*n+1*). For instance, *G*(3)(1) = 3 = 2^{1} + 2^{0} and *P*(3)(1) = *f*(2^{1} + 2^{0},2) = ω^{1} + ω^{0} = ω + 1. Addition, multiplication and exponentiation of ordinal numbers are effectively outlined.

We declare that ${displaystyle f(G(m)(n),n+1)>f(G(m)(n+1),n+2)}$:

Let ${displaystyle G'(m)(n)}$ be *G*(*m*)(*n*) after making use of the primary,

*base-changing* operation in producing the following factor of the Goodstein sequence,

however earlier than the second *minus 1* operation on this technology.

Observe that ${displaystyle G(m)(n+1)=G'(m)(n)-1}$.

Then ${displaystyle f(G(m)(n),n+1)=f(G'(m)(n),n+2)}$. Now we apply the *minus 1* operation, and ${displaystyle f(G'(m)(n),n+2)>f(G(m)(n+1),n+2)}$, as ${displaystyle G'(m)(n)=G(m)(n+1)+1}$.

For instance, ${displaystyle G(4)(1)=2^{2}}$ and ${displaystyle G(4)(2)=2cdot 3^{2}+2cdot 3+2}$, so ${displaystyle f(2^{2},2)=omega ^{omega }}$ and ${displaystyle f(2cdot 3^{2}+2cdot 3+2,3)=omega ^{2}cdot 2+omega cdot 2+2}$, which is strictly smaller. Word that with a purpose to calculate *f(G(m)(n),n+1)*, we first want to write down *G*(*m*)(*n*) in hereditary base *n*+1 notation, as for example the expression ${displaystyle omega ^{omega }-1}$ will not be an ordinal.

Thus the sequence *P*(*m*) is strictly lowering. As the usual order < on ordinals is well-founded, an infinite strictly lowering sequence can’t exist, or equivalently, each strictly lowering sequence of ordinals terminates (and can’t be infinite). However *P*(*m*)(*n*) is calculated instantly from *G*(*m*)(*n*). Therefore the sequence *G*(*m*) should terminate as effectively, that means that it should attain 0.

Whereas this proof of Goodstein’s theorem is pretty straightforward, the *Kirby–Paris theorem*,^{[1]} which reveals that Goodstein’s theorem will not be a theorem of Peano arithmetic, is technical and significantly harder. It makes use of countable nonstandard models of Peano arithmetic.

## Prolonged Goodstein’s theorem[edit]

Suppose the definition of the Goodstein sequence is modified in order that as a substitute of

changing every incidence of the bottom *b* with *b* + 1

it replaces it with *b* + 2. Would the sequence nonetheless terminate?

Extra usually, let *b*_{1}, *b*_{2}, *b*_{3}, … be any sequences of integers.

Then let the (*n* + 1)-st

time period *G*(*m*)(*n* + 1) of the prolonged Goodstein sequence of *m* be as

follows: take the hereditary base *b _{n}* illustration of

*G*(

*m*)(

*n*) and change every incidence of the bottom

*b*

_{n}with

*b*

_{n+1}after which subtract one.

The declare is that this sequence nonetheless terminates.

The prolonged proof defines

*P*(

*m*)(

*n*) =

*f*(

*G*(

*m*)(

*n*),

*n*) as

follows: take the hereditary base

*b*illustration of

_{n}*G*(

*m*)(

*n*), and change every incidence of the bottom

*b*with the primary infinite ordinal number ω.

_{n}The

*base-changing*operation of the Goodstein sequence when going

from

*G*(

*m*)(

*n*) to

*G*(

*m*)(

*n*+ 1) nonetheless doesn’t change the worth of

*f*.

For instance, if

*b*= 4 and if

_{n}*b*

_{n+1}= 9,

then

${displaystyle f(3cdot 4^{4^{4}}+4,4)=3omega ^{omega ^{omega }}+omega =f(3cdot 9^{9^{9}}+9,9)}$, therefore the ordinal ${displaystyle f(3cdot 4^{4^{4}}+4,4)}$ is strictly higher than the ordinal ${displaystyle f{huge (}(3cdot 9^{9^{9}}+9)-1,9{huge )}.}$

## Sequence size as a operate of the beginning worth[edit]

The **Goodstein operate**, ${displaystyle {mathcal {G}}:mathbb {N} to mathbb {N} }$, is outlined such that ${displaystyle {mathcal {G}}(n)}$ is the size of the Goodstein sequence that begins with *n*. (It is a total function since each Goodstein sequence terminates.) The extraordinarily excessive progress price of ${displaystyle {mathcal {G}}}$ will be calibrated by relating it to numerous commonplace ordinal-indexed hierarchies of features, such because the features ${displaystyle H_{alpha }}$ within the Hardy hierarchy, and the features ${displaystyle f_{alpha }}$ within the fast-growing hierarchy of Löb and Wainer:

- Kirby and Paris (1982) proved that

- ${displaystyle {mathcal {G}}}$ has roughly the identical growth-rate as ${displaystyle H_{epsilon _{0}}}$ (which is identical as that of ${displaystyle f_{epsilon _{0}}}$); extra exactly, ${displaystyle {mathcal {G}}}$ dominates ${displaystyle H_{alpha }}$ for each ${displaystyle alpha <epsilon _{0}}$, and ${displaystyle H_{epsilon _{0}}}$ dominates ${displaystyle {mathcal {G}},!.}$
- (For any two features ${displaystyle f,g:mathbb {N} to mathbb {N} }$, ${displaystyle f}$ is claimed to
**dominate**${displaystyle g}$ if ${displaystyle f(n)>g(n)}$ for all sufficiently massive ${displaystyle n}$.)

- Cichon (1983) confirmed that

- ${displaystyle {mathcal {G}}(n)=H_{R_{2}^{omega }(n+1)}(1)-1,}$
- the place ${displaystyle R_{2}^{omega }(n)}$ is the results of placing
*n*in hereditary base-2 notation after which changing all 2s with ω (as was accomplished within the proof of Goodstein’s theorem).

- Caicedo (2007) confirmed that if ${displaystyle n=2^{m_{1}}+2^{m_{2}}+cdots +2^{m_{okay}}}$ with ${displaystyle m_{1}>m_{2}>cdots >m_{okay},}$ then

- ${displaystyle {mathcal {G}}(n)=f_{R_{2}^{omega }(m_{1})}(f_{R_{2}^{omega }(m_{2})}(cdots (f_{R_{2}^{omega }(m_{okay})}(3))cdots ))-2}$.

Some examples:

(For Ackermann function and Graham’s number bounds see fast-growing hierarchy#Functions in fast-growing hierarchies.)

## Software to computable features[edit]

Goodstein’s theorem can be utilized to assemble a complete computable function that Peano arithmetic can’t show to be whole. The Goodstein sequence of a quantity will be successfully enumerated by a Turing machine; thus the operate which maps *n* to the variety of steps required for the Goodstein sequence of *n* to terminate is computable by a selected Turing machine. This machine merely enumerates the Goodstein sequence of *n* and, when the sequence reaches *0*, returns the size of the sequence. As a result of each Goodstein sequence finally terminates, this operate is whole. However as a result of Peano arithmetic doesn’t show that each Goodstein sequence terminates, Peano arithmetic doesn’t show that this Turing machine computes a complete operate.

## See additionally[edit]

## References[edit]

## Bibliography[edit]

- Goodstein, R. (1944), “On the restricted ordinal theorem”,
*Journal of Symbolic Logic*,**9**(2): 33–41, doi:10.2307/2268019, JSTOR 2268019, S2CID 235597. - Cichon, E. (1983), “A Quick Proof of Two Not too long ago Found Independence Outcomes Utilizing Recursive Theoretic Strategies”,
*Proceedings of the American Mathematical Society*,**87**(4): 704–706, doi:10.2307/2043364, JSTOR 2043364. - Caicedo, A. (2007), “Goodstein’s function” (PDF),
*Revista Colombiana de Matemáticas*,**41**(2): 381–391.

## Exterior hyperlinks[edit]