Goodstein series

Goodstein sequences are special sequences of natural numbers . They play a role in a mathematical theorem , Goodstein's Theorem . The special thing about this proposition is that it can be formulated with the means of Peano arithmetic , but cannot be proven exclusively with them. This is because Peano arithmetic does not uniquely model the natural numbers; that is, it also allows models other than natural numbers in which Goodstein's theorem does not hold. This theorem is an example of the fact that not every unprovable statement has to be as complicated and unimaginable as the unprovable statements in Godel's incompleteness theorem .

Definition of the Goodstein episodes

Any natural number can be expanded to a given base as follows : ${\displaystyle n}$ ${\displaystyle b}$

${\displaystyle n=a_{m}b^{m}+\cdots +a_{2}b^{2}+a_{1}b^{1}+a_{0}b^{0}=\sum _{k=0}^{m}a_{k}b^{k}}$

where are the coefficients that lie between and (see place value system ). ${\displaystyle a_{k}}$ ${\displaystyle 0}$ ${\displaystyle b-1}$

For example, the representation of a natural number in the decimal system is : ${\displaystyle 35}$

${\displaystyle 35=3\cdot 10^{1}+5\cdot 10^{0}=30+5}$

The representation for base 2 is

${\displaystyle 35=1\cdot 2^{5}+1\cdot 2^{1}+1\cdot 2^{0}=32+2+1}$

This representation for the base is now applied to the exponents, and then to the exponents of the exponents, until there is no longer a number above the base. This representation is called the iterated representation to the base ( English hereditary base representation ). This is the representation for the number : ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle 35}$

${\displaystyle 35=2^{(2^{2}+1)}+2^{1}+2^{0}}$

This iterated representation of the Goodsteinsche operation is bloat ( English bump the base defined). This replaces wherever the base is in the iterated representation of a number by . This figure, which represents the number iterated to the base and then expanded, is referred to here as ${\displaystyle b}$ ${\displaystyle b+1}$ ${\displaystyle n}$ ${\displaystyle b}$

${\displaystyle a_{b}\colon \mathbb {N} \to \mathbb {N} }$

written; There are many different ways of writing this in literature.

${\displaystyle a_{2}(35)=a_{2}\left(2^{2^{2}+1}+2^{1}+2^{0}\right)}$

${\displaystyle =3^{3^{3}+1}+3^{1}+3^{0}=22.876.792.454.965}$

If now is a natural number, then the Goodstein sequence with starting value ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle (g_{b}(n))_{b\in \mathbb {N} }\;}$

defined using this figure : ${\displaystyle a_{b}}$

${\displaystyle g_{1}(n):=n\;}$

${\displaystyle g_{b}(n):={\begin{cases}a_{b}(g_{b-1}(n))-1&b>1,\ g_{b-1}(n)>0\\0&b>1,\ g_{b-1}(n)=0\end{cases}}}$

The second term in the sequence is calculated by iterating to the base , then expanding it and subtracting it from the expanded number . ${\displaystyle n}$ ${\displaystyle b=2}$ ${\displaystyle 1}$

Examples

The Goodstein episodes for are still quite short: ${\displaystyle n=1,2,3}$

${\displaystyle n=1}$:

${\displaystyle g_{1}(1)=1}$

${\displaystyle g_{2}(1)=0}$

${\displaystyle n=2}$:

${\displaystyle g_{1}(2)=2}$

${\displaystyle g_{2}(2)=a_{2}(2^{1})-1=3^{1}-1=2}$

${\displaystyle g_{3}(2)=a_{3}(2)-1=2-1=1}$

${\displaystyle g_{4}(2)=a_{4}(1)-1=1-1=0}$

${\displaystyle n=3}$:

${\displaystyle g_{1}(3)=3}$

${\displaystyle g_{2}(3)=a_{2}(2^{1}+1)-1=3^{1}+1-1=3}$

${\displaystyle g_{3}(3)=a_{3}(3^{1})-1=4^{1}-1=3}$

${\displaystyle g_{4}(3)=a_{4}(3\cdot 4^{0})-1=3\cdot 5^{0}-1=2}$

${\displaystyle g_{5}(3)=a_{5}(2\cdot 5^{0})-1=2\cdot 6^{0}-1=1}$

