Ubersketch (talk | contribs) No edit summary Tag: Visual edit |
mNo edit summary |
||
| Line 1: | Line 1: | ||
[[File:Laver 6.jpeg|thumb|220x220px|The sixth Laver table as a grayscale bitmap.]] |
[[File:Laver 6.jpeg|thumb|220x220px|The sixth Laver table as a grayscale bitmap.]] |
||
| − | '''Laver tables''' are an infinite family of magmas that may give rise to a large number function.<ref>{{cite web|first=Richard|last=Laver|url=http://arxiv.org/abs/math.LO/9204204|title=On the Algebra of Elementary Embeddings of a Rank into Inself|accessdate=2014-08-23}}</ref> They were first defined by Richard Laver in 1992. For \(n \geq 0\), |
+ | '''Laver tables''' are an infinite family of magmas that may give rise to a large number function.<ref>{{cite web|first=Richard|last=Laver|url=http://arxiv.org/abs/math.LO/9204204|title=On the Algebra of Elementary Embeddings of a Rank into Inself|accessdate=2014-08-23}}</ref> They were first defined by Richard Laver in 1992. For \(n \geq 0\), the size-\(n\) Laver table is a binary operator \(\star\) over \(\mathbb{Z}_{2^n}\), with the following properties: |
\[a \star 1 = a + 1 \pmod{2^n}\] |
\[a \star 1 = a + 1 \pmod{2^n}\] |
||
\[a \star (b \star c) = (a \star b) \star (a \star c)\] |
\[a \star (b \star c) = (a \star b) \star (a \star c)\] |
||
| − | The period of the function \(a \mapsto 1 \star a\) |
+ | 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|098820}}), 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)) \geq 2^n\), 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 \geq 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 [[fast-growing hierarchy]],<ref>With \(f_{\alpha + 1}(n) = f_\alpha^{n + 1}(1)\)</ref> and \(q(5) > f_9(f_8(f_8(254)))\).<ref>{{cite web|first=Randall|last=Dougherty|url=http://arxiv.org/abs/math.LO/9205202|title=Critical points in an algebra of elementary embeddings|accessdate=2014-08-23}}</ref> Dougherty has expressed pessimism about the complexity of proving better lower bounds, and no upper bounds are known as of yet. |
Let \(q(n)\) be minimal so that \(p(q(n)) \geq 2^n\), 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 \geq 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 [[fast-growing hierarchy]],<ref>With \(f_{\alpha + 1}(n) = f_\alpha^{n + 1}(1)\)</ref> and \(q(5) > f_9(f_8(f_8(254)))\).<ref>{{cite web|first=Randall|last=Dougherty|url=http://arxiv.org/abs/math.LO/9205202|title=Critical points in an algebra of elementary embeddings|accessdate=2014-08-23}}</ref> Dougherty has expressed pessimism about the complexity of proving better lower bounds, and no upper bounds are known as of yet. |
||
| Line 17: | Line 17: | ||
\[j \cdot k = \bigcup_{\alpha < \lambda} j(k \cap V_\alpha)\] |
\[j \cdot k = \bigcup_{\alpha < \lambda} j(k \cap V_\alpha)\] |
||
| − | That is, we "apply \(j\) to \(k\) approaching \(V_\lambda\)." This operator has \(j(kl) = (jk)(jl)\), a property known as ''left-distributivity''. [incomplete, please expand] |
+ | 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-distributivity''. [incomplete, please expand] |
== Examples == |
== Examples == |
||
| Line 75: | Line 75: | ||
== See also == |
== See also == |
||
{{Combinatorial googologisms}} |
{{Combinatorial googologisms}} |
||
| + | |||
| + | [[ja:レイバーのテーブル]] |
||
[[Category:Functions]] |
[[Category:Functions]] |
||
[[Category:Numbers]] |
[[Category:Numbers]] |
||
Revision as of 23:46, 8 June 2019
The sixth Laver table as a grayscale bitmap.
Laver tables are an infinite family of magmas that may give rise to a large number function.[1] They were first defined by Richard Laver in 1992. For \(n \geq 0\), the size-\(n\) Laver table is a binary operator \(\star\) over \(\mathbb{Z}_{2^n}\), with the following properties:
\[a \star 1 = a + 1 \pmod{2^n}\] \[a \star (b \star c) = (a \star b) \star (a \star c)\]
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)) \geq 2^n\), 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 \geq 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 fast-growing hierarchy,[2] and \(q(5) > f_9(f_8(f_8(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]
Explanation
For \(\lambda \in \text{Lim}\), let \(\mathcal{E}_\lambda\) be the set of elementary embeddings \(V_\lambda \mapsto V_\lambda\) (explained on the rank-into-rank cardinal page). 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-distributivity. [incomplete, please expand]
Examples
A size-2 Laver table is shown below:
| 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:
| 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
- ↑ Laver, Richard. On the Algebra of Elementary Embeddings of a Rank into Inself. Retrieved 2014-08-23.
- ↑ With \(f_{\alpha + 1}(n) = f_\alpha^{n + 1}(1)\)
- ↑ Dougherty, Randall. Critical points in an algebra of elementary embeddings. Retrieved 2014-08-23.
- ↑ Dehornoy, Patrick. Laver Tables (starting on slide 26). Retrieved 2018-12-11.