[FOM] Large cardinals and finite combinatorics
joeshipman@aol.com
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
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.
More information about the FOM
mailing list