白黒のビットマップで表したサイズ 6 のレイバーのテーブル
レイバーのテーブル(Laver table)とは、1992年にリチャード・レイバーによって定義された巨大関数の素となるマグマ（二項演算付き集合）の無限族 \(P_0, P_1, P_2, \ldots\) である[1]。\(n \geq 0\) に対し、 サイズ \(n\) のレイバーのテーブル \(P_n\) は \(\mathbb{Z}_{2^n}\) (位数 \(2^n\) の巡回群であり、\(\{0,1,\ldots, 2^n-1\}\) と自然に同一視される) の上で定義された二項演算子 \(\star_n\) であり、以下を満たす：
\begin{eqnarray*} & & a \star_n 0 = 0 \\ & & a \star_n 1 = a + 1 \pmod{2^n} \\ & & a \star_n b = (a \star_n (b - 1)) \star_n (a \star_n 1) \quad (1 < b < 2^n-1) \\ \end{eqnarray*}
関数 \(a \mapsto 1 \star_n a\) の周期は \(n\) の関数になり、それを \(p(n)\) と表すことにする。\(n \leq 56\) における \(p(n)\) の値は \(1, 1, 2, 4, 4, 8, 8, 8, 8, 16, \ldots, 16\) (OEIS A098820)となり、ある一定の値以上は増えないかのように見える。\(p\) が発散することは \(\textrm{ZFC}\) 公理系に階層内階層基数が存在するという公理を加えた体系で証明されている。残念ながら階層内階層基数の存在は \(\textrm{ZFC}\) 公理系との無矛盾性を深刻に疑う人がいてもおかしくはないほど強い公理である[注 1]。\(p\) が発散することは階層内階層基数の存在を用いずには示されていないため、依然未解決問題である。
\(p(a) = 2^n\) を満たす最小の数 \(a\) を返す関数として \(q(n)\) を定義し、これを \(p\) の擬逆関数と呼ぶ。\(q\) は急激に増加し \(p\) が発散する時に限り全域である。\(n \leq 4\) における \(q\) の値は \(0, 2, 3, 5, 9\) である。\(q(5)\) の well-defined 性は示されていないが、ランドール・ドハティは階層内階層基数の存在を仮定した上で修整した急増加関数[注 2]に関して \(q(n+1) \geq f_{\omega+1}(\lfloor \log_3 n \rfloor - 1)\) となることと \(q(5) \geq f_9(f_8(f_8(254)))\) となることを示した[2]。より精密な下からの評価が単純に証明できるかに関してドハティは悲観的な意見を表しており、上からの評価についてはいまだ知られていない。Googology Wikiにおける予想としては \(q(6)\) がTREE(3)やSCG(13)どころかローダー数より大きいとされていたが、根拠は「既知の証明に要する集合論の強さ」以外には不明である[注 3]。
説明[]
極限順序数 \(\lambda\) に対し、\(\varepsilon_{\lambda}\) で初等的埋め込み \(V_{\lambda} \hookrightarrow V_{\lambda}\) 全体の集合を表す（初等的埋め込みについては階層内階層基数のページを参照）。\(j,k \in \varepsilon_{\lambda}\) に対する演算 \(j \cdot k\)（または \(jk\) と書く[注 4]）を以下のように定義する：
\[j \cdot k = \bigcup_{\alpha < \lambda} j(k \cap V_\alpha)\]
ただし \(k \cap V_\alpha\) は \(k\) を \(\{x \in V_\alpha \mid (x,k(x)) \in V_\alpha\}\) に制限して得られる写像である。\(k \notin V_{\lambda}\) なので \(k\) 自身は \(j\) に代入できないが \(k \cap V_{\alpha} \in V_{\lambda}\) であるので \(k \cap V_{\alpha}\) は \(j\) に代入することができる。すなわち、\(k\) の 定義域である\(V_{\lambda}\) の近似列 \((V_{\alpha})_{\alpha < \lambda}\) に沿って \(k\) の制限を \(j\) に代入していくことで、擬似的に "\(k\) を \(j\) に代入" しているのである。この演算は \(j(kl) = (jk)(jl)\) すなわち左分配則を満たす。
以下、階層内階層基数公理\(I3\)を仮定し、\(\lambda\)は対応する巨大基数であると仮定する。すなわち\(\varepsilon_{\lambda}\)が自明マグマでないと仮定する。上述のように定義される初等的埋め込みの演算とレイバーのテーブルには以下のような関係がある：
- \(k\stackrel{*}{\bigcap}V_θ\)を\(\{〈x,y〉∈V_θ×V_θ,y∈k(x)\}\)と定義する。
- \(k\overset{θ}{=}ℓ\)を\(k\stackrel{*}{\bigcap}V_θ\)=\(ℓ\stackrel{*}{\bigcap}V_θ\)の意味とする。
- \(j∈\mathcal{E}_λ\)について、\(\operatorname{cr}j\)を\(j\)の臨界点とする(臨界点については階層内階層基数のページを参照)。
- \(j∈\mathcal{E}_λ\)について、\(\mathcal{A}_j\)を、\(\{j\}\)の生成する\(\varepsilon_{\lambda}\)の部分マグマ（\(j\)に\(\cdot\)を繰り返し適用して得られる初等埋め込み全体の集合）とする。
- \(j∈\mathcal{E}_λ\)について、\(\operatorname{cr}\mathcal{A}_j=\{\operatorname{cr}k:k∈\mathcal{A}_j\}\)とおく。
- \(j∈\mathcal{E}_λ\)について、\(〈γ_h:h∈ω〉\)を\(\operatorname{cr}\mathcal{A}_j\)の昇順の枚挙とする。
- \(j_{(0)}=\mathrm{id}\)(恒等写像)\(,j_{(1)}=j,j_{(h+1)}=j_{(h)}j\)とする。
このとき、
- \(j_{(0)}=\mathrm{id}\)だから、\(j_{(m)}j_{(0)}\overset{γ_n}{=}j_{(0)}.\)
- \(j_{(1)}=j\)だから、\(j_{(m)}j_{(1)}=j_{(m)}j=j_{(m+1)},\)[1]の定理11により\(m=2^n-1\)ならば\(j_{(m)}j_{(1)}=j_{(2^n)}\overset{γ_n}{=}j_{(0)}.\)
- \(·\)は左分配則を満たすから、\(j_{(m)}j_{(h+1)}=j_{(m)}(j_{(h)}j_{(1)})=(j_{(m)}j_{(h)})(j_{(m)}j_{(1)}).\)
なので、\(m\star_nh=ℓ\)と\(j_{(m)}j_{(h)}\overset{γ_n}{=}j_{(ℓ)}\)は同値となる。
例[]
\(\mathbb{Z}_{2^n}\) は \(\{0,1,\ldots,2^n-1\}\) と 同一視されることが多いが、\(0\) の代わりに \(2^n\) を用いて \(\{1,2,\ldots,2^n\}\) と同一視することも可能である。パトリック・デホーノイによって、\(\{1,2,\ldots,2^n\}\) と同一視した場合のレイバーのテーブルの計算アルゴリズムが与えられている[3]。特に \(p(n)\) と \(q(n)\) は \(\textrm{ZFC}\) 公理系やより弱い理論で定義可能な計算可能関数である。上に述べたように、\(q(n)\) が全域かどうかは \(\textrm{ZFC}\) 公理系では知られていない。
サイズ2[]
サイズ2のテーブルを下に示す。
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 2 | 4 | 2 | 4 |
| 2 | 3 | 4 | 3 | 4 |
| 3 | 4 | 4 | 4 | 4 |
| 4 | 1 | 2 | 3 | 4 |
1行目の成分は周期2で繰り返されるので、\(p(2) = 2\) となる。
サイズ3[]
サイズ3のテーブルを下に示す。
| 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 |
1行目の成分は周期4で繰り返されるので、\(p(3) = 4\) となる。
外部リンク[]
- 猫山にゃん太, Laver table - レイバーのテーブル, GitHubページ.（javascriptによる計算プログラム）
- 猫山にゃん太, レイバーのテーブル, YouTube.（紹介動画）
- Mitsuki1729, scratch巨大数選手権コンテスト レイバーのテーブル, scratchプロジェクト.（scratchによる\(q(5)\)計算プログラム）
脚注[]
- ↑ Googology Wikiの古い記事では「深刻に疑わしい」と書かれていたが、実際に階層内階層基数の存在の無矛盾性が深刻に疑わしいかどうかを集合論の専門家に伺ってみたところ、疑う人がいてもおかしくはない程度であるという反応だった。時代にもよるのかもしれないが、そこまで疑わしいと断言できる根拠はないのかもしれない。
- ↑ OEIS A098820にはアッカーマン関数と書かれているが、原論文のp. 2にはアッカーマン関数の亜種と書かれている。これはアッカーマン関数の定義に複数の等価でない流儀が存在することに起因すると思われる。
- ↑ Googology Wikiの古い記事に記載されていた予想であり、現在は削除されている。そのため予想としての信憑性に乏しいと考えられているのかもしれない。論文などで妥当性が検証されている予想ではない。既知の証明に要する集合論の強さは計算可能関数の増大度と関係がないが、これがあたかも関係があるかのように誤って説明されることもある。
- ↑ レイバーの原論文では \(j(k)\) と書かれているが、丸カッコを演算子に使うと演算の結合順の指定に丸カッコが使えなくなるのでここでは避ける。
出典[]
- ↑ 1.0 1.1 Laver, Richard. On the Algebra of Elementary Embeddings of a Rank into Itself, arXiv. (論文タイトル末尾は itself だが、arXivのページタイトルは Inself と誤記されている)
- ↑ Dougherty, Randall. Critical points in an algebra of elementary embeddings, arXiv.
- ↑ Dehornoy, Patrick. Laver Tables, 講演スライド.