1
$\begingroup$

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)$ ?
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much! I never read about the $g(n+1)<f(n)<g(n+2)$ -inequality. $\endgroup$ – Peter Jul 26 '15 at 19:51
  • $\begingroup$ Did you notice my question : math.stackexchange.com/questions/1345845/… ? $\endgroup$ – Peter Jul 26 '15 at 20:04
  • $\begingroup$ @Peter No, I didn't. I shall take a look to it tomorrow. I highly suspect the statement to be true, at least for large $a$. $\endgroup$ – wythagoras Jul 26 '15 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.