Goodsteinova věta

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 11. listopadu 2019; kontroly vyžadují 9 úprav .

Goodsteinův teorém je teorém matematické logiky o přirozených číslech , dokázaný Reubenem Goodsteinem [1] . Tvrdí, že všechny Goodsteinovy sekvence končí nulou. Jak ukázali L. Kirby a Jeff Paris [2] [3] , Goodsteinův teorém není prokazatelný v Peanově axiomatice ( ) (lze však dokázat např. v aritmetice druhého řádu ). $PA$

Goodsteinova sekvence

Uvažujme reprezentaci kladných celých čísel jako součet mocninných členů se stejným základem.

Například zapišme číslo 581 pomocí základu 2:

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

Rozložme exponenty podle stejného principu:

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

Podobné rozšíření lze získat pro libovolné číslo.

Na výsledný výraz použijeme rekurzivně následující operaci:

zvýšení "základu" o 1 a odečtení 1 od samotného čísla.

Po aplikaci první operace (změňte 2 na 3 a odečtěte jedničku od čísla) tedy dostaneme výraz

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

Po druhém (změňte 3 na 4 a odečtěte jedničku od čísla):

4^{4^{4+1}+1}+4^{4^{4}+4}+3\krát 4^{3}+3\krát 4^{2}+3\krát 4+3.

Po třetím (změňte 4 na 5 a odečtěte jedničku od čísla):

5^{5^{5+1}+1}+5^{5^{5}+5}+3\krát 5^{3}+3\krát 5^{2}+3\krát 5+2.

Goodsteinova věta říká, že konečný výsledek bude vždy 0.

Platí také silnější tvrzení: Pokud se místo 1 přidá k základu nějaké libovolné číslo a odečte se od samotného čísla, pak vždy dostaneme 0, i když exponenty nejsou zpočátku rozloženy v základu 2.

Poslední základ jako diskrétní funkce původního čísla roste velmi rychle a již při něm dosahuje hodnoty . Pro , bude to vždy Woodallovo číslo [4] . $n=4$ $3\times 2^{27}\times 2^{3\times 2^{27}}-1=3\times 2^{402653211}-1$ $n>3$

Příklad

Zvažte příklad Goodsteinovy posloupnosti pro čísla 1, 2 a 3.

Číslo	Základna	Záznam	Význam
jeden	2	jeden	jeden
	3	jedenáct	0
2	2	2 1	2
	3	3 1 - 1	2
	čtyři	2:1	jeden
	5	1 - 1	0
3	2	2 1 + 1	3
	3	(3 1 + 1) − 1 = 3 1	3
	čtyři	4 1 − 1 = 1 + 1 + 1	3
	5	(1 + 1 + 1) − 1 = 1 + 1	2
	6	(1 + 1) − 1 = 1	jeden
	7	1 – 1 = 0	0

Poznámky

↑ Goodstein, R. (1944), O omezené ordinální větě , Journal of Symbolic Logic vol . 9: 33–41 , < https://www.jstor.org/pss/2268019 >
↑ Kirby, L. & Paris, J. (1982), Přístupné výsledky nezávislosti pro Peano aritmetiku , Bulletin London Mathematical Society vol. 14: 285–293 , < http://reference.kfupm.edu.sa/content/a/ c/accessible_independence_results_for_pean_59864.pdf > Archivováno 25. srpna 2011 na Wayback Machine
↑ Roger Penrose. Velký malý a lidská mysl. Příloha 1.
↑ Uvažujme reprezentaci čísla ve tvaru , kde je náš základ. Když zůstane pouze koeficient at , rovný jedné, označíme hodnotu this . Poté, když se číslo změní na Je snadné ukázat, že v průběhu dalšího vývoje každé snížení koeficientu o 1 zdvojnásobuje k. Poslední hodnota základu bude . $\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$