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,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},\mathrm{\cdots },m^{.{\cdot }^m},\mathrm{\cdots },$$

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

Proposition 1.

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

1. $x\le f(x,y)$.

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

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

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

5. $f{(x,y)}^{f(x,y)}\le f(x,y+2)$

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

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

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

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

10. .

Proof.

Most of the proofs are done by induction.

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

2. To see for $x>1$, induct on $y$. First, . Next, assume . Then .

   To see for $x>1$, again induct on $y$. First, . Next, assume . Then .

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

4. If $y=0$, then $f{(x,0)}^2=x^2\le 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)}\le x^{f(x,z+1)}=x^{f(x,y)}=f(x,y+1)$. The inequality $2f(x,z)\le f(x,z+1)$ is derived previously.

5. If $y=0$, then $f{(x,0)}^{f(x,0)}=x^x=f(x,1)\le 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)}\le 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. $f(x,y)+f(x,z)\le 2f(x,t)\le f(x,t+1)$.

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

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

4. Induct on $z$. If $z=0$, then $f(f(x,y),0)=f(x,y)$. Next, assume $f(f(x,y),z)\le 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)}\le f{(x,y+1)}^{f(x,y+2z)}\le x^{f(x,y)f(x,y+2z)}\le x^{f(x,y+2z+1)}=f(x,y+2z+2)$.

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

∎

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

Proposition 2.

$f$ is primitive recursive.

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
Canonical name	PropertiesOfSuperexponentiation
Date of creation	2013-03-22 19:07:21
Last modified on	2013-03-22 19:07:21
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	7
Author	CWoo (3771)
Entry type	Result
Classification	msc 40-00
Classification	msc 03D20
Related topic	SuperexponentiationIsNotElementary