This is an English translation of my Japanese blog post submitted for a Japanese googological event last year.
I denote by \(\textrm{Lim}\) the class of non-zero limit ordinals.
Throughout this blog post, a function means a map \(\mathbb{N} \to \mathbb{N}\), and I denote by \(\textrm{Func}\) the set of functions. For functions \(g\) and \(h\), I define the relation \(g < h\) by the strict order of their growth rates. Namely, the relation \(g < h\) holds if and only if there is an \(N \in \mathbb{N}\) such that for any \(n \in \mathbb{N}\), \(n > N\) implies \(g(n) < h(n)\).
A family \((g_{\beta})_{\beta \in \alpha} \in \textrm{Func}^{\alpha}\) of functions indexed by an ordinal \(\alpha\) is said to be a linear hierarchy if for any \((\beta,\gamma) \in \alpha^2\), \(\beta < \gamma\) implies \(g_{\beta} < g_{\gamma}\).
Given an ordinal \(\alpha\) and its system \begin{eqnarray*} \textrm{Lim} \cap \alpha & \to & \alpha^{\mathbb{N}} \\ \beta & \mapsto & (\beta[n])_{n \in \mathbb{N}} \end{eqnarray*} of fundamental sequences, people often expect that the associated FGH \((f_{\beta})_{\beta \in \alpha} \in \textrm{Func}^{\alpha}\) forms a linear hierarchy, it does not necessarily hold. I introduce a counterexample of the expectation in this blog post.
Here, I recall that \((f_{\beta})_{\beta \in \alpha}\) is defined in the following transfinite induction:
- If \(\beta = 0\), then \(f_{\beta}(n) := n+1\).
- If \(\beta\) is a successor ordinal, setting \(\beta = \gamma+1\), then \(f_{\beta}(n) := f_{\gamma}^n(n)\).
- If \(\beta\) is a non-zero limit ordinal, then \(f_{\beta}(n) := f_{\beta[n]}(n)\).
- Counterexample of the expectation that \((f_{\beta})_{\beta \in \alpha}\) forms a linear hierarchy.
- Set \(\alpha := \omega^{\omega}+1\).
- An ordinal \(\beta\) is said to be an additive principal ordinal if it is closed under addition, i.e. for any ordinals \(\gamma_1\) and \(\gamma_2\) smaller than \(\beta\), \(\gamma_1 + \gamma_2 < \beta\). I denote by \(\textrm{AP}\) the set of non-zero limit additive principal ordinal smaller than \(\alpha\). Then we have \(\textrm{AP} \subset \textrm{Lim} \cap \alpha\).
- Now the map
\begin{eqnarray*} \omega+1 & \to & \textrm{AP} \\ a & \mapsto & \omega^{1+a} \end{eqnarray*}
- is bijective. I denote by \(\textrm{Idx}\) its inverse. For any \(\beta \in \textrm{Lim} \cap \alpha\) and \(n \in \mathbb{N}\), I define \(\beta[n] \in \alpha\) in the following way:
- Suppose \(\beta \in \textrm{AP}\).
- Put \(a := \textrm{Idx}(\beta)\).
- If \(n \leq a < \omega\), then \(\beta[n] := n\).
- If \(n > a\), then \(\beta[n] := \omega^a \times n\).
- If \(a = \omega\), then \(\beta[n] := \omega^{1+n}\).
- Suppose \(\beta \notin \textrm{AP}\).
- I denote by \(\gamma_0 + \cdots + \gamma_{m-1} + \gamma_m\) (\(m \in \mathbb{N}\)) the unique expression of \(\beta\) by a descending sequence \((\gamma_i)_{i = 0}^{m}\) of additive principal ordinals.
- Then \(\beta[n] := \gamma_0 + \cdots + \gamma_{m-1} + \gamma_m[n]\).
- We have obtained a system
\begin{eqnarray*} \textrm{Lim} \cap \alpha & \to & \alpha^{\mathbb{N}} \\ \beta & \mapsto & (\beta[n])_{n \in \mathbb{N}} \end{eqnarray*}
- of fundamental systems for \(\alpha\). I denote by \((f_{\beta})_{\beta \in \alpha}\) the FGH associated to \(\alpha\) and its system of fundamental sequences. Then for any \(n \in \mathbb{N}\), we have
\begin{eqnarray*} \omega[n] & = & \omega^{1+0}[n] = \left\{ \begin{array}{ll} 0 & (n = 0) \\ \omega^0 \times n & (n > 0) \end{array} \right. = n \\ \omega^{1+n}[n] & = & n \\ \omega^{\omega}[n] & = & \omega^{1+n}. \end{eqnarray*}
- Therefore we obtain
\begin{eqnarray*} f_{\omega}(n) & = & f_n(n) \\ f_{\omega^{\omega}}(n) & = & f_{\omega^{\omega}[n]}(n) = f_{\omega^{1+n}}(n) = f_{\omega^{1+n}[n]}(n) = f_n(n). \end{eqnarray*}
- It implies \(f_{\omega} = f_{\omega^{\omega}}\). By \(\omega < \omega^{\omega}\), \((f_{\beta})_{\beta \in \alpha}\) is not a linear hierarchy. □
As a result, FGH does not necessarily yield a linear hierarchy. In particular, we need to be careful when we use FGH for the estimation of two distinct functions. The order of the corresponding ordinals does not necessarily imply the order of their growth rates.