Set theory seminar notes-April 1, 2016-Generalized Laver tables part II.

On April 1, 2016 I gave a talk at 10:00a.m. at the Set Theory seminar at the Graduate Center titled Generalized Laver Tables Part II. This talk is a continuation of the same topic I talked about here last semester, and this talk is a part of the research project generalizations of Laver tables that I have been investigating since July of 2015. Here are the notes for the talk.

Classical Laver tables

The $n$-th classical Laver table is the unique algebra $A_{n}=(\{1,…,2^{n}\},*)$ where

  1. $x*1=x+1$ whenever $x<2^{n}$
  2. $2^{n}*1=1$
  3. $x*(y*z)=(x*y)*(x*z)$.

Let $\mathcal{E}_{\lambda}$ denote the set of all elementary embeddings $j:V_{\lambda}\rightarrow V_{\lambda}$
Suppose that $j\in\mathcal{E}_{\lambda}$ is a rank-into-rank embedding and $\gamma<\lambda$. Then there is some $n$ where $\langle j\rangle/\equiv^{\gamma}$ is isomorphic to $A_{n}$.

Generalizations of Laver tables

The following list of algebras lists out all the generalizations of the notion of a classical Laver table which I have investigated.

Classical Laver tables-These algebras have one generator and one binary operation. The braid group acts on these algebras.

Generalized Laver table-These algebras have multiple generators, but one binary operation. These algebras are always locally finite.

Endomorphic Laver tables-These algebras can have possibly multiple generators, possibly multiple operations, and the operations can have arbitrary arity. Endomorphic Laver tables are usually infinite. Endomorphic Laver tables seem to be very difficult to compute in part due to the immense size of the output. There are generalizations of the notion of a braid group (positive braid monoid) that act on the endomorphic Laver tables. For instance, suppose that $G_{n}$ is the group presented by $\{\sigma_{i}\mid 0\leq i<n\}$ with relations $\sigma_{i}\sigma_{i+1}\sigma_{i+2}\sigma_{i}=\sigma_{i+2}\sigma_{i}\sigma_{i+1}\sigma_{i+2}$ and
$\sigma_{i}\sigma_{j}=\sigma_{j}\sigma_{i}$ whenever $|i-j|>2$. Let $G_{n}^{+}$ be the monoid presented by the same generators and relations. Then $G_{n}^{+}$ acts on $X^{n-2}$. Furthermore, the algebra $G_{\omega}$ can be given a ternary self-distributive operation which I conjecture gives rise to free ternary self-distributive algebras.
Partially endomorphic Laver tables-These algebras have multiple generators, multiple operations, the operations can have arbitrary arity, only some of the operations distribute with each other. These algebras are always infinite.

Twistedly endomorphic Laver tables-These algebras have multiple generators, multiple operations, operations can have arbitrary arity, these algebras satisfy the twisted self-distributivity laws such as $t(a,b,t(x,y,z))=t(t(a,b,x),t(b,a,y),t(a,b,z))$. Any semigroup can be used to generate more complicated twisted self-distributivity identities. Twistedly endomorphic Laver tables do not seem to arise in any way from algebras of elementary embeddings.

So far I am the only researcher working on the generalizations of Laver tables although around last July another researcher (a knot theorist) has expressed interest and has some ideas that one can research about generalized Laver tables.

Permutative LD-systems

Suppose that $*$ is a binary function symbol. Then define the Fibonacci terms $t_{n}(x,y)$ by the following rules:

  1. $t_{1}(x,y)=y$
  2. $t_{2}(x,y)=x$
  3. $t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y)$.

For example, if $x=y=1$ and $*$ is addition $+$, then $t_{n}(x,y)$ is simply the $n$-th Fibonacci number.

The first few Fibonacci terms are

  • $t_{3}(x,y)=x*y$
  • $t_{4}(x,y)=(x*y)*x$
  • $t_{5}(x,y)=((x*y)*x)*(x*y)$
  • $t_{6}(x,y)=(((x*y)*x)*(x*y))*((x*y)*x).$

The algebra of elementary embeddings $(\mathcal{E}_{\lambda},*,\circ)$ satisfies the braid identity $j\circ k=(j*k)\circ j$. Furthermore, by applying the braid identity multiple times, we obtain $j\circ k=(j*k)\circ j=((j*k)*j)\circ(j*k)=…=t_{n+1}(j,k)\circ t_{n}(j,k).$


Now suppose that $(\kappa_{n})_{n\in\omega}$ is a cofinal increasing sequence in $\lambda$. Then define a metric $d$ on $\mathcal{E}_{\lambda}$ by letting $d(j,k)=\frac{1}{n}$ whenever $j\neq k$ where $n$ is the least natural number with $j|_{V_{\kappa_{n}}}\neq k|_{V_{\kappa_{n}}}$ and where $d(j,j)=0$.

$\mathbf{Proposition:}$ $(\mathcal{E}_{\lambda},d)$ is a complete metric space without isolated points.

