You are here
Homesuperexponentiation is not elementary
Primary tabs
superexponentiation is not elementary
In this entry, we will show that the superexponetial function $f:\mathbb{N}^{2}\to\mathbb{N}$, given by
$f(m,0)=m,\qquad f(m,n+1)=m^{{f(m,n)}}$ 
is not elementary recursive (we set $f(0,n):=0$ for all $n$). We will use the properties of $f$ (listed here) to complete this task.
The idea behind the proof is to find a property satisfied by all elementary recursive functions but not by $f$. The particular property we have in mind is the “growth rate” of a function. We want to demonstrate that $f$, in some way, grows faster than any elementary function $g$. This idea is similar to showing that $2^{x}$ is larger than, say, $x^{{100}}$ for large enough $x$. Formally,
Definition. A function $h:\mathbb{N}^{2}\to\mathbb{N}$ is said to majorize $g:\mathbb{N}^{k}\to\mathbb{N}$ if there is a $b\in\mathbb{N}$, such that for any $a_{1},\ldots,a_{k}\in\mathbb{N}$:
$g(a_{1},\ldots,a_{k})<h(a,b),\qquad\mbox{where }a=\max\{a_{1},\ldots,a_{k}\}>1.$ 
It is easy to see that no binary function majorizes itself:
Proposition 1.
$h:\mathbb{N}^{2}\to\mathbb{N}$ does not majorize $h$.
Proof.
Otherwise, there is a $b$ such that for any $x,y$, $h(x,y)<h(a,b)$ where $a=\max\{x,y\}>1$. Let $c=\max\{a,b\}>1$. Then $h(c,b)<h(\max\{b,c\},b)=h(c,b)$, a contradiction. ∎
Let $\mathcal{ER}$ be the set of all elementary recursive functions.
Proposition 2.
Let $\mathcal{A}$ be the set of all functions majorized by $f$. Then $\mathcal{ER}\subseteq\mathcal{A}$.
Proof.
We simply show that $\mathcal{A}$ contains the addition, multiplication, difference, quotient, and the projection functions, and that $\mathcal{A}$ is closed under composition, bounded sum, and bounded product. And since $\mathcal{ER}$ is the smallest such set, the proof completes.

For addition, multiplication, and difference: suppose $t=\max\{x,y\}>1$. Then $x+y\leq 2t=2f(t,0)\leq f(t,1)<f(t,2)$, and $xy\leq t^{2}=f(t,0)^{2}\leq f(t,1)<f(t,2)$. Moreover, $xy\leq t=f(t,0)<f(t,1)$, and $\operatorname{quo}(x,y)\leq t=f(t,0)<f(t,1)$.

For projection functions $p_{m}^{k}$, suppose $t=\max\{x_{1},\ldots,x_{k}\}>1$. Then $p_{m}^{k}(\boldsymbol{x})=x_{m}\leq t=f(t,0)<f(t,1)$.

Suppose $g_{1},\ldots,g_{m}\in A$ are $n$ary, and $h\in A$ is $m$ary. Let $u=h(g_{1},\ldots,g_{m})$ and suppose $x=\{x_{1},\ldots,x_{n}\}>1$. Given $u(\boldsymbol{x})=h(g_{1}(\boldsymbol{x}),\ldots,g_{m}(\boldsymbol{x}))$, let $z=\max\{g_{1}(\boldsymbol{x}),\ldots,g_{m}(\boldsymbol{x})\}$. We have two cases:
(a) $z\leq 1$. Let $y=\max\{h(y_{1},\ldots,y_{m})\mid y_{i}\in\{0,1\}\}$. Then $u(\boldsymbol{x})\leq y<f(x,y)$.
(b) $z>1$. Then, for some $i$, $z=g_{i}(\boldsymbol{x})<f(x,s)$ for some $s$, since $g_{i}\in A$. Then $u(\boldsymbol{x})=h(g_{1}(\boldsymbol{x}),\ldots,g_{m}(\boldsymbol{x}))\leq f(% z,t)$ for some $t$ since $h\in\mathcal{A}$. Now, $f(z,t)=f(g_{i}(\boldsymbol{x}),t)<f(f(x,s),t)\leq f(x,s+2t)$. As a result, $u(\boldsymbol{x})<f(x,s+2t)$.
In either case, let $r=\max\{y,s+2t\}$. We see that $u(\boldsymbol{x})<f(x,r)$.

