10
$\begingroup$

Laver showed in 1995 that the period of the first row of certain Laver tables is unbounded, assuming that a rank-into-rank cardinal exists.

The most accessible proof of his result that I was able to find is in chapter 12 of Patrick Dehornoy's Braids and Self-Distributivity (Springer 2000). The proof is quite technical. Laver defines an algebra on the models of set-theory - technically, on certain elementary embeddings of huge sets. He defines two operations on such elementary embeddings, quotients out certain large infinities to get finite results, and investigates their properties.

My question is: why should elementary embeddings of ZFC have anything to do with the periodicity of these finite tables?

More generally, is there some guiding intuition I can use to make sense of Laver's very complex construction? I find it difficult to understand how Laver could have plowed through this weird and intricate technical construction without having some reason to think it would lead to some kind of specific finitary result.

$\endgroup$
4
  • 8
    $\begingroup$ Have you tried reading Laver's paper? The introduction seems to explain it pretty well - he was interested in the algebra given by elementary embeddings generated by a single one, and then one can associate to it a family of finite algebras. These algebras are essentially Laver tables. $\endgroup$
    – Wojowu
    Dec 16, 2021 at 12:05
  • 7
    $\begingroup$ The point is that Laver's interest didn't begin from those tables/finite algebras. They arose naturally when he was studying those elementary embeddings. Before Theorem 11 he defines certain finite algebras which he denotes $\mathscr A_{j,n}$, and after the theorem he notes they can be described directly as tables you are familiar with. $\endgroup$
    – Wojowu
    Dec 16, 2021 at 12:17
  • 8
    $\begingroup$ The comments by @Wojowu are the answer to your question. The embeddings arising from very large cardinals are important in their own right. So Laver studied their interrelationships, and they led him to self-distributive algebras, like the Laver tables. That this resulted in unexpected finitary information was "good luck", but it's the sort of luck that often comes from deeply investigating natural mathematical structures (like those elementary embeddings). $\endgroup$ Dec 16, 2021 at 12:34
  • 1
    $\begingroup$ @AndreasBlass Wojowu Is there some intuition or heuristic for why this intricate algebra from embeddings should yield this particular periodic property? And why it requires such huge cardinals to get it all to work? I find the proof very hard to follow because of its rabbit-out-of-a-hat quality. It really is an astounding result though isn't it! $\endgroup$
    – kdog
    Dec 16, 2021 at 19:54

2 Answers 2

13
$\begingroup$

As was already mentioned in the comments, the premise of the question is somewhat backwards. Indeed, looking at Laver's paper, the combinatorial structures now known as Laver tables were not at all his initial motivation. Instead, from the start and throughout Laver was interested in elementary embeddings of some $V_\lambda$ and the algebras they produce under certain operations, one of which is "applying" one elementary embedding to another. This operation satisfies a relation $a(bc)=(ab)(ac)$ (and thus defines what is sometimes known as a shelf). For instance, Laver has shown that the shelf generated by one elementary embedding $j$, which he denotes $\mathscr A_j$, is free.

Now, $\mathscr A_j$ is a large and complicated algebra. One of Laver's results (essentially Theorem 11 of the paper) is that the study of $\mathscr A_j$ can be reduced to studying certain finite algebras, $\mathscr A_{j,n}$, which have $2^n$ elements. These algebras are again defined using elementary embeddings, but as Laver explains after the theorem, these algebras also have a completely explicit description not referring to any large cardinals - these are the Laver tables that you are familiar with.

Therefore Laver's motivation was studying certain algebras which arise naturally if you are interested in large cardinals. Any relation to finitary structures was an afterthought to him.

