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\). Further, mrna extended 段階配列表記 to a notation up to the countable limit of Extended Buchholz's function called 降下段階配列表記 on 10/09/2020 using a similar method.

The limit function \(g(n)\) of 段階配列表記 is approximated to \(f_{\p_0(\W_\w)}(n)\) using a specific system of fundamenntal 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*}


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.

See also

Googology in Asia

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 巨大数大好き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 · 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 · Sushi Kokuu Hen

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