STROM(3)

TREE(3) [1] je velké číslo , které je horní hranicí řešení v Kruskalově grafo - teorémě . TREE(3) je nepředstavitelný počet krát Grahamovo číslo . Číslo STROM(3) je tak velké, že jej Knuthovy a Conwayovy šipky nedokážou zapsat.

Kruskalova věta

V teorii grafů je strom grafem, ve kterém jsou všechny vrcholy spojeny hranami (případně přes jiné vrcholy) a neexistují žádné cykly (sekvence hran spojujících jakýkoli vrchol se sebou samým). V tomto případě jsou stromy zakořeněné, to znamená, že mají určitý vrchol - kořen. Toto je jasná, ale neformální definice stromu . Kruskalova věta [2] uvádí posloupnost stromů TREE( n ) popsanou následujícími zákony:

1. Každý i -tý strom má nejvýše i vrcholů.
2. Vrcholy mají jeden z n typů; pro TREE(3) je vhodné je nazývat „červená“, „zelená“ a „modrá“.
3. Žádný strom nesmí být topologickou minoritou pozdějšího stromu.

TREE(1) poskytuje jeden strom s jedním vrcholem: pokud se pokusíte přidat další strom se dvěma vrcholy, odstranění kteréhokoli z nich bude mít za následek první. TREE(2)=3, v této sekvenci strom s jedním červeným vrcholem, dvěma modrými vrcholy a jedním modrým vrcholem. Ale počínaje TREE(3) dochází ke skutečné explozi délky sekvence. Kruskalova věta však říká, že pro žádné konečné n nebude posloupnost nekonečná .

Je zajímavé poznamenat, že první strom má jeden „červený“ vrchol a bez ohledu na n žádný jiný strom nemá „červené“ vrcholy. V opačném případě by při odstranění všech vrcholů kromě této "červené" byl získán první strom.

Slabá stromová funkce

Strom( n ), slabou stromovou funkci [3] , definujeme jako délku nejdelšího sledu stromů s vrcholy stejné barvy, popsaného následujícími zákony:

1. Každý i -tý strom má nejvýše i + n vrcholů.
2. Žádný strom nesmí být topologickou minoritou pozdějšího stromu.

Je známo [3] , že , , , a je již větší než Grahamovo číslo.

Je také známo [4] , že TREE(3) je mnohem větší než (horní index v tomto případě označuje iterovanou funkci ).

TREE(3) číselné měřítko

Častou mylnou představou je tvrzení Guinessovy knihy rekordů , že Grahamovo číslo  je největší číslo, jaké kdy bylo použito v matematickém důkazu : tato informace je dávno zastaralá, protože číslo STROM(3) se také používá v matematickém kontextu a je nepoměrně větší než číslo Graham. K vyjádření čísla STROM(3) jsou k ničemu nejen věže stupňů , ale také Knuthův a Conwayův zápis . V Birdově masivní notaci [5] lze TREE(3) zhruba vyjádřit jako . Celková rychlost růstu funkce TREE( n ) se odhaduje jako z hlediska rychle rostoucí hierarchie .

TREE(3) přitom zdaleka není největším číslem, se kterým se v matematických pracích setkáváme: v dalších letech byla popsána větší čísla, například SSCG(3) , SCG(13) [6] , stejně jako čísla specifikovaná pomocí nevypočitatelných funkcí, jako je Rayo číslo .

Poznámky

1. ↑ Jay Bennett. Obtočte hlavu kolem obrovského čísla STROMU(3) . Populární mechanika (20. října 2017). Staženo 27. května 2020. Archivováno z originálu dne 1. července 2020. (neurčitý)
2. ↑ STROM(3) a nestranné hry | Komplexní projektivní 4-prostor . Staženo 1. února 2020. Archivováno z originálu 1. února 2020. (neurčitý)
3. ↑ 1 2 TREE sekvence | Google Wiki | fandom . Staženo 1. února 2020. Archivováno z originálu 9. ledna 2020. (neurčitý)
4. ↑ teorie grafů – Jak roste STROM(3) tak, že je tak velký? (Vysvětlení pro laiky) - Výměna zásobníku matematiky . Staženo 1. února 2020. Archivováno z originálu 1. února 2020. (neurčitý)
5. ↑ Zápis ptačího pole . Získáno 20. května 2022. Archivováno z originálu dne 11. listopadu 2021. (neurčitý)
6. ↑ Číslo subkubického grafu . Staženo 1. února 2020. Archivováno z originálu 1. února 2020. (neurčitý)

Literatura

• Friedman, Harvey M. (2002), Internal finite tree embeddings. Úvahy o základech matematiky (Stanford, CA, 1998) , sv. 15, Lect. Poznámky Log., Urbana, IL: Assoc. symbol. Logika, str. 60–91 
• Gallier, Jean H. (1991), Co je tak zvláštního na Kruskalově větě a ordinálu Γ 0 ? Přehled některých výsledků v teorii důkazů , Ann. Čisté jablko. Logic T. 53(3): 199–260, doi : 10.1016 / 0168-0072 (91)90022-E , 
• Kruskal, JB (květen 1960), Well-quasi-ording, the tree teorem, and Vazsonyi's conjective , Transactions of the American Mathematical Society (American Mathematical Society). — T. 95 (2): 210–225, doi 1993287/10.2307: > 
• Marcone, Alberto. Wqo a bqo teorie v subsystémech aritmetiky druhého řádu  //  Reverse Mathematics : journal. - 2001. - Sv. 21 . - str. 303-330 .
• Nash-Williams, C. St. JA (1963), On well-quasi-ording finite trees , Proc. Camb. Phil. soc. V. 59 (4): 833–835 , DOI 10.1017/S0305004100003844 
• Rathjen, Michael; Weiermann, Andreas. Důkazová teoretická zkoumání Kruskalova teorému  (anglicky)  // Annals of Pure and Applied Logic: journal. - 1993. - Sv. 60 , č. 1 . - str. 49-88 . - doi : 10.1016/0168-0072(93)90192-g .
• Simpson, Stephen G. (1985), Neprokazatelnost určitých kombinatorických vlastností konečných stromů, Harrington, LA; Morley, M. & Scedrov, A. a kol., Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, str. 87–117 
• Smith, Rick L. (1985), Síla konzistence některých konečných forem Higmanových a Kruskalových teorémů, v Harringtonu, LA; Morley, M. & Scedrov, A. a kol., Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, str. 119–136