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

Laver 表（Laver Table）是 Richard Laver 在 1992 年提出的一个增长速度很快的表。<ref>Laver, Richard. [http://arxiv.org/abs/math.LO/9204204 On the Algebra of Elementary Embeddings of a Rank into Itself]. Retrieved 2014-08-23. </ref>

=== 定义 ===
考虑作用于 <math>\{1,\cdots,2^n\}</math> 上的二元运算 <math>\star_n</math>，它满足如下条件：

\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>猫山にゃん太. Laver table - レイバーのテーブル[EB/OL]. 2022. [https://n-nekoyama.github.io/googology/laver_table/. 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> 将不是存在且唯一的。

我们定义如下函数的周期为 p(n):

* <math>2^n\rightarrow2^n</math>
* <math>a\mapsto1\star_na</math>

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

=== 取值 ===

==== Laver 表 ====
以下展示了前 6 个 Laver 表。<ref>Dehornoy, Patrick. [https://web.archive.org/web/20230429003832/https://www.lmno.cnrs.fr/archives/dehornoy/Talks/Dyz.pdf Laver Tables] (starting on slide 26). Retrieved 2018-12-11.</ref>
{| 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
|}

=== 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>

=== 强度 ===
Dougherty 证明了 <math>q^n(1) > f_{\omega+1} (\lfloor log3 n\rfloor - 1)</math>。<ref>Dougherty, Randall. [http://arxiv.org/abs/math.LO/9205202 Critical points in an algebra of elementary embeddings.] Retrieved 2014-08-23.</ref>

事实上，二元关系 <math>\star_n</math> 的存在唯一性以及函数 p(n) 的发散性并非显然的结果，它实际上与集合论中的嵌入有着深刻的联系。

事实上，p(n) 发散的结论是在 I3 公理下才能够得到证明的。因此，作为一个快速增长的函数，q(n) 的完全性（即在所有自然数 n 下都有定义）在 ZFC+I3

下得到了证明。用 [[googology]] 更熟悉（但是并不严格）的说法，我们目前认为 q(n) 的增长率的上界为 [[证明论序数|PTO(ZFC+I3)]]。

== 参考资料 ==
{{默认排序:相关问题}}
[[分类:记号]]