Movatterモバイル変換

Getal van Graham

Uit Wikipedia, de vrije encyclopedie

Hetgetal van Graham, genoemd naar dewiskundige Ronald Graham, is een onvoorstelbaar grootnatuurlijk getal. Het werd algemeen erkend als het grootste getal dat ooit in een serieuswiskundig bewijs is gebruikt, en was als zodanig opgenomen in hetGuinness 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 alsgoogol ofgoogolplex er volkomen bij in het niet vallen. Het getal van Graham is te groot om in dewetenschappelijke notatie te worden uitgedrukt, zelfs met meervoudig opeenvolgende exponenten. Het getal dient te worden weergegeven als een element van eenrij getallen gedefinieerd met behulp vanKnuths pijlomhoognotatie. Met behulp vanelementaire 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 deRamsey-theorie. De probleemstelling is als volgt:

Stel je eenn-dimensionalehyperkubus voor, en verbind elk paarknooppunten met elkaar zodat een completegraaf op 2ⁿ knooppunten ontstaat. Beschilder vervolgens elke kant in deze graaf in een van twee kleuren. Wat is de kleinste waarde vann waarvoor elk van de mogelijke beschilderingen ten minste één completeplanaire 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 datn ≥ 6 moet zijn. Jarenlang geloofden sommige deskundigen datn = 6, hetgeen nogal een schril contrast is met het getal van Graham, een bewezen bovenlimiet. In 2001 beweesGeoff Exoo echter datn ≥ 11, en in 2008 Jerome Barkley datn ≥ 13 moet zijn.^[2]

Definitie van het getal van Graham

[bewerken |brontekst bewerken]

Zoals gezegd is het getal van Graham alleen te schrijven in depijlomhoognotatie. 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 dewetenschappelijke notatie of meervoudigexponentië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 alsexponent voor hetgrondtal 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 getalF. 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 63recursieve stappen, waarin steeds $G_{i}$ wordt gebruikt als het aantal omhoog-pijltjes in $G_{i+1}$ , het getal van Graham verkregen.