$\endgroup$
3
  • $\begingroup$ Thanks! That's really interesting and useful information. I added a comment above - I still wonder if there is some intuition, some overarching reason that this particular algebra of elementary embeddings, which is so hard to understand, should yield this particular property (see my comment above in the comments). $\endgroup$
    – kdog
    Dec 16, 2021 at 20:02
  • $\begingroup$ by the way, please let me know if there is a clearer online transfer of the link to Laver's paper. The version you linked to is so faded it is difficult to read in spots. I do not even understand Laver's notation in Lemma 1: what is ($V_\lambda,$ $\epsilon$, $A$) supposed to mean? $\endgroup$
    – kdog
    Dec 22, 2021 at 5:13
  • $\begingroup$ @kdog It is a structure of a set $V_\lambda$ together with membership relation $\varepsilon$ and a predicate for elements of $A$. $\endgroup$
    – Wojowu
    Dec 22, 2021 at 10:57
4
$\begingroup$

Richard Laver was a set theorist throughout his entire career, so he was originally motivated to investigate very large cardinals and the resulting finite algebras from a set theoretic perspective, but today it is probably best to think of the Laver tables $A_{n}$ as algebraic objects within a much larger class of algebraic objects. With this algebraic perspective, large cardinals are a source of examples of such algebraic objects, and large cardinals also provide the consistency strength to prove more theorems.

Red herrings

As one looks more closely at the Laver tables and similar structures, one observes that some ideas are essential while others are non-essential or just special cases of a more general idea including the following notions.

  1. The Laver tables, algebras generated by 1 elementary embedding-The Laver tables are simply the one-generator finite algebraic structures within much broader classes of algebraic structures such as the nilpotent left-distributive algebras. The Laver tables are analogous to the finite cyclic groups while the broader class of algebraic structures is analogous to the class of all groups. You get a more accurate analogy by relating the Laver tables to the cyclic $p$-groups while the broader class of algebraic structures is analogous to the class of all $p$-groups and related objects such as pro-$p$-groups (in this analogy, $\mathcal{E}_{\lambda}$ corresponds to a dense $G_{\delta}$-subset of a pro-$p$-group). And yes, these generalizations of Laver tables have the same kind of intricate structure and periodicity that appears with the Laver tables.

  2. Set theory-While the Laver tables originally arose from set theory, they along with similar algebraic structures can easily be studied without any reference to large cardinals. Furthermore, some of these structures similar to Laver tables cannot arise from large cardinals.

  3. Composition-The composition of elementary embeddings and a more general composition like operation in the Laver tables should be thought of as operations that are constructed from the self-distributive application operation.

  4. Rank-into-rank embeddings-One can construct self-distributive algebras such as the Laver tables from $n$-huge cardinals rather than rank-into-rank cardinals.

  5. A linearly ordered set of critical points-The notion of a critical point is essential for Laver tables, but it can be generalized quite a bit. The direct product of two Laver tables $A_{5}\times A_{6}$ will have a partially ordered but not linearly ordered set of critical points. In algebra, one would typically like to study classes of algebraic structures that are closed under taking products (or at least finite product), quotients, and substructures. One should therefore consider algebraic structures with a partially ordered set of critical points.

Starting from nilpotence

The nilpotent left-distributive algebras are algebraic structures that resemble the algebras of elementary embeddings and Laver tables. The notion of a nilpotent left-distributive algebras is very easy to define, but it precisely captures the notion of a critical point and composition operation as well as other notions related to Laver table for finite algebras (infinite algebras will require a different axiomatization though, but that is a completely open research direction). I admit that very little is known about nilpotent left-distributive algebras (these structures will become more understandable in the future when people write papers on these structures), but they so far seem to be one of the most important classes of algebraic structures that contains the Laver tables but does not contains objects like non-trivial quandles which are quite different from the Laver tables.

If $(X,*)$ is a left-distributive algebra, then define terms $x^{[n]},x_{[n]}$ for $n\geq 1$ recursively by letting $x^{[1]}=x_{[1]}=x$ and $x^{[n+1]}=x*x^{[n]},x_{[n+1]}=x_{[n]}*x$.

