FANDOM


6th Laver table

白黒のビットマップで表したサイズ 6 のレイバーのテーブル

レイバーのテーブルとは巨大関数の素となるマグマ(二項演算付き集合)の無限族 \(L_0, L_1, L_2, \ldots\) である[1]。1992年にリチャード・レイバーによって定義された[2]。\(n \geq 0\) に対し、 サイズ \(n\) のレイバーのテーブル \(L_n\) は \(\mathbb{Z}_{2^n}\) (位数 \(2^n\) の巡回群であり、\(\{0,1,2,\ldots, 2^n-1\}\) と自然に同一視される) の上で定義された二項演算子 \(\star\) であり、以下を満たす:

\begin{eqnarray*} & & a \star 1 = a + 1 \pmod{2^n} \\ & & a \star (b \star c) = (a \star b) \star (a \star c) \ \ \ \textrm{(左分配則)} \\ \end{eqnarray*}

関数\(a \mapsto 1 \star a\)の周期は\(n\)の関数になり、それを \(p(n)\) と表すことにする。\(n \leq 56\) における \(p(n)\) の値は \(1, 1, 2, 4, 4, 8, 16, \ldots, 16\) (OEIS A098820)となり、まるで成長が遅い関数であるように見える。\(p\) が発散することは \(\textrm{ZFC}\) 公理系に階層内階層基数が存在するという公理を加えた体系で証明されている。残念ながら階層内階層基数の存在は \(\textrm{ZFC}\) 公理系との無矛盾性を深刻に疑う人がいてもおかしくはないほど強い公理である[3]。\(p\) が発散することは階層内階層基数の存在を用いずには示されていないため、依然未解決問題である。

\(p(q(n)) = 2^n\) を満たす最小の数を返す関数として\(q\)を定義し、これを \(p\) の擬逆関数と呼ぶ。\(q\)は\(p\)が発散する時に限り全域である急増加関数である。\(n \leq 4\) における \(q\) の値は \(0, 2, 3, 5, 9\) である。\(q(5)\) のwell-defined性は示されていないが、ランドール・ドハティは階層内階層基数の存在を仮定した上で修整した急増加関数[4]に関して \(q(n+1) \geq f_{\omega+1}(\lfloor \log_3 n \rfloor - 1)\) となることと \(q(5) \geq f_9(f_8(f_8(254)))\) となることを示した[5]。より精密な下からの評価が単純に証明できるかに関してドハティは悲観的な意見を表しており、上からの評価についてはいまだ知られていない。予想としては\(q(6)\) がTREE(3)SCG(13)どころかLoader.cより大きいとされている[6]

説明

極限順序数 \(\lambda\) に対し、\(\varepsilon_{\lambda}\) で初等的埋め込み\(V_{\lambda} \hookrightarrow V_{\lambda}\) 全体の集合を表す(初等的埋め込みについては階層内階層基数のページを参照)。\(j,k \in \varepsilon_{\lambda}\) に対する演算 \(j \cdot k\)(または \(jk\) と書く[7])を以下のように定義する:

\[j \cdot k = \bigcup_{\alpha < \lambda} j(k |_{V_{\alpha}})\]

ただし \(k |_{V_{\alpha}}\) は \(k\) の \(V_{\alpha} \subset V_{\lambda}\) への制限(のグラフ)である。\(k \notin V_{\lambda}\)なので\(k\)自身は \(j\) に代入できないが \(k |_{V_{\alpha}} \in V_{\lambda}\) であるので \(k |_{V_{\alpha}}\) は \(j\) に代入することができる。すなわち、\(k\) の 定義域である\(V_{\lambda}\) の近似列 \((V_{\alpha})_{\alpha < \lambda}\) に沿って \(k\) の制限を \(j\) に代入していくことで、擬似的に"\(k\) を \(j\) に代入"しているのである。この演算は \(j(kl) = (jk)(jl)\) すなわち左分配則を満たす。

サイズ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\)となる。

出典

  1. Goucher, Adam. Large cardinalsComplex Projective 4-Space  Retrieved 2013-12-18.
  2. Laver, Richard. On the Algebra of Elementary Embeddings of a Rank into Inself. Retrieved 1992-04-13.
  3. 英語版では「深刻に疑わしい」と書かれているが、実際に階層内階層基数の存在の無矛盾性が深刻に疑わしいかどうかを集合論の専門家に伺ってみたところ、疑う人がいてもおかしくはない程度であるという反応だった。時代にもよるのかもしれないが、そこまで疑わしいと断言できる根拠はないのかもしれない。
  4. OEIS A098820にはアッカーマン関数と書かれているが、原論文のp. 2にはアッカーマン関数の亜種と書かれているので誤りであると推測される。
  5. Dougherty, Randall. Critical points in an algebra of elementary embeddings. Retrieved 1992-05-07.
  6. 英語版の古い記事に記載されていた予想であり、現在は削除されている。そのため予想としての信憑性に乏しいと考えられているのかもしれない。
  7. レイバーの原論文では \(j(k)\) と書かれているが、丸カッコを演算子に使うと演算の結合順の指定に丸カッコが使えなくなるのでここでは避ける。