Posts filed under ‘logic’

Laver tables and “unprovable” statements

Laver tables are combinatorial objets whose definition is surprisingly simple. However, they do have somewhat weird properties, which come from their relationship with questions of set theorists (namely, how do elementary embeddings of models of set theory behave). It also have connections with braid group theory, which I do not know. The Wikipedia article gives the basic facts, a survey by Patrick Dehornoy will give relevant bibliography, and friends of mine wrote an undergraduate thesis on the subject (in French).

The most basic definition of Laver tables is the Cayley table of a self-distributive binary operation. This means we define an exotic operation \star on a set of numbers, and fill a square table with the outcomes of this operation. The required property of this operation is a \star (b \star c) = (a \star b) \star (a \star c). This operation does not share properties with our usual operations, which are often associative of commutative. Suppose the set of numbers is \{0, 1, ..., n-1\} and that 1 acts on the right by shifts : i \star 1 = i+1 and (n-1) \star 1 = 0. (more…)

20 February 2009 at 4:51 pm 4 comments