Getal van Graham

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het getal van Graham, genoemd naar de wiskundige Ronald Graham, is een onvoorstelbaar groot natuurlijk getal. Het wordt algemeen erkend als het grootste getal dat ooit in een serieus wiskundig bewijs is gebruikt, en is als zodanig opgenomen in het Guinness Book of Records.

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 er uit ziet. De laatste tien cijfers van het getal van Graham zijn ...2464195387.

Grahams probleem[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 2n knooppunten ontstaat. Beschilder vervolgens elke kant in deze graaf in één 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. [1]

Definitie van het getal van Graham[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]

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


3\uparrow3=3^3=27

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

 3\uparrow\uparrow\uparrow3 =
 3\uparrow\uparrow7625597484987 =
 \underbrace{3^{3^{3^{3^{\cdots^3}}}} }_{7625597484987}
ofwel 33 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 10googolplex. En het is nog niet eens G1.

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.

Zie ook[bewerken]

Externe links[bewerken]


Bronnen, noten en/of referenties