[FOM] Graham's Number, Re: 271:Clarification of Smith Article

[Andrew Aberdein]

On 27 Mar 2006, at 4:42 pm, Andreas Weiermann wrote:

> It might be of some general interest to see whether the lower bound in
> H. Friedman's Theorem 2 (cited below) is larger
> than the Graham number holding the world record for
> a natural number appearing in a mathematical proof.

>> THEOREM 2. Theorem 1 can be proved in strictly finite mathematics. 
>> However,
>> any such proof in ACA_0 + Pi12-BI must use at least 2^[1000] symbols.
>>
>> Here 2^[1000] is an exponential stack of 2's of height 1000.

The Graham number is much, much larger than this.

The Knuth up arrow, here written as ^, is defined by:

a ^ n  = a to the n-th power
a ^^ n = an exponential stack of a's of height n.
a [k arrows] n = a [k-1 arrows] stack of a's of height n.

So Friedman's number could be written as 2^^1000.

Graham's number has been stated in several different ways, some of them 
larger than others.  When I asked him, the one which Ron Graham himself 
endorsed was Martin Gardner's version.  He has Graham's number = G(63), 
where G(0) = 3^^^^3 and G(n) = 3^...^3 with G(n-1) arrows.  Even G(0) 
would be vastly larger than 2^^1000.

I have seen some much smaller statements of Graham's number, including 
3^^^^^^43 and 3^...^3 with 64 ^s, which I suspect are misstatements.  
Each of these numbers are between G(0) and G(1), and therefore also 
larger than Friedman's number.

Regards, Andrew

--
A n d r e w   A b e r d e i n,  P h. D.
Humanities and Communication,
Florida Institute of Technology,
Melbourne, Florida 32901-6975, U.S.A.
[+1] (321) 674 8368   http://my.fit.edu/~aberdein/