TRÆ(3)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 21. oktober 2022; verifikation kræver 1 redigering .

TRÆ(3) [1] er et stort tal , som er den øvre grænse for løsningen i Kruskals grafteoretiske sætning . TRÆ(3) er et ufatteligt antal gange Graham-tallet . Tallet TRÆ(3) er så stort, at Knuths og Conways piletegn ikke kan skrive det ned.

Kruskals sætning

I grafteori er et træ en graf, hvor alle toppunkter er forbundet med kanter (muligvis gennem andre toppunkter), og der er ingen cyklusser (sekvenser af kanter, der forbinder ethvert toppunkt til sig selv). I dette tilfælde er træerne rodfæstede, det vil sige, at de har et bestemt toppunkt - roden. Dette er en klar, men uformel definition af et træ . Kruskals sætning [2] angiver rækkefølgen af ​​træer TRÆ( n ) beskrevet af følgende love:

1. Hvert i -te træ har højst i toppunkter.
2. Hjørner har en af ​​n typer; for TREE(3) er det praktisk at kalde dem "røde", "grønne" og "blå".
3. Intet træ må være et topologisk minor af et senere træ.

TRÆ(1) giver et enkelt træ med et toppunkt: Hvis du forsøger at tilføje et andet med to toppunkter, vil fjernelse af et hvilket som helst af dem resultere i det første. TRÆ(2)=3, i denne rækkefølge et træ med et rødt toppunkt, to blå toppunkter og et blåt toppunkt. Men startende med TREE(3), er der en reel eksplosion i sekvenslængde. Kruskals sætning siger dog, at for enhver endelig n vil sekvensen ikke være uendelig .

Det er interessant at bemærke, at det første træ har ét "rødt" toppunkt, og uanset n har intet andet træ "røde" toppunkter. Ellers ville det første træ blive opnået, når du fjerner alle hjørner, undtagen denne "røde".

Svag træfunktion

Vi definerer træ( n ), en svag træfunktion [3] , som længden af ​​den længste række af træer med hjørner af samme farve, beskrevet af følgende love:

1. Hvert i -te træ har højst i + n toppunkter.
2. Intet træ må være et topologisk minor af et senere træ.

Det er kendt [3] at , , , og allerede er større end Graham-tallet.

Det er også kendt [4] , at TREE(3) er meget større end (det hævede skrift angiver i dette tilfælde en itereret funktion ).

TRÆ(3) nummerskalering

En almindelig misforståelse er Guinness World Records påstand om, at Grahams tal  er det største tal, der nogensinde er brugt i et matematisk bevis : denne information er for længst forældet, da tallet TREE(3) også bruges i en matematisk sammenhæng, og det er uforholdsmæssigt større end nummeret Graham. For at repræsentere tallet TREE(3) er ikke kun tårnene med grader ubrugelige , men også notationerne af Knuth og Conway . I Birds massive notation [5] kan TRÆ(3) groft sagt udtrykkes som . Den overordnede vækstrate for TREE( n )-funktionen estimeres som i form af et hurtigt voksende hierarki .

Samtidig er TREE(3) langt fra det største antal, man støder på i matematiske værker: i de efterfølgende år blev større tal beskrevet, for eksempel, såsom SSCG(3) , SCG(13) [6] , samt tal angivet ved hjælp af ikke-beregnerbare funktioner, såsom Rayo-nummeret .

Noter

1. ↑ Jay Bennett. Vikl dit hoved omkring taltræets enorme(3) . Populær mekanik (20. oktober 2017). Hentet 27. maj 2020. Arkiveret fra originalen 1. juli 2020. (ubestemt)
2. ↑ TRÆ(3) og upartiske spil | Kompleks projektiv 4-rum . Hentet 1. februar 2020. Arkiveret fra originalen 1. februar 2020. (ubestemt)
3. ↑ 1 2 TRÆ-sekvens | Google Wiki | fandom . Hentet 1. februar 2020. Arkiveret fra originalen 9. januar 2020. (ubestemt)
4. ↑ grafteori - Hvordan vokser TRÆ(3) for at blive så stort? (Lægtmandsforklaring) - Matematik Stack Exchange . Hentet 1. februar 2020. Arkiveret fra originalen 1. februar 2020. (ubestemt)
5. ↑ Fuglens array-notation . Hentet 20. maj 2022. Arkiveret fra originalen 11. november 2021. (ubestemt)
6. ↑ Subkubisk grafnummer . Hentet 1. februar 2020. Arkiveret fra originalen 1. februar 2020. (ubestemt)

Litteratur

• Friedman, Harvey M. (2002), Interne endelige træindlejringer. Refleksioner over matematikkens grundlag (Stanford, CA, 1998) , vol. 15, Lect. Notes Log., Urbana, IL: Assoc. symbol. Logik, s. 60-91 
• Gallier, Jean H. (1991), Hvad er så specielt ved Kruskals sætning og ordinalen Γ 0 ? En undersøgelse af nogle resultater i bevisteori , Ann. Rent æble. Logic T. 53(3): 199-260, doi : 10.1016 / 0168-0072 (91)90022-E , 
• Kruskal, JB (maj 1960), Well-quasi-ordering, træsætningen og Vazsonyis formodning , Transactions of the American Mathematical Society (American Mathematical Society). — T. 95 (2): 210–225, doi 1993287/10.2307: > 
• Marcone, Alberto. Wqo og bqo teori i delsystemer af andenordens aritmetik  //  Omvendt matematik: tidsskrift. - 2001. - Bd. 21 . - S. 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. Bevisteoretiske undersøgelser af Kruskals teorem  (engelsk)  // Annals of Pure and Applied Logic: journal. - 1993. - Bd. 60 , nr. 1 . - S. 49-88 . - doi : 10.1016/0168-0072(93)90192-g .
• Simpson, Stephen G. (1985), Ikke-bevisbarhed af visse kombinatoriske egenskaber af endelige træer, i Harrington, LA; Morley, M. & Scedrov, A. et al., Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, s. 87-117 
• Smith, Rick L. (1985), Konsistensstyrkerne af nogle endelige former af Higman- og Kruskal-sætningerne, i Harrington, LA; Morley, M. & Scedrov, A. et al., Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, s. 119-136 

Store tal
Tal	google Shannon nummer Googolplex Skæv nummer Moser nummer Graham nummer TRÆ(3) Rayo nummer
Funktioner	Ackermann funktion Veblen funktion Psi-funktioner af Buchholz tetration Pentation Hyperoperator Hurtigt voksende hierarki Langsomt voksende hierarki Hardy hierarki
Notationer	Steinhaus-Moser notation Knuth pil notation Conway pil notation Massiv Bowers-notation