Googology Wiki
Advertisement
Googology Wiki

Hyper primitive sequence system is a notation defined by a Japanese googologist Yukito.[1][2] It is an extension of primitive sequence system, which is a subsystem of Bashicu matrix system, using difference sequences. The limit of this notation is \(\psi_0(\Omega_{\omega})\) with respect to fast-growing hierarchy and Buchholz's function. Although it has the same limit as pair sequence system, it expands in a way compatible with the system of fundamental sequences for Buchholz's function unlike pair sequence system.

Definition

A term in the notation is a finite sequence \(S = (S_i)_{i=1}^{m}\) of natural numbers followed by a natural number \(n\) in a bracket, i.e. an expression of the form \((S_1,\ldots,S_m)[n]\). It is evaluated in the following recursive way:

  1. If \(m = 0\), then set \(S[n] = n\).
  2. Suppose \(m > 0\).
    1. For an \(i \in \mathbb{N}\) satisfying \(i \leq m\), put \(P_i = \{j \in \mathbb{N} \mid 1 \leq j < i \land S_j < S_i\}\).
    2. Put \(k = 0\).
    3. If \(k = 0\), then put \(m_k = m\).
    4. If \(k > 0\), then put \(m_k = \max P_{m_{k-1}}\).
    5. If \(P_{m_k} \neq \emptyset\), then increment \(k\), and go back to the line 2-3.
    6. Define a finite sequence \(\textrm{Expand}(S,n)\) in the following way:
      1. If \(k = 0\), then put \(\textrm{Expand}(S,n) = (S_1,\ldots,S_{m-1})\).
      2. Suppose \(k > 0\).
        1. Denote by \(N = (N_i)_{i=0}^{k-1}\) the difference sequence \((S_{m_i}-S_{m_{i+1}})_{i=0}^{k-1}\) of \((S_{m_i})_{i=0}^{k}\).
        2. Define the bad root \(r\) and the ascension level \(\delta\) in the following way:
          1. Suppose \(N_0 = 1\).
            1. Put \(r = m_1\).
            2. Put \(\delta = 0\).
          2. Suppose \(N_0 \neq 1\).
            1. Suppose that there does not exist an \(i \in \mathbb{N}\) such that \(0 < i \leq k-1\) and \(N_i < N_0\).
              1. Put \(r = 1\).
              2. Put \(\delta = S_m - 1\).
            2. Suppose that such an \(i\) exists.
              1. Denote by \(p\) the minimum of such an \(i\).
              2. Put \(r = m_p\).
              3. Put \(\delta = S_m - S_r - 1\).
        3. Put \(G = (S_i)_{i=1}^{r-1}\). (If \(r = 1\), then it is the empty sequence.)
        4. For an \(h \in \mathbb{N}\), put \(B(h) = (S_i + h \delta)_{i=r}^{m-1}\).
        5. Then \(\textrm{Expand}(S,n)\) is the concaternation of \(G,B(0),\ldots,B(n)\).
    7. Set \(S[n] = \textrm{Expand}(S,n)[n+1]\).

The function \((0,\omega)[n]\) defined as \((0,n)[n]\) gives the limit of this notation.

Standard form

The set \(OT\) of finite sequences of standard forms in hyper primitive sequence system is defined in the following recursive way:

  1. For any \(n \in \mathbb{N}\), \((0,n) \in OT\).
  2. For any \((S,n) \in (OT \setminus \{()\}) \times \mathbb{N}\), \(\textrm{Expand}(S,n) \in OT\).

Then \(OT\) is a recursive subset of the set \(T\) of finite sequences of natural numbers as we will explain in #Termination section, and \(\textrm{Expand}\) gives a primitive recursive map \((T \setminus \{()\}) \times \mathbb{N} \to T\), which preserves standard forms.

Explanation

Follow the convention and the terminology in the article on difference sequences. Hyper primitive sequence system employs the bad root searching rule \(\textrm{Parent} \colon \textrm{FinSeq} \times \mathbb{N} \to \textrm{FinSeq}\) for the primitive sequence system explained here. Indeed \((m_i)_{i=0}^{k}\) and \(N\) in the definition of \(S[n]\) precisely coincide with \(\textrm{Ancestors}(S)\) and \(\textrm{Kaiser}(S)\) respectively.

