Not to be confused with strong 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 12/08/2020.[1][2] 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.[3]

Using the iteration of \(g(n)\), mrna coined a large number \(g^{100}(100)\) as 段階配列数.[4]


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.[3]

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:

  1. If \(\alpha \in \mathbb{N}\), then \(o(\alpha) := D_{\alpha} 0\).
  2. If there exists some \(\beta \in S\) and \(\gamma \in P\) such that \(\alpha = \beta + \gamma\), then \(o(\alpha) := o(\beta) + o(\gamma)\).
  3. 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.[5][6]


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

  1. The user page of mrna in Japanese Googology Wiki.
  2. mrna, "段階配列表記", Google Document, 2020.
  3. 3.0 3.1 p進大好きbot, 段階配列表記観察日記, Japanese Googology Wiki user blog.
  4. mrna, 段階配列数, twitter.
  5. mrna, 多変数段階配列表記, Google Document.
  6. mrna, 段階配列表記 解説配信, Google Document.

See also

Fish numbers: Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7
Mapping functions: S map · SS map · S(n) map · M(n) map · M(m,n) map
By Aeton: Okojo numbers · N-growing hierarchy
By BashicuHyudora: Primitive sequence number · Pair sequence number · Bashicu matrix system
By Kanrokoti: KumaKuma ψ function
By 巨大数大好きbot: Flan numbers
By Jason: Irrational arrow notation · δOCF · δφ · ε function
By mrna: 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ
By Nayuta Ito: N primitive
By p進大好きbot: Large Number Garden Number
By Yukito: Hyper primitive sequence system · Y sequence · YY sequence · Y function
Indian counting system: Lakh · Crore · Tallakshana · Uppala · Dvajagravati · Paduma · Mahakathana · Asankhyeya · Dvajagranisamani · Vahanaprajnapti · Inga · Kuruta · Sarvanikshepa · Agrasara · Uttaraparamanurajahpravesa · Avatamsaka Sutra · Nirabhilapya nirabhilapya parivarta
Chinese, Japanese and Korean counting system: Wan · Yi · Zhao · Jing · Gai · Zi · Rang · Gou · Jian · Zheng · Zai · Ji · Gougasha · Asougi · Nayuta · Fukashigi · Muryoutaisuu
Other: Taro's multivariable Ackermann function · TR function · Arai's \(\psi\) · Sushi Kokuu Hen

Community content is available under CC-BY-SA unless otherwise noted.