In a fast-growing hierarchy, what conditions on $(\alpha,\beta,n)$ imply $f_\alpha(n)<f_\beta(n)$?

93 Views Asked by At

Consider any specific fast-growing hierarchy $(f_\alpha)$ defined with one of the commonly used systems of fundamental sequences (e.g., any of those mentioned at the given link, using either Cantor normal forms up to $\epsilon_0$ or Veblen normal forms up to $\Gamma_{0}$).

Clearly, for some values of $n$, $\alpha<\beta$ does not imply $f_\alpha(n)< f_\beta(n)$; e.g., for all $n>1$, we have $f_{n+1}(n)>f_\omega(n)$ even though $n+1<\omega.$

Furthermore, it seems that for any limit ordinal $\beta$ and any $n>1$, there exists a successor ordinal $\alpha<\beta$ such that $f_{\alpha}(n)>f_\beta(n):$

$$f_\beta(n)=f_{\beta[n]}(n)=f_{\beta[n][n]}(n)=\dots=f_{\gamma}(n)<f_{\gamma}^n(n)=f_{\gamma+1}(n) $$

where $\gamma$ is the first successor ordinal produced by the (possibly repeated) diagonalizations $\beta[n]\dots$, and $\alpha=\gamma+1$.

Question: What conditions on $(\alpha,\beta,n)$ will guarantee that $f_\alpha(n)\lt f_\beta(n)$? Which of the following claims are valid?

  1. If $0<k<n$, then $f_{\alpha+k}(n)<f_{\alpha+n}(n).$
  2. If $\alpha<\beta$ and $\alpha,\beta$ are both successors, then $f_\alpha(n)\lt f_\beta(n)$ for all $n\gt 1$.
  3. If $\alpha<\beta$ and $\alpha,\beta$ are both limits, then $f_\alpha(n)\lt f_\beta(n)$ for all $n\gt 1$.
  4. If $\alpha<\beta$ and $\alpha$ is a limit, then $f_\alpha(n)\lt f_\beta(n)$ for all $n\gt 1$.

NB: (0) is valid because, if $0<k<n$, then $f_{\alpha+k}(n)<f_{\alpha+k}^n(n)=f_{\alpha+k+1}(n)<f_{\alpha+k+1}^n(n)=f_{\alpha+k+2}(n)<\dots<f_{\alpha+n}(n).$

As an aside, I notice that if (2) holds, and $\alpha<\beta$ are both limit ordinals, then we have not only $f_\alpha(n)\lt f_\beta(n)$, but also $f_{\alpha+k}(n)<f_\beta(n)$, for all $0<k<n$: $$f_{\alpha+k}(n)<f_{\alpha+n}(n)= f_{\alpha+\omega}(n)\le f_\beta(n)$$

where the rightmost inequality follows from (2) because $\alpha+\omega$ is the least limit ordinal greater than $\alpha.$