段階配列表記

\( \newcommand{\W}{\Omega} \newcommand{\w}{\omega} \newcommand{\p}{\psi} \newcommand{\a}{\alpha} \newcommand{\b}{\beta} \newcommand{\g}{\gamma}\) 段階配列表記^[1]は mrna^[2] が2020年8月12日に公開^[3]した巨大数表記である。

段階配列表記は、ブーフホルツのψ関数の \(\p\) と\((0)\) を消し去って、表記化したものに相当する。段階配列表記の画期的な点の１つは、ブーフホルツのオリジナルの順序数表記と異なり順序数の共終数の類似である項の\(\textrm{dom}\)に対応する写像を直接定義せずに \(\p_0(\Omega_{\omega})\) までの順序数を表現していることである。代わりに展開規則には\(k\)という文字の置換を用いた具体的なアルゴリズムが採用されている。

段階配列表記の増加速度は \(0(n)[n]\) で \(f_{\p_0(\W_\w)}(n)\) である^[4]。

段階配列数 は段階配列表記を用いて定義^[5]された巨大数である。

定義

文字列集合 \(S\)

非負整数と \((\) と \()\) と \(+\) のみからなる文字列の集合 \(S\) を下記のように定義する。

いかなる非負整数も \(S\) に属する。
いかなる \(\a, \b \in S\) に対しても、文字列 "\(\a+\b\)" は \(S\) に属する。
いかなる \(\a\in S\) に対しても、\(n\) が非負整数ならば文字列 "\(n(\a)\)" は \(S\) に属する。

集合 \(P\)

以下を満たす \(\g \in S\) 全体の集合を \(P\) とする。

いかなる \(\a, \b \in S\) に対しても \(\g \neq \a+\b\) である。
\(\g \neq 0\) である。

集合 \(S_n\)

非負整数と\((\) と \()\) と \(+\) と \(k\) のみからなる文字列の集合 \(S_n\) を下記のように定義する。(\(n\) は非負整数)

文字 \(k\) は \(S_n\) に属する。
いかなる \(\a \in S,~\b \in S_n\) に対しても、文字列 "\(\a+\b\)" は \(S_n\) に属する。
いかなる \(\a \in S_n\) に対しても、\(n\leq m\) ならば文字列 "\(m(\a)\)" は \(S_n\) に属する。

文字列 \(S_{n,\a}(\b)\)

\(S_{n,\a}(\b)\) を \(S_n\) の要素 \(\a\) の文字 \(k\) を文字列 \(\b\) に置き換えた文字列とする。

写像 \(f(\a,n)\)

正整数全体の集合を\(\mathbb{N}_+\)と置く。写像 \begin{eqnarray*}f \colon S\times \mathbb{N}_+&\rightarrow& S\\(\a,n) &\mapsto& f(\a,n)\end{eqnarray*} を下記のように定義する。 (\(a,b,m\) は非負整数)

