# [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.
```