[FOM] Large cardinals and finite combinatorics
joeshipman at aol.com
Tue Jun 12 17:51:23 EDT 2007
Friedman has found some combinatorial statements equivalent to the
1-consistency of various large cardinals, but these statements are not
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"?
AOL now offers free email to everyone. Find out more about what's free
from AOL at AOL.com.
More information about the FOM