Suppose that $(X,*)$ is a left-distributive algebra. We say that an element $x\in X$ is a left-identity if $x*y=y$ for each $y\in Y$. We say that a subset $L\subseteq X$ is a left-ideal if $x*y\in L$ whenever $y\in L$. Let $\mathrm{Li}(X)$ be the collection of all left-identities in $(X,*)$. Then we say that $(X,*)$ is a nilpotent left-distributive algebra if

  1. $\mathrm{Li}(X)$ is a left-ideal, and

  2. for each $x\in X$, there exists an $n$ where $x^{[n]}\in\mathrm{Li}(X)$.

The algebra $\mathcal{E}_{\lambda}/\equiv^{\gamma}$ is nilpotent because of the following prominent result:

Theorem (Kunen inconsistency): Suppose that $j:V_{\alpha}\rightarrow V_{\alpha}$ is a non-trivial elementary embedding. Let $\lambda=\lim_{n\in\omega}j^{n}(\mathrm{crit}(j))$. Then $\alpha=\lambda$ or $\alpha=\lambda+1$.

Let us now obtain critical points and a composition operation from nilpotent left-distributive algebras.

If $(X,*)$ is a left-distributive algebra, then for each $n\in\omega$, define an operation $*_{n}$ recursively by letting $x*_{0}y=y,x*_{n+1}y=x*_{n}(x*y)=x*(x*_{n}y)$. Each $*_{n}$ is self-distributive. If $(X,*)$ is a nilpotent-self-distributive algebra, then the sequence $(x*_{n}y)_{n}$ is eventually constant for each $x,y\in X$, so let $x*_{\infty}y=\lim_{n\rightarrow\infty}x*_{n}y$. Define a relation $\preceq$ on $(X,*)$ by setting $x\preceq y$ if and only if $x*_{\infty}y\in\mathrm{Li}(X)$. Then $\preceq$ is a pre-ordering. Let $\simeq$ be the equivalence relation defined by letting $x\simeq y$ iff $x\preceq y\preceq x$. Let $\mathrm{crit}[X]=X/\simeq$, and let $\mathrm{crit}(x)$ denote the equivalence class containing $x$ whenever $x\in X$. Then $\mathrm{crit}[X]$ is partially ordered by letting $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ if and only if $x\preceq y$. One can define an implication operation on $\mathrm{crit}[X]$ by letting $\mathrm{crit}(x)\rightarrow\mathrm{crit}(y)=\mathrm{crit}(x*_{\infty}y).$

Suppose that $X$ is a self-distributive algebra where $\mathrm{Li}(X)$ is a non-empty left-ideal. Suppose that $L$ is a poset. Then we say that a mapping $\phi:X\rightarrow L$ is a critical point operator if it satisfies the following conditions:

i. $\phi(x)\leq\phi(y)\leftrightarrow\phi(x)\leq\phi(x*y)$.

ii. $\phi(y)\leq\phi(x*y)$.

iii. $\phi(y)\leq\phi(z)\rightarrow\phi(x*y)\leq\phi(x*z)$.

iv. $\phi(x)=1$ if and only if $x\in\mathrm{Li}(X)$.

v. $\phi(x)=\phi(x*x)$ if and only if $x\in\mathrm{Li}(X).$

vi. For all $x\in X$, there is a $c\in X$ with $c*c\in\mathrm{Li}(X)$ and $\phi(x)=\phi(c)$.

If $X$ is a nilpotent LD-system, then the mapping $\mathrm{crit}:X\rightarrow\mathrm{crit}[X]$ is a critical point operator.

Proposition: Suppose that $X$ is a finite left distributive algebra, and $\phi:X\rightarrow L$ is a critical point operator. Then $(X,*)$ is nilpotent, and $\phi(x)\leq\phi(y)$ if and only if $\mathrm{crit}(x)\leq\mathrm{crit}(y)$

The above proposition shows that the finite nilpotent left-distributive algebras are just the finite left-distributive algebras with a sensible (though partially ordered) notion of critical points. One can obtain nilpotent self-distributive algebras from rank-into-rank embeddings without even invoking Kunen's inconsistency result.

