Skip to main content
1 of 1

Laver tables often involve unconventional types of induction. In fact, constructing the Laver tables and proving that they are self-distributive involves an unusual double and triple induction.

Consider the following Lemmas.

$\textbf{Lemma 1}$ For all $N$ there exists a unique binary operation $*$ on $\{1,...,N\}$ such that

  1. $x*1=x+1$ whenever $x<N$

  2. $N*x=x$ for all $x$ and

  3. $x*y=(x*(y-1))*(x+1)$ whenever $x<N$ and $y>1$.

One proves Lemma 1 for each $x*y$ by a double induction which is descending on $x$ and for each $x$ the induction is ascending on $y$.

In fact, many results about Laver tables are proven using a descending then ascending double induction.

$\textbf{Lemma 2}$ For all $N$ the algebra $(\{1,...,N\},*)$ satisfies the self-distributivity identity $x*(y*z)=(x*y)*(x*z)$ if and only if $x*N=N$ whenever $x\in\{1,...,N\}.$

The direction $\rightarrow$ in Lemma 2 is straightforward, but the direction $\leftarrow$ is by descending induction on $x$, then for each $x$ one proceeds by ascending induction on $y$ and for each $y$, one uses ascending induction on $z$. Notice how one uses a descending induction for each variable in $x*(y*z)$ to the left of the operation $*$ and one uses an ascending induction for each variable to the right of the operation $*$. Similarly, one uses a descending induction for $x$ in $x*y$ in Lemma 1 and one uses an ascending induction on $y$ in $x*y$ in Lemma 1 because $x$ is on the left side of $*$ and $y$ is on the right side of $*$.

Lemma 2 is needed to prove the following theorem.

$\textbf{Theorem}$ The algebra $(\{1,...,N\},*)$ satisfies the self-distributivity identity $x*(y*z)=(x*y)*(x*z)$ if and only if $N=2^{n}$ for some $n$.

The self-distributive algebra $(\{1,...,2^{n}\},*)$ is known as the $n$-th classical Laver table.