Goodstein tétele

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. november 11-én felülvizsgált verziótól ; az ellenőrzések 9 szerkesztést igényelnek .

Goodstein tétele a matematikai logika természetes számokra vonatkozó tétele , bizonyítja Reuben Goodstein [1] . Azt állítja, hogy minden Goodstein-szekvencia nullára végződik. Mint L. Kirby és Jeff Paris [2] [3] kimutatta , Goodstein tétele a Peano-axiomatikában ( ) nem bizonyítható (de bizonyítható pl. a másodrendű aritmetikában ). $PA$

A Goodstein sorozat

Tekintsük a pozitív egész számok ábrázolását azonos bázisú hatványtagok összegének.

Például írjuk fel az 581-es számot a 2-es bázis használatával:

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

Bontsuk fel a kitevőket ugyanezen elv szerint:

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

Bármely számhoz hasonló bővítés érhető el.

A kapott kifejezésre rekurzív módon a következő műveletet alkalmazzuk:

az "alapot" növelve 1-gyel, és magából a számból kivonva az 1-et.

Így az első művelet alkalmazása után (módosítson 2-t 3-ra, és vonjon ki egyet a számból) megkapja a kifejezést

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

A második után (módosítsa a 3-at 4-re, és vonjon le egyet a számból):

4^{4^{4+1}+1}+4^{4^{4}+4}+3\szer 4^{3}+3\szor 4^{2}+3\szer 4+3.

A harmadik után (módosítsa a 4-et 5-re, és vonjon le egyet a számból):

5^{5^{5+1}+1}+5^{5^{5}+5}+3\szer 5^{3}+3\szor 5^{2}+3\szer 5+2.

Goodstein tétele kimondja, hogy a végeredmény mindig 0 lesz.

Egy erősebb állítás is igaz: Ha 1 helyett tetszőleges számot adunk az alaphoz, és kivonjuk magából a számból, akkor mindig 0-t kapunk, még akkor is, ha a kitevőket kezdetben nem bontjuk fel a 2. bázisban.

Az utolsó bázis az eredeti szám diszkrét függvényeként nagyon gyorsan növekszik, és már ekkor eléri az értéket . A , mindig a Woodall-szám [4] lesz . $n=4$ $3\times 2^{27}\times 2^{3\times 2^{27}}-1=3\times 2^{402653211}-1$ $n>3$

Példa

Tekintsünk egy példát az 1, 2 és 3 számok Goodstein sorozatára.

Szám	Bázis	Felvétel	Jelentése
egy	2	egy	egy
	3	tizenegy	0
2	2	2 1	2
	3	3 1-1 _	2
	négy	2-1	egy
	5	1-1	0
3	2	2 1 + 1	3
	3	(3 1 + 1) − 1 = 3 1	3
	négy	4 1 − 1 = 1 + 1 + 1	3
	5	(1 + 1 + 1) − 1 = 1 + 1	2
	6	(1 + 1) − 1 = 1	egy
	7	1–1 = 0	0

Jegyzetek

↑ Goodstein, R. (1944), A korlátozott ordinális tételről , Journal of Symbolic Logic 9. kötet: 33–41 , < https://www.jstor.org/pss/2268019 >
↑ Kirby, L. & Paris, J. (1982), Accessible independence results for Peano aritmetic , Bulletin London Mathematical Society , 14. kötet: 285–293 , < http://reference.kfupm.edu.sa/content/a/ c/accessible_independence_results_for_pean_59864.pdf > Archiválva : 2011. augusztus 25. a Wayback Machine -nél
↑ Roger Penrose. Nagy kicsi és az emberi elme. 1. melléklet.
↑ Tekintsük egy szám ábrázolását az alakban , ahol a bázisunk. Ha csak az eggyel egyenlő együtthatója marad meg, akkor ennek értékét jelöljük . Ezt követően, amikor a szám átváltozik Könnyen kimutatható, hogy a további evolúció során az együttható 1-gyel történő minden egyes csökkenése megduplázza k. Az alap utolsó értéke . $\sum a_{i}k^{\sum b_{ij}k^{\pontok ))$ $k$ $k^{2}$ $k$ $k_{2}$ $k=k_{2}+1$ $k_{2}k+k_{2}.$ $k$ $k_{2}\cdot 2^{k_{2}}-1$