If $X$ is a nilpotent self-distributive algebra, and $\alpha\in\mathrm{crit}[X]$, then there is some $c\in X$ with $c*c\in\mathrm{Li}(X)$ and $\mathrm{crit}(c)=\alpha.$ Define a congruence $\equiv^{\alpha}$ on $X$ by letting $x\equiv^{\alpha}y$ if and only if $c*x=c*y$.

The nilpotent left-distributive algebras can also be endowed with a composition operation in some sense.

An LD-monoid is an algebraic structure $(X,*,\circ,1)$ where $(X,*)$ is an LD-system, $(X,\circ,1)$ is a monoid, and

  1. $x*1=1,1*x=x$,

  2. $x\circ y=(x*y)\circ x$,

  3. $x*(y\circ z)=(x*y)\circ(x*z)$,

  4. $(x\circ y)*z=x*(y*z)$.

A nilpotent LD-monoid is an LD-monoid $(X,*,\circ,1)$ where $(X,*)$ is nilpotent and $\text{Li}(X)=\{1\}$.

If $(X,*,\circ,1)$ is a nilpotent LD-monoid, then $(\mathrm{crit}[X],\rightarrow,\wedge,1)$ is a Heyting semilattice where $\mathrm{crit}(x)\wedge\mathrm{crit}(y)=\mathrm{crit}(x\circ y)$.

Suppose that $(X,*)$ is a nilpotent left-distributive algebra where $\text{Li}(X)$ is a non-empty left-ideal.

Let $\simeq$ be the smallest equivalence relation on $\bigcup_{n\in\omega}X^{n}$ that satisfies the following conditions whenever $m\geq 0,n\geq 0$, and $x_{1},\dots,x_{m},y_{1},\dots,y_{n}\in X$:

i. $(x_{1},\dots,x_{m},a,y_{1},\dots,y_{n})\simeq(x_{1},\dots,x_{m},y_{1},\dots,y_{n})$ whenever $a\in\mathrm{Li}(X)$.

ii. $(x_{1},\dots,x_{m},a,b,y_{1},\dots,y_{n})\simeq(x_{1},\dots,x_{m},a*b,a,y_{1},\dots,y_{n})$ whenever $a,b\in X$

Let $\text{LDM}(X)=\bigcup_{n\in\omega}X^{n}/\simeq$. We shall let $[x_{1},\dots,x_{m}]$ denote the equivalence class containing $(x_{1},\dots,x_{m})$. Then $\text{LDM}(X)$ is a LD-monoid with operations defined by $[x_{1},\dots,x_{m}]\circ[y_{1},\dots,y_{n}]=[x_{1},\dots,x_{m},y_{1},\dots,y_{n}]$ and $[]*[y_{1},\dots,y_{n}]=[y_{1},\dots,y_{n}]$ and $[x_{1},\dots,x_{m+1}]*[y_{1},\dots,y_{n}]= [x_{1},\dots,x_{m}]*[x_{m+1}*y_{1},\dots,x_{m+1}*y_{n}]$.

If $(X,*)$ is a nilpotent LD-system, then $\text{LDM}(X)$ is a nilpotent LD-monoid, and the mapping $e:X\rightarrow\text{LDM}(X)$ defined by $e(x)=[x]$ is a homomorphism. This is therefore a construction that allows one to obtain a composition operation from the self-distributive operation.

Proposition: A finite left-distributive algebra $(X,*)$ where $\text{Li}(X)$ is a left-ideal is nilpotent if and only if $\text{LDM}(X)$ is finite.

The nilpotent left-distributive algebras generated by a single element in a sense are just the Laver tables.

Proposition: Suppose that $X$ is a finite monogenic left-distributive algebra such that $\mathrm{Li}(X)\neq\emptyset$. Then $X\simeq A_{n}$.

Proposition: The Laver tables $A_{n}$ are up-to-isomorphism, the only finite monogenic nilpotent left-distributive algebras.

Theorem: Suppose that $X$ is a monogenic nilpotent left-distributive algebra. Then either $X$ is isomorphic to a Laver table $n$ or $X$ is infinite and for all $n$, we have $X/\equiv^{\alpha_{n}}\simeq A_{n}$ where $\alpha_{n}=\mathrm{crit}(x_{[2^{n}]})$.

