Goodstein Theorem

Goodstein 's theorem is a theorem of mathematical logic about natural numbers , proved by Ruben Goodstein ^[1] . Claims that all Goodstein sequences end in zero. As L. Kirby and Jeff Paris ^[2] ^[3] showed, Goodstein's theorem is equivalent to the statement of the consistency of Peano arithmetic $(PA)$ ${\ displaystyle (PA)}$ $(PA)$ , and therefore, by virtue of Gödel's second theorem and consistency $P A$ ${\ displaystyle PA}$ $PA$ Goodstein's theorem is unprovable in $P A$ ${\ displaystyle PA}$ $PA$ (but can be proved, for example, in second-order arithmetic ).

Goodstein Sequence

Consider the representation of positive integers as the sum of power terms with the same base.

For example, write the number 581 using base 2:

581=512+64+4+1=2^{9}+2^{6}+2^{2}+2^{0}.

{\ displaystyle 581 = 512 + 64 + 4 + 1 = 2 ^ {9} + 2 ^ {6} + 2 ^ {2} + 2 ^ {0}.}

We decompose the exponents according to the same principle:

581=2^{2^{3}+1}+2^{2^{2}+2}+2^{2}+1=2^{2^{2+1}+1}+2^{2^{2}+2}+2^{2}+1.

{\ displaystyle 581 = 2 ^ {2 ^ {3} +1} + 2 ^ {2 ^ {2} +2} + 2 ^ {2} + 1 = 2 ^ {2 ^ {2 + 1} +1} + 2 ^ {2 ^ {2} +2} + 2 ^ {2} +1.}

A similar decomposition can be obtained for any number.

We will recursively apply the following operation to the resulting expression:

an increase in “base” by 1 and subtraction of 1 from the number itself.

Thus, after applying the first operation (changing 2 to 3 and subtracting one from the number), the expression will be obtained

3^{3^{3+1}+1}+3^{3^{3}+3}+3^{3}.

{\ displaystyle 3 ^ {3 ^ {3 + 1} +1} + 3 ^ {3 ^ {3} +3} + 3 ^ {3}.}

After the second (change 3 to 4 and subtract one from the number):

4^{4^{4+1}+1}+4^{4^{4}+4}+3\times 4^{3}+3\times 4^{2}+3\times 4+3.

{\ displaystyle 4 ^ {4 ^ {4 + 1} +1} + 4 ^ {4 ^ {4} +4} +3 \ times 4 ^ {3} +3 \ times 4 ^ {2} +3 \ times 4 + 3.}

After the third (change 4 to 5 and subtract the unit from the number):

5^{5^{5+1}+1}+5^{5^{5}+5}+3\times 5^{3}+3\times 5^{2}+3\times 5+2.

{\ displaystyle 5 ^ {5 ^ {5 + 1} +1} + 5 ^ {5 ^ {5} +5} +3 \ times 5 ^ {3} +3 \ times 5 ^ {2} +3 \ times 5 + 2.}

Goodstein's theorem states that in the end 0 will always be obtained.

A stronger statement is also true: If instead of 1 we add some arbitrary number to the base and subtract it from the number itself, then we always get 0, even if the exponents are not decomposed initially in base 2.

The last base as a discrete function of the initial number grows very quickly, and already at $n=4$ ${\ displaystyle n = 4}$ it reaches a value $3\times 2^{402653211}-1$ ${\ displaystyle 3 \ times 2 ^ {402653211} -1}$ . At $n>3$ ${\ displaystyle n> 3}$ it will always be the number of Sabit and the number of Woodal .

Example

Consider an example of a Goodstein sequence for numbers 1, 2, and 3.

Number	Base	Record	Value
one	2	one	one
	3	eleven	0
2	2	2 ¹	2
	3	3 ¹ - 1	2
	four	2 - 1	one
	five	1 - 1	0
3	2	2 ¹ + 1	3
	3	(3 ¹ + 1) - 1 = 3 ¹	3
	four	4 ¹ - 1 = 1 + 1 + 1	3
	five	(1 + 1 + 1) - 1 = 1 + 1	2
	6	(1 + 1) - 1 = 1	one
	7	1 - 1 = 0	0

Notes

↑ Goodstein, R. (1944), " On the restricted ordinal theorem ", Journal of Symbolic Logic T. 9: 33–41 , < https://www.jstor.org/pss/2268019 >
↑ Kirby, L. & Paris, J. (1982), " Accessible independence results for Peano arithmetic ", Bulletin London Mathematical Society Vol. 14: 285–293 , < http://reference.kfupm.edu.sa/content/ a / c / accessible_independence_results_for_pean_59864.pdf > Archived August 25, 2011 on Wayback Machine
↑ Roger Penrose. Big small and human mind. Annex 1.

[1] Goodstein, R. (1944), " On the restricted ordinal theorem ", Journal of Symbolic Logic T. 9: 33–41 , < https://www.jstor.org/pss/2268019 >

[2] Kirby, L. & Paris, J. (1982), " Accessible independence results for Peano arithmetic ", Bulletin London Mathematical Society Vol. 14: 285–293 , < http://reference.kfupm.edu.sa/content/ a / c / accessible_independence_results_for_pean_59864.pdf > Archived August 25, 2011 on Wayback Machine

[3] Roger Penrose. Big small and human mind. Annex 1.

Goodstein Theorem

Goodstein Sequence

Example

Notes

More articles: