[FOM] Large cardinals and finite combinatorics

[joeshipman@aol.com]

Friedman has found some combinatorial statements equivalent to the 
1-consistency of various large cardinals, but these statements are not 
simple.

However, there is an example of a simple combinatorial statement whose 
only known proof requires an extremely large cardinal; we just don't 
know whether the large cardinal is necessary (though we know that PRA 
is not powerful enough to prove it).

For a given natural number n, there is a well-defined operation * on 
the integers mod 2^n which can be calculated recursively using 2 rules:

p*1 = (p+1) mod 2^n

p*(q*r)=(p*q)*(p*r)  [self-distributive law]


The 2^n x 2^n "multiplication table" is called the "nth Laver table".

It can be shown with large cardinals (using an embedding from a rank 
into a rank) that for any k there exists n such that, in the nth Laver 
table, (1*1) does not equal (1*(2^k)).

Dougherty has shown that for k=5, n, if it exists, must be at least 
A(9,A(8,A(8,255))) where A is an Ackermann function, and that PRA 
cannot prove that n(k) exists.

The existence of n(k) is a good candidate for the simplest example of 
an arithmetical or combinatorial proposition provable from a large 
cardinal but not known to be provable in ZFC (actually, even simpler is 
the existence of n(5), which says that for some n, the nth Laver table 
has (1*1) not equal to (1*33).)

Does anyone know of any other candidates for "simplest theorem we can 
only prove with large cardinals"?

-- JS
________________________________________________________________________
AOL now offers free email to everyone.  Find out more about what's free 
from AOL at AOL.com.