Teorema lui Goodstein

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 11 noiembrie 2019; verificările necesită 9 modificări .

Teorema lui Goodstein este o teoremă a logicii matematice despre numerele naturale , demonstrată de Reuben Goodstein [1] . Afirmă că toate secvențele Goodstein se termină cu zero. După cum arată L. Kirby și Jeff Paris [2] [3] , teorema lui Goodstein nu este demonstrabilă în axiomatica Peano ( ) (dar poate fi demonstrată, de exemplu, în aritmetica de ordinul doi ). $PA$

Secvența Goodstein

Considerați reprezentarea numerelor întregi pozitive ca o sumă de termeni de putere cu aceeași bază.

De exemplu, să scriem numărul 581 folosind baza 2:

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

Să descompunăm exponenții după același principiu:

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

O extindere similară poate fi obținută pentru orice număr.

Vom aplica recursiv următoarea operație expresiei rezultate:

mărind „baza” cu 1 și scăzând 1 din numărul însuși.

Astfel, după aplicarea primei operații (schimbați 2 în 3 și scădeți unul din număr), se va obține expresia

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

După al doilea (schimbați 3 cu 4 și scădeți unul din număr):

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

După al treilea (schimbați 4 în 5 și scădeți unul din număr):

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

Teorema lui Goodstein spune că rezultatul final va fi întotdeauna 0.

O afirmație mai puternică este, de asemenea, adevărată: dacă în loc de 1 se adaugă la bază un număr arbitrar și se scade din numărul însuși, atunci se va obține întotdeauna 0 chiar dacă exponenții nu sunt descompuși inițial în baza 2.

Ultima bază ca funcție discretă a numărului inițial crește foarte repede și deja la ea atinge valoarea . Pentru , va fi întotdeauna numărul Woodall [4] . $n=4$ $3\times 2^{27}\times 2^{3\times 2^{27}} -1=3\times 2^{402653211}-1$ $n>3$

Exemplu

Luați în considerare un exemplu de succesiune Goodstein pentru numerele 1, 2 și 3.

Număr	Baza	Înregistrare	Sens
unu	2	unu	unu
	3	unsprezece	0
2	2	2 1	2
	3	3 1 − 1	2
	patru	2 - 1	unu
	5	1 - 1	0
3	2	2 1 + 1	3
	3	(3 1 + 1) − 1 = 3 1	3
	patru	4 1 − 1 = 1 + 1 + 1	3
	5	(1 + 1 + 1) − 1 = 1 + 1	2
	6	(1 + 1) − 1 = 1	unu
	7	1 − 1 = 0	0

Note

↑ Goodstein, R. (1944), On the restricted ordinal theorem , Journal of Symbolic Logic vol . 9: 33–41 , < https://www.jstor.org/pss/2268019 >
↑ Kirby, L. & Paris, J. (1982), Accesible independence results for Peano athmetic , Bulletin London Mathematical Society vol. 14: 285–293 , < http://reference.kfupm.edu.sa/content/a/ c/accessible_independence_results_for_pean_59864.pdf > Arhivat 25 august 2011 la Wayback Machine
↑ Roger Penrose. Mare mic și mintea umană. Atasamentul 1.
↑ Luați în considerare reprezentarea unui număr sub forma , unde este baza noastră. Când rămâne doar coeficientul lui at , egal cu unu, notăm valoarea acestui . După aceea, când numărul se transformă în Este ușor de arătat că, în cursul evoluției ulterioare, fiecare scădere a coeficientului cu 1 dublează k. Ultima valoare a bazei va fi . $\sum a_{i}k^{\sum b_{ij}k^{\dots ))$ $k$ $k^{2}$ $k$ $k_{2}$ $k=k_{2}+1$ $k_{2}k+k_{2}.$ $k$ $k_{2}\cdot 2^{k_{2}}-1$