Googology Wiki
Advertisement
Googology Wiki
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.[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

Original numbers, functions, notations, and notions

By Aeton: Okojo numbers · N-growing hierarchy
By 新井 (Arai): Arai's psi function
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
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



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

By ふぃっしゅ (Fish): 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 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
Advertisement