${\displaystyle g_{6}(3)=a_{6}(6^{0})-1=7^{0}-1=0}$

Note that increasing the base has no effect from here on , because the number is then smaller than the base; she is bgzl. so single-digit on this basis . ${\displaystyle b=4}$

${\displaystyle n=4}$:

${\displaystyle g_{1}(4)=4}$

${\displaystyle g_{2}(4)=a_{2}(2^{2})-1=3^{3}-1=26}$

${\displaystyle g_{3}(4)=a_{3}(2\cdot 3^{2}+2\cdot 3^{1}+2)-1=2\cdot 4^{2}+2\cdot 4^{1}+2-1=41}$

${\displaystyle g_{4}(4),\ldots ,g_{10}(4)=60,83,109,139,173,211,253\;}$

${\displaystyle g_{11}(4)=a_{11}(2\cdot 11^{2}+11^{1})-1=2\cdot 12^{2}+12^{1}-1=299}$

${\displaystyle g_{12}(4)=a_{12}(2\cdot 12^{2}+11)-1=2\cdot 13^{2}+11-1=348}$

${\displaystyle \dots }$

${\displaystyle g_{100}(4)=101^{2}+21\cdot 101+90=12.412}$

${\displaystyle \dots }$

${\displaystyle g_{1000}(4)=1001^{2}+18\cdot 1001+534=1.020.533}$

${\displaystyle \dots }$

This sequence rises for a long time, up to the base , then remains constant twice as long, and then falls until the value is reached at the base . The number of steps required is itself a number with more than 121 million decimal places. ${\displaystyle 3\cdot 2^{402.653.209}}$ ${\displaystyle 3\cdot 2^{402.653.211}-1}$ ${\displaystyle 0}$

Greater values ​​of give an idea of ​​how quickly Goodstein sequences can grow . ${\displaystyle n}$

${\displaystyle n=19}$:

${\displaystyle g_{1}(19)=19}$

${\displaystyle g_{2}(19)=a_{2}(2^{2^{2}}+2+1)-1=3^{3^{3}}+3=7.625.597.484.990}$

${\displaystyle g_{3}(19)=4^{4^{4}}+3\approx 1{,}3\cdot 10^{154}}$

${\displaystyle g_{4}(19)=5^{5^{5}}+2\approx 1{,}8\cdot 10^{2184}}$

${\displaystyle g_{5}(19)=6^{6^{6}}+1\approx 2{,}6\cdot 10^{36.305}}$

${\displaystyle g_{6}(19)=7^{7^{7}}\approx 3{,}8\cdot 10^{695.974}}$

${\displaystyle g_{7}(19)=8^{8^{8}}-1=7\cdot 8^{(7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7)}+}$

${\displaystyle \ldots +7\cdot 8^{8+1}+7\cdot 8^{8}+7\cdot 8^{7}+7\cdot 8^{6}+}$

${\displaystyle 7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7}$

${\displaystyle \approx 6\cdot 10^{15.151.335}}$

${\displaystyle \dots }$

Despite the rapid growth of these episodes, Goodstein's Theorem now claims that all of these episodes will eventually fall and end. ${\displaystyle 0}$

Goodstein's theorem

Goodstein's theorem is:

Every Goodstein sequence with any initial value from the natural numbers reaches the value in a finite number of steps . ${\displaystyle 0}$

This theorem was proven in 1944 by the English logician Reuben Louis Goodstein (1912–1985). This theorem is of particular interest in mathematics because it cannot be derived using the axioms of Peano arithmetic . Instead, the proof uses means of set theory , specifically the theory of ordinal numbers .

Proof of Goodstein's Theorem

The Kirby and Paris theorem states that Goodstein's theorem cannot be proved by means of Peano arithmetic. So you need a more powerful tool: the ordinals .

The theory of ordinal numbers extends the natural numbers by quantities that are larger than all natural numbers. The smallest infinite ordinal number is called Omega (small Greek letter ). Ordinal numbers can be added, multiplied and raised to the power, but some rules for calculating natural numbers do not apply generally to ordinal numbers (e.g. is ). Ordinal numbers are ordered according to size (they have a total order ), the three types of arithmetic mentioned are monotonic in all arguments, and the ordinal numbers are well ordered , i.e. that is, there is no strictly monotonically decreasing infinite sequence of ordinals. ${\displaystyle \omega }$ ${\displaystyle \omega +1\neq 1+\omega =\omega }$