$\textbf{Corollary:}$ $|\mathcal{E}_{\lambda}\mid\geq 2^{\aleph_{0}}$.

$\textbf{Proof:}$ This follows from the fact that every complete metric space without any isolated points has cardinality at least continuum.

$\textbf{Proposition:}$ Let $j,k\in\mathcal{E}_{\lambda}$. Then

  1. if $\textrm{crit}(j)>\textrm{crit}(k)$, then
    1. $t_{2n+1}(j,k)\rightarrow j\circ k$
    2. $t_{2n}(j,k)\rightarrow Id_{V_{\lambda}}$
  2. if $\textrm{crit}(j)\leq\textrm{crit}(k)$, then
    1. $t_{2n}(j,k)\rightarrow j\circ k$
    2. $t_{2n+1}(j,k)\rightarrow Id_{V_{\lambda}}$.

An LD-system is an algebra $(X,*)$ that satisfies the identity $x*(y*z)=(x*y)*(x*z)$.

Let $X$ be an LD-system. An element $x\in X$ is said to be a left-identity if $x*y=y$ for each $y\in X$. Let $\textrm{Li}(X)$ denote the set of all left-identities of $X.$ A subset $L\subseteq X$ is said to be a left-ideal if $y\in L$ implies that $x*y\in L$ as well.

An LD-system $X$ is said to be permutative if

  1. $\textrm{Li}(X)$ is a left-ideal in $X$ and
  2. for all $x,y\in X$ there exists an $n$ with $t_{n}(x,y)\in \textrm{Li}(X)$.

The motivation behind the notion of a permutative LD-system is that the permutative LD-systems capture the notion that the Fibonacci terms converge to the identity without any reference to any topology.

Example: $\mathcal{E}_{\lambda}/\equiv^{\gamma}$ is a reduced permutative LD-system.

A permutative LD-system is said to be reduced if $|\textrm{Li}(X)|=1$.

Proposition: Let $X$ be a permutative LD-system. Let $\simeq$ be the equivalence relation on $X$ where $x\simeq y$ iff $x=y$ or if $x,y\in \textrm{Li}(X)$. Then $\simeq$ is a congruence on $X$ and $X/\simeq$ is a reduced permutative LD-system.

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

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

Example: $(\mathcal{E}_{\lambda},*,\circ,1)$ is an LD-monoid.

Theorem: Suppose that $(X,*)$ is a reduced permutative LD-system with left-identity $1$. Then define an operation $\circ$ on $X$ where $x\circ y=t_{n+1}(x,y)$ where $n$ is the least natural number with $t_{n}(x,y)=1$.  Then $(X,*,\circ,1)$ is an LD-monoid.

Critical points:

Define $x^{n}*y=x*(x*(…*(x*y)))$ ($n$-copies of $x$). More formally, $x^{0}*y=y$ and $x^{n+1}*y=x*(x^{n}*y)=x^{n}*(x*y)$.

Suppose that $X$ is a permutative LD-system and $x,y\in X$. Then define $\textrm{crit}(x)\leq \textrm{crit}(y)$ iff there exists some $n$ where $x^{n}*y\in \textrm{Li}(X)$.

Theorem: Suppose that $X$ is a permutative LD-system. Then

  1. $\textrm{crit}(x)\leq \textrm{crit}(x)$
  2. $\textrm{crit}(x)\leq \textrm{crit}(y)$ and $\textrm{crit}(y)\leq \textrm{crit}(z)$ implies $\textrm{crit}(x)\leq \textrm{crit}(z)$.
  3. $\textrm{crit}(x)\leq \textrm{crit}(y)$ implies $\textrm{crit}(r*x)\leq \textrm{crit}(r*y)$.
  4. $\textrm{crit}(x)$ is maximal in $\{\textrm{crit}(y)\mid y\in X\}$ if and only if $x\in \textrm{Li}(X)$.
  5. $\{\textrm{crit}(x)\mid x\in X\}$ is a linear ordering.
  6. If $(X,*)$ is reduced, then $\textrm{crit}(x\circ y)=Min(\textrm{crit}(x),\textrm{crit}(y)).$

Let $\textrm{crit}[X]=\{\textrm{crit}(x)\mid x\in X\}$. If $x\in X$, then define the mapping $x^{\sharp}:\textrm{crit}[X]\rightarrow \textrm{crit}[X]$ by $x^{\sharp}(\textrm{crit}(y))=\textrm{crit}(x*y)$.

The motivation behind the function $x^{\sharp}$ is the basic fact about elementary embeddings that if $j,k\in\mathcal{E}_{\lambda}$, then $j(\textrm{crit}(k))=\textrm{crit}(j*k)$.

    Theorem: Suppose that $X$ is a permutative LD-system.

  1. $x^{\sharp}(\alpha)\geq\alpha$ for $x\in X,\alpha\in \textrm{crit}[X]$.
  2. $x^{\sharp}(\alpha)>\alpha$ if and only if $\alpha\geq \textrm{crit}(x)$ and $\alpha\neq Max(\textrm{crit}[X])$.
  3. Let $A=\{\alpha\in \textrm{crit}[X]\mid x^{\sharp}(\alpha)\neq Max(\textrm{crit}[X])\}$. Then $x^{\sharp}|_{A}$ is injective.