If \(\textrm{Ancestors}(S)\) is of length \(1\), then \(S\) is a successor term, and \(\textrm{Expand}(S,n)\) is obtained by deleting the rightmost entry of \(S\). If \(\textrm{Ancestors}(S)\) is of length \(> 1\), then apply an expansion rule to \(\textrm{Kaiser}(S)\) quite similar to the one in primitive sequence system; if \(\textrm{Ancestors}(\textrm{Kaiser}(S))\) is of length \(1\), then decrement the rightmost entry of \(\textrm{Kaiser}(S)\), and otherwise, copy the bad part of \(\textrm{Kaiser}(S)\) with respect to \(\textrm{Parent}\). Denote by \(\textrm{Kaiser}(S)(n)\) the resulting finite sequence. As \(\textrm{Kaiser}(S)\) is the differece sequence of \(\textrm{RightNodes}(S)\), \(\textrm{Kaiser}(S)(n)\) is the difference sequence of a unique finite sequence \(\textrm{RightNodes}(S)(n)\) whose first entry is \(\textrm{RightNodes}(S)_0\). Finally, \(\textrm{Expand}(S,n)\) is given by replacing the subsequence \(\textrm{RightNodes}(S)\) of \(S\) by \(\textrm{RightNodes}(S)(n)\) and interpolating the intermidiate entries by the copies of the corresponding entries of \(S\) modified by the ascention level.

Through the interpretation above, hyper primitive sequence system can be regarded as an analog of the system of two-lined hydra diagrams, which corresponds to pair sequence system.

Termination

For the convention and the terminology, see the following:

  • [Buc1] W. Buchholz, A new system of proof-theoretic ordinal functions, Annals of Pure and Applied Logic, Volume 32, 1986, pp. 195–207.
  • [Buc2] W. Buchholz, Relating ordinals to proofs in a perspicious way, Reflections on the Foundations of Mathematics, Essays in Honor of Solomon Feferman, Lecture Notes in Logic, vol. 15, 2002, pp. 37–59.

The termination of hyper primitive sequence system has been proved by a Japanese Googology Wiki user p進大好きbot in the following way:

Let \(T_B\) denote the set of terms in Buchholz's notation, in which \(D_{\omega}\) does not appear.[3] Define a total recursive map \begin{eqnarray*} \textrm{Trans} \colon T_B & \to & T \\ t & \mapsto & \textrm{Trans}(t) \end{eqnarray*} in the following recursive way:

  1. If \(t = 0\), then set \(\textrm{Trans}(t) = ()\).
  2. Suppose \(t = t_0 + D_u t_1\) for some \((u,t_0,t_1) \in \mathbb{N} \times T_B \times T_B\).[4]
    1. If \(t_1 = D_0 0 \cdot m\) for some \(m \in \mathbb{N}\), then \(\textrm{Trans}(t)\) is the concatenation of \(\textrm{Trans}(t_0)\) and \((u,\underbrace{u+1,\ldots,u+1}_{m})\).[5]
    2. Otherwise, \(\textrm{Trans}(t)\) is the concatenation of \(\textrm{Trans}(t_0)\), \((u)\), and the finite sequence obtained by adding \(u+1\) to each entry of \(\textrm{Trans}(t_1)\).

Let \(OT_B \subset T_B\) denote the subset of ordinal terms below \(D_1 0\).[6]

