# properties of superexponentiation

In this entry, we list some basic properties of the superexponetial function $f:\mathbb{N}^{2}\to\mathbb{N}$, defined recursively by

 $f(m,0)=m,\qquad f(m,n+1)=m^{f(m,n)}.$

Furthermore, we set $f(0,n):=0$ for all $n$.

Given $m$, the values of $f$ are

 $m,m^{m},m^{m^{m}},\cdots,m^{\ldotp\cdotp^{m}},\cdots,$

where the evaluation of these values start from the top, for example: $3^{3^{3}}=3^{81}$.

###### Proposition 1.

Suppose $x,y,z\in\mathbb{N}$ (including $0$), and for all except the first assertion, $x>1$.

1. 1.

$x\leq f(x,y)$.

2. 2.

$f(x,y)$ is increasing in both arguments.

3. 3.

$2f(x,y)\leq f(x,y+1)$.

4. 4.

$f(x,y)^{2}\leq f(x,y+1)$.

5. 5.

$f(x,y)^{f(x,y)}\leq f(x,y+2)$

6. 6.

$f(x,y)+f(x,z)\leq f(x,1+\max\{y,z\})$.

7. 7.

$f(x,y)\cdot f(x,z)\leq f(x,1+\max\{y,z\})$.

8. 8.

$f(x,y)^{f(x,z)}\leq f(x,2+\max\{y,z\})$.

9. 9.

$f(f(x,y),z)\leq f(x,y+2z)$.

10. 10.

$y.

###### Proof.

Most of the proofs are done by induction.

1. 1.

The case when $x=0$ is obvious. Assume now that $x\neq 0$. Induct on $y$. The case $y=0$ is clear. Suppose $x\leq f(x,y)$. Then $x\leq x^{x}\leq x^{f(x,y)}=f(x,y+1)$.

2. 2.

To see $f(x,y) for $x>1$, induct on $y$. First, $f(x,0)=x. Next, assume $f(x,y). Then $f(x,y+1)=x^{f(x,y)}.

To see $f(x,y) for $x>1$, again induct on $y$. First, $f(x,0)=x. Next, assume $f(x,y). Then $f(x,y+1)=x^{f(x,y)}<(x+1)^{f(x,y)}<(x+1)^{f(x+1,y)}=f(x+1,y+1)$.

3. 3.

Induct on $y$: if $y=0$, then $2f(x,0)=2x\leq x^{2}\leq x^{x}=f(x,1)$. Next, assume $2f(x,y)\leq f(x,y+1)$. Then $2f(x,y+1)=x^{f(x,y)}\leq x^{2f(x,y)}\leq x^{f(x,y+1)}=f(x,y+2)$.

4. 4.

If $y=0$, then $f(x,0)^{2}=x^{2}\leq x^{x}=x^{f(x,0)}=f(x,1)$. Otherwise, $y=z+1$. Then $f(x,y)^{2}=f(x,z+1)^{2}=x^{2f(x,z)}\leq x^{f(x,z+1)}=x^{f(x,y)}=f(x,y+1)$. The inequality $2f(x,z)\leq f(x,z+1)$ is derived previously.

5. 5.

If $y=0$, then $f(x,0)^{f(x,0)}=x^{x}=f(x,1)\leq f(x,2)$. Otherwise, $y=z+1$. Then $f(x,y)^{f(x,y)}=f(x,z+1)^{f(x,z+1)}=x^{f(x,z)f(x,z+1)}\leq x^{f(x,z+1)^{2}}=x^% {f(x,z+2)}=f(x,z+3)=f(x,y+2)$.

From the last three statements, the next three proofs can be easily settled, fisrt, let $t=\max\{y,z\}$. Then

1. 6.

$f(x,y)+f(x,z)\leq 2f(x,t)\leq f(x,t+1)$.

2. 7.

$f(x,y)f(x,z)=f(x,t)^{2}\leq f(x,t+1)$.

3. 8.

$f(x,y)^{f(x,z)}\leq f(x,t)^{f(x,t)}\leq f(x,t+2)$.

4. 9.

Induct on $z$. If $z=0$, then $f(f(x,y),0)=f(x,y)$. Next, assume $f(f(x,y),z)\leq f(x,y+2z)$. Then $f(f(x,y),z+1)=f(x,y)^{f(f(x,y),z)}=f(x,y)^{f(x,y+2z)}\leq f(x,y+1)^{f(x,y+2z)}% \leq x^{f(x,y)f(x,y+2z)}\leq x^{f(x,y+2z+1)}=f(x,y+2z+2)$.

5. 10.

Induct on $y$. The case when $y=0$ is obvious. Next, if $y, then $y+1.

Concerning the recursiveness of $f$, here is another basic property of $f$:

###### Proposition 2.

$f$

###### Proof.

Since $f(m,0)=m=p_{1}^{1}(m)$ and $f(m,n+1)=\exp(m,f(m,n))=g(m,n,f(m,n))$, where $g(x,y,z)=\exp(p_{1}^{3}(x,y,z),p_{3}^{3}(x,y,z))$, are defined by primitive recursion via functions $p_{1}^{1}$ and $g$, and since the projection functions $p_{i}^{j}$, the exponential function $\exp$, and consequently $g$, are primitive recursive ($g$ obtained by composition), we see that $f$ is primitive recursive. ∎

Remark. Another recursive property of $f$ is that $f$ is not elementary recursive. The proof uses the properties listed above. It is a bit lengthy, and is done in the link below.

Title properties of superexponentiation PropertiesOfSuperexponentiation 2013-03-22 19:07:21 2013-03-22 19:07:21 CWoo (3771) CWoo (3771) 7 CWoo (3771) Result msc 40-00 msc 03D20 SuperexponentiationIsNotElementary