$\mathbf{Theorem}$ Let $X$ be a permutative LD-system and let $\simeq$ be a congruence on $X$. Then there is a partition $A,B$ of $\textrm{crit}[X]$ such that $A$ is a downwards closed subset, $B$ is an upwards closed subset, and

    1. whenever $\textrm{crit}(x)\in B$ there is some $y\in \textrm{Li}(X)$ with $x\simeq y$ and
    2. whenever $\textrm{crit}(x)\in A$ and $x\simeq y$ we have $\textrm{crit}(x)=\textrm{crit}(y)$.

Furthermore, if $X$ is reduced, then $\simeq$ is also a congruence with respect to the composition operation $\circ$.

For example, suppose that $X$ is a permutative LD-system and $\alpha\in\textrm{crit}[X]$. Then there exists some $r\in X$ with $\textrm{crit}(r)=\alpha$ and where $r*r\in \textrm{Li}(X)$. Therefore define an equivalence relation $\equiv^{\alpha}$ by letting $x\equiv^{\alpha}y$ if and only if $r*x=r*y$. Then $\equiv^{\alpha}$ is a congruence on $X$ that does not depend on the choice of $r$. In the above, theorem, if $\simeq$ is the equivalence relation $\equiv^{\alpha}$, then $A=\{\beta\in\textrm{crit}[X]\mid\beta<\alpha\}$ and $B=\{\beta\in\textrm{crit}[X]\mid\beta\geq\alpha\}$.

Generalized Laver tables

Let $A$ be a set. Let $A^{+}$ denote the set of all strings over the alphabet $A$. Let $\preceq$ denote the prefix ordering on $A$. Let $L\subseteq A^{+}$ be a downwards closed subset such that $L\cap B^{+}$ is finite whenever $B\in[A]^{<\omega}$. Let $M=\{\mathbf{x}a\mid\mathbf{x}\in L,a\in A\}\cup A$. Let $F=M\setminus L$. Then there is a unique operation $*$ such that

  1. $\mathbf{x}*a=\mathbf{x}a$ whenever $\mathbf{x}\in L,a\in A$
  2. $\mathbf{x}*\mathbf{y}=\mathbf{y}$ whenever $\mathbf{x}\in F$.
  3. $\mathbf{x}*\mathbf{y}a=(\mathbf{x}*\mathbf{y})*\mathbf{x}a$ whenever $\mathbf{x},\mathbf{y}\in F,a\in A$.

The algebra $(M,*)$ is called a pre-generalized Laver table. If $(M,*)$ is an LD-system, then we shall call $(M,*)$ is a generalized Laver table. Every generalized Laver table is a permutative LD-system.

Let $|\mathbf{x}|$ denote the length of a string $\mathbf{x}$.
If $A$ is a set, then $(A^{\leq 2^{n}})^{+}=\{\mathbf{x}\in A^{+}:|\mathbf{x}|\leq 2^{n}\}$ is a generalized Laver table. The operation $*$ on $(A^{\leq 2^{n}})^{+}$ can be computed very quickly here even though
$$|(A^{\leq 2^{n}})^{+}|=|A|\cdot\frac{|A|^{2^{n}}-1}{|A|-1}.$$
The only hinderence to computing $*$ seems to be the length of the output.

$\mathbf{Theorem:}$ Suppose that $j\in\mathcal{E}_{\lambda},\alpha<\lambda$. Then $(j*j)(\alpha)\leq j(\alpha)$.

$\mathbf{Proof:}$ Let $\beta$ be the least ordinal with $j(\beta)>\alpha$. Then
$$V_{\lambda}\models\forall x<\beta,j(x)\leq\alpha,$$
so by applying elementarity, we have
$$V_{\lambda}\models\forall x < j(\beta),j*j(x)\leq j(\alpha).$$
Therefore, since $\alpha < j(\beta)$, we have $(j*j)(\alpha)\leq j(\alpha)$.

$\mathbf{Example:}$ There exists a generalized Laver table $M$ over the alphabet $\{0,1\}$ with $|M|=64$ and $x\in M,\alpha\in \textrm{crit}[X]$ with $(x*x)^{\sharp}(\alpha)>x^{\sharp}(\alpha)$. In particular, whenever $\simeq$ is a congruence on $M$ where if $x\simeq y$ then $\textrm{crit}(x)=\textrm{crit}(y)$ then $M/\simeq$ is not isomorphic to any subalgebra of an algebra of the form $\mathcal{E}_{\lambda}/\equiv^{\gamma}$.