For the next two parts, suppose $g\in A$ is $(n+1)$ary. For any $\boldsymbol{x}=(x_{1},\ldots,x_{n})$, let $x=\max\{x_{1},\ldots,x_{n}\}$, and for any $y$, assume $z=\max\{x,y\}>1$. Since $g\in A$, let $t\in\mathbb{N}$ be such that $g(\boldsymbol{x},y)\leq f(z,t)$, where $z$ is as described above.
Let $g_{s}(\boldsymbol{x},y):=\sum_{{i=0}}^{y}g(\boldsymbol{x},i)$. We break this down into cases:
(a) $x>1$. Then $g(\boldsymbol{x},i)<f(z_{i},t)$ where $z_{i}=\max\{x,i\}>1$ for each $i$. Let $f(z_{j},t)$ be the maximum among the $f(z_{i},t)$. Then $g_{s}(\boldsymbol{x},y)\leq(y+1)f(z_{j},t)\leq(y+1)f(z,t)$, as $j\leq y$. Since $y+1\leq z+1<2z=2f(z,0)\leq f(z,1)$, we see that $g_{s}(\boldsymbol{x},y)<f(z,1)f(z,t)\leq f(z,t_{1})$, where $t_{1}=1+\max\{1,t\}$.
(b) $x=1$. Then $y>1$. So $g_{s}(\boldsymbol{x},y)=h(\boldsymbol{x})+\sum_{{i=2}}^{y}g(\boldsymbol{x},i)$, where $h(\boldsymbol{x})=g(\boldsymbol{x},0)+g(\boldsymbol{x},1)$. Let $v=\max\{h(v_{1},\ldots,v_{n})\mid v_{i}\in\{0,1\}\}$. Then $g_{s}(\boldsymbol{x},y)\leq v+\sum_{{i=2}}^{y}g(\boldsymbol{x},i)$. As before, $g(\boldsymbol{x},i)\leq f(z_{i},t)$ for each $i\leq 2$, so pick the largest $f(z_{j},t)$ among the $f(z_{i},t)$. Then $\sum_{{i=2}}^{y}g(\boldsymbol{x},i)\leq(y1)f(z_{j},t)\leq(y1)f(z,t)<zf(z,t)=% f(z,0)f(z,t)\leq f(z,t+1)$. Therefore, $g_{s}(\boldsymbol{x},y)<v+f(z,t+1)<f(z,v)+f(z,t+1)\leq f(z,t_{2})$, where $t_{2}=1+\max\{v,t+1\}$.
In each case, pick $t_{3}=\max\{t_{1},t_{2}\}$, so that $g_{s}(\boldsymbol{x},y)<f(z,t_{3})$.

Let $g_{p}(\boldsymbol{x},y):=\prod_{{i=0}}^{y}g(\boldsymbol{x},i)$. We again break down the proof into cases:
(a) $x>1$. Then each $g(\boldsymbol{x},i)<f(z_{i},t)$ where $z_{i}=\max\{x,i\}>1$. Let $f(z_{j},t)$ be the maximum among the $f(z_{i},t)$. Then $g_{s}(\boldsymbol{x},y)\leq f(z_{j},t)^{{(y+1)}}\leq f(z,t)^{{(y+1)}}$. Since $y+1\leq z+1<2z=2f(z,0)\leq f(z,1)$, we see that $g_{s}(\boldsymbol{x},y)<f(z,t)^{{f(z,1)}}\leq f(z,t_{1})$, where $t_{1}=2+\max\{1,t\}$.
(b) $x=1$. Then $y>1$. So $g_{p}(\boldsymbol{x},y)=h(\boldsymbol{x})\prod_{{i=2}}^{y}g(\boldsymbol{x},i)$, where $h(\boldsymbol{x})=g(\boldsymbol{x},0)g(\boldsymbol{x},1)$. Let $v=\max\{h(v_{1},\ldots,v_{n})\mid v_{i}\in\{0,1\}\}$. Then $g_{p}(\boldsymbol{x},y)\leq v\prod_{{i=2}}^{y}g(\boldsymbol{x},i)$. As before, each $g(\boldsymbol{x},i)\leq f(z_{i},t)$, so pick the largest $f(z_{j},t)$ among the $f(x_{i},t)$. Then $\prod_{{i=2}}^{y}g(\boldsymbol{x},i)\leq f(z_{j},t)^{{(y1)}}\leq f(z,t)^{{(y% 1)}}<f(z,t)^{z}=f(z,t)^{{f(z,0)}}\leq f(z,t+2)$. Therefore, $g_{p}(\boldsymbol{x},y)<vf(z,t+2)<f(z,v)f(z,t+2)\leq f(z,t_{2})$, where $t_{2}=1+\max\{v,t+2\}$.
In each case, pick $t_{3}=\max\{t_{1},t_{2}\}$, so that $g_{p}(\boldsymbol{x},y)<f(z,t_{3})$.
As a result, $\mathcal{ER}\subseteq\mathcal{A}$. In other words, every elementary function is majorized by $f$. ∎
In conclusion, we have
Corollary 1.
$f$ is not elementary.
Proof.
If it were, it would majorize itself, which is impossible. ∎
Remark. Although $f$ is not elementary recursive, it is easy to see that, for any $n$, the function $f_{n}:\mathbb{N}\to\mathbb{N}$ defined by $f_{n}(m):=f(m,n)$ is elementary. This can be done by induction on $n$:
$f_{0}(m)=f(m,0)=m=p_{1}^{1}(m)$ is elementary, and if $f_{n}(m)$ is elementary, so is $f_{{n+1}}(m)=f(m,n+1)=\exp(m,f(m,n))=\exp(p_{1}^{1}(m),f_{n}(m))$, since $\exp$ is elementary, and elementary recursiveness preserves composition.
Using this fact, one may in fact show that $\mathcal{ER}=\mathcal{A}\cap\mathcal{PR}$, where $\mathcal{PR}$ is the set of all primitive recursive functions.
Mathematics Subject Classification
03D20 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections