巨大数研究 Wiki
登録
Advertisement
巨大数研究 Wiki
主要記事: BEAF

BEAF (Bowers Exploding Array Function) は、Jonathan Bowersが考案した巨大数を生み出す関数です。この入門記事では、この関数を直感的に理解できるように、少しずつ紹介します。

矢印表記

BEAFについて理解する前に、拡張演算子の本質を理解する必要があります。矢印表記ドナルド・クヌースが考案した演算子です。

\(a\uparrow b = a^b\).
\(a\uparrow\uparrow b = \underbrace{a\uparrow a\uparrow\ldots\uparrow a\uparrow a}_b = \underbrace{a^{a^{a^{.^{.^.}}}}}_b\). 巨大数研究者は、これをテトレーションと言う。矢印は右から左へと順番に計算をする。
\(a\uparrow\uparrow\uparrow b = \underbrace{a\uparrow\uparrow a\uparrow\uparrow\ldots\uparrow\uparrow a\uparrow\uparrow a}_b\). ペンテーションとも言う。

一般的に、

\(a\uparrow^n b = \underbrace{a\uparrow^{n-1} a\uparrow^{n-1}\ldots\uparrow^{n-1} a\uparrow^{n-1} a}_b\).

ここで、いくつかの計算例を示します。

\(3\uparrow 4 = 3^4 = 81\) (3 to the power of 4)
\(2\uparrow\uparrow 4 = 2\uparrow 2\uparrow 2\uparrow 2 = 2\uparrow 2\uparrow 4 = 2\uparrow 16 = 65536\) (2 tetrated to 4))
\(4\uparrow\uparrow 4 = 2361022671...5261392896\); about \(8.0723\cdot 10^{153}\) digits (4 tetrated to 4)
\(3\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow 3\uparrow\uparrow 3 = 3\uparrow\uparrow 3^{3^3} = 3\uparrow\uparrow 7625597484987\) (3 pentated to 3)

演算子表記

Jonathan Bowersは、矢印表記を一般化した演算子表記を開発しました。

\(a\ \{n\}\ b = a\uparrow^n b\)
i.e.: \(a\ \{1\}\ b = a^b\)
and \(a\ \{n\}\ b = \underbrace{a\ \{n - 1\}\ a\ \{n - 1\}\ \ldots\ \{n - 1\}\ a\ \{n - 1\}\ a}_b\)

たとえば、 \(3\ \{4\}\ 5 = 3\uparrow\uparrow\uparrow\uparrow 5\) となります。

この形の演算子表記は、矢印表記を短く書き換えたに過ぎません。しかし、Bowersはnをかこむ括弧を1重から2重へと増やすことで、さらに拡張しました。

\(a\ \{\{1\}\}\ b = \underbrace{a\ \{a\ \{\ldots a\ \{a}_b\}\ a\ldots\}\ a\}\ a\)

Bowers は、これをaのb重膨張 (a expanded to b) と呼びました。ここで、bは一番外を含んだ括弧の重複数で、(aの数 + 1) / 2 です。(情報科学者の方へ:膨張は原始帰納ではありません。あらかじめ計算された回数のループでは、プログラムできないからです。)

たとえば、このように計算されます。

\(3\ \{\{1\}\}\ 3 = 3\ \{3\ \{3\}\ 3\}\ 3 = 3\ \{3\ \{2\}\ 7625597484987\}\ 3\)

nを1から2に変えると、乗算膨張になります。

\(a\ \{\{2\}\}\ b = \underbrace{a\ \{\{1\}\}\ a\ \{\{1\}\}\ \ldots\ \{\{1\}\}\ a\ \{\{1\}\}\ a}_b\)

さらにnを大きくすると、このようになります。

\(a\ \{\{3\}\}\ b = \underbrace{a\ \{\{2\}\}\ a\ \{\{2\}\}\ \ldots\ \{\{2\}\}\ a\ \{\{2\}\}\ a}_b\) (冪乗膨張)
\(a\ \{\{4\}\}\ b = \underbrace{a\ \{\{3\}\}\ a\ \{\{3\}\}\ \ldots\ \{\{3\}\}\ a\ \{\{3\}\}\ a}_b\) (膨張テトレーション)
膨張ペンテーション, 膨張ヘキセーション、と続きます。

これらの演算子はすべて右から左へと計算する演算子で、ハイパー演算子と同様に計算ができます。

括弧を2重から3重にすると、爆発になります。

\(a\ \{\{\{1\}\}\}\ b = \underbrace{a\ \{\{a\ \{\{\ldots a\ \{\{a\}\}\ a\ldots\}\}\ a\}\}\ a}_b\)
\(a\ \{\{\{2\}\}\}\ b = \underbrace{a\ \{\{\{1\}\}\}\ a\ \{\{\{1\}\}\}\ \ldots\ \{\{\{1\}\}\}\ a\ \{\{\{1\}\}\}\ a}_b\) (乗算爆発)
\(a\ \{\{\{3\}\}\}\ b = \underbrace{a\ \{\{\{2\}\}\}\ a\ \{\{\{2\}\}\}\ \ldots\ \{\{\{2\}\}\}\ a\ \{\{\{2\}\}\}\ a}_b\) (冪乗爆発)
\(a\ \{\{\{4\}\}\}\ b = \underbrace{a\ \{\{\{3\}\}\}\ a\ \{\{\{3\}\}\}\ \ldots\ \{\{\{3\}\}\}\ a\ \{\{\{3\}\}\}\ a}_b\) (爆発テトレーション)
爆発ペンテーション、爆発ヘキセーション、と続きます。

括弧が4重になると爆轟 (乗算爆轟、冪乗爆轟、爆轟ペンテーション)、5つになるとペントネーション (乗算ペントネーション、冪乗ペントネーション、ペントノテトレーション)となり、ヘキソネーション、ヘプトネーションと続きます。

演算子表記には、4つの変数があります。

\(a\ \{1\}\ b = a^b\)
\(a\ \{1\}^d\ b = \underbrace{a\ \{a\ \{\ldots a\ \{a\}^{d - 1}\ a\ldots\}^{d - 1}\ a\}^{d - 1}\ a}_b\)
\(a\ \{c\}^d\ b = \underbrace{a\ \{c - 1\}^d\ a\ \{c - 1\}^d\ \ldots\ \{c - 1\}^d\ a\ \{c - 1\}^d\ a}_b\)

ここで、上付文字の dは、cに何重の括弧がついているかを示します。たとえば、 \(\{\ldots\}^4\) は \(\{\{\{\{\ldots\}\}\}\}\) を表しています。この表記は Jonathan Bowers は使いませんでした。

巨大数研究者のChris Birdは、この4変数表記はチェーン表記と同じ程度の関数の増加速度となることを証明しました。ところが、まだBEAFの表面をちょっとひっかいた程度に過ぎません!

線形配列表記

演算子表記では、だんだん書ききれなくなってきました。より簡単に書くために、\(a\ \{c\}^d\ b\) を \(\{a, b, c, d\}\) と書き換えます。すなわち、

  • \(\{a, b, 1, 1\} = a^b\)
  • \(\{a, b, 1, d\} = \underbrace{\{a, a, \{a, a, \ldots \{a, a, a, d - 1\} \ldots, d - 1\}, d - 1\}}_b\) if \(d > 1\)
  • \(\{a, b, c, d\} = \underbrace{\{a, \{a, \ldots \{a, a, c - 1, d\} \ldots, c - 1, d\}, c - 1, d\}}_b\) if \(c > 1\)

1がデフォルトであると考えて、配列の最後が1だけであれば切り落とすことができます。たとえば、 \(\{a, b, 1, 1\}\) は \(\{a, b\} = a^b\) となります。

2番目と3番目のルールを再帰的な性質によって簡略化することができます。

\(\{a, b, 1, d\} = \underbrace{\{a, a, \{a, a, \ldots \{a, a, a, d - 1\} \ldots, d - 1\}, d - 1\}}_b\)
\(= \{a, a, \underbrace{\{a, a, \ldots \{a, a, a, d - 1\} \ldots, d - 1\}}_{b - 1}, d - 1\} = \{a, a, \{a, b - 1, 1, d\}, d - 1\}\)
\(\{a, b, c, d\} = \underbrace{\{a, \{a, \ldots \{a, a, c - 1, d\} \ldots, c - 1, d\}, c - 1, d\}}_b\)
\(= \{a, \underbrace{\{a, \ldots \{a, a, c - 1, d\} \ldots, c - 1, d\}}_{b - 1}, c - 1, d\} = \{a, \{a, b - 1, c, d\}, c - 1, d\}\)

