Wiki Googologie
Advertisement

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

External Links

Advertisement