100
pages

Les tables de Laver sont une famille infinie de magmas pouvant donner naissance à une fonction de grand nombre.[1] Ils ont été définis pour la première fois par Richard Laver en 1992. Pour n ≥ 0, la table de Laver de taille n est un opérateur binaire sur , avec les propriétés suivantes :

\begin{eqnarray*} a \star 0 & = & 0 \\ a \star 1 & = & a+1 \\ a \star b & = & (a \star (b-1)) \star (a \star 1) \ (b \neq 0,1) \end{eqnarray*}

The period of the function $$a \mapsto 1 \star a$$ depends on n, and we will denote it by p(n). The first few values of p(n) are $$1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, \ldots$$ (OEIS A098820), a slow-growing function. p is provably divergent in the system ZFC + "there exists a rank-into-rank cardinal." Unfortunately, the latter axiom is so strong that there are a few specialists who doubt the consistency of the system. Since the divergence of p has not been proven otherwise, it remains an unsolved problem.

Let q(n) be minimal so that p(q(n)) ≥ 2n, the "pseudoinverse" of p. q is a fast-growing function that is total iff p is divergent. The first few values of q are 0, 2, 3, 5, 9. The existence of q(n) for n ≥ 5 has not even been confirmed, but under the assumption of the previously mentioned axiom, Randall Dougherty has shown that $$q^n(1) > f_{\omega+1}(\lfloor \log_3 n \rfloor - 1)$$ in a slightly modified version of the hiérarchie de croissance rapide,[2] and q(5) > f9(f8(f8(254))).[3] Dougherty has expressed pessimism about the complexity of proving better lower bounds, and no upper bounds are known as of yet.

Patrick Dehornoy provides a simple algorithm for filling out Laver tables.[4]

The expected size of q(6) was very large[5], however no reasoning or proof has been given other than "the strength of set theories required to prove a computable function total", however a computable function f needs not outgrow all computable functions provably total in a set theory that is known to be required to prove that the function is total.

## Explanation

For $$\lambda \in \text{Lim}$$, let $$\mathcal{E}_\lambda$$ be the set of elementary embeddings $$V_\lambda \mapsto V_\lambda$$. For $$j,k \in \mathcal{E}_\lambda$$, we define the operator $$j\cdot k$$ (or jk) as follows:

$j \cdot k = \bigcup_{\alpha < \lambda} j(k \cap V_\alpha)$

Here, $$k \cap V_\alpha$$ is the restriction of k to the subset $$\{x \in V_\alpha \mid (x,k(x)) \in V_\alpha\}$$. Although k is not an element of the domain $$V_\lambda$$ of j, $$k \cap V_\alpha$$ is an element of it. That is, we "apply j to k approaching $$V_\lambda$$." This operator has j(kl) = (jk)(jl), a property known as left-selfdistributivity. Laver table is known to be isomorphic to a magma associated to $$\mathcal{E}_\lambda$$ using critical points, and hence is deeply related to a large cardinal axiom.[1]

## Examples

The cyclic group can be identified with the set $$\{1,2,3,\ldots,2^n\}$$ through the canonical projection. A size-2 Laver table is shown below:[4]

1 2 3 4
1 2 4 2 4
2 3 4 3 4
3 4 4 4 4
4 1 2 3 4

The entries at the first row repeat with a period of 2, and therefore $$p(2) = 2$$.

A size-3 Laver table is shown below:[4]

1 2 3 4 5 6 7 8
1 2 4 6 8 2 4 6 8
2 3 4 7 8 3 4 7 8
3 4 8 4 8 4 8 4 8
4 5 6 7 8 5 6 7 8
5 6 8 6 8 6 8 6 8
6 7 8 7 8 7 8 7 8
7 8 8 8 8 8 8 8 8
8 1 2 3 4 5 6 7 8

The entries at the first row repeat with a period of 4, and therefore p(3) = 4.

## Sources

1. 1,0 et 1,1 Laver, Richard. On the Algebra of Elementary Embeddings of a Rank into Itself. Retrieved 2014-08-23.. (Bien que le dernier mot du titre de l'article soit "itself", il y a une faute de frappe "Inself" dans le titre de la page arXiv.)
2. With $$f_{\alpha + 1}(n) = f_\alpha^{n + 1}(1)$$
3. Dougherty, Randall. Critical points in an algebra of elementary embeddings. Retrieved 2014-08-23.
4. 4,0 4,1 et 4,2 Dehornoy, Patrick. Laver Tables (starting on slide 26). Retrieved 2018-12-11.
5. https://googology.wikia.org/wiki/Laver_table?diff=prev&oldid=81250