しかし、この書き換えは問題があることに気がつくことでしょう。帰納的規則を定めましたが、初期条件が定められていないため、いずれの式も\(b\)が永遠に減りつづけてしまいます。そこで、\(b\)が1に到達したときの規則を定めます。

\(\{a, 1, c, d\} = a\)

このステップは、BEAFの定義で非常に重要です。分からなければ、紙で計算をしてみて下さい。

5変数以上

ここまでの規則をまとめます。

  • \(\{a, b, 1, 1\} = \{a, b\} = a^b\)
  • \(\{a, 1, c, d\} = a\)
  • \(\{a, b, 1, d\} = \{a, a, \{a, b - 1, 1, d\}, d - 1\}\), \(b,d > 1\)
  • \(\{a, b, c, d\} = \{a, \{a, b - 1, c, d\}, c - 1, d\}\), \(b,c > 1\)

簡約化の新しい方法によって、最後の2つの式にかすかに規則性が見えてきました。この規則性に基づいて、5つ目の引数を追加します。

  • \(\{a, b\} = a^b\)
  • \(\{a, 1, c, d, e\} = a\)
  • \(\{a, b, 1, 1, e\} = ???\)
  • \(\{a, b, 1, d, e\} = \{a, a, \{a, b - 1, 1, d, e\}, d - 1, e\}\), \(b,d > 1\)
  • \(\{a, b, c, d, e\} = \{a, \{a, b - 1, c, d, e\}, c - 1, d, e\}\), \(b,c > 1\)

3つ目の式が完成していませんが、4つ目と5つ目の式から逆方向に外挿することで、このように完成させることができます。

\(\{a, b, 1, 1, e\} = \{a, a, a, \{a, b - 1, 1, 1, e\}, e - 1\}\)

幸いにして、5つ目の引数は簡単に追加で来ました。同じパターンで、6つ目の引数を追加することができます。

  • \(\{a, b\} = a^b\)
  • \(\{a, 1, c, d, e, f\} = a\)
  • \(\{a, b, 1, 1, 1, f\} = \{a, a, a, a, \{a, b - 1, 1, 1, 1, f\}, f - 1\}\), \(b,f > 1\)
  • \(\{a, b, 1, 1, e, f\} = \{a, a, a, \{a, b - 1, 1, 1, e, f\}, e - 1, f\}\), \(b,e > 1\)
  • \(\{a, b, 1, d, e, f\} = \{a, a, \{a, b - 1, 1, d, e, f\}, d - 1, e, f\}\), \(b,d > 1\)
  • \(\{a, b, c, d, e, f\} = \{a, \{a, b - 1, c, d, e, f\}, c - 1, d, e, f\}\), \(b,c > 1\)

同様の一般化を、任意の数の引数に対して行うことができます。簡潔に書くために、いくつかの用語を定義します。1つ目の引数 \(a\) は 基数、2つ目の \(b\) は プライムと言います。プライムの後は、最初の1でない引数を パイロット、パイロットの1つ前の引数を 副操縦士と言います。そして、副操縦士よりも前のすべての引数を乗客と言います。配列の値を \(v(A)\) と書きます。これらの用語を使って、線形配列表記を記述することができます。

線形配列表記

\(b\) を基数、\(p\) をプライムとする。

  1. 基数ルール パイロットがいない場合(すなわち、基数の後のすべての引数が1の時)、\(v(A) = b^p\)
  2. プライムルール プライムが1の時、 \(v(A) = b\)
  3. 破滅ルール それ以外の時には、
    1. 副操縦士を元の配列のプライムを1減らしたものに置き換える。
    2. パイロットの値を1減らす。
    3. すべての乗客を \(b\) にする。
(定義終了)

これが、2002年頃に作られた Bower の配列表記を再構築したものです。元々は5つのルールでしたが、現在のBEAFで採用されている3つのルールに落とし込むことができました。

線形配列表記の定義ができたので、計算の直感を得るために、いくつかの例を示します。

\begin{eqnarray*} \{3,3,1,1,1,3\} &=& \{3,3,3,3,\{3,2,1,1,1,3\},2\} \\ &=& \{3,3,3,3,\{3,3,3,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,2,3,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,\{3,1,3,3,3,2\},2,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,3,2,3,3,2\},2,3,3,2\},2\} \end{eqnarray*}

もし、配列の中の引数がすべて同じであれば、さらに高次の配列へと変換することができます。

3変数を4変数に変換:

  • {a,a,a} = {a,2,1,2}
  • {a,a,{a,a,a}} = {a,3,1,2}
  • {a,a,{a,a,a,{a,a,a}}} = {a,4,1,2}
  • 以下同様

4変数を5変数に変換:

  • {a,a,a,a} = {a,2,1,1,2}
  • {a,a,a,{a,a,a,a}} = {a,3,1,1,2}
  • {a,a,a,{a,a,a,{a,a,a,{a,a,a,{a,a,a,a}}}}} = {a,6,1,1,2}

5変数を6変数に変換:

  • {a,a,a,a,a} = {a,2,1,1,1,2}
  • {a,a,a,a,a,{a,a,a,a,a}} = {a,3,1,1,1,2}
  • {a,a,a,a,a,{a,a,a,a,a,{a,a,a,a,a}}} = {a,4,1,1,1,2}

一般に、 {a,b,1,1,...,1,1,2} = {a,a,a,...,a,a,{a,a,a,...a,a,{a,a,a,...,a,a,{a,a,a,...,a,a}...}}} となります。ここで、括弧{}はb 重です。

多次元配列

ここで、新しい概念である配列次元演算子を導入します。2つの整数a,bに対する配列次元演算子は、次のように定義されます。

\(b \& a = \underbrace{\{a, a, ..., a, a\}}_b\)

この関数は、これまでの定義すべてを「対角化」します。これはとても大きな関数です。急成長階層をよく知っているのであれば、 \(n \& n\) はおよそ \(f_{\omega^\omega}(n)\) と近似できます。

配列表記の拡張を続けるためには、直感の段階を上げる必要があります。\(b \& a\) は \(a^b = \underbrace{\{a \cdot a \cdots a \cdot a\}}_b\) と式の形が少し似ているので、基数ルールを次のように変えた「レベル2の配列表記」を考えます。

  1. 基数ルール パイロットがいない場合(すなわち、基数の後のすべての引数が1の時)、\(v(A) = p \& b\)

レベル2の配列表記を示すために、配列に下付文字2を加えて \(\{a, b\}_2 = p \& b\) とします。同じようにして、レベル3の配列表記を作ることができます。\(b \&_2 a = \underbrace{\{a, a, ..., a, a\}_2}_b\) と定義して、基数ルールの \(\&\) を \(\&_2\) に変えます。はい、これがレベル3の配列表記です。

ここからは、拡張は簡単ですが少し退屈です。一般化して、レベル\(r\)の配列表記のルールをこのように作ってみましょう。

  1. 基数ルール パイロットがいなくて、 \(r = 1\) であれば、 \(v(A) = b^p\) とする。
  2. レベルルール パイロットがいなくて、 \(r > 1\) であれば、 \(v(A) = p \&_{r - 1} b\) とする。
  3. プライムルールと破滅ルールは同じ。

では、どうすればこの拡張を最大限活用できるでしょうか?\(r\)を大きくしたいわけですから、\(r\)を配列の値にしてしまうのが一番効率的です。

\(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}}\)

いっそのこと、これを \(b\) 回繰り返してしまいましょう。

\(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{._{._.}}}}\)

これを \(b \&_{1, 2} a\) と書きます。そうすれば、「レベル 1,2 の表記」を定義できます。(ううむ、なぜ「1,2」なのでしょうか?先に進んでから考えてみましょう。)次に、 \(2,2\) を考えますが、これは単純に \(\{a, a, \ldots, a, a\}_{1,2}\) です。ここから、レベルnの表記を考えたときと同様に、帰納的にレベルn,2の表記を定義できます。

