Comparison of arbitary conway chains (in particular a chain with $m$ $m's$) to $f_{\omega^2}(n)$

Question

Wikipedia describes the Conway chained arrow notation and the fast growing hierarchy.

I learnt that the function $f(n):=\large f_{\omega^2}(n)$ has the same growth rate as the function $g(n):=n\rightarrow n\rightarrow n\rightarrow ... \rightarrow n\rightarrow n$ with $n\ n's$ in the chain.

• But how can I concretely compare a number $f(m)$ to a number $g(n)$ for arbitary natural numbers m,n ?
• How can I compare arbitary conway chains with some value of $f(m)$ ?
• For which natural numbers $n$ does the inequality $g(n)>f(n)$ hold , and for which $f(n)>g(n)$ ?

Answer 1

In general we have $$f_{\omega a+b}(c) \approx \underbrace{3 \rightarrow 3 \cdots 3 \rightarrow 3}_{a+1} \rightarrow c \rightarrow (b+1)$$

Let's evaluate some small numbers. $f(1)=2$, $g(1)=1$, $g(2)=4$ $$g(3)<f(2)=f_{\omega2}(2)=f_{\omega+2}(2)=f_{\omega+1}(f_{\omega+1}(2))=f_{\omega+1}(f_{\omega+1}(2))=f_{\omega+1}(f_{\omega}(8))\approx3 \rightarrow 3 \rightarrow (2 \rightarrow 8 \rightarrow 7) \rightarrow 2 < g(4)$$

$$g(4) < f(3)=f_{\omega3}(3)=f_{\omega2+3}(3)\approx 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 4 < g(5)$$

$$g(5) < f(4)=f_{\omega4}(4)=f_{\omega3+4}(4)\approx 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 5 < g(6)$$

In general, we have $g(n+1)<f(n)<g(n+2)$ for $n\geq2$. It is fairly hard to formally proof.

$f(n)>g(n)$ holds for all natural $n$. It certainly holds for $n\geq2$, and we also have $f(1)=2>1=g(1)$. In fact it also holds for 0, since $f(0)=1$ and $g(0)$ is empty thus zero.