\(\a=m\) と表せるならば、
\(f(\a,n)=0\)
\(\a=\b+0~(\b\in S)\) と表せるならば、
\(f(\a,n)=\b\)
\(\a=\b+\g~(\b\in S,~\g\in P)\) と表せるならば、
\(f(\a,n)=\b+f(\g,n)\)
\(\a=a(S_{0,\b}(b))~(a\neq 0,~b\neq 0,~a\geq b,~\b\in S_0)\) と表せるならば、
\(f(\a,n)=0(S_{0,\b}(b))\)
\(\a=S_{0,\b}(m(0))~(\b\in S_0)\) と表せるならば、
\(f(\a,n)=S_{0,\b}(\underbrace{m+m+\cdots+m}_{n~{\rm 個}})\)
\(\a=S_{0,\b}(m(\g+0))~(\b\in S_0,~\g\in S)\) と表せるならば、
\(f(\a,n)=S_{0,\b}(\underbrace{m(\g)+m(\g)+\cdots+m(\g)}_{n~{\rm 個}}) \)
\(\a=a(S_{b,\b}(b))~(\b\in S_b,~a\lt b,~b\neq 0)\) と表せるならば、
\(f(\a,n)=a(\underbrace{S_{b,\b}(b'(S_{b,\b}(b'(\cdots S_{b,\b}(b'}_{S_{b,\b}(b'~{\rm が}~n~{\rm 個}}~\underbrace{)))\cdots)}_{n~{\rm 個}})\) (\(b'\) は \(b\) の前者)
\(\a=S_{0,\b}(a(S_{b,\g}(b)))~(\b\in S_0,~\g\in S_b,~a\lt b,~b\neq 0)\) と表せるならば、
\(f(\a,n)=S_{0,\b}(f(a(S_{b,\g}(b)),n))\)

巨大数表記

\(0[n]=n\times 2\)
\(\a[n]=f(\a,n)[n\times 2]~(\a\neq 0)\)

巨大数

\(g(n)=0(n)[n]\) としたとき、\(g^{100}(100)\) を段階配列数とする。

解析

以下はp進大好きbotによる停止性および解析に関する結果である^[4]。

\(\mathbb{N}\)を非負整数全体の集合、\(T\)をBuchholzの表記系、\(OT \subset T\)をBuchholzの順序数表記とする。写像 \begin{eqnarray*} o \colon S & \to & T \setminus \{0\} \\ \alpha & \mapsto & o(\alpha) \end{eqnarray*} を以下のように再帰的に定める：

\(\alpha \in \mathbb{N}\)ならば、\(o(\alpha) := D_{\alpha} 0\)である。
\(\alpha = \beta + \gamma\)を満たす\(\beta \in S\)と\(\gamma \in P\)が存在するならば、\(o(\alpha) := o(\beta) + o(\gamma)\)である。
\(\alpha = m(\beta)\)を満たす\(m \in \mathbb{N}\)と\(\beta \in S\)が存在するならば、\(o(\alpha) := D_m o(\beta)\)である。

\(OS := \{\alpha \in S \mid o(\alpha) \in OT \land o(\alpha) < D_1 0\}\)と置く。

定理（\(OS\)の整礎性）
(1) いかなる\((a_i)_{i \in \mathbb{N}} \in \mathbb{N}_+^{\mathbb{N}}\)と\(\alpha \in OS\)に対しても、ある\(N \in \mathbb{N}\)が存在して、\(f(\cdots f(\alpha,a_0) \cdots,a_N) = 0\)である。
(2) いかなる\(\alpha \in OS\)と\(n \in \mathbb{N}_+\)に対しても、\(\alpha[n]\)は定義され\(\alpha[n] \geq H_{o(\alpha)}(n-1)\)である。ただし\(C_0(\varepsilon_{\Omega_{\omega}+1}) \cap \Omega\)には\([]\)の\(\{a \in OT \mid a < D_1 0\}\)への制限により基本列を定める。

特に\(g(n)\)は\(\mathbb{N}_+\)上全域でかつハーディ階層\(H_{\psi_0(\Omega_{\omega})}(n-1)\)に近似される。ここで用いた基本列は巨大数論で最も頻繁に用いられるデニスによる基本列とはわずかに異なることに注意する。

計算例

\begin{eqnarray*} & & g(1) = 0(1)[1] = 0(0)[2] = 0+0[4] = 0[8] = 16 \\ & & g(2) = 0(2)[2] = 0(1(1))[4] = 0(1(0(1(0(1(0(1(0)))))))[8] = 0(1(0(1(0(1(0(\underbrace{1+\cdots+1}_{8}))))))[16] \\ & = & 0(1(0(1(0(1(0(\underbrace{\underbrace{1+\cdots+1}_{7}+0(\cdots 0(\underbrace{1+\cdots+1}_{7}+0(\underbrace{1+\cdots+1}_{7}+0}_{16}))\cdots)))))))[32] \\ & = & \cdots \end{eqnarray*}

拡張

更にmrnaは段階配列表記を拡張し、2020年9月10日に拡張ブーフホルツ順序数までの順序数を表現できる降下段階配列表記を、2020年10月20日にラティエンの\(\psi\)関数を用いて\(\psi_{\chi_0(0)}(\psi_{\chi_{\varphi_0(\varphi_0(0))}(0)}(0))\)までの順序数を表現できると期待されている多変数段階配列表記を同様の手法で開発した。^[6]^[7]

またmrnaは多変数配列表記の限界に対応する順序数を 1-stage omega ordinalまたは略して1-SOOと命名した。もし上の期待が正しければ、1-stage omega ordinalは\(\psi_{\chi_0(0)}(\psi_{\chi_{\varphi_0(\varphi_0(0))}(0)}(0))\)と一致する。

文献

↑ mrna, "段階配列表記", Google Document, 2020
↑ mrna の巨大数研究 Wikiユーザーページ
↑ mrna, 定義公開の twitter 投稿
↑ ^4.0 ^4.1 p進大好きbot, 段階配列表記観察日記, 巨大数研究 Wikiユーザーブログ.
↑ mrna, 段階配列数の定義の twitter 投稿.
↑ mrna, 多変数段階配列表記, Google Document.
↑ mrna, 段階配列表記　解説配信, Googole Document.