そして、レベル 1,3 は

\(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{._{._.}},2},2}\)

となり、一般的にレベル 1,n は、n > 1 の時にこのようになります。

\(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{._{._.}},n - 1},n - 1}\)

ここまでは悪くないです。では、1,1,2はどうなるでしょうか?ここから先は、レベルをあらわす \(r\) が複数の数字を持つわけなので、通常の線形配列と同じようにすれば良いわけです。つまり、\(r\)の複数の数字の中で、最初の1ではない数字を仮に「レベルパイロット」と呼んで、レベルパイロットの1つ前のレベル副操縦士を、配列全体からプライムを1減らしたものと入れ替えて、レベルパイロットを1減らして、最初の \(p\) 個の数字を\(b\)にします。

そもそも、なぜパイロットレベルパイロットを区別する必要があるのでしょうか?レベルについて気にする必要があるのは、配列が基数とプライムだけになったとき、つまり \(\{b, p\}_{1,1,2}\) のような形になったときだけです。ここで重要なことは、 \(r\) は配列の一部であるため、レベルパイロットパイロットそのものである、ということです。

さて、ここでレベルをあらわす \(r\) を括弧の中に入れるように、表記法をアップデートしてみましょう。Bower は高次元に興味があったので、 \(r\) を2行目に入れてしまいました。たとえば、

\[\left\{ \begin{matrix} b,p \\ 1,1,2 \end{matrix} \right\}\]

となります。これを1行で書く時には、 \(\{b, p\ (1)\ 1, 1, 2\}\) と書きます。ここで、 (1) は行と行の間を示します。ここでまた、各行は(可算)無限個の1で自動的に満たされるため、この配列は \(\{b, p, 1\ (1)\ 1, 1, 2\}\) や \(\{b, p, 1, 1, 1\ (1)\ 1, 1, 2, 1, 1\}\) と同じことになります。

ためしに、新しい2行配列への拡張を今までのルールに適用してみましょう。たとえば、 \(\{b, p (1) 2\}\) を考えてみます。2がパイロットになりますが、2の前には数字がないので、副操縦士がいません!副操縦士がいない場合についても考える必要があります。また、このような場合にも問題があります。

\(\{b, p (1) 1, 1, 2\} = \{b, b, b, \ldots (1) b, \{b, p - 1 (1) 1, 1, 2\}, 2\}\)

問題は、1行目に無限個の b があることです。p個だけがほしいのです。「乗客」の定義も、2行配列にしたことで拡張する必要があります。まとめると、このようになります。

  • 基数は、1つ目の要素。
  • プライムは、2つ目の要素。
  • パイロットは、基数の次の最初の1ではない要素。
  • 副操縦士は、パイロットの直前の要素。2行目の最初がパイロットであれば、副操縦士は存在しない。
  • 前の要素とは、同じ行にある前の要素である。したがって、 \(\{a, b (1) c, d\}\) においては、\(d\)の前の要素は \(c\) であって、 \(a\) と \(b\) は違う。
  • ある行のプライムブロックは、その行の中の最初の \(p\) 個の要素、つまりプライムの個数の要素である。
  • 飛行機は、パイロットとすべての前の要素である。パイロットが2行目にあれば、飛行機は前の行のプライムブロックを含む。
  • 乗客は、飛行機の中でパイロットと副操縦士(もしいれば)を除くすべての要素である。

これ以外のルールは線形配列表記と同じです。最初に「レベル」として考えていたものは、配列の中に組み込まれてしまったので、「レベルルール」は必要ではありません。

ここに、計算例を示します。

\begin{eqnarray*} \{3,3,3 (1) 2\} &=& \{3,\{3,2,3 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,1,3 (1) 2\},2 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,3,2 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,2,2 (1) 2\},1 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,2,2 (1) 2\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,\{3,1,2 (1) 2\},1 (1) 2\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,3 (1) 2\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,3,3 (1) 1\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,3,3\} (1) 2\},2 (1) 2\} \end{eqnarray*}

3行以上

3行配列で最も簡単で意味のある配列は \(\{b, p (1) (1) 2\}\) です。ここで、2行目は1だけです。これは、パイロットが3行目の2で、副操縦士はなく、乗客は1行目と2行目のプライムブロックなので、それぞれ最初のp個のエントリとなって、その2行がすべてbになって、パイロットである3行目の最初の要素は2から1を引いて1となるため3行目が消去されて、 \(\{b, b, \ldots, b, b (1) b, b, \ldots, b, b\}\) と等しくなります。ここで、それぞれの行に、 \(p\) 個の要素があります。この例では、パイロットが3行目に移動しましたが、さらに副操縦士をつけると、たとえば \(\{b, p (1) (1) 1, 2\} = \{b, p (1) (1) \{b, p - 1 (1) (1) 1, 2\}\}\) のように計算ができます。3行以上は同様に振る舞うので、一般化してしまいましょう。

飛行機の定義を、次のように変える必要があります。

  • 飛行機は、パイロットと、パイロットと同じ行のすべてのパイロットの前の要素と、すべての前の行のプライムブロックである。

パイロットが1行目にいるときには、前の行は存在しないため、飛行機は前の要素だけになります。これで、前の飛行機の定義に入っていた条件節(「パイロットが2行目にあれば」の文)を書く必要がなくなります。

さて、これでようやく平面配列表記の定義が完成しました。では、行の次には何が来るでしょうか?

3次元

そうです、平面です。平面と平面の間の境界には (2) を使います。最小の2平面配列は \(\{b, p (2) 2\} = \{b, b, \ldots, b, b (1) b, b, \ldots, b, b (1) \ldots (1) b, b, \ldots b, b (1) b, b, \ldots, b, b\}\)、つまり \(p \times p\) 配列の \(b\) です。(これを \(p^2 \& b\) とも書くことができます。後で、詳しく説明します。) ついに複数の平面に到達します。ほぼ予想通りに計算出来ます。

それでは、きちんとした定義を与えましょう。一般化するために、さらにいくつかの抽象的な用語を導入します。その1つは構造です。構造は、要素、行、あるいは平面のどの可能性もあります。それでは、一般的な構造に対するプライムブロックを定義しましょう。

  • ある行のプライムブロックとは、最初の \(p\) 個の要素で、ある平面のプライムブロックは最初の \(p \times p\) の正方形の要素、つまり最初の \(p\) 行のプライムブロックである。
  • Xの前の要素とは、Xと同じ行内の前の要素である。Xの前の行とは、Xと同じ平面内の前の行である。
  • 飛行機とは、パイロットと、すべての前の要素、そしてすべての前の構造のプライムブロックである。

この最後の定義は、BEAFの動作の核心部分なので、よく理解して下さい。

たとえば、ザッポル = {10,10 (2) 2} を考えてみましょう。パイロットは 2 です。これは行の先頭の要素なので、前の要素はありません。そして、前の平面のプライムブロックは、\(10 \times 10\) の正方形の要素になります。破滅ルールにより、パイロットの2が1になって消去され、乗客であるプライムブロックはすべて10に変わることにより、\(10 \times 10\) 配列の 10 となります。

4次元以上

Bowers によれば、平面が無限に重なったもの、すなわち3次元空間は領域(realm)で、4次元空間はフルーン(flune)です。領域とフルーンを分ける記号は、それぞれ (3)と(4) です。

一般に、 (n) は次のn次元空間との境界を示す記号です。要素は0次元空間なので、カンマは (0) を省略したものだと考えることができます。"構造"とは、任意のn次元空間です。n次元空間を \(X^n\) と表記します。

それでは、これまでの定義を"構造"、"プライムブロック"、"前の構造"、そして"飛行機"によって書き直してみましょう。

  • 構造とは、要素、行、平面、領域、フルーン、5次元空間、…等である。要素を構造として、構造の無限の連なりを構造であると、帰納的に定義出来る。
  • ある行のプライムブロックとは、最初の\(p\)個の要素である。ある平面のプライムブロックとは、 \(p \times p\) の正方形である。ある領域のプライムブロックは、最初の \(p \times p \times p\) の立方体である。同様にして、より高次元のプライムブロックを定義出来る。ある行のプライムブロックとは最初の\(p\)個の要素であり、\(X^n\) 構造のプライムブロックは最初の \(p\) 個の \(X^{n-1}\)構造であるとすれば、帰納的に定義出来る。
  • Aに対する前の構造とは、同じ \(X^{n + 1}\) 構造の中の前の \(X^n\) 構造である。例えば、Aの前の要素Aと同じ行の中のAよりも前の要素であり、Aの前の行とはAと同じ平面の中のAよりも行であり、等となる。
  • 飛行機とは、パイロットと、すべての前の要素と、すべての前の構造のプライムブロックである。

