Grahams tal: definition og betydning i Ramsey-teori
Grahams tal: Læs om definitionen og dens betydning i Ramsey-teori — et af de største tal i matematikken og dets overraskende konsekvenser.
Grahams tal er et ekstremt stort naturligt tal, som blev indført af matematikeren Ronald Graham i forbindelse med et problem i Ramsey-teori. Graham viste, at svaret på hans oprindelige Ramsey-type-problem er mindre end Grahams tal, og tallet fungerer derfor som et (meget groft) øvre skøn i et teoretisk bevis.
Hvordan defineres Grahams tal?
Grahams tal er defineret ved en meget hurtig voksende, iterativ proces, der bruger Knuths up-arrow-notation (en måde at beskrive gentagne potenser og hyperoperationer på). En kort og standard måde at beskrive konstruktionen på er:
g1 = 3 ↑↑↑↑ 3, og for hvert n ≥ 1 defineres g(n+1) = 3 ↑^{g(n)} 3, altså hvor antallet af up-pile (↑) i udtrykket er lig med g(n). Grahams tal G sættes så til g64 (dvs. det 64. led i denne række).
Det betyder, at allerede g1 er astronomisk stort (tårne af potenser med højde og kompleksitet, der overskrider almindelig forestilling), og hvert trin i rækken fører til et tal med vækst langt ud over almindelige eksponentielle eller selv dobbelttetrationelle størrelser. Derfor bliver G ubegribeligt stort.
Betydning i Ramsey-teori
Den oprindelige motivation for Grahams tal var et spørgsmål i Ramsey-teori om farvninger af kanter i højdimensionelle hyperkuber og forekomsten af bestemte monochromatiske delstrukturer. Ronald Graham brugte sin konstruktion til at give et konkret, omend ekstremt stort, øvre skøn for det dimensionstal, hvor en vis ønsketegenskab nødvendigvis optræder ved enhver to-farvning. Så Grahams tal er ikke et «naturligt» antal, man regner med at møde i praktiske beregninger, men et bevisligt øvre skøn i teoretisk kombinatorik.
Hvorfor er tallet så enormt?
- Itererede hyperoperationer: Hver gang man anvender reglen g(n+1) = 3 ↑^{g(n)} 3, øges antallet af pile (↑) dramatisk, og det fører til vækstformer langt voldsommere end almindelig eksponentiering eller tetration.
- Umålelig størrelse i fysisk forstand: Grahams tal er så stort, at selv hvis hvert enkelt ciffer i Grahams tal blev skrevet med den mindste tænkelige skrifttype, ville det stadig være for stort til at passe ind i det observerbare univers.
- Alligevel veldefineret og endelig: På trods af størrelsen er Grahams tal et helt endeligt, veldefineret naturligt tal — ikke et symbol for uendelighed.
Senere arbejde og nutidig opfattelse
Efter Grahams oprindelige arbejde har andre forskere finpudset og skærpet de teknikker, der bruges i denne type Ramsey-problemer. Det betyder, at man i mange tilfælde i dag kan give meget mindre (og mere relevante) øvre skøn for de samme eller beslægtede problemer. Det ændrer dog ikke, at Grahams tal historisk er blevet et kendt eksempel på, hvor store tal der kan dukke op i teoretiske beviser.
Grahams tal har desuden været populært omtalt i populærvidenskabelige bøger og artikler som et illustrativt eksempel på ekstrem vækst i matematikken. Det fungerer som en måde at vise forskellen mellem «teoretisk» størrelsesorden (hvor et tal blot skal være endeligt og kunne indgå i et bevis) og «praktisk» størrelsesorden (hvor størrelsen skal kunne håndteres eller fortolkes i fysiske termer).
Ekstra bemærkninger
Selvom Grahams tal er ubegribeligt stort, kan visse aritmetiske egenskaber (fx nogle af de sidste decimaler) udledes ved hjælp af modulær aritmetik og strukturen i definitionen. Men det ændrer ikke ved, at størrelsesordenen for tallet som helhed ligger langt uden for enhver fysisk eller praktisk anvendelse.
Grahams tal er derfor først og fremmest en matematisk kuriositet og et historisk vigtigt eksempel på, hvordan Ramsey-type-argumenter kan føre til enorme, men endelige, øvre grænser i kombinatorik og diskret matematik.
Kontekst
Ramsey-teori er et område af matematikken, hvor man stiller spørgsmål som følgende:
Antag, at vi tegner et antal punkter og forbinder hvert punktpar med en linje. Nogle linjer er blå og andre er røde. Kan vi altid finde 3 punkter, for hvilke de 3 linjer, der forbinder dem, alle har samme farve?
Det viser sig, at for dette enkle problem er svaret "ja", når vi har 6 eller flere punkter, uanset hvordan linjerne er farvet. Men når vi har 5 punkter eller færre, kan vi farve linjerne, så svaret er "nej".
Lad os igen sige, at vi har nogle punkter, men nu er de hjørnerne af en n-dimensionel hyperkube. De er stadig forbundet af blå og røde linjer. For 4 punkter er der 6 linjer, der forbinder dem. Kan vi finde 4 punkter, der alle ligger på samme plan, og hvor de 6 linjer, der forbinder dem, alle har samme farve?
Ved at kræve, at de 4 punkter skal ligge på et plan, har vi gjort problemet meget sværere. Vi vil gerne vide: For hvilke værdier af n er svaret "nej" (for en bestemt måde at farve linjerne på), og for hvilke værdier af n er svaret "ja" (for alle måder at farve linjerne på)? Men dette problem er endnu ikke blevet løst helt.
I 1971 fandt Ronald Graham og B. L. Rothschild et delvist svar på dette problem. De viste, at for n=6 er svaret "nej". Men når n er meget stort, lige så stort som Grahams tal eller større, er svaret "ja".
En af grundene til, at dette delvise svar er vigtigt, er, at det betyder, at svaret i sidste ende er "ja" for i hvert fald nogle store n. Før 1971 vidste vi ikke engang så meget.
Der findes en meget mindre grænse for det samme problem kaldet N. Den er lig med 
, hvor 
. Denne svagere øvre grænse for problemet, der blev tilskrevet et upubliceret arbejde af Graham, blev i sidste ende offentliggjort og navngivet af Martin Gardner i Scientific American i november 1977.
Definition
Grahams tal er ikke blot for stort til at skrive alle dets cifre ned, det er endda for stort til at skrive det i videnskabelig notation. For at kunne skrive det ned, må vi bruge Knuths op-pil notation.
Vi vil skrive en række tal ned, som vi kalder g1, g2, g3 osv. Hvert tal vil blive brugt i en ligning til at finde det næste. g64 er Grahams tal.
Her er først nogle eksempler på opadgående pile:
er 3x3x3, hvilket er lig med 27. En pil mellem to tal betyder blot, at det første tal er ganget med sig selv det andet antal gange.- Man kan tænke på
som 
, fordi to pile mellem tal A og B blot betyder, at A er skrevet ned et B antal gange med en pil mellem hvert A. Fordi vi ved, hvad enkeltpile er, er 3 ganget med sig selv 3 gange, og vi ved, at er syvogtyve. Så er 3x3x3x3x3x....x3x3x3, i alt 27 gange. Det svarer til 7.625.597.484.987. 
er 
og vi ved, at er 7,625,597,484,987. Så er 
. Det kan også skrives som 
med i alt 7.625.597.484.987 3'ere. Dette tal er så enormt, at dets cifre, selv skrevet meget små, kunne fylde det observerbare univers og videre ud over det.- Selv om dette tal måske allerede er ubegribeligt, er det kun begyndelsen på dette kæmpe tal.
- Det næste trin på denne måde er
eller 
. Dette er det tal, som vi kalder g1.
Derefter er g2 lig med 
; antallet af pile i dette tal er g1.
g3 er lig med 
, hvor antallet af pile er g2.
Vi fortsætter på denne måde. Vi stopper, når vi definerer g64 til at være , hvor antallet af pile er g63.
Dette er Grahams nummer.
Relaterede sider
- Knuths op-pil notation
Spørgsmål og svar
Spørgsmål: Hvem definerede Grahams nummer?
Svar: Ronald Graham definerede Grahams tal.
Spørgsmål: Hvilket område af matematikken arbejdede Ronald Graham inden for, da han definerede tallet?
A: Ronald Graham arbejdede inden for et område af matematikken kaldet Ramsey-teori, da han definerede tallet.
Sp: Hvad beviste Ronald Graham med sit problem?
Svar: Ronald Graham beviste, at svaret på hans problem var mindre end Grahams tal.
Spørgsmål: Hvor stort er Grahams tal sammenlignet med andre tal, der bruges i matematiske beviser?
Svar: Grahams tal er et af de største tal, der nogensinde er blevet brugt i et matematisk bevis.
Spørgsmål: Hvis hvert enkelt ciffer i tallet blev skrevet, ville det så passe ind i det observerbare univers?
Svar: Selv hvis hvert enkelt ciffer i Grahams tal blev skrevet med den mindst mulige skrift, ville det stadig være for stort til at passe ind i det observerbare univers.
Spørgsmål: Kan man på nogen måde beregne eller anslå, hvor stort dette tal er?
Svar: Der er ingen præcis måde at beregne eller estimere, hvor stort dette særlige naturlige tal er, da det endnu ikke er blevet fuldt ud fastlagt.
Spørgsmål: Hvorfor findes der et så stort naturligt tal, og hvilket formål tjener det?
Svar: Dette meget store naturlige tal findes, fordi det blev brugt af Ronald Grahm som en del af et matematisk bevis og tjener som en øvre grænse for hans løsning.
Søge