Wiki Googologie
Advertisement

\( \newcommand{\W}{\Omega} \newcommand{\w}{\omega} \newcommand{\p}{\psi} \newcommand{\a}{\alpha} \newcommand{\b}{\beta} \newcommand{\g}{\gamma}\)

段階配列表記 (notation de la séquence en escalier) est une notation créée par un utilisateur japonais du Googology Wiki, mrna, le 12 août 2020.[1][2] Elle se veut une variante de la notation basée sur la fonction de Buchholz donnée en remplaçant pn par n et en supprimant (0). Un des aspects les plus importants est que 段階配列表記 exprime les ordinaux jusqu'à \(\p_0(\Omega_{\omega})\) sans introduire une carte comme dom dans la notation originale de Buchholz, qui calcule une valeur d'un terme analogue à la cofinalité d'un ordinal. Au lieu de cela, elle donne un moyen explicite de calculer l'imbrication en termes de remplacement d'un symbole formel k.

La fonction limite g(n) de 段階配列表記 est approchée de \(f_{\p_0(\W_\w)}(n)\) en utilisant un système spécifique de séquences fondamentales expliqué plus loin.[3]

En utilisant l'itération de g(n), mrna a inventé un grand nombre g100(100) comme 段階配列数,[4]

Définition

Système de notation S

We denote by 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 "α+β" belongs to S.
  • For any \(\a\in S\) and \(n \in \mathbb{N}\), the formal string "n(α)" 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 Sn

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

Références

  1. La page utilisateur de mrna dans le Googology Wiki japonais.
  2. mrna, "段階配列表記", Document Google, 2020.
  3. 3,0 et 3,1 p進大好きbot, 段階配列表記観察日記, Blog des utilisateurs japonais de Googology Wiki.
  4. mrna, 段階配列数, twitter.
  5. mrna, 多変数段階配列表記, Google Document.
  6. mrna, 段階配列表記 解説配信, Google Document.
Advertisement