ここまでで、完全に多次元配列表記を定義することができました。ここまでの定義をまとめます。

多次元配列表記

定義:

  • 基数 \(b\) は、1番目の要素である。
  • プライム \(p\) は、2番目の要素である。
  • パイロットは、プライムの後の最初の1でない要素である。
  • 副操縦士は、パイロットの直前の要素である。パイロットが行の最初であれば、副操縦士は存在しない。
  • 構造とは、要素、行、平面、領域、フルーン、5次元空間、…等である。要素を構造として、構造の無限の連なりを構造であると、帰納的に定義出来る。
  • ある行のプライムブロックとは、最初の\(p\)個の要素である。ある平面のプライムブロックとは、 \(p \times p\) の正方形である。ある領域のプライムブロックは、最初の \(p \times p \times p\) の立方体である。同様にして、より高次元のプライムブロックを定義出来る。ある行のプライムブロックとは最初の\(p\)個の要素であり、\(X^n\) 構造のプライムブロックは最初の \(p\) 個の \(X^{n-1}\)構造であるとすれば、帰納的に定義出来る。
  • Aに対する前の構造とは、同じ \(X^{n + 1}\) 構造の中の前の \(X^n\) 構造である。例えば、Aの前の要素Aと同じ行の中のAよりも前の要素であり、Aの前の行とはAと同じ平面の中のAよりも行であり、等となる。
  • 飛行機とは、パイロットと、すべての前の要素と、すべての前の構造のプライムブロックである。
  • 乗客とは、飛行機の中のパイロットと副操縦士(もし存在すれば)以外のすべての要素である。

規則:

  1. 基数ルール パイロットがいない場合(すなわち、基数の後のすべての引数が1の時)、\(v(A) = b^p\)
  2. プライムルール プライムが1の時、 \(v(A) = b\)
  3. 破滅ルール それ以外の時には、
    1. 副操縦士を元の配列のプライムを1減らしたものに置き換える。
    2. パイロットの値を1減らす。
    3. すべての乗客を \(b\)にする。
(定義の終了)

やりました!これが Bird と Bowers が開発した拡張配列表記です。当初は7つのルールがありましたが、現代の BEAF の定義によってかなり簡潔になっています。


配列次元演算子

配列次元演算子は、& と表記され(論理積 "and" 演算子と混同しないで下さい)、& の左側に書かれている構造の配列を、& の右側の数字で埋めます。ここで、構造とはなんでしょうか?最初の構造は数字で、 \(n\ \&\ m = \{\underbrace{m,m,m,\cdots,m,m,m}_{\text{n 個の m}}\}\) となります。数字よりも上の構造は、X構造と言われ、m として評価されます。したがって、 \(X\ \&\ m = m \&\ m = \{m, m (1) 2\}\) となります。

もし他の数字を使いたければ、括弧に数字を入れて示すことができます。つまり、 \(X\ \&\ a[b] = b\ \&\ a[b]\) ということです。この表記は、 Bowers 自身は使いませんでした。

数字 X の上の構造は X+1,X+2,X+3,...,2X,2X+1,2X+2,2X+3,...,3X,4X,...,\(X^2\), 等となります。X+m は1行の要素の下に m 個の要素があるもの、 2X は2行、 3X は3行、 nX+m は n 行の要素の下に m 個の要素があるもの、となります。ここで、ここまでに示してきた表記と配列次元演算子の間の対応を示します。

