Getal van Graham

Het getal van Graham, genoemd naar de wiskundige Ronald Graham, is een onvoorstelbaar groot natuurlijk getal. Het werd algemeen erkend als het grootste getal dat ooit in een serieus wiskundig bewijs is gebruikt, en was als zodanig opgenomen in het Guinness Book of Records. Ondertussen zijn er enkele andere getallen die een praktisch nut hebben en groter zijn dan het getal van Graham, maar het getal van Graham was het eerste dat in grootte vér boven andere gekende grote getallen ging,^[1] en heeft zijn mythische status behouden.

Het getal van Graham is zo groot, dat zelfs gigantische getallen als googol of googolplex er volkomen bij in het niet vallen. Het getal van Graham is te groot om in de wetenschappelijke notatie te worden uitgedrukt, zelfs met meervoudig opeenvolgende exponenten. Het getal dient te worden weergegeven als een element van een rij getallen gedefinieerd met behulp van Knuths pijlomhoognotatie. Met behulp van elementaire getaltheorie is echter wel uit te rekenen hoe het eind van het getal eruitziet. De laatste tien cijfers van het getal van Graham zijn ...2464195387.

Grahams probleem[bewerken | brontekst bewerken]

Het getal van Graham is een bovenlimiet van de oplossing van een vraagstuk uit de tak van wiskunde die bekendstaat als de Ramsey-theorie. De probleemstelling is als volgt:

Stel je een n-dimensionale hyperkubus voor, en verbind elk paar knooppunten met elkaar zodat een complete graaf op 2ⁿ knooppunten ontstaat. Beschilder vervolgens elke kant in deze graaf in een van twee kleuren. Wat is de kleinste waarde van n waarvoor elk van de mogelijke beschilderingen ten minste één complete planaire subgraaf van vier knooppunten bevat met alle kanten van dezelfde kleur?

Een oplossing voor dit vraagstuk is nog niet bekend. Er kan bewezen worden dat het getal van Graham een theoretische bovengrens is van dit vraagstuk. In 1971 bewezen Graham en Rothschild dat n ≥ 6 moet zijn. Jarenlang geloofden sommige deskundigen dat n = 6, hetgeen nogal een schril contrast is met het getal van Graham, een bewezen bovenlimiet. In 2001 bewees Geoff Exoo echter dat n ≥ 11, en in 2008 Jerome Barkley dat n ≥ 13 moet zijn.^[2]

Definitie van het getal van Graham[bewerken | brontekst bewerken]

Zoals gezegd is het getal van Graham alleen te schrijven in de pijlomhoognotatie. Om het getal van Graham aan te duiden definiëren we de volgende rij:

{\begin{matrix}G_{0}=4\end{matrix}}

G_{1}=3\underbrace {\uparrow \uparrow \uparrow \uparrow } _{G_{0}=4}3

G_{2}=3\underbrace {\uparrow \uparrow \uparrow \cdots \uparrow } _{G_{1}}3

G_{n}=3\underbrace {\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots \uparrow } _{G_{(n-1)}}3

In deze reeks is het getal van Graham gelijk aan $G_{64}$ .

Toelichting[bewerken | brontekst bewerken]

Het getal van Graham is zo onvoorstelbaar groot dat zelfs G₁ al niet meer in de wetenschappelijke notatie of meervoudig exponentiële notatie is op te schrijven. Zie onderstaande uitwerking om dit te illustreren:

3\uparrow 3=3^{3}=27

3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7625597484987

3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 7625597484987=\underbrace {3^{3^{3^{3^{\cdots ^{3}}}}}} _{7625597484987}

ofwel 3³ berekenen, en vervolgens steeds weer, namelijk 7.625.597.484.985 maal, het berekende getal gebruiken als exponent voor het grondtal 3.

Dit is een getal dat het menselijke bevattingsvermogen ver te boven gaat, vele malen groter dan bijvoorbeeld 10^googolplex (= googolplexian = $10^{10^{10^{100}}}$ ). En het is nog niet eens G₁.

Noem het voorgaande getal F. Dan geldt dat
$G_{1}=3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow F=\underbrace {3\uparrow \uparrow 3\uparrow \uparrow \dots \uparrow \uparrow 3} _{F\mathrm {\,kopie{\ddot {e}}n\,van\,} 3}$

Vervolgens wordt na 63 recursieve stappen, waarin steeds $G_{i}$ wordt gebruikt als het aantal omhoog-pijltjes in $G_{i+1}$ , het getal van Graham verkregen.