Stage array notation

\(
\newcommand{\W}{\Omega}
\newcommand{\w}{\omega}
\newcommand{\p}{\psi}
\newcommand{\a}{\alpha}
\newcommand{\b}{\beta}
\newcommand{\g}{\gamma}\)
段階配列表記 (stage array notation) is a notation created by a Japanese Googology Wiki user mrna on August 12, 2020.The user page of mrna in Japanese Googology Wiki.mrna, "段階配列表記", Google Document, 2020. It is intended to be a variant of the notation based on Buchholz's function given by replacing \(\p_n\) by \(n\) and removing \((0)\). One of the most important aspects is that 段階配列表記 expresses ordinals up to \(\p_0(\Omega_{\omega})\) without introducing a map like \(\textrm{dom}\) in the Buchholz's original notation, which compute a value of a term analogous to the cofinality of an ordinal. Instead, it gives an explicit way to compute the nesting in terms of a replacement of a formal symbol \(k\).
The limit function \(g(n)\) of 段階配列表記 is approximated to \(f_{\p_0(\W_\w)}(n)\) using a specific system of fundamental sequences explained later.p進大好きbot, 段階配列表記観察日記, Japanese Googology Wiki user blog.
Using the iteration of \(g(n)\), mrna coined a large number \(g^{100}(100)\) as 段階配列数 (stage array number).mrna, 段階配列数, twitter.
== Definition ==
=== Notation system \(S\) ===
We denote by \(\mathbb{N}\) the set of non-negative integers. We define a set \(S\) of formal strings of non-negative integers, \((\), \()\), and \(+\) in the following recursive way:
* Every \(n \in \mathbb{N}\) belongs to \(S\).
* For any \(\a, \b \in S\), the formal string "\(\a+\b\)" belongs to \(S\).
* For any \(\a\in S\) and \(n \in \mathbb{N}\), the formal string "\(n(\a)\)" belongs to \(S\).
=== Set \(P\) ===
We denote by \(P\) the recursive subset of all \(\g \in S\) satisfying the following:
* For any \(\a, \b \in S\), \(\g \neq \a+\b\).
* \(\g \neq 0\).
=== Set \(S_n\) ===
For each \(n \in \mathbb{N}\), we define a set \(S\) of formal strings of of non-negative integers, \((\), \()\), \(+\), and a fixed letter \(k\) in the following recursive way:
* The letter \(k\) belongs to \(S_n\).
* For any \(\a \in S,~\b \in S_n\), the formal string "\(\a+\b\)" belongs to \(S_n\).
* For any \(\a \in S_n\) and \(m \in \mathbb{N}\), if \(n\leq m\), then the formal string "\(m(\a)\)" belongs to \(S_n\).
=== Formal string \(S_{n,\a}(\b)\) ===
For any \(n \in \mathbb{N}\), \(\a \in S_n\), and formal string \(\b\), we denote by \(S_{n,\a}(\b)\) the formal string given by replacing all the occurrence of \(k\) in \(\a\) by \(\b\).
=== Map \(f(\a,n)\) ===
We denote by \(\mathbb{N}_+\) the set of all positive integers. We define a map
\begin{eqnarray*}
f \colon S\times \mathbb{N}_+&\rightarrow& S\\
(\a,n) &\mapsto& f(\a,n)
\end{eqnarray*}
in the following recursive way:
* If \(\a\in\mathbb{N}\), then \(f(\a,n)=0\).
* If there exists some \(\b \in S\) such that \(\a=\b+0\), then \(f(\a,n)=\b\).
* If there exist some \(\b\in S\) and \(\g\in P\) such that \(\a=\b+\g\), then \(f(\a,n)=\b+f(\g,n)\).
* If there exist some \(a,b \in \mathbb{N}_+\) such that \(a\geq b\), \(\b\in S_0\), and \(\a=a(S_{0,\b}(b))\), then \(f(\a,n)=0(S_{0,\b}(b))\).
* If there exist some \(m \in \mathbb{N}\) and \(\b \in S_0\) such that \(\a=S_{0,\b}(m(0))\), then \(f(\a,n)=S_{0,\b}(\underbrace{m+m+\cdots+m}_{n})\).
* If there exist some \(m \in \mathbb{N}\), \(\b\in S_0\), and \(\g\in S\) such that \(\a=S_{0,\b}(m(\g+0))\), then \(f(\a,n)=S_{0,\b}(\underbrace{m(\g)+m(\g)+\cdots+m(\g)}_{n})\).
* If there exist some \(a \in \mathbb{N}\), \(b \in \mathbb{N}_+\), and \(\b\in S_b\) such that \(a\lt b\) and \(\a=a(S_{b,\b}(b))\), then \(f(\a,n)=a(\underbrace{S_{b,\b}(b'(S_{b,\b}(b'(\cdots S_{b,\b}(b'}_{n~S_{b,\b}(b'{\rm s}}~\underbrace{)))\cdots)}_{n})\), where \(b'\) is the predecessor of \(b\).
* If there exist some \(a \in \mathbb{N}\), \(b \in \mathbb{N}_+\), \(\b\in S_0\), and \(\g\in S_b\) such that \(a\lt b\) and \(\a=S_{0,\b}(a(S_{b,\g}(b)))\), then \(f(\a,n)=S_{0,\b}(f(a(S_{b,\g}(b)),n))\).
=== Large number notation ===
We define a function
\begin{eqnarray*}
[] \colon S \times \mathbb{N}_+ & \to & \mathbb{N}_+ \\
(\a,n) & \mapsto \a[n]
\end{eqnarray*}
in the following recursive way:
* If \(\a= 0\), then \(0[n]=n\times 2\).
* If \(\a \neq 0\), then \(\a[n]=f(\a,n)[n\times 2]\).
== Large number ==
The creator mrna coined \(g^{100}(100)\) as 段階配列数, where \(g(n)\) is defined as \(0(n)[n]\) for any \(n \in \mathbb{N}_+\).
== Analysis ==
We explain the result on termination and analysis originally proven by a Japanese Googology Wiki user p進大好きbot.
Let \(T\) denote Buchholz's notation system, and \(OT \subset T\) Buchholz's ordinal notation. We define a map
\begin{eqnarray*}
o \colon S & \to & T \setminus \{0\} \\
\alpha & \mapsto & o(\alpha)
\end{eqnarray*}
in the following recursive way:
# If \(\alpha \in \mathbb{N}\), then \(o(\alpha) := D_{\alpha} 0\).
# If there exists some \(\beta \in S\) and \(\gamma \in P\) such that \(\alpha = \beta + \gamma\), then \(o(\alpha) := o(\beta) + o(\gamma)\).
# If there exist some \(m \in \mathbb{N}\) and \(\beta \in S\) such that \(\alpha = m(\beta)\), then \(o(\alpha) := D_m o(\beta)\).
We put \(OS := \{\alpha \in S \mid o(\alpha) \in OT \land o(\alpha) < D_1 0\}\).
Theorem（Well-foundedness of \(OS\)）
(1) For any \((a_i)_{i \in \mathbb{N}} \in \mathbb{N}_+^{\mathbb{N}}\) and \(\alpha \in OS\), there exists some \(N \in \mathbb{N}\) such that \(f(\cdots f(\alpha,a_0) \cdots,a_N) = 0\).
(2) For any \(\alpha \in OS\) and \(n \in \mathbb{N}_+\), the computation of \(\alpha[n]\) terminates and the inequality \(\alpha[n] \geq HH_{o(\alpha)}(n-1)\) holds. Here, we endow \(C_0(\varepsilon_{\Omega_{\omega}+1}) \cap \Omega\) with the system of fundamental sequences associated to the restriction of \([]\) to \(\{a \in OT \mid a < D_1 0\}\).
In particular, \(g(n)\) is a total function on \(\mathbb{N}_+\) googologically approximated to Hardy hierarchy \(HH_{\psi_0(\Omega_{\omega})}(n-1)\). We note that the system of fundamental sequences used here is a little different from the most popular one in googology originally introduced by a Googology Wiki user Denis Maksudov.
== Demonstration ==
\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*}
== Extensions ==
Later, mrna extended 段階配列表記 to a notation up to the countable limit of Extended Buchholz's function called 降下段階配列表記 on 10/09/2020, and to a notation expected to express all ordinals below \(\psi_{\chi_0(0)}(\psi_{\chi_{\varphi_0(\varphi_0(0))}(0)}(0)) = \psi_{\chi_0(0)}(\psi_{\chi_{\omega}(0)}(0))\) with respect to Rathjen's \(\psi\) called 多変数段階配列表記 on 20/10/2020 using a similar method.mrna, 多変数段階配列表記, Google Document.mrna, 段階配列表記　解説配信, Google Document.
== Large ordinal ==
Further, mrna coined the ordinal corresponding to the limit of 多変数段階配列表記 as 1-stage omega ordinal or 1-SOO for short with respect to the correspondence associated to the expansion rule under the assumption of the well-foundedness. If the expectation above is correct, 1-stage omega ordinal coincides with \(\psi_{\chi_0(0)}(\psi_{\chi_{\varphi_0(\varphi_0(0))}(0)}(0)) = \psi_{\chi_0(0)}(\psi_{\chi_{\omega}(0)}(0))\).
== Sources ==
ja:段階配列表記
fr:Notation de la séquence en escalier
== See also ==
Category:Notations
Category:Numbers
Category:Transfinite ordinals
Category:Higher computable level
Category:Googology in Asia
Category:Buchholz's psi-functions
Category:Array Notations