\begin{eqnarray*} 1\ \&\ n &=& \{n\} = n \\ 2\ \&\ n &=& \{n,n\} = n^n \\ 3\ \&\ n &=& \{n,n,n\} = n \uparrow^{n} n \\ 4\ \&\ n &=& \{n,n,n,n\} = n \underbrace{ \{\{\cdots\{\{n\}\}\cdots\}\} }_{n \{\}'s} n \\ m\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{m n's}}\} &=& \{n,m (1) 2\} \\ X\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}}\} &=& \{n,n (1) 2\} \\ X+1\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) n\} \\ X+2\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) n,n\} \\ X+3\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) n,n,n\} \\ X+m\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{m n's}}\} \\ 2X\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}}\} \\ 3X\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}}\} \\ mX\ \&\ n &=& \{\underbrace{X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n(1)\cdots(1)X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n}_{\text{m X's}}\} &=& \{n,m (2) 2\} \\ X^2\ \&\ n &=& \{\underbrace{X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n(1)\cdots(1)X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n}_{\text{n X's}} &=& \{n,n (2) 2\} \end{eqnarray*}

お分かりのように、最後の3つの例は、それぞれ \(\{n,3 (2) 2\}, \{n,m (2) 2\}\) そして \(\{n,n (2) 2\}\) と簡略化できます。ここで、最後の "2" は次の平面で、3次元配列の開始を意味します。幸いにして、多次元の配列をそのままの形で描く必要がなくなります。重要な点は、多項式の形を使うことです。 \(a_1X^m+a_2X^{m-1}+a_3X^{m-2}+\cdots+a_{m-1}X+a_m \&\ b[p]\) という式は、配列が \(a_1\) 個の \(X^m\) (m次元配列の b)、そして \(a_2\) 個の \(X^{m-1}\)、そして \(a_3\) 個の \(X^{m-2}\)、といった構造となっていることを意味しています。要素の個数は、X を p に入れ替えて、通常の多項式を計算することで分かります。たとえば、 \(X^{100}+X^{99} \&\ 3[4]\) は \(4^{100}+4^{99}\) 個の要素があります。

ゴンギュラス は、配列次元演算子を使うと (10100) & 10 と書くことができて、これは100次元超立方体に1辺に10が10個入っている状態ですが、それを 101次元超立方体を使って簡略化すると {10,10 (100) 2} となります。

テトレーション配列

ここまでで、急成長階層が分かる方であれば、 \(f_{\omega^{\omega^\omega}}\) のレベルまでのシステムを構築することができました。次のステップはあまり分かりやすくはありませんが、さらに上のシステムへと続けるためには、肝要です。

\(\{b, p (0, 1) 2\}\)

これは一体何を意味するのでしょうか?これは \(X^X\) 構造で、 \(X^X\) 構造のプライムブロックは \(p^p\) 構造、つまり \(\underbrace{p \times p \times \cdots \times p \times p}_p\) の多次元立方体となります。つまり、2 x 2 の 2 の正方形か、 3 x 3 の 3 の立方体か、 4 x 4 の 4 の4次元超立方体か、といったようになります。これを実際に計算する時には、 (0, 1) を (p) と入れ替えます。たとえば、 \(\{b, 4 (0, 1) 2\} = \{b, 4 (4) 2\}\) となります。

技術的なメモです。 \(X^X\) 構造で表現される空間を、次元グループと言います。次元グループでは、それぞれの軸を特定の有限の数ではなく、order type \(\omega\) の軸の連なりで表現します。

\(\{b, p (1, 1) 2\}\)

This is an \(X^{X + 1}\) structure; its prime block is \(p^{p + 1}\). Generally, an \((n, m)\) separator creates an \(X^{mX + n}\) structure. It is a row of dimensional groups.

Linear separator arrays can describe all possible \(X^P\), where \(P\) is a polynomial in \(X\). (Here and in the rest of the article, we restrict "polynomial" to have nonnegative integer coefficients.) They do this by supplying a list of coefficients from degree 0 on:

\((a_0, a_1, a_2, a_3, \ldots)\) describes a structure of type \(X^{a_0 + a_1X + a_2X^2 + a_3X^3 + \cdots}\)

So, for example, (0, 0, 1) describes \(X^{X^2}\) (dimensional gang), and (1, 0, 6, 1) describes \(X^{1 + 6X^2 + X^3}\). You will notice that now zeroes are the default rather than 1's; this is one of BEAF's more annoying properties.

\(\{b, p (0 (1) 1) 2\} = \{b, p ((1) 1) 2\}\)

Of course, we have no reason to stop at linear arrays for separators. This structure is \(X^{X^X}\), a superdimensional group. (Vectors in a superdimensional group have order type \(\omega^\omega\).) In general for the second row,

\((a_{00}, a_{01}, a_{02}, \ldots (1) a_{10}, a_{11}, a_{12}, \ldots )\) describes a structure of type \(X^{a_{00} + a_{01}X + a_{02}X^2 + a_{03}X^3 + \cdots + a_{10}X^X + a_{11}X^{X + 1} + a_{12}X^{X + 2} + \ldots}\).

The third row ((1)(1)1) describes \(X^{X^{2X}}\) (no, we're not at \(X^{X^{X^X}}\) yet!), and the (n + 1)-th row describes \(X^{X^{nX}}\). The second plane ((2)1) is \(X^{X^{X^2}}\), the second realm ((3)1) is \(X^{X^{X^3}}\), and so on and so forth. We finally reach \(X^{X^{X^X}} = X \uparrow\uparrow 4\) at the second dimensional group, ((0, 1) 1). The inner pair of parentheses describes a polynomial \(P\) in \(X\), with the outer one describing \(X^{X^{X^P}}\).

\(\{b, p (((1) 1) 1) 2\}\)

This is \(X^{X^{X^{X^X}}} = X \uparrow\uparrow 5\).

\(\{b, p (((0, 1) 1) 1) 2\}\) describes \(X \uparrow\uparrow 6\)
\(\{b, p ((((1) 1) 1) 1) 2\}\) describes \(X \uparrow\uparrow 7\)
\(\{b, p ((((0, 1) 1) 1) 1) 2\}\) describes \(X \uparrow\uparrow 8\)
etc.

The limit of all this is the \(X \uparrow\uparrow X\) structure. If we stop here, we have tetrational array notation.

定義への挑戦

Bowers はテトレーション配列に厳密な定義を与えようとしませんでしたが、ためしにやってみましょう。The only thing holding us back right now is the definition of prime blocks, which is specifically tailored for dimensional arrays only. Let's look at our current inductive definition:

  • The prime block of an entry is an entry.
  • The prime block of an \(X^{n + 1}\) structure is the prime blocks of its first \(p\) \(X^n\)-structures.

(There is a slight change here, but it can be seen that it has minimal effect.) This definition doesn't say what happens when our structure is an \(X^X\) structure, because it's not a structure of the form \(X^{n + 1}\).

Let's try to extend this definition to allow all \(X^P\) for degree-1 polynomials \(P\).

  • The prime block of an entry is an entry.
  • The prime block of an \(X^{P+1}\) structure is the prime blocks of its first \(p\) \(X^P\)-structures, where \(P\) is a polynomial in \(X\).
  • The prime block of an \(X^{P+X}\) structure is the prime block of its first \(X^{P + p}\)-structure.

This breaks down at \(X^{X^2}\) as expected, but there is a pattern emerging.

  • The prime block of an entry is an entry.
  • The prime block of an \(X^{P + 1}\) structure is the prime blocks of its first \(p\) \(X^P\)-structures, where \(P\) is a polynomial in \(X\).
  • The prime block of an \(X^{P + X}\) structure is the prime block of its first \(X^{P + p}\)-structure.
  • The prime block of an \(X^{P + X^2}\) structure is the prime block of its first \(X^{P + pX}\)-structure.
  • The prime block of an \(X^{P + X^3}\) structure is the prime block of its first \(X^{P + pX^2}\)-structure.
  • In general, the prime block of an \(X^{P + X^{n + 1}}\) structure is the prime block of its first \(X^{P + pX^n}\)-structure.

This works up until \(X^{X^X}\). At this rate we'll never get to \(X \uparrow\uparrow X\)!

2回目の挑戦

Let's generalize the concept of "structure" to help out our definition.

  • \(0\) is a structure.
  • If \(\alpha\) is a structure, \(X^\alpha\) is also a structure.
  • If \(\alpha\) and \(\beta\) are structures, \(\alpha + \beta\) is also a structure.

This allows things like \(2X\) and \(4X^X + X + 1\), and works up until our limit of \(X \uparrow\uparrow X\). Furthermore, let's define a limit structure as one of the form \(X^\alpha\) for \(\alpha > 0\) or \(\alpha+\beta\) for \(\alpha\) and \(\beta\) being limit structures, and a successor structure as one of the form \(\alpha + 1\).

Now we'll recursively define the prime block of a structure \(\alpha[p]\).

  • \(0[p] = \{\}\)
  • \((\alpha + 1)[p] = \alpha[p] \cup \{\text{the last entry of }\alpha + 1\}\)
  • \(X[p] = p\) and \(X^{\alpha + 1}[p] = X^{\alpha} p\)
  • \(X^{\alpha}[p] = X^{\alpha[p]}\) if and only if \(\alpha\) is a limit structure.
  • \((X^{\alpha_1} + X^{\alpha_2} + \cdots + X^{\alpha_{k - 1}} + X^{\alpha_k})[p] = (X^{\alpha_1} + X^{\alpha_2} + \cdots + X^{\alpha_{k - 1}} )[p] \cup X^{\alpha_k}[p])\) where \(\alpha_k\) is the smallest \(\alpha_i\)
  • \(X\uparrow\uparrow X[0] = 1\) and \(X\uparrow\uparrow X[p] = X^{X\uparrow\uparrow X[p-1]}\)

If you are confused by now, skip it. All you need an intuitive conception of how this works.

There's one final step. Notice how we used the word "smallest" in the definition above, but structures aren't numbers and we haven't yet defined an ordering. This is easy:

  • \(\alpha < \alpha + X^0\)
  • \(X^\alpha < X^\beta\) iff \(\alpha < \beta\)
  • \(\alpha + \gamma < \beta + \gamma\) iff \(\alpha < \beta\)

And we're done! Tetrational arrays.

But can we make this simpler?

順序数として (上級編)

数学の知識がある読者は、ここまでの議論が順序数による階層と似ていることに気がついたかもしれません。\(X\) 関数は \(\omega\) とよく似ていて、プライムブロックの定義は急成長階層の Wainer 階層と似ているように見えます。\(\alpha[p]\) という表記を使ったのは、そのためです。ここまでで、 \(\varepsilon_0\) までの表記を構築できました。これは、ここまでの BEAF の強さになっています。これまでの表記を順序数を使って書き直すのは、理にかなっています。やってみましょう。

We'll define an array as a function \(A : \varepsilon_0 \mapsto \mathbb{N}_+\), where the number of outputs greater than 1 is finite. (This prevents infinite arrays like {6, 6, 6, ...}.) Let \(b = A(0)\), \(p = A(1)\), \(\pi = \min\{\alpha > 1: A(\alpha) > 1\}\) (the position of the pilot), and \(\kappa = \pi - 1\) (the position of the copilot).

Define the prime block \(\Pi(\alpha)\):

  • \(\Pi(0) = \{\}\)
  • \(\Pi(\alpha + 1) = \{\alpha\} \cup \Pi(\alpha)\)
  • \(\Pi(\alpha) = \Pi(\alpha[p])\) if \(\alpha\) is a limit ordinal

(This looks a lot like the slow-growing hierarchy.) Define the passengers as \(S = \Pi(\pi) \backslash \{\pi, \kappa\}\).

And the three rules:

  1. Base rule. If \(\pi\) does not exist, \(v(A) = b^p\).
  2. Prime rule. If \(p = 1\), \(v(A) = p\).
  3. Catastrophic rule. Define \(A'\) as \(A\) with the following modifications:
    • Define \(B\) as \(A\), but with \(B(1) = p - 1\).
    • If \(\kappa\) exists, \(A'(\kappa) := v(B)\).
    • \(A'(\pi) = A(\pi) - 1\).
    • \(A(\sigma) := b\) for \(\sigma \in S\).
    • \(v(A) = v(A')\).

Although less accessible, this is a far simpler definition than above!

One more thing; let's define some fundamental sequences for ordinals below \(\varepsilon_0\).

  • \(\omega^\alpha[n] = \omega^{\alpha[n]}\) for limit ordinals \(\alpha\)
  • \(\omega^{\alpha + 1}[n] = \omega^\alpha n\)
  • \((\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_k})[n] = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_k}[n]\) where \(\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_k\)
  • \(\omega \uparrow\uparrow 0 = 1\)
  • \((\omega \uparrow\uparrow (\alpha + 1))[n] = \omega^{\omega \uparrow\uparrow \alpha}[n]\)

We threw in a definition of \(\omega \uparrow\uparrow n\) to ensure that we properly mirror Bowers' \(X\) hierarchy. Indeed, after \(\varepsilon_0\) the fundamental sequences depart a bit from the usual.

ペンテーション配列

ペンテーション配列は、少しわけがわかりません。なんといっても一番良くないのは、ペンテーション配列を表記する方法が考案されていないのです!Bowers は、そのことを気にしませんでした。彼はただ、配列次元演算子を使ってペンテーション配列を書いただけです。

配列次元演算子を覚えていますか?このようなものです。

\(a \& b = \{b, a (1) 2\}\)

配列次元演算子は、1行の配列の時に導入してから、ずっと使っていませんでした。そして、 & の記号はさらにその先のレベルにまで拡張可能であることが分かります。

\(a^2 \& b = \{b, a (2) 2\}\)

右辺はa×aの配列にbという要素が満たされているもの、すなわち a2 配列の b であることを理解することは、難しくありません。ここで、 "\(a^2\)" という表記は、最初に計算してしまってはいけないことに注意して下さい。これはむしろ、配列の次元の形を示す青写真です。

\(a^k \& b = \{b, a (k) 2\}\)

In general, the array-of operator lets us specify many dimensions, and even tetrational arrays such as this one:

\(a^{a^a} \& b = a \uparrow\uparrow 3 \& b = \{b, a ((1) 1) 2\}\)

For those who understood the ordinal definition above, we can formally define \(f(a) \& b = \{0 \mapsto b, 1 \mapsto a, f(\omega) \mapsto 2\}\).

The smallest pentational array is this one:

\((a \uparrow\uparrow a) \& b = \{b, a (???) 2\}\)

There is no notation for this array (an \(X \uparrow\uparrow X\) structure), but it's certainly definable with ordinals, where \(\omega \uparrow\uparrow \omega = \varepsilon_0\) using the fundamental sequence \(\varepsilon_0[n] = \omega \uparrow\uparrow n\). We'll take a moment to apologize to the readers who don't get ordinals yet. Skip ahead to the legion arrays if you're one of them.

At this point you may be wondering what \(X \uparrow\uparrow\uparrow X\) is, but we can't move on to that until we've defined \(X \uparrow\uparrow (X2)\) or the fundamental sequence of "\(\omega \uparrow\uparrow (\omega2)\)". Our current definition of \(\uparrow\uparrow\) over the ordinals would make \(\omega \uparrow\uparrow (\omega2) = \omega \uparrow\uparrow \omega\), so we need to repair that.

If we amend our definition to \(\omega \uparrow\uparrow (1 + \alpha) = \omega^{\omega \uparrow\uparrow \alpha}\), we can clearly see that \(\omega \uparrow\uparrow (1 + \omega) = \omega \uparrow\uparrow \omega\) is the fixed point of the function \(\omega \mapsto \omega^\alpha\).

\(\omega \uparrow\uparrow (\omega2)\) should be the next fixed point, i.e. \(\varepsilon_1\). One particularly clean definition of \(\varepsilon_1\) is the limit of \(\varepsilon_0, \varepsilon_0^{\varepsilon_0}, \varepsilon_0^{\varepsilon_0^{\varepsilon_0}}, \ldots\), so why not make \(\varepsilon_1 = \varepsilon_0 \uparrow\uparrow \omega = (\omega \uparrow\uparrow \omega) \uparrow\uparrow \omega\)? This seems slightly odd at first, since in general \(a \uparrow\uparrow a2 \neq (a \uparrow\uparrow a) \uparrow\uparrow a\). Ordinals work in mysterious ways.

The next fixed point is \(\omega \uparrow\uparrow (\omega3) = \varepsilon_1 \uparrow\uparrow \omega = \varepsilon_2\), and in general \(\omega \uparrow\uparrow (\omega n) = \varepsilon_{n - 2} \uparrow\uparrow \omega = \varepsilon_{n-1}\) for finite \(n > 0\). Understandably, the limit of all these is \(\omega \uparrow\uparrow (\omega^2) = \varepsilon_\omega\).

Yada yada yada. Nothing too interesting here until \(\varepsilon_{\varepsilon_0} = \omega \uparrow\uparrow (\omega \uparrow\uparrow \omega) = \omega \uparrow\uparrow\uparrow 3\) an \(\varepsilon_{\varepsilon_{\varepsilon_0}} = \omega \uparrow\uparrow\uparrow 4\). The triple arrows are quite promising, and indeed the limit of all this is \(\zeta_0 = \omega \uparrow\uparrow\uparrow \omega\). Boom. Done.

厳密な定義

良い知らせです。ペンテーション配列を正式に定義するためには、順序数と収束列を定義すればそれでいいわけです。配列表記は標準的な順序数の計算には含まれていないため、きちんと定義を与える必要があります。

  • \(\alpha \uparrow\uparrow 0 = 1\)
  • \(\alpha \uparrow\uparrow (n + 1) = \alpha^{\alpha \uparrow\uparrow n}\) for \(n < \omega\)
  • \(\alpha \uparrow\uparrow \beta = \bigcup\{\gamma < \beta : \alpha \uparrow\uparrow \gamma\}\) for limit ordinals \(\beta\)
  • \(\alpha \uparrow^{k} (\beta + \omega) = lim\{(\alpha \uparrow^k \beta),(\alpha \uparrow^k \beta)^{(\alpha \uparrow^k \beta)},(\alpha \uparrow^k \beta)^{(\alpha \uparrow^k \beta)^{(\alpha \uparrow^k \beta)}},...\}\) for \(\beta \geq \omega\)
  • \((\alpha \uparrow\uparrow \beta)[n] = \alpha \uparrow\uparrow \beta[n]\)

より大きいレギオンを使わない配列

前節で、 \(\zeta_0 = \omega \uparrow\uparrow\uparrow \omega\) まで定義ができました。これは、 \(\omega \uparrow\uparrow\uparrow \omega = \{\omega, \omega, 3\}\) とも書くことができます。では、 \(\{\omega, \omega, 4\}\) の定義をしない理由があるでしょうか?また、\(\{\omega, \omega, 1, 2\}\) はどうでしょう?\(\{\omega, \omega (0, 1) 2\}\) は?

唯一の障害は、厳密な定義ができるかどうかです。順序数による BEAF を定義する必要があります。まずは、有限の長さの矢印に対する矢印表記から始めます。

  • \(\alpha \uparrow \beta = \alpha^\beta\)
  • \(\alpha \uparrow^k 0 = 1\)
  • \(\alpha \uparrow^{k + 1} (n + 1) = \alpha \uparrow^k (\alpha \uparrow^{k + 1} n)\) for \(n < \omega\)
  • \(\alpha \uparrow^k \beta = \sup\{\gamma < \beta : \alpha \uparrow^k \gamma\}\) for limit ordinals \(\beta\)
  • \(\alpha \uparrow^{k} (\beta + \omega) = lim\{(\alpha \uparrow^k \beta),(\alpha \uparrow^k \beta)\uparrow^{k-1}(\alpha \uparrow^k \beta),(\alpha \uparrow^k \beta)\uparrow^{k-1}(\alpha \uparrow^k \beta))\uparrow^{k-1}(\alpha \uparrow^k \beta),...\} \) for \(\beta \geq \omega\)
  • \((\alpha \uparrow^k \beta)[n] = \alpha \uparrow^k \beta[n]\)


It's not hard to see that ordinal arrow notation is similar to the Veblen function, and the differences are mostly in the fundamental hierarchies. Analogous to the Veblen unction, \(\alpha \mapsto \omega \uparrow^{k + 1} (\omega + \alpha)\) enumerates the fixed points of \(\alpha \mapsto \omega \uparrow^k \alpha\).

Already this definition is mildly annoying due to the sheer number of rules. Anyways, let's try \(k = \omega\):

  • \(\alpha \uparrow^\omega \beta = \sup\{k < \omega : \alpha \uparrow^k \beta\}\)
  • \((\alpha \uparrow^\omega \beta)[n] = \alpha \uparrow^n \beta\)

Take note that \(\omega \uparrow^\omega \omega = \phi_\omega(0)\). Our existing framework works for successor ordinals \(k\), but we need some limits here:

  • \(\alpha \uparrow^\kappa \beta = \sup\{\gamma < \kappa : \alpha \uparrow^\gamma \beta\}\)
  • \((\alpha \uparrow^\kappa \beta)[n] = \alpha \uparrow^{\kappa[n]} \beta\)

Putting it all together:

  • \(\alpha \uparrow \beta = \alpha^\beta\)
  • \(\alpha \uparrow^\kappa 0 = 1\)
  • \(\alpha \uparrow^{\kappa + 1} (n + 1) = \alpha \uparrow^\kappa (\alpha \uparrow^{\kappa + 1} n)\) for \(n < \omega\)
  • \(\alpha \uparrow^\kappa (\beta + 1) = (\alpha \uparrow^\kappa \beta) \uparrow^\kappa \alpha\) for \(\beta \geq \omega\)
  • \(\alpha \uparrow^\kappa \beta = \sup\{\gamma < \kappa : \alpha \uparrow^\gamma \beta\}\) for limit ordinals \(\kappa\)
  • \(\alpha \uparrow^\kappa \beta = \sup\{\gamma < \beta : \alpha \uparrow^\kappa \gamma\}\) for limit ordinals \(\beta\)
  • \((\alpha \uparrow^\kappa \beta)[n] = \alpha \uparrow^{\kappa[n]} \beta\) for limit ordinals \(\kappa\)
  • \((\alpha \uparrow^\kappa \beta)[n] = \alpha \uparrow^\kappa \beta[n]\) for limit ordinals \(\beta\)

This definition works okay, but the last two pairs of rules have identical conditions. In the case of \((\omega \uparrow^\omega \omega)[n]\), we'd rather have \(\omega \uparrow^n \omega\), so if \(\kappa\) and \(\beta\) are limit ordinals, we should focus on \(\kappa\) first.

In the meantime, let's write this out as three-entry array notation. This is ordinary three-entry notation with some limit ordinal cases. To simplify things, we won't allow any of the entries to be 0 as with ordinary array notation.

  • \(\{a, b, 1\} = a^b\)
  • \(\{a, 1, c\} = a\)
  • \(\{a, b + 1, c + 1\} = \{a, \{a, b, c + 1\}, c\}\) for \(b < \omega\)
  • \(\{a, b + 1, c\} = \{\{a, b, c\}, a, c\}\) for \(b \geq \omega\)
  • \(\{a, b, c\} = \sup\{x < c: \{a, b + 1, x\}\}\) for \(c \in \text{Lim}\)
  • \(\{a, b, c + 1\} = \sup\{x < b: \{a, b + 1, c + 1\}\}\) for \(b \in \text{Lim}\)
  • \(\{a, b, c\}[n] = \{a, b, c[n]\}\) for \(c \in \text{Lim}\)
  • \(\{a, b, c + 1\}[n] = \{a, b[n], c + 1\}\) for \(b \in \text{Lim}\)

Where \(\text{Lim}\) is set of all limit ordinals.

We can also remove the fourth and fifth rules if we define them as the limits of the sixth and seventh rules, respectively.

Now for four entries:

  • \(\{a, b, 1, 1\} = a^b\)
  • \(\{a, 1, c, d\} = a\)
  • \(b < \omega:\)
    • \(\{a, b + 1, 1, d + 1\} = \{a, \{a, b, 1, d + 1\}, 1, d\}\)
    • \(\{a, b + 1, c + 1, d\} = \{a, \{a, b, c + 1, d\}, c, d\}\)
  • \(b > \omega:\)
    • \(\{a, b + 1, c, d\} = \{\{a, b, c, d\}, a, c, d\}\)
  • \(\{a, b, c, d\}[n] = \{a, b, c, d[n]\}\) for \(d \in \text{Lim}\)
  • \(\{a, b, c, d + 1\}[n] = \{a, b, c[n], d + 1\}\) for \(c \in \text{Lim}\)
  • \(\{a, b, c + 1, d + 1\}[n] = \{a, b[n], c + 1, d + 1\}\) for \(b \in \text{Lim}\)

Generalization is easy from here.

Linear ordinal array notation

Definitions are unchanged — the first entry is the base \(b\), the second entry is the prime \(p\), the first non-1 entry after the prime is the pilot, the entry before it is the copilot, and the passengers are all entries before the copilot. In addition, we'll define the limiter \(l\) as the last limit ordinal after the base; it may not exist if there are only successor ordinals from the prime on.

All entries are between zero and \(\omega_1\) exclusive.

  1. Base rule. If there is no pilot, \(v(A) = b^p\).
  2. Prime rule. If \(p = 1\), \(v(A) = b\).
  3. Catastrophic rule. If there is no limiter and \(p < \omega\)...
    1. Replace the copilot with a copy of the array with the prime decreased by 1. (The prime must be a successor ordinal, otherwise there would be a limiter.)
    2. Decrease the pilot by 1.
    3. Set all the passengers to \(b\).
  4. Infinite catastrophic rule. If there is no limiter and \(p \geq \omega\)...
    1. Replace the base with a copy of the array with the prime decreased by 1. (The prime must be a successor ordinal, otherwise there would be a limiter.)
    2. Set the prime to the original value of \(b\).
  5. Limit rule. Otherwise...
    1. Let \(v(A)[n]\) be the value of the array with the limiter changed to \(l[n]\).
    2. \(v(A) = \sup\{1 \leq < n < \omega : v(A)[n]\}\).
(end of definition)

Of course, we have no reason to stop at linear arrays. Our tetrational BEAF easily extends to ordinals; we just need to throw in the limit rule, and expand the domain of \(A\) from \(\varepsilon_0\) to \(\omega_1\), the first ordinal without a fundamental sequence with countable length. We'll prohibit ourselves from just plugging in any large countable ordinal, since we're building from the ground up and using BEAF to define the ordinals as we go along.

ところで、これでどこまでの順序数を定義したことになるでしょうか?かなりたくさんです。

  • \(\Gamma_0 = \{\omega, \omega, 1, 2\}\) (膨張配列)
  • \(\vartheta(\Omega^2) = \{\omega, \omega, 1, 1, 2\}\)
  • \(\vartheta(\Omega^\omega) = \{\omega, \omega (1) 2\}\)
  • \(\vartheta(\Omega^\Omega) = \{\omega, \omega, 2 (1) 2\}\) (英語版のソースのコメントより: これが本当かどうかは分からない。LVO のページからコピーしただけ。)
  • \(\vartheta(\varepsilon_{\Omega + 1}) = \{\omega, \omega (\varepsilon_0) 2\}\)

現時点でのこの表記の限界は \(\vartheta(\Omega_\omega)\) となります。これは、ものすごい成果です!

レギオン配列

順序数が分からない読者の皆さん、ここまでお待ちいただいてありがとうございます!ここまでで、レギオンを使わないBEAFである「サブレギオン BEAF」の説明をしました。Bowers は、ここまでのすべてを「L空間」(L-space) と呼びました。

ここで、配列次元演算子 & がよみがえります。どんどんと強い表記が出てきていますが、& も同様に強くなります。ここまでの配列次元演算子では、たとえば {3, 3, 3}&3 (トリアクルス) によってペンテーション配列が定義出来ました。配列次元演算子は、常に最も強い表記を対角化することができます。

トリアクルスは、 (3&3)&3 とも書くことができます。配列次元演算子は左結合なので、この括弧を外して 3&3&3 と書くことができます。そうすると、自然に新しい演算子 ♦ が導入され、 bp = b&b&...&b&bp 回繰り返したものと定義できます。この演算子は、レギオンを使わないBEAFの限界を示していて、これまでに定義した関数の中で最も強力になります。

\(b♦p\) という式の形から、少し \(b^p\) を思い出させられるので、2行配列の時にやったことと同じトリックを使ってみましょう。この「レベル2のサブレギオンBEAF」を、基数ルールを \(b♦p\) に定義し直すことで作ることができます。

2行配列表記の時にやったように、高レベルのサブレギオン BEAF へと拡張して、レベルは配列の一部となります。ここでは、すぐにレベルを配列の中に入れてしまいましょう。

\(\{b, p / 2\} = b♦p\)

スラッシュの境界は、レギオン空間と言われる新しい空間の種類の区切りです。パイロットの 2 は2番目のレギオンにあります。これはちょうど、平面配列表記の時に、パイロットを2行目に移動したのと同じことです。レギオンのプライムブロックは \(b♦p\) となり、したがってたとえば \(\{b, p / 3\} = \{b♦p / 2\}\) となります。

\(\{b, p / 1, 2\} = \{b♦p / \{b, p - 1 / 2\}\}\)

Legions form a larger space than rows, planes, or any structure we've defined so far, so we can put multiple entries in the second legion.

\(\{b, p / 1 / 2\} = \{b♦p / b♦p\}\)

We can also throw in more than two legions...

\(\{b, p (/1) 2\} = \{b♦p / b♦p / \ldots / b♦p / b♦p\}\) with \(p\) legions
\(\{b, p (/0,1) 2\} = \{b♦p / b♦p / \ldots / b♦p / b♦p\}\) where the legions form a \(p^p\) structure

...and the legions themselves can take on dimensional structures of any size.

Another notation for \(\{b, p (/1) 2\} = \{b♦p / b♦p / \ldots / b♦p / b♦p\}\) is \(p \&\& b\), or p legion array of b. Similarly, \(\{b, p (/(1)1) 2\} = p^p \&\& b\), so the && operator works similarly to & but with legions instead of entries. We'll use b♦♦p to mean b&&b&&..&&b&&b p times, and we'll introduce "legion legion space" using the separator \(//\).

\(\{b, p // 2\} = b♦♦p = b \&\& b \&\& \ldots \&\& b \&\& b\)
\(\{b, p (//1) 2\} = \{b♦♦p / b♦♦p / \ldots / b♦♦p / b♦♦p\} = b \&\&\& p\)
\(\{b, p /^n 2\} = b♦^np = b \&^n b \&^n \ldots \&^n b \&^n b\)
\(\{b, p (/^n1) 2\} = \{b♦^np / b♦^np / \ldots / b♦^np / b♦^np\} = b \&^{n + 1} p\)

Extension is straightforward.

\(\{b, p (1)/ 2\} = \{b, p /^p 2\} = b (1)\& p\)
\(\{b, p ///(1)///(1)/// 2\}\)

Why not give the legions a multidimensional structure themselves? Trouble is, we need to define this. Let L be a legion structure, which is greater than all structures up to but not including legions. (So L is a legion in the same way that X is a row.) We could say that L = {X, X / 2}, but that's uncomfortably circular. Anyways, the prime block of a legion is \(b♦p\).

Two legions is a \(2L\) structure, a row of legions is an \(XL\) structure, a legion legion // is an \(L^2\) structure. From here we can put L inside an array the same way we wrote things such as {X, X, X}. We can write \(\{L, L\}\) or \(\{L, L, L\}\) or \(\{L, X (1) 2\} = X\&L\). Unfortunately, by this time we have no notation for separators, but Bowers supplied the notation \(\{L, L\}_{b, p}\) (say) to mean an \(\{L, L\}\) structure solved with b as the base and p as the prime.

We continue to drop L into larger and larger arrays until we reach the landmark \(\{L, L / 2\}\), or lugion space. Bowers also writes this \(L2\) using the separator \ and the operator \(a@b\), or a legiattic array of b.

定式化

We will quickly catch up on the definition of legion arrays with ordinals. First, we'll notice that the array-of operator has three parts: a base, prime, and structure type. For example, \(3\&4\) has base 4, prime 3, and structure type X, and \(3 \uparrow\uparrow\uparrow 4 \& 5\) has base 5, prime 3, and structure type \(X \uparrow\uparrow\uparrow 4\). Bowers' minor abuse of notation can be mended with a three-argument array-of operator:

\(\lambda(b, p, \xi) = \{(0, b), (1, p), (\xi, 2)\}\)

That is, base \(b\), prime \(p\), and the number 2 in position \(\xi\). Normally \(\xi\) is a limit ordinal, but our new function allows any \(\xi > 1\).

The ordinal for legion space is the unnamed ordinal \(\vartheta(\Omega_\omega) = \{\omega, \omega / 2\}\), and its fundamental sequence is \(\vartheta(\Omega_\omega)[1] = \omega,\,\vartheta(\Omega_\omega)[2] = \lambda(\omega, \omega, \omega),\,\vartheta(\Omega_\omega)[3] = \lambda(\omega, \omega, \lambda(\omega, \omega, \omega)),\) and so and so forth. This defines the prime block of a \(\vartheta(\Omega_\omega)\) structure as defined before.

(ここから先は、英語版ではコメントアウトされていますが、そのまま載せてみます。)

This ordinal is directly analogous to Bowers' L-space. To convert things with ordinals, just swap out L with \(\vartheta(\Omega_\omega)\):

  • \(2L = \vartheta(\Omega_\omega)2\), separator "/ 1 /"
  • \(XL = \vartheta(\Omega_\omega)\omega\), separator "(/1)"
  • \(L^2 = \vartheta(\Omega_\omega)^2\), separator "//"
  • \(\{L, X\} = \vartheta(\Omega_\omega)^\omega\), separator "(1)/"
  • \(\{L, L\} = \vartheta(\Omega_\omega)^{\vartheta(\Omega_\omega)}\)
  • \(\{L, L, 2\} = \vartheta(\Omega_\omega) \uparrow\uparrow \vartheta(\Omega_\omega)\)
  • \(\{L, L (1) 2\} = \lambda(\vartheta(\Omega_\omega), \vartheta(\Omega_\omega), \omega)\)
  • \(\{L, L (0, 1) 2\} = \lambda(\vartheta(\Omega_\omega), \vartheta(\Omega_\omega), \varepsilon_0)\)
  • \(\{L, L / 2\} = L2 = \lambda(\vartheta(\Omega_\omega), \vartheta(\Omega_\omega), \vartheta(\Omega_\omega))\), separator "\"
  • \(\{L2, L2 \backslash 2\} = L3 = \lambda(L2, L2, L2)\), separator "|"
  • \(\{L3, L3 | 2\} = L4 = \lambda(L3, L3, L3)\), separator "-"
  • \(\{L4, L4 - 2\} = L5 = \lambda(L4, L4, L4)\)
  • \(LX = \vartheta(\Omega_{\omega^2})\)
  • \(L(X^2) = \vartheta(\Omega_{\omega^3})\)
  • \(L(X^X) = \vartheta(\Omega_{\omega^\omega})\)
  • \(LL = \vartheta(\Omega_\Omega)\)
  • \(LLL = \vartheta(\Omega_{\Omega_\omega})\)
  • \(L^X = \psi(\psi_I(0))\)

Our notation is clashing with itself. Haven't we already defined \(L^X\), and why is it bigger this time? Bowers' L notation maxes out here due to an ambiguity, but we will continue to (ab)use it for the sake of understanding.

  • \(L^{2X} = \psi(\psi_I(1))\)
  • \(L^{X^2} = \psi(\psi_I(\omega))\)
  • \(L^{X^X} = \psi(\psi_I(\omega^\omega))\)
  • \(L^L = \psi(\psi_I(\vartheta(\Omega_\omega)))\)
  • \(\{L, 3, 2\} = \psi(\psi_I(\vartheta(\Omega_\omega)))\)
  • \(\{L, 4, 2\} = \psi(\psi_I(\psi(\psi_I(\vartheta(\Omega_\omega)))))\)
  • \(\{L, X, 2\} = \psi(I)\)
  • \(\{L, L, 2\} = \psi(I \vartheta(\Omega_\omega))\)
  • \(\{L, \{L, L, 2\}, 2\} = \psi(I \psi(I \vartheta(\Omega_\omega)))\)
  • \(\{L, X, 3\} = \psi(I^2)\)
  • \(\{L, X, n\} = \psi(I^{n-1})\)
  • \(\{L, X, X\} = \psi(I^\omega)\)
  • \(\{L, L / 2\} = \)

Although we have no good reason to stop, this is where BEAF traditionally ends. This final ordinal describes the level of ミーミーミーロッカプーワ・ウンパ.

外部リンク

Advertisement