10,570 Pages

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}$$

The limit function $$g(n)$$ of 段階配列表記 is approximated to $$f_{\p_0(\W_\w)}(n)$$ using a specific system of fundamenntal sequences explained later.

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

## 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) = 0(0) = 0+0 = 0 = 16 \\ & & g(2) = 0(2) = 0(1(1)) = 0(1(0(1(0(1(0(1(0))))))) = 0(1(0(1(0(1(0(\underbrace{1+\cdots+1}_{8})))))) \\ & = & 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))))))) \\ & = & \cdots \end{eqnarray*}

## Sources

1. The user page of mrna in Japanese Googology Wiki.
2. mrna, "段階配列表記", Google Document, 2020.
3. p進大好きbot, 段階配列表記観察日記, Japanese Googology Wiki user blog.