We now assign an ordinal number to every natural number by iterating to the base and then replacing each with . The resulting ordinal numbers can be obtained from and natural numbers through a finite sequence of additions, multiplications and exponentiations ; is called the set of ordinal numbers that can be represented in this way ; this set is also the smallest ordinal number that cannot be represented in this way. So we have a map ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \varepsilon _{0}}$

${\displaystyle A_{b}(n)\colon \mathbb {N} \to \varepsilon _{0}}$

Here, too, there are different spellings in the literature.

It is Z. B.

${\displaystyle A_{2}(19)=A_{2}(2^{2^{2}}+2+1)=\omega ^{\omega ^{\omega }}+\omega +1}$

${\displaystyle A_{3}(g_{2}(19))=A_{3}(3^{3^{3}}+3)=\omega ^{\omega ^{\omega }}+\omega }$

Is less than , then a finite ordinal number, e.g. B. is ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle A_{b}(n)}$

${\displaystyle A_{5}(3)=3}$

The expansion has no effect on the ordinal number, because it does not matter whether you replace each with in the iterated representation or first each with and then each with , so it applies ${\displaystyle b}$ ${\displaystyle \omega }$ ${\displaystyle b}$ ${\displaystyle b+1}$ ${\displaystyle b+1}$ ${\displaystyle \omega }$

${\displaystyle A_{b+1}(a_{b}(n))=A_{b}(n)}$

However, subtracting has an effect on the ordinal number: it is reduced. ${\displaystyle 1}$

For example

${\displaystyle A_{5}(a_{4}(4^{4}+4))=A_{5}(5^{5}+5)=\omega ^{\omega }+\omega }$

${\displaystyle A_{5}(a_{4}(4^{4}+4)-1)=A_{5}(5^{5}+4)=\omega ^{\omega }+4}$

We now assign a sequence of ordinal numbers to the Goodstein sequence as follows: ${\displaystyle (g_{b}(n))_{b\in \mathbb {N} }}$ ${\displaystyle (G_{b}(n))_{b\in \mathbb {N} }}$

${\displaystyle G_{b}(n):=A_{b+1}(g_{b}(n))}$

This sequence is often (the parallel sequence English parallel sequence mentioned).

This sequence of ordinal numbers is strictly monotonically decreasing, so it has to end at after a finite number of steps , because the ordinal numbers are well ordered. Since and applies to everyone , the Goodstein episode ends after a finite number of steps. ${\displaystyle 0}$ ${\displaystyle G_{b}(n)\geq g_{b}(n)}$ ${\displaystyle n}$ ${\displaystyle b}$

Goodstein's theorem does not say anything about the number of steps after which a Goodstein sequence ends; so it is a pure existential proposition:

For every natural one exists such that is. ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle g_{b}(n)=0}$

Independence from Peano arithmetic

While the proof of Goodstein's theorem is still relatively easy if one is familiar with the theory of ordinals, the claim that this theorem cannot be proven with Peano arithmetic alone is much more difficult to prove. Laurie Kirby and Jeff Paris succeeded in doing this in 1982. The theorem named after them uses a non-standard model of Peano arithmetic.

literature

• RL Goodstein: On the restricted ordinal theorem. In: Journal of Symbolic Logic. Vol. 9, No. 2, 1944, ISSN  0022-4812 , pp. 33-41.
• Laurie Kirby , Jeff Paris : Accessible independence results for Peano arithmetic . In: Bulletin of the London Mathematical Society. Vol. 14, No. 4, 1982, ISSN  0024-6093 , pp. 285-293, doi : 10.1112 / blms / 14.4.285 .
• Patrick Dehornoy : Does arithmetic need infinity? In: The Infinite ( Spectrum of Science. Special. 1, 2001, ISSN  0943-7096 ). Spectrum-der-Wissenschaft-Verlags-Gesellschaft, Heidelberg 2001.

Web links