Stage array notation

View full site to see MathJax equation

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 August 12, 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.

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

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:

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.

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))\).

See also

Googology in Japan

Original numbers, functions, notations, and notions

By Aeton: Okojo numbers · N-growing hierarchy
By 新井 (Arai): Arai's psi function
By aster: White-aster notation · White-aster
By バシク (BashicuHyudora): Primitive sequence number · Pair sequence number · Bashicu matrix system 1/2/3/4 original idea
By ふぃっしゅ (Fish): Fish numbers (Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7 · S map · SS map · s(n) map · m(n) map · m(m,n) map) · Bashicu matrix system 1/2/3/4 formalisation · TR function (I0 function)
By Gaoji: Weak Buchholz's function
By じぇいそん (Jason): Irrational arrow notation · δOCF · δφ · ε function
By 甘露東風 (Kanrokoti): KumaKuma ψ function
By koteitan: Bashicu matrix system 2.3
By mrna: 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ
By Naruyoko Naruyo: Y sequence formalisation · ω-Y sequence formalisation
By Nayuta Ito: N primitive · Flan numbers (Flan number 1 · Flan number 2 · Flan number 3 · Flan number 4 version 3 · Flan number 5 version 3) · Large Number Lying on the Boundary of the Rule of Touhou Large Number 4 · Googology Wiki can have an article with any gibberish if it's assigned to a number
By Okkuu: Extended Weak Buchholz's function
By p進大好きbot: Ordinal notation associated to Extended Weak Buchholz's function · Ordinal notation associated to Extended Buchholz's function · Naruyoko is the great · Large Number Garden Number
By たろう (Taro): Taro's multivariable Ackermann function
By ゆきと (Yukito): Hyper primitive sequence system · Y sequence original idea · YY sequence · Y function · ω-Y sequence original idea

Methodology

By バシク (BashicuHyudora): Bashicu matrix system as a notation template
By じぇいそん (Jason): Shifting definition
By mrna: Side nesting
By Nayuta Ito and ゆきと (Yukito): Difference sequence system

Implementation of existing works into programs

By ふぃっしゅ (Fish): Ackermann function
By koteitan: Ackermann function · Beklemishev's worms · KumaKuma ψ function
By Mitsuki1729: Ackermann function · Graham's number · Conway's Tetratri · Fish number 1 · Fish number 2 · Laver table
By みずどら: White-aster notation
By Naruyoko Naruyo: p進大好きbot's Translation map for pair sequence system and Buchholz's ordinal notation · KumaKuma ψ function · Naruyoko is the great
By 猫山にゃん太 (Nekoyama Nyanta): Flan number 4 version 3 · Fish number 5 · Laver table
By Okkuu: Fish number 1 · Fish number 2 · Fish number 3 · Fish number 5 · Fish number 6
By rpakr: p進大好きbot's ordinal notation associated to Extended Weak Buchholz's function · Standardness decision algorithm for Taranovsky's ordinal notation

Proofs, translation maps for analysis schema, and other mathematical contributions

By ふぃっしゅ (Fish): Computing last 100000 digits of mega · Approximation method for FGH using Arrow notation · Translation map for primitive sequence system and Cantor normal form
By Kihara: Proof of an estimation of TREE sequence · Proof of the incomparability of Busy Beaver function and FGH associated to Kleene's \(\mathcal{O}\)
By koteitan: Translation map for primitive sequence system and Cantor normal form
By Naruyoko Naruyo: Translation map for Extended Weak Buchholz's function and Extended Buchholz's function
By Nayuta Ito: Comparison of Steinhaus-Moser Notation and Ampersand Notation
By Okkuu: Verification of みずどら's computation program of White-aster notation
By p進大好きbot: Proof of the termination of Hyper primitive sequence system · Proof of the termination of Pair sequence number · Proof of the termination of segements of TR function in the base theory under the assumption of the \(\Sigma_1\)-soundness and the pointwise well-definedness of \(\textrm{TR}(T,n)\) for the case where \(T\) is the formalisation of the base theory

Entertainments

By 小林銅蟲 (Kobayashi Doom): Sushi Kokuu Hen
By koteitan: Dancing video of a Gijinka of Fukashigi · Dancing video of a Gijinka of 久界 · Storyteller's theotre video reading Large Number Garden Number aloud

See also: Template:Googology in Asia