Theorem: Suppose that there exists a rank-into-rank cardinal. Then the Laver tables $A_{n}$ are the only nilpotent monogenic left-distributive algebras.

Laver-like algebras

For the order of operations, the implied parentheses are grouped on the left so that $a*b*c*d=((a*b)*c)*d$.

A left-distributive algebra $(X,*)$ is Laver-like precisely when

  1. $\mathrm{Li}(X)$ is a left-ideal and

  2. whenever $x_{n}\in X$ for each $n\in\omega$, there exists some $N$ where $x_{0}*\dots*x_{N}\in\mathrm{Li}(X)$.

Every Laver-like algebra is nilpotent, and if $(X,*)$ is Laver-like, then $\mathrm{crit}[X]$ is well-ordered. Every quotient algebra $\mathcal{E}_{\lambda}/\equiv^{\gamma}$ of rank-into-rank embeddings is Laver-like (this is the Laver-Steel theorem).

Theorem: Every Laver-like generated by a single element is isomorphic to a Laver table $A_{n}$.

Proposition: If $(X,*)$ is a reduced Laver-like algebra, then mapping $e_{X}:X\rightarrow\text{LDM}(X)$ is an isomorphism (so there exists some composition operation $\circ$ such that $(X,*,\circ,1)$ is an LD-monoid).

The Laver-like algebras therefore more closely resemble the algebras of elementary embeddings, but there are still reduced Laver-like algebras that cannot arise from elementary embeddings.

Construction of new nilpotent left-distributive algebras from old ones

The construction of the Laver tables is actually a special case of a technique for constructing new nilpotent self-distributive algebras from old ones.

While there are plenty of ways to construct new nilpotent left-distributive algebras from old ones, it is most fruitful to construct new nilpotent left-distributive algebras that have the same number of generators as the old algebras but which have a higher poset of critical points (more specifically if $Y$ is the new left-distributive algebra, and $X$ is the old one, then $\textrm{crit}(Y)$ is isomorphic to $\textrm{crit}(X)\cup\{\mu\}$ where $\mu$ is a new element defined by letting $\mu>\gamma$ for each $\gamma\in\textrm{crit}(X)$). The best way to achieve this is to begin with a finite left-distributive algebra $(X,*)$ that is generated by a system $(x_{a})_{a\in A}$ and obtain a new finite left-distributive algebra $(Y,*)$ that is generated by $(y_{a})_{a\in A}$ and where $\mathrm{crit}[Y]\setminus\{1\}$ has a maximum element $\gamma$ and there there is a (necessarily surjective) homomorphism $\phi:Y\rightarrow X$ with $\ker(\phi)=(\equiv^{\gamma})$ and where $\phi(y_{a})=x_{a}$ for each $a\in A$. Observe that in this case, $X$ is isomorphic to a subalgebra $\{c*y\mid y\in Y\}$ of $Y$ where $\mathrm{crit}(c)=\gamma$.

A way to build the algebra $Y$ from $X$ algorithmically is to start off with $X$ and then repeatedly construct new algebras $Z$ that contain $X$ as a subalgebra but where $Z$ is generated by $X\cup\{r\}$ for some element $r\in Z$ and where $Z\setminus\{r\}$ is a subalgebra of $Z$ that can be written as a sub-direct product of previously constructed algebras.

When one applies this technique of extending algebras to larger algebras one element at a time, one goes from $A_{n}$ to $A_{n+1}$ by traversing through all the intermediate algebras $\{x\in A_{n+1}\mid x\geq r\}$ where $1\leq r\leq 2^{n}+1$.

$\endgroup$
1
  • $\begingroup$ Thanks very much for this fascinating analysis. To be honest it will take me some time fully to digest it. I'm at the level now of just trying to understand the proof of Kunen's bound on the limit of iterates of a critical point and will reach the other parts of your answer as time goes on. $\endgroup$
    – kdog
    Dec 20, 2021 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.