查看“︁Laver Table”︁的源代码

'''Laver 表'''，是一种无限族的原群，它们产生了一个可能增长极快的函数。它们由理查德·拉弗（Richard Laver）于 1992 年首次定义。<ref>Laver, R. (1992). On the Algebra of Elementary Embeddings of a Rank into Itself. [https://arxiv.org/abs/math/9204204 arXiv:math/9204204] '''[math.LO]'''. </ref>

=== 定义 ===
Laver 表基于以下定理：对于每个<math>n\geq0</math>，在[[序数#有限序数|有限序数]]集 <math>\{1,\cdots,2^n\}</math> 上存在唯一的二元运算 <math>\star_n</math>，<ref>Philippe, B. (2018). Laver tables and combinatorics. ''(EB/OL)''. Available at: https://hal.science/hal-01883830/file/Laver-Tables.pdf</ref>满足：

\begin{eqnarray*}a \star_n 0 & = & 0 \\a \star_n 1 & = & (a+1) \mod 2^n \\a \star_n i & = & (a \star_n (i-1)) \star_n (a \star_n 1) \ (i \neq 0,1)\end{eqnarray*}

Laver 表 <math>A_n</math> 定义为唯一的取值为 <math>a\ \star_n\ b</math> 的 <math>2^n\times2^n</math> 表。Laver 表可以用此<ref>n-nekoyama (n.d.). Laver table - レイバーのテーブル. ''(EB/OL)''. Available at: https://n-nekoyama.github.io/googology/laver_table/</ref>进行计算。

注意这一定理仅适用于 2 的[[高德纳箭头#乘方|幂]]。假如我们考虑的二元运算作用于一般的 <math>\{1,\cdots,a\}</math> 上，其中 <math>a\neq 2^n</math>，则这样的二元运算 <math>\star_n</math> 将不是存在且唯一的。

我们定义函数 <math>a\mapsto1\star_na</math> 的周期为 p(n)。

定义 q(n) 为函数 p(n) 的“伪逆”，即 <math>q(n)=\min\{N|p(N)\geq2^n\}</math>。

==== 强度 ====
p(n) 的前几个值为1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, …，<ref>A098820 - OEIS. ''(EB/OL), OEIS''. Available at: https://oeis.org/A098820</ref>这是一个增长缓慢的函数。

p 在 [[ZFC公理体系|ZFC]]+存在 rank-into-rank 基数（或 ZFC+I3）公理系统中被证明是发散的。但遗憾的是，后者这一公理过于强大，以至于少数专家对其系统的相容性存疑。由于 p 的发散性尚未通过其他方式证明，这仍是一个未解问题。用 [[googology]] 更熟悉（但是并不严格）的说法，我们目前认为 q(n) 的增长率的上界为 [[证明论序数|PTO(ZFC+I3)]]。

q 是一个快速增长的函数，其全域性当且仅当 p 发散。q(n) 的前几个值为 0, 2, 3, 5, 9。尽管 n≥5 时 q(n) 的存在性尚未被确认，但在上述公理假设下，Randall Dougherty 证明，在[[快速增长层级]]结构的一个稍作修改的版本中，<math>q^n(1)>f_{\omega+1}(\lfloor\log_3n\rfloor-1)</math>，且 <math>q(5) > f_9 (f_8 (f_8(254)))</math>。<ref>Dougherty, R. (1992). Critical points in an algebra of elementary embeddings. [https://arxiv.org/abs/math/9205202 arXiv:math/9205202] '''[math.LO]'''.</ref>Dougherty 对证明更优下界的可能性表示悲观，目前也没有更严格的上界已知。Laver 表是[[序数#递归序数|可计算的]]，因此 q(n)在较小时会被[[忙碌海狸函数]] Σ(n) 超越。

Patrick Dehornoy 提供了一种填充 Laver 表的简单算法。<ref name=":0">Dehornoy, Patrick. [https://web.archive.org/web/20230429003832/https://www.lmno.cnrs.fr/archives/dehornoy/Talks/Dyz.pdf Laver Tables]</ref>然而，每个表格的大小以及 <math>\star</math> 运算所定义的循环群的规模都呈指数级增长，因此这目前是一个NP问题。

q(6) 的预期规模非常大<ref name=":0">Dehornoy, Patrick. [https://web.archive.org/web/20230429003832/https://www.lmno.cnrs.fr/archives/dehornoy/Talks/Dyz.pdf Laver Tables]</ref>，但除了“证明可计算函数全域所需的集合论强度”外，没有给出其他理由或证明。然而，一个可计算函数f并不需要超过所有在已知需要证明该函数全域的集合论中可证明全域的可计算函数。
[[文件:Laver6_new_PNG.png|缩略图|第六个 Laver 表的灰度图]]

==== 解释 ====
对于[[序数#极限序数|极限序数]] <math>\lambda</math>，设 <math>\mathcal{E}_\lambda</math> 为所有[[初等嵌入]] <math>V_\lambda \mapsto V_\lambda</math> 的集合。对 <math>j,k \in \mathcal{E}_\lambda</math>，我们定义运算符 <math>j\cdot k</math>（或记为 <math>jk</math>）如下：

<math>j \cdot k = \bigcup_{\alpha < \lambda} j(k \cap V_\alpha)</math>

此处，<math>k \cap V_\alpha</math> 表示 <math>k</math> 在集合 <math>\{x \in V_\alpha \mid (x,k(x)) \in V_\alpha\}</math> 上的限制。虽然 <math>k</math> 本身不属于 <math>j</math> 的[[ZFC公理体系#定义域|定义域]] <math>V_\lambda</math>，但 <math>k \cap V_\alpha</math> 是它的元素。这一操作可理解为“对逐渐接近 <math>V_\lambda</math> 的 <math>k</math> 应用 <math>j</math>”。该运算符满足性质 <math>j(kl) = (jk)(jl)</math>，此性质被称为左自分布性（left-selfdistributivity）。已知 Laver 表与通过临界点关联到 <math>\mathcal{E}_\lambda</math> 的原群同构，因此与[[大基数公理]]密切相关。

=== 取值 ===

==== Laver 表 ====
以下展示了前 6 个 Laver 表。<ref name=":0" />
<div style="text-wrap: nowrap;">
{| class="wikitable mw-collapsible mw-collapsed"
|+<math>\star_0</math> 的 Laver 表
!
!1
|-
|'''1'''
|1
|}
{| class="wikitable mw-collapsible mw-collapsed"
|+<math>\star_1</math> 的 Laver 表
!
!1
!2
|-
|'''1'''
|2
|2
|-
|'''2'''
|1
|2
|}
{| class="wikitable mw-collapsible mw-collapsed"
|+<math>\star_2</math> 的 Laver 表
!
!1
!2
!3
!4
|-
|1
|2
|4
|2
|4
|-
|2
|3
|4
|2
|4
|-
|3
|4
|4
|4
|4
|-
|4
|1
|2
|3
|4
|}
{| class="wikitable mw-collapsible mw-collapsed"
|+<math>\star_3</math> 的 Laver 表
|-
!
!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
|}
{| class="wikitable mw-collapsible mw-collapsed"
|+<math>\star_4</math> 的 Laver 表
|-
!
!1
!2
!3
!4
!5
!6
!7
!8
!9
!10
!11
!12
!13
!14
!15
|16
|-
!1
|2
|12
|14
|16
|2
|12
|14
|16
|2
|12
|14
|16
|2
|12
|14
|16
|-
!2
|3
|12
|15
|16
|3
|12
|15
|16
|3
|12
|15
|16
|3
|12
|15
|16
|-
!3
|4
|8
|12
|16
|4
|8
|12
|16
|4
|8
|12
|16
|4
|8
|12
|16
|-
!4
|5
|6
|7
|8
|13
|14
|15
|16
|5
|6
|7
|8
|13
|14
|15
|16
|-
!5
|6
|8
|14
|16
|6
|8
|14
|16
|6
|8
|14
|16
|6
|8
|14
|16
|-
!6
|7
|8
|15
|16
|7
|8
|15
|16
|7
|8
|15
|16
|7
|8
|15
|16
|-
!7
|8
|16
|8
|16
|8
|16
|8
|16
|8
|16
|8
|16
|8
|16
|8
|16
|-
!8
|9
|10
|11
|12
|13
|14
|15
|16
|9
|10
|11
|12
|13
|14
|15
|16
|-
!9
|10
|12
|14
|16
|10
|12
|14
|16
|10
|12
|14
|16
|10
|12
|14
|16
|-
!10
|11
|12
|15
|16
|11
|12
|15
|16
|11
|12
|15
|16
|11
|12
|15
|16
|-
!11
|12
|16
|12
|16
|12
|16
|12
|16
|12
|16
|12
|16
|12
|16
|12
|16
|-
!12
|13
|14
|15
|16
|13
|14
|15
|16
|13
|14
|15
|16
|13
|14
|15
|16
|-
!13
|14
|16
|14
|16
|14
|16
|14
|16
|14
|16
|14
|16
|14
|16
|14
|16
|-
!14
|15
|16
|15
|16
|15
|16
|15
|16
|15
|16
|15
|16
|15
|16
|15
|16
|-
!15
|16
|16
|16
|16
|16
|16
|16
|16
|16
|16
|16
|16
|16
|16
|16
|16
|-
!16
|1
|2
|3
|4
|5
|6
|7
|8
|9
|10
|11
|12
|13
|14
|15
|16
|}
{| class="wikitable mw-collapsible mw-collapsed"
|+<math>\star_5</math> 的 Laver 表
|-
!
!1
!2
!3
!4
!5
!6
!7
!8
!9
!10
!11
!12
!13
!14
!15
!16
!17
!18
!19
!20
!21
!22
!23
!24
!25
!26
!27
!28
!29
!30
!31
!32
|-
!1
|2
|12
|14
|16
|18
|28
|30
|32
|2
|12
|14
|16
|18
|28
|30
|32
|2
|12
|14
|16
|18
|28
|30
|32
|2
|12
|14
|16
|18
|28
|30
|32
|-
!2
|3
|12
|15
|16
|19
|28
|31
|32
|3
|12
|15
|16
|19
|28
|31
|32
|3
|12
|15
|16
|19
|28
|31
|32
|3
|12
|15
|16
|19
|28
|31
|32
|-
!3
|4
|8
|12
|16
|20
|24
|28
|32
|4
|8
|12
|16
|20
|24
|28
|32
|4
|8
|12
|16
|20
|24
|28
|32
|4
|8
|12
|16
|20
|24
|28
|32
|-
!4
|5
|6
|7
|8
|13
|14
|15
|16
|21
|22
|23
|24
|29
|30
|31
|32
|5
|6
|7
|8
|13
|14
|15
|16
|21
|22
|23
|24
|29
|30
|31
|32
|-
!5
|6
|24
|30
|32
|6
|24
|30
|32
|6
|24
|30
|32
|6
|24
|30
|32
|6
|24
|30
|32
|6
|24
|30
|32
|6
|24
|30
|32
|6
|24
|30
|32
|-
!6
|7
|24
|31
|32
|7
|24
|31
|32
|7
|24
|31
|32
|7
|24
|31
|32
|7
|24
|31
|32
|7
|24
|31
|32
|7
|24
|31
|32
|7
|24
|31
|32
|-
!7
|8
|16
|24
|32
|8
|16
|24
|32
|8
|16
|24
|32
|8
|16
|24
|32
|8
|16
|24
|32
|8
|16
|24
|32
|8
|16
|24
|32
|8
|16
|24
|32
|-
!8
|9
|10
|11
|12
|13
|14
|15
|16
|25
|26
|27
|28
|29
|30
|31
|32
|9
|10
|11
|12
|13
|14
|15
|16
|25
|26
|27
|28
|29
|30
|31
|32
|-
!9
|10
|28
|30
|32
|10
|28
|30
|32
|10
|28
|30
|32
|10
|28
|30
|32
|10
|28
|30
|32
|10
|28
|30
|32
|10
|28
|30
|32
|10
|28
|30
|32
|-
!10
|11
|28
|31
|32
|11
|28
|31
|32
|11
|28
|31
|32
|11
|28
|31
|32
|11
|28
|31
|32
|11
|28
|31
|32
|11
|28
|31
|32
|11
|28
|31
|32
|-
!11
|12
|16
|28
|32
|12
|16
|28
|32
|12
|16
|28
|32
|12
|16
|28
|32
|12
|16
|28
|32
|12
|16
|28
|32
|12
|16
|28
|32
|12
|16
|28
|32
|-
!12
|13
|14
|15
|16
|29
|30
|31
|32
|13
|14
|15
|16
|29
|30
|31
|32
|13
|14
|15
|16
|29
|30
|31
|32
|13
|14
|15
|16
|29
|30
|31
|32
|-
!13
|14
|16
|30
|32
|14
|16
|30
|32
|14
|16
|30
|32
|14
|16
|30
|32
|14
|16
|30
|32
|14
|16
|30
|32
|14
|16
|30
|32
|14
|16
|30
|32
|-
!14
|15
|16
|31
|32
|15
|16
|31
|32
|15
|16
|31
|32
|15
|16
|31
|32
|15
|16
|31
|32
|15
|16
|31
|32
|15
|16
|31
|32
|15
|16
|31
|32
|-
!15
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|16
|32
|-
!16
|17
|18
|19
|20
|21
|22
|23
|24
|25
|26
|27
|28
|29
|30
|31
|32
|17
|18
|19
|20
|21
|22
|23
|24
|25
|26
|27
|28
|29
|30
|31
|32
|-
!17
|18
|28
|30
|32
|18
|28
|30
|32
|18
|28
|30
|32
|18
|28
|30
|32
|18
|28
|30
|32
|18
|28
|30
|32
|18
|28
|30
|32
|18
|28
|30
|32
|-
!18
|19
|28
|31
|32
|19
|28
|31
|32
|19
|28
|31
|32
|19
|28
|31
|32
|19
|28
|31
|32
|19
|28
|31
|32
|19
|28
|31
|32
|19
|28
|31
|32
|-
!19
|20
|24
|28
|32
|20
|24
|28
|32
|20
|24
|28
|32
|20
|24
|28
|32
|20
|24
|28
|32
|20
|24
|28
|32
|20
|24
|28
|32
|20
|24
|28
|32
|-
!20
|21
|22
|23
|24
|29
|30
|31
|32
|21
|22
|23
|24
|29
|30
|31
|32
|21
|22
|23
|24
|29
|30
|31
|32
|21
|22
|23
|24
|29
|30
|31
|32
|-
!21
|22
|24
|30
|32
|22
|24
|30
|32
|22
|24
|30
|32
|22
|24
|30
|32
|22
|24
|30
|32
|22
|24
|30
|32
|22
|24
|30
|32
|22
|24
|30
|32
|-
!22
|23
|24
|31
|32
|23
|24
|31
|32
|23
|24
|31
|32
|23
|24
|31
|32
|23
|24
|31
|32
|23
|24
|31
|32
|23
|24
|31
|32
|23
|24
|31
|32
|-
!23
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|24
|32
|-
!24
|25
|26
|27
|28
|29
|30
|31
|32
|25
|26
|27
|28
|29
|30
|31
|32
|25
|26
|27
|28
|29
|30
|31
|32
|25
|26
|27
|28
|29
|30
|31
|32
|-
!25
|26
|28
|30
|32
|26
|28
|30
|32
|26
|28
|30
|32
|26
|28
|30
|32
|26
|28
|30
|32
|26
|28
|30
|32
|26
|28
|30
|32
|26
|28
|30
|32
|-
!26
|27
|28
|31
|32
|27
|28
|31
|32
|27
|28
|31
|32
|27
|28
|31
|32
|27
|28
|31
|32
|27
|28
|31
|32
|27
|28
|31
|32
|27
|28
|31
|32
|-
!27
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|28
|32
|-
!28
|29
|30
|31
|32
|29
|30
|31
|32
|29
|30
|31
|32
|29
|30
|31
|32
|29
|30
|31
|32
|29
|30
|31
|32
|29
|30
|31
|32
|29
|30
|31
|32
|-
!29
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|30
|32
|-
!30
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|31
|32
|-
!31
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|32
|-
!32
|1
|2
|3
|4
|5
|6
|7
|8
|9
|10
|11
|12
|13
|14
|15
|16
|17
|18
|19
|20
|21
|22
|23
|24
|25
|26
|27
|28
|29
|30
|31
|32
|}
</div>
==== q 函数 ====
事实上 <math>p(n)</math> 是一个增长速度非常缓慢的函数。

我们有

* <math>q(0) = 0</math>
* <math>q(1) = 2</math>
* <math>q(2)=3</math>
* <math>q(3)=5</math>
* <math>q(4)=9</math>
* <math>q(5) > f_9 (f_8 (f_8(254)))</math>，其中这里的 [[增长层级#快速增长层级|FGH]] 改版定义为 <math>f_{\alpha+1}(n)=f_\alpha^{n+1}(n)</math>

== 参考资料 ==
{{默认排序:相关问题}}
[[分类:记号]]
<references />
[[分类:集合论相关]]