Lemma (Compatibility of \(\textrm{Trans}\))
The restriction of \(\textrm{Trans}\) to \(OT_B\) satisfies the following:
(1) It is a bijective map onto \(OT\).
(2) For any \((t,n) \in (OT_B \setminus \{0\}) \times \mathbb{N}\), \(\textrm{Trans}(t) \neq ()\), and there exists a \(t' \in OT_B\) such that \(\textrm{Trans}(t') = \textrm{Expand}(\textrm{Trans}(t),n)\) and \(t' < t\). If \(n > 0\) then such a \(t'\) can be taken so that \(t[n-1] < t' \leq t[n]\).[7]
Proof
For an \(m \in \mathbb{N}\), define \(\Sigma_m \subset OT_B\) in the following recursive way:
  1. If \(m = 0\), then set \(\Sigma_m = \{D_0 D_u 0 \mid u \in \mathbb{N} \land u > 0\}\).
  2. If \(m > 0\), then set \(\Sigma_m = \Sigma_{m-1} \cup \{t[n] \mid (t,n) \in \Sigma_{m-1} \times \mathbb{N}\}\).
By [Buc1] 2.2 Lemma (c) and 2.3 Lemma (b), we have \(\bigcup_{m \in \mathbb{N}} \Sigma_m = OT_B\).
Let \(t \in OT_B\). By the argument above, there exists an \(m \in \mathbb{N}\) such that \(t \in \Sigma_m\). Denote by \(\mu\) the minimum of such an \(m\). We show \(\textrm{Trans}(t) \in OT\) by induction of \(\mu\).
If \(\mu = 0\), then we have \(t = D_0 D_u 0\) for some \(u \in \mathbb{N}\) satisfying \(u > 0\), and hence \(\textrm{Trans}(t) = (0,u) \in OT\). Suppose \(\mu > 0\) in the following. Take a \((t',n) \in \Sigma_{\mu-1} \times \mathbb{N}\) satisfying \(t = t'[n]\). By the induction hypothesis, we have \(\textrm{Trans}(t') \in OT_B\). By \(t \notin \Sigma_{\mu-1}\), we have \(t \neq t'\), and hence \(t' \neq 0\). It implies \(t = t'[n] < t'\) by [Buc1] 3.2 Lemma (a).
Take a unique \((u,t_0,t_1) \in \mathbb{N} \times OT_B \times OT_B\) satisfying \(t' = t_0 + D_u t_1\). By the definition of \(\textrm{Expand}\) and \(\textrm{Trans}\), we have \(\textrm{Trans}(t) = \textrm{Expand}(\textrm{Trans}(t'),n) \in OT_B\) unless \(\textrm{dom}(t_1) = T_v\) for some \(v \in \mathbb{N}\) satifying \(u \leq v\).[8] Therefore we may assume \(\textrm{dom}(t_1) = T_v\) for some \(v \in \mathbb{N}\) satifying \(u \leq v\).
For each \(m \in \mathbb{N}\), denote by \(t_2(m)\) a unique ordinal term satisfying \(o(t_2(m)) = o(t'(m))\), where \(t'(m)\) is the term obtained by replacing the rightmost appearrence of \(D_v 0\) in \(t'[m]\) by \(0\).[9] Again by the definition of \(\textrm{Expand}\) and \(\textrm{Trans}\), \(\textrm{Trans}(t_2(m))\) and \(\textrm{Trans}(t'(m))\) coincide with \(\textrm{Expand}(\textrm{Trans}(t'),m)\).
We have \(t_2(n) \leq t'(n) < t \leq t_2(n+1) \leq t'(n+1)\), and \(t\) coincides with the term obtained by replacing the righmost appearrence of \(0\) in \(t'(n)\) by \(D_v 0\) because of \(t = t'[n]\). Therefore \(\textrm{Trans}(t)\) coincides with the concatenation of \(\textrm{Trans}(t'(n))\) and \((a+v+1)\), where \(a\) is the next rightmost entry of \(\textrm{RightNodes}(\textrm{Trans}(t))\) with respect to the bad root searching rule \(\textrm{Parent}\), and \(\textrm{Trans}(t'(n+1))\) coincides with the concatenation of \(\textrm{Trans}(t)\) and a finite sequence. Since the deletion of the rightmost entry is given by the application of \(\textrm{Expand}(-,0)\), it implies \(t \in OT\).
Thus the restriction of \(\textrm{Trans}\) to \(OT_B\) gives a map to \(OT\). The assertions (1) and (2) immediately follow from the argument above, because of \(\textrm{Trans}(D_0 0 + D_0 0) = (0,0)\) and \(\textrm{Trans}(D_u 0) = (0,u)\) for any \(u \in \mathbb{N}\) satisfying \(u > 0\). □

As is shown in the proof above, hyper primitive sequence system is quite compatible with Buchholz's ordinal notation unlike pair sequence system.

Theorem (The termination of hyper primitive sequence system)
(1) The pair of \(OT\) and the lexicographic order \(<_{OT}\) on it is an ordinal notation.
(2) Let \(S \in OT \setminus \{()\}\). For any map \(f \colon \mathbb{N} \to \mathbb{N}\), there exists a unique finite sequence \((X_k)_{k=0}^{N}\) in \(OT\) such that \(X_0 = S\), \(X_k\) is a non-empty sequence satisfying \(\textrm{Expand}(X_k,f(k)) = X_{k+1}\) for any \(k \in \mathbb{N}\) smaller than \(N+1\), and \(X_N= ()\).
Proof
(1) By Lemma and [Buc1] 2.2 Lemma (c), the pair of \(OT_B\) and its canonical ordering \(<_{OT_B}\), which coincides with the lexicographic ordering for a suitable ordering of letters by definition, is an ordinal notation. Since \(\textrm{Trans}\) preserves the lexicographic ordering, Lemma (Compatibility of \(\textrm{Trans}\)) (1) implies that \((OT_B,<_{OT_B})\) is isomorphic to \((OT,<_{OT})\). Thus \((OT,<_{OT})\) is an ordinal notation.
(2) Since \((OT_B,<_{OT_B})\) is an ordinal notation, the compatibility of the canonical ordering on \(OT_B\) and \([ \ ]\) and Lemma (Compatibility of \(\textrm{Trans}\)) (2) implies the assertion for the case where \(S\) belongs to the image of \(\textrm{Trans}\), which coincides with \(OT\) by Lemma (Compatibility of \(\textrm{Trans}\)) (1).□


Analysis

By Lemma (2), the limit of hyper primitive sequence is \(\psi_0(\Omega_{\omega})\) with respect to the Hardy hierarchy and a minor replacement of the recursive system of fundamental sequences assciated to Buchholz's ordinal notation. In particular, it is also approximated to \(\psi_0(\Omega_{\omega})\) in fast growing hierarchy. The composite \begin{eqnarray*} o \circ (\textrm{Trans} |_{OT_B})^{-1} \colon OT \to \psi_0(\Omega_{\omega}) \end{eqnarray*} gives an interpretation of terms in hyper primitive sequence system of standard form into ordinals below \(\psi_0(\Omega_{\omega})\). The following table exhibits examples of the correspondence:

hyper primitive seqeunce ordinal
\(()\) \(0\)
\((0)\) \(1\)
\((0,0)\) \(2\)
\((0,0,0)\) \(3\)
\((0,1)\) \(\omega\)
\((0,1,0)\) \(\omega+1\)
\((0,1,0,0)\) \(\omega+2\)
\((0,1,0,0,0)\) \(\omega+3\)
\((0,1,0,1)\) \(\omega \times 2\)
\((0,1,0,1,0)\) \(\omega \times 2+1\)
\((0,1,0,1,0,0)\) \(\omega \times 2+2\)
\((0,1,0,1,0,0,0)\) \(\omega \times 2+3\)
\((0,1,0,1,0,1)\) \(\omega \times 3\)
\((0,1,1)\) \(\omega^2\)
\((0,1,1,0)\) \(\omega^2+1\)
\((0,1,1,0,0)\) \(\omega^2+2\)
\((0,1,1,0,1)\) \(\omega^2+\omega\)
\((0,1,1,0,1,0)\) \(\omega^2+\omega+1\)
\((0,1,1,0,1,1)\) \(\omega^2 \times 2\)
\((0,1,1,1)\) \(\omega^3\)
\((0,1,2)\) \(\omega^{\omega}\)
\((0,1,2,1)\) \(\omega^{\omega+1}\)
\((0,1,2,1,1)\) \(\omega^{\omega+2}\)
\((0,1,2,1,2)\) \(\omega^{\omega \times 2}\)
\((0,1,2,2)\) \(\omega^{\omega^2}\)
\((0,1,2,2,1)\) \(\omega^{\omega^2+1}\)
\((0,1,2,2,1,1)\) \(\omega^{\omega^2+2}\)
\((0,1,2,2,1,2)\) \(\omega^{\omega^2+\omega}\)
\((0,1,2,2,1,2,1)\) \(\omega^{\omega^2+\omega+1}\)
\((0,1,2,2,1,2,1,1)\) \(\omega^{\omega^2+\omega+2}\)
\((0,1,2,2,1,2,1,2)\) \(\omega^{\omega^2+\omega \times 2}\)
\((0,1,2,2,1,2,2)\) \(\omega^{\omega^2 \times 2}\)
\((0,1,2,2,2)\) \(\omega^{\omega^3}\)
\((0,1,2,3)\) \(\omega^{\omega^{\omega}}\)
\((0,2)\) \(\varepsilon_0 = \psi_0(\Omega)\)
\((0,2,1)\) \(\varepsilon_0 \times \omega = \psi_0(\Omega+1)\)
\((0,2,1,1)\) \(\varepsilon_0 \times \omega^2 = \psi_0(\Omega+2)\)
\((0,2,1,2)\) \(\varepsilon_0 \times \omega^{\omega} = \psi_0(\Omega+\omega)\)
\((0,2,1,2,1)\) \(\varepsilon_0 \times \omega^{\omega+1} = \psi_0(\Omega+\omega+1)\)
\((0,2,1,2,1,1)\) \(\varepsilon_0 \times \omega^{\omega+2} = \psi_0(\Omega+\omega+2)\)
\((0,2,1,2,1,2)\) \(\varepsilon_0 \times \omega^{\omega \times 2} = \psi_0(\Omega+\omega \times 2)\)
\((0,2,1,2,2)\) \(\varepsilon_0 \times \omega^{\omega^2} = \psi_0(\Omega+\omega^2)\)
\((0,2,1,2,3)\) \(\varepsilon_0 \times \omega^{\omega^{\omega}} = \psi_0(\Omega+\omega^{\omega})\)
\((0,2,1,3)\) \(\varepsilon_0^2 = \psi_0(\Omega+\psi_0(\Omega))\)
\((0,2,1,3,1)\) \(\varepsilon_0^2 \times \omega = \psi_0(\Omega+\psi_0(\Omega)+1)\)
\((0,2,1,3,1,2)\) \(\varepsilon_0^2 \times \omega^{\omega} = \psi_0(\Omega+\psi_0(\Omega)+\omega)\)
\((0,2,1,3,1,2,3)\) \(\varepsilon_0^2 \times \omega^{\omega^{\omega}} = \psi_0(\Omega+\psi_0(\Omega)+\omega^{\omega})\)
\((0,2,1,3,1,3)\) \(\varepsilon_0^3 = \psi_0(\Omega+\psi_0(\Omega) \times 2)\)
\((0,2,1,3,2)\) \(\varepsilon_0^{\omega} = \psi_0(\Omega+\psi_0(\Omega+1))\)
\((0,2,1,3,2,1)\) \(\varepsilon_0^{\omega} \times \omega = \psi_0(\Omega+\psi_0(\Omega+1)+1)\)
\((0,2,1,3,2,1,2)\) \(\varepsilon_0^{\omega} \times \omega^{\omega} = \psi_0(\Omega+\psi_0(\Omega+1)+\omega)\)
\((0,2,1,3,2,1,2,3)\) \(\varepsilon_0^{\omega} \times \omega^{\omega^{\omega}} = \psi_0(\Omega+\psi_0(\Omega+1)+\omega^{\omega})\)
\((0,2,1,3,2,1,3)\) \(\varepsilon_0^{\omega+1} = \psi_0(\Omega+\psi_0(\Omega+1)+\psi_0(\Omega))\)
\((0,2,1,3,2,1,3,1)\) \(\varepsilon_0^{\omega+1} \times \omega = \psi_0(\Omega+\psi_0(\Omega+1)+\psi_0(\Omega)+1)\)
\((0,2,1,3,2,1,3,2)\) \(\varepsilon_0^{\omega \times 2} = \psi_0(\Omega+\psi_0(\Omega+1) \times 2)\)
\((0,2,1,3,2,2)\) \(\varepsilon_0^{\omega^2} = \psi_0(\Omega+\psi_0(\Omega+2))\)
\((0,2,1,3,2,2,1)\) \(\varepsilon_0^{\omega^2} \times \omega = \psi_0(\Omega+\psi_0(\Omega+2)+1)\)
\((0,2,1,3,2,2,2)\) \(\varepsilon_0^{\omega^3} = \psi_0(\Omega+\psi_0(\Omega+3))\)
\((0,2,1,3,2,3)\) \(\varepsilon_0^{\omega^{\omega}} = \psi_0(\Omega+\psi_0(\Omega+\omega))\)
\((0,2,1,3,2,3,1)\) \(\varepsilon_0^{\omega^{\omega}} = \psi_0(\Omega+\psi_0(\Omega+\omega)+1)\)
\((0,2,1,3,2,3,2)\) \(\varepsilon_0^{\omega^{\omega} \times \omega} = \psi_0(\Omega+\psi_0(\Omega+\omega+1))\)
\((0,2,1,3,2,3,3)\) \(\varepsilon_0^{\omega^{\omega^2}} = \psi_0(\Omega+\psi_0(\Omega+\omega^2))\)
\((0,2,1,3,2,3,4)\) \(\varepsilon_0^{\omega^{\omega^{\omega}}} = \psi_0(\Omega+\psi_0(\Omega+\omega^{\omega}))\)
\((0,2,1,3,2,4)\) \(\varepsilon_0^{\varepsilon_0} = \psi_0(\Omega+\psi_0(\Omega+\psi_0(\Omega)))\)
\((0,2,1,3,2,4,1)\) \(\varepsilon_0^{\varepsilon_0} \times \omega = \psi_0(\Omega+\psi_0(\Omega+\psi_0(\Omega))+1)\)
\((0,2,1,3,2,4,2)\) \(\varepsilon_0^{\varepsilon_0 \times \omega} = \psi_0(\Omega+\psi_0(\Omega+\psi_0(\Omega)+1))\)
\((0,2,1,3,2,4,3)\) \(\varepsilon_0^{\varepsilon_0^{\omega}} = \psi_0(\Omega+\psi_0(\Omega+\psi_0(\Omega+1)))\)
\((0,2,2)\) \(\varepsilon_0 \uparrow \uparrow \omega = \psi_0(\Omega \times 2)\)
\((0,2,2,1)\) \(\psi_0(\Omega \times 2+1)\)
\((0,2,2,2)\) \(\psi_0(\Omega \times 3)\)
\((0,2,3)\) \(\psi_0(\Omega \times \omega) = \psi_0(\psi_1(\psi_0(0)))\)
\((0,2,3,1)\) \(\psi_0(\Omega \times \omega + 1) = \psi_0(\psi_1(\psi_0(0))+\psi_0(0))\)
\((0,2,3,2)\) \(\psi_0(\Omega \times (\omega + 1)) = \psi_0(\psi_1(\psi_0(0))+\psi_1(0))\)
\((0,2,3,3)\) \(\psi_0(\Omega \times \omega^2) = \psi_0(\psi_1(\psi_0(0)+\psi_0(0)))\)
\((0,2,3,4)\) \(\psi_0(\Omega \times \omega^{\omega}) = \psi_0(\psi_1(\psi_0(\psi_0(0))))\)
\((0,2,3,4,1)\) \(\psi_0(\Omega \times \omega^{\omega}+1) = \psi_0(\psi_1(\psi_0(\psi_0(0)))+\psi_0(0))\)
\((0,2,3,4,2)\) \(\psi_0(\Omega \times (\omega^{\omega}+1)) = \psi_0(\psi_1(\psi_0(\psi_0(0)))+\psi_1(0))\)
\((0,2,3,4,3)\) \(\psi_0(\Omega \times \omega^{\omega+1}) = \psi_0(\psi_1(\psi_0(\psi_0(0))+\psi_0(0)))\)
\((0,2,3,4,4)\) \(\psi_0(\Omega \times \omega^{\omega \times 2}) = \psi_0(\psi_1(\psi_0(\psi_0(0)+\psi_0(0))))\)
\((0,2,3,4,5)\) \(\psi_0(\Omega \times \omega^{\omega^{\omega}}) = \psi_0(\psi_1(\psi_0(\psi_0(\psi_0(0)))))\)
\((0,2,3,5)\) \(\psi_0(\Omega \times \psi_0(\Omega)) = \psi_0(\psi_1(\psi_0(\psi_1(0))))\)
\((0,2,4)\) \(\psi_0(\Omega^2) = \psi_0(\psi_1(\psi_1(0)))\)
\((0,2,4,1)\) \(\psi_0(\Omega^2+1) = \psi_0(\psi_1(\psi_1(0))+\psi_0(0))\)
\((0,2,4,2)\) \(\psi_0(\Omega^2+\Omega) = \psi_0(\psi_1(\psi_1(0))+\psi_1(0))\)
\((0,2,4,3)\) \(\psi_0(\Omega^2 \times \omega) = \psi_0(\psi_1(\psi_1(0)+\psi_0(0)))\)
\((0,2,4,3,1)\) \(\psi_0(\Omega^2 \times \omega + 1) = \psi_0(\psi_1(\psi_1(0)+\psi_0(0))+\psi_0(0))\)
\((0,2,4,3,2)\) \(\psi_0(\Omega^2 \times \omega + \Omega) = \psi_0(\psi_1(\psi_1(0)+\psi_0(0))+\psi_1(0))\)
\((0,2,4,3,3)\) \(\psi_0(\Omega^2 \times \omega^2) = \psi_0(\psi_1(\psi_1(0)+\psi_0(0)+\psi_0(0)))\)
\((0,2,4,3,4)\) \(\psi_0(\Omega^2 \times \omega^{\omega}) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_0(0))))\)
\((0,2,4,3,5)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(0))))\)
\((0,2,4,3,5,1)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega)+1) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(0)))+\psi_0(0))\)
\((0,2,4,3,5,2)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega)+\Omega) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(0)))+\psi_1(0))\)
\((0,2,4,3,5,3)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega+1)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(0))+\psi_0(0)))\)
\((0,2,4,3,5,4)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega+\omega)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(0))))\)
\((0,2,4,3,5,5)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times 2)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(0)+\psi_1(0))))\)
\((0,2,4,3,5,6)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times \omega)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_0(0)))))\)
\((0,2,4,3,5,6,1)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times \omega)+1) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_0(0))))+\psi_0(0))\)
\((0,2,4,3,5,6,2)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times \omega)+\Omega) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_0(0))))+\psi_1(0))\)
\((0,2,4,3,5,6,3)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times \omega+1)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_0(0)))+\psi_0(0)))\)
\((0,2,4,3,5,6,4)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times \omega+\omega))= \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_0(0))+\psi_0(0))))\)
\((0,2,4,3,5,6,5)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times (\omega+1))) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_0(0))+\psi_1(0))))\)
\((0,2,4,3,5,6,6)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times \omega^2)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_0(0)+\psi_0(0)))))\)
\((0,2,4,3,5,6,7)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times \omega^{\omega})) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_0(\psi_0(0))))))\)
\((0,2,4,3,5,6,8)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega \times \psi_0(\Omega))) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_0(\psi_1(0))))))\)
\((0,2,4,3,5,7)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega^2)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_1(0)))))\)
\((0,2,4,3,5,7,1)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega^2)+1) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_1(0))))+\psi_0(0))\)
\((0,2,4,3,5,7,2)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega^2)+\Omega) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_1(0))))+\psi_1(0))\)
\((0,2,4,3,5,7,3)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega^2+1)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_1(0)))+\psi_0(0)))\)
\((0,2,4,3,5,7,4)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega^2)^{\omega}) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_1(0))+\psi_0(0))))\)
\((0,2,4,3,5,7,5)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega^2+\Omega)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_1(0))+\psi_1(0))))\)
\((0,2,4,3,5,7,6)\) \(\psi_0(\Omega^2 \times \psi_0(\Omega^2 \times \omega)) = \psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_1(0)+\psi_0(0)))))\)
\((0,2,4,4)\) \(\psi_0(\Omega^3) = \psi_0(\psi_1(\psi_1(0)+\psi_1(0)))\)
\((0,2,4,4,1)\) \(\psi_0(\Omega^3+1) = \psi_0(\psi_1(\psi_1(0)+\psi_1(0))+\psi_0(0))\)
\((0,2,4,4,2)\) \(\psi_0(\Omega^3+\Omega) = \psi_0(\psi_1(\psi_1(0)+\psi_1(0))+\psi_1(0))\)
\((0,2,4,4,3)\) \(\psi_0(\Omega^3 \times \omega) = \psi_0(\psi_1(\psi_1(0)+\psi_1(0)+\psi_0(0)))\)
\((0,2,4,4,4)\) \(\psi_0(\Omega^4) = \psi_0(\psi_1(\psi_1(0)+\psi_1(0)+\psi_1(0)))\)
\((0,2,4,5)\) \(\psi_0(\Omega^{\omega}) = \psi_0(\psi_1(\psi_1(\psi_0(0))))\)
\((0,2,4,5,1)\) \(\psi_0(\Omega^{\omega}+1) = \psi_0(\psi_1(\psi_1(\psi_0(0)))+\psi_0(0))\)
\((0,2,4,5,2)\) \(\psi_0(\Omega^{\omega}+\Omega) = \psi_0(\psi_1(\psi_1(\psi_0(0)))+\psi_1(0))\)
\((0,2,4,5,3)\) \(\psi_0(\Omega^{\omega} \times \omega) = \psi_0(\psi_1(\psi_1(\psi_0(0))+\psi_0(0)))\)
\((0,2,4,5,4)\) \(\psi_0(\Omega^{\omega+1}) = \psi_0(\psi_1(\psi_1(\psi_0(0))+\psi_1(0)))\)
\((0,2,4,5,5)\) \(\psi_0(\Omega^{\omega^2}) = \psi_0(\psi_1(\psi_1(\psi_0(0)+\psi_0(0))))\)
\((0,2,4,5,6)\) \(\psi_0(\Omega^{\omega^{\omega}}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_0(0)))))\)
\((0,2,4,5,7)\) \(\psi_0(\Omega^{\psi_0(\Omega)}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(0)))))\)
\((0,2,4,5,7,1)\) \(\psi_0(\Omega^{\psi_0(\Omega)}+1) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(0))))+\psi_0(0))\)
\((0,2,4,5,7,2)\) \(\psi_0(\Omega^{\psi_0(\Omega)}+\Omega) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(0))))+\psi_1(0))\)
\((0,2,4,5,7,3)\) \(\psi_0(\Omega^{\psi_0(\Omega)} \times \omega) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(0)))+\psi_0(0)))\)
\((0,2,4,5,7,4)\) \(\psi_0(\Omega^{\psi_0(\Omega)+1}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(0)))+\psi_1(0)))\)
\((0,2,4,5,7,5)\) \(\psi_0(\Omega^{\psi_0(\Omega+1)}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(0))+\psi_0(0))))\)
\((0,2,4,5,7,6)\) \(\psi_0(\Omega^{\psi_0(\Omega)^{\omega}}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(0)+\psi_0(0)))))\)
\((0,2,4,5,7,7)\) \(\psi_0(\Omega^{\psi_0(\Omega \times 2)}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(0)+\psi_1(0)))))\)
\((0,2,4,5,7,8)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \omega)}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(0))))))\)
\((0,2,4,5,7,8,1)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \omega)}+1) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(0)))))+\psi_0(0))\)
\((0,2,4,5,7,8,2)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \omega)}+\Omega) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(0)))))+\psi_1(0))\)
\((0,2,4,5,7,8,3)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \omega)} \times \omega) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(0))))+\psi_0(0)))\)
\((0,2,4,5,7,8,4)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \omega)+1}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(0))))+\psi_1(0)))\)
\((0,2,4,5,7,8,5)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \omega+1)}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(0)))+\psi_0(0))))\)
\((0,2,4,5,7,8,6)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \omega)^{\omega}}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(0))+\psi_0(0)))))\)
\((0,2,4,5,7,8,7)\) \(\psi_0(\Omega^{\psi_0(\Omega \times (\omega+1))}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(0))+\psi_1(0)))))\)
\((0,2,4,5,7,8,8)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \omega^2)}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(0)+\psi_0(0))))))\)
\((0,2,4,5,7,8,9)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \omega^{\omega})}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(\psi_0(0)))))))\)
\((0,2,4,5,7,8,10)\) \(\psi_0(\Omega^{\psi_0(\Omega \times \psi_0(\Omega))}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_0(\psi_1(0)))))))\)
\((0,2,4,5,7,9)\) \(\psi_0(\Omega^{\psi_0(\Omega^2)}) = \psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(0))))))\)
\((0,2,4,6)\) \(\psi_0(\Omega^{\Omega}) = \psi_0(\psi_1(\psi_1(\psi_1(0))))\)
\((0,3)\) \(\psi_0(\Omega_2) = \psi_0(\psi_2(0))\)
\((0,3,1)\) \(\psi_0(\Omega_2+1) = \psi_0(\psi_2(0)+\psi_0(0))\)
\((0,3,2)\) \(\psi_0(\Omega_2+\Omega) = \psi_0(\psi_2(0)+\psi_1(0))\)
\((0,3,3)\) \(\psi_0(\Omega_2 \times 2) = \psi_0(\psi_2(0)+\psi_2(0))\)
\((0,3,4)\) \(\psi_0(\Omega_2 \times \omega) = \psi_0(\psi_2(\psi_0(0)))\)
\((0,3,5)\) \(\psi_0(\Omega_2 \times \Omega) = \psi_0(\psi_2(\psi_1(0)))\)
\((0,3,6)\) \(\psi_0(\Omega_2^2) = \psi_0(\psi_2(\psi_2(0)))\)
\((0,4)\) \(\psi_0(\Omega_3) = \psi_0(\psi_3(0))\)
\((0,n+1)\) \(\psi_0(\Omega_n) = \psi_0(\psi_n(0))\)

Sources

  1. The user page of Yukito in the Japanese Googology Wiki.
  2. Yukito, ハイパー原始数列
  3. The notation is defined in [Buc1] p. 200.
  4. The addition is defined in [Buc1] p. 203.
  5. The scalar multiplication is defined in [Buc1] p. 203.
  6. The notion of an ordinal term is defined in [Buc1] p. 201.
  7. The recursive system of fundamental sequences is defined in [Buc1] p. 203--204 except for the case of ([].4) (ii). Replacing ([].4) (ii) by the rule 6 in Definition in [Buc2] p. 6 applied to the convention \(\Omega_0 = 1\), we obtain the full definition of the recursive system of fundamental sequences.
  8. The map \(\textrm{dom}\) is defined in [Buc1] p. 203--204.
  9. The map \(o\) is defined in [Buc1] p. 201.

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


Implementation of existing works into programs

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

By ふぃっしゅ (Fish): Computing last 10000 digits of mega · 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 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