Grahamovo číslo: extrémně velké číslo v Ramseyově teorii
Objevte Grahamovo číslo — extrémně velké číslo v Ramseyově teorii: jeho původ, význam v matematice a proč překonává představivost i vesmír.
Grahamovo číslo je extrémně velké přirozené číslo, které definoval matematik Ronald Graham při řešení problému z oblasti Ramseyho teorie. Graham demonstroval, že odpověď na jeho konkrétní problém je menší než toto číslo, takže Grahamovo číslo slouží jako explicitní horní odhad pro danou úlohu.
Konkrétní Ramseyovský problém, kterému se Graham věnoval, se týká dvoubarevných obarvení hran n-rozměrného hyperkrychle (resp. souvisejícího úplného grafu na vrcholech hyperkrychle) a existence určitého typu monochromatického podgrafu (čtyřvrcholového úplného podgrafu ležícího v jedné rovině — „čtverce“). Graham ukázal, že pro dostatečně velké n musí takový podgraf existovat pro každé 2-barevné obarvení hran; Grahamovo číslo je extrémně velkým explicitním odhadem toho, jak velké to n může být. Přesná (nejmenší možná) hodnota n pro tuto úlohu zůstává neznámá a je zřejmě mnohem menší než Grahamovo číslo.
Grahamovo číslo je vytvořeno pomocí Knuthovy šipkové notace, která umožňuje kompaktně vyjádřit velmi rychle rostoucí funkce. Základní příklady této notace jsou:
- a ↑ b = a^b (obyčejná mocnina),
- a ↑↑ b = iterovaná mocnina (tetrace), tj. a^(a^(...^a)) s b výskyty a,
- vyšší počty šipek značí dál exponenciální iteraci na stále vyšší úrovni růstu.
Definice Grahamova čísla (ve zjednodušeném popisu) se dává rekurentně takto: nejprve se vezme
g1 = 3 ↑↑↑↑ 3 (trojka se čtyřmi šipkami mezi trojkami). Poté pro každé n ≥ 1 platí
gn+1 = 3 se gn šipkami 3 (tedy mezi dvěma trojkami je počet šipek roven předchozí hodnotě gn). Nakonec se definuje Grahamovo číslo jako
G = g64.
Tato konstrukce vede k číslu, které je zcela mimo intuici: G je mnohonásobně větší než běžné „velké“ čísla jako googol nebo googolplex, mnohonásobně větší než počet atomů v pozorovatelném vesmíru; i kdybychom každou cifru zapsali nejmenším čitelným písmem, desetinné vyjádření by se stále nikdy nevešlo do pozorovatelného vesmíru. Přesto lze některé vlastnosti Grahamova čísla rozhodnout — například pomocí modularních výpočtů je možné spočítat několik posledních číslic jeho desetinného zápisu — celkové desítkové vyjádření je však nemožné uvést v běžné notaci.
Je důležité zdůraznit, že Grahamovo číslo nebylo navrženo jako tvrzení, že hledané n v původním problému má právě tuto hodnotu; jde o velmi konzervativní horní odhad. Pozdější práce a zlepšení metod výrazně snížily horní odhady pro podobné problémy, takže skutečné minimální n je pravděpodobně mnohem menší než G. Přesto Grahamovo číslo zůstává významným příkladem toho, jak rychle může růst matematicky definovaná funkce, a slouží jako ilustrace a výukový prostředek při vysvětlování velkých čísel a notací jako Knuthovy šipky.
Pro úplnost: existují i jiné matematicky definované objekty a postupy (například funkce typu Busy Beaver nebo některé hladce definované kombinatorické funkce jako TREE(3)), které vedou k číslům rostoucím ještě mnohem rychleji než Grahamovo číslo; to ukazuje, že „velikost“ čísel v matematice může překročit i velmi silnou intuici o tom, co je „velmi velké“.
Kontext
Ramseyho teorie je oblast matematiky, která si klade otázky typu:
Předpokládejme, že nakreslíme nějaký počet bodů a každou dvojici bodů spojíme přímkou. Některé čáry jsou modré a některé červené. Najdeme vždy 3 body, pro které mají všechny 3 přímky, které je spojují, stejnou barvu?
Ukázalo se, že pro tento jednoduchý problém je odpověď "ano", pokud máme 6 nebo více bodů, bez ohledu na to, jak jsou čáry vybarveny. Když však máme 5 nebo méně bodů, můžeme čáry vybarvit tak, že odpověď bude "ne".
Grahamovo číslo pochází z variace na tuto otázku.
Opět řekněme, že máme nějaké body, ale nyní jsou to rohy n-rozměrné hyperkostky. Stále jsou všechny spojeny modrými a červenými čarami. Pro libovolné 4 body existuje 6 přímek, které je spojují. Najdeme 4 body, které všechny leží v jedné rovině a všech 6 přímek, které je spojují, má stejnou barvu?
Tím, že jsme požadovali, aby 4 body ležely v rovině, jsme problém značně ztížili. Rádi bychom věděli: pro jaké hodnoty n je odpověď "ne" (pro některý způsob vybarvení přímek) a pro jaké hodnoty n je "ano" (pro všechny způsoby vybarvení přímek)? Tento problém však dosud nebyl zcela vyřešen.
V roce 1971 našli Ronald Graham a B. L. Rothschild částečnou odpověď na tento problém. Ukázali, že pro n=6 je odpověď "ne". Pokud je však n velmi velké, stejně velké jako Grahamovo číslo nebo větší, odpověď zní "ano".
Jedním z důvodů, proč je tato částečná odpověď důležitá, je to, že znamená, že odpověď je nakonec "ano" alespoň pro nějaké velké n. Před rokem 1971 jsme nevěděli ani tolik.
Definice
Grahamovo číslo je nejen příliš velké na to, abychom mohli zapsat všechny jeho číslice, ale je příliš velké i na to, abychom ho zapsali vědeckým zápisem. Abychom ho mohli zapsat, musíme použít Knuthovu notaci se šipkami nahoru.
Zapíšeme si posloupnost čísel, kterou nazveme g1, g2, g3 atd. Každé z nich použijeme v rovnici k nalezení dalšího. g64 je Grahamovo číslo.
Nejprve uvádíme několik příkladů šipek nahoru:
- 3 ↑ 3 {\displaystyle 3\uparrow 3}
je 3x3x3, což je 27. Šipka mezi dvěma čísly znamená pouze to, že první číslo se násobí druhým číslem tolikrát, kolikrát se násobí. - Lze si představit 3 ↑↑ 3 {\displaystyle 3\uparrow \uparrow 3}
jako 3 ↑ ( 3 ↑ 3 ) {\displaystyle 3\uparrow (3\uparrow 3)}
, protože dvě šipky mezi čísly A a B znamenají pouze A zapsané několikrát B se šipkou mezi každým A. Protože víme, co jsou to jednotlivé šipky, 3 ↑ ( 3 ↑ 3 ) {\displaystyle 3\uparrow (3\uparrow 3)} je 3 vynásobené sebou samým 3 ↑ 3 {\displaystyle 3\uparrow 3} krát a víme, že 3 ↑ 3 {\displaystyle 3\uparrow 3} je dvacet sedm. Takže 3 ↑↑ 3 {\displaystyle 3\uparrow 3} je 3x3x3x3x....x3x3, celkem 27krát. To se rovná 7 625 597 484 987. - 3 ↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow 3}
je 3 ↑↑ ( 3 ↑↑ 3 ) {\displaystyle 3\uparrow \uparrow (3\uparrow \uparrow 3)}
a víme, že 3 ↑↑ 3 {\displaystyle 3\uparrow \uparrow 3} je 7,625,597,484,987. Takže 3 ↑↑ ( 3 ↑↑ 3 ) {\displaystyle 3\uparrow \uparrow (3\uparrow \uparrow 3)} je 3 ↑↑ 7 , 625 , 597 , 484 , 987 {\displaystyle 3\uparrow \uparrow 7,625,597,484,987}
. To lze také zapsat jako 3 ↑ ( 3 ↑ ( 3 ↑ ( 3 ↑ . . . ( 3 ↑ ( 3 ↑ ( 3 ↑ 3 ) {\displaystyle 3\uparrow (3\uparrow (3\uparrow (3\uparrow (3\uparrow ...(3\uparrow (3\uparrow (3\uparrow (3\uparrow 3)}
s celkem 7 625 597 484 987 3s. Toto číslo je tak obrovské, že jeho číslice, i když jsou zapsány velmi malými číslicemi, by mohly zaplnit celý pozorovatelný vesmír i mimo něj. - Ačkoli je toto číslo možná již nepochopitelné, je to sotva začátek tohoto obřího čísla.
- Další krok je 3 ↑↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow 3}
nebo 3 ↑↑↑ ( 3 ↑↑↑ 3 ) {\displaystyle 3\uparrow \uparrow (3\uparrow \uparrow \uparrow 3)}
. Toto číslo budeme nazývat g1.
Poté se g2 rovná 3 ↑↑↑↑ ... ↑↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow 3}
; počet šipek v tomto počtu je g1.
g3 se rovná 3 ↑↑↑↑↑ ... ↑↑↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3}
, kde počet šipek je g2.
Takto pokračujeme dál. Zastavíme se, když definujeme g64 jako 3 ↑↑↑↑↑ ... ↑↑↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3} , kde počet šipek je g63.
Toto je Grahamovo číslo.
Související stránky
- Knuthův zápis se šipkou nahoru
Otázky a odpovědi
Otázka: Kdo určil Grahamovo číslo?
Odpověď: Grahamovo číslo definoval Ronald Graham.
Otázka: V jaké oblasti matematiky pracoval Ronald Graham, když definoval toto číslo?
Odpověď: Ronald Graham pracoval v oblasti matematiky zvané Ramseyho teorie, když definoval toto číslo.
Otázka: Co Ronald Graham svým problémem dokázal?
Odpověď: Ronald Graham dokázal, že odpověď na jeho problém je menší než Grahamovo číslo.
Otázka: Jak velké je Grahamovo číslo ve srovnání s jinými čísly používanými v matematických důkazech?
Odpověď: Grahamovo číslo je jedno z největších čísel, které kdy bylo použito v matematickém důkazu.
Otázka: Kdyby se zapsala každá číslice tohoto čísla, vešla by se do pozorovatelného vesmíru?
Odpověď: I kdyby byla každá číslice Grahamova čísla napsána tím nejmenším možným písmem, stále by byla příliš velká na to, aby se vešla do pozorovatelného vesmíru.
Otázka: Dá se nějak vypočítat nebo odhadnout, jak velké toto číslo je?
Odpověď: Neexistuje žádný přesný způsob, jak vypočítat nebo odhadnout, jak velké je toto konkrétní přirozené číslo, protože dosud nebylo zcela určeno.
Otázka: Proč tak velké přirozené číslo existuje a k čemu slouží?
Odpověď: Toto velmi velké přirozené číslo existuje proto, že bylo použito Ronaldem Grahmem jako součást matematického důkazu a slouží jako horní hranice jeho řešení.
Vyhledávání