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,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 (http://planetmath.org/PropertiesOfSuperexponentiation)) 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},\mathrm{\dots},{a}_{k}\in \mathbb{N}$:
$$ 
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$, $$ where $a=\mathrm{max}\{x,y\}>1$. Let $c=\mathrm{max}\{a,b\}>1$. Then $$, a contradiction^{}. ∎
Let $\mathcal{E}\mathcal{R}$ be the set of all elementary recursive functions.
Proposition 2.
Let $\mathrm{A}$ be the set of all functions majorized by $f$. Then $\mathrm{E}\mathit{}\mathrm{R}\mathrm{\subseteq}\mathrm{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{E}\mathcal{R}$ is the smallest such set, the proof completes.

•
For addition, multiplication, and difference: suppose $t=\mathrm{max}\{x,y\}>1$. Then $$, and $$. Moreover, $$, and $$.

•
For projection functions ${p}_{m}^{k}$, suppose $t=\mathrm{max}\{{x}_{1},\mathrm{\dots},{x}_{k}\}>1$. Then $$.

•
Suppose ${g}_{1},\mathrm{\dots},{g}_{m}\in A$ are $n$ary, and $h\in A$ is $m$ary. Let $u=h({g}_{1},\mathrm{\dots},{g}_{m})$ and suppose $x=\{{x}_{1},\mathrm{\dots},{x}_{n}\}>1$. Given $u(\bm{x})=h({g}_{1}(\bm{x}),\mathrm{\dots},{g}_{m}(\bm{x}))$, let $z=\mathrm{max}\{{g}_{1}(\bm{x}),\mathrm{\dots},{g}_{m}(\bm{x})\}$. We have two cases:

(a)
$z\le 1$. Let $y=\mathrm{max}\{h({y}_{1},\mathrm{\dots},{y}_{m})\mid {y}_{i}\in \{0,1\}\}$. Then $$.

(b)
$z>1$. Then, for some $i$, $$ for some $s$, since ${g}_{i}\in A$. Then $u(\bm{x})=h({g}_{1}(\bm{x}),\mathrm{\dots},{g}_{m}(\bm{x}))\le f(z,t)$ for some $t$ since $h\in \mathcal{A}$. Now, $$. As a result, $$.
In either case, let $r=\mathrm{max}\{y,s+2t\}$. We see that $$.

(a)

•
For the next two parts, suppose $g\in A$ is $(n+1)$ary. For any $\bm{x}=({x}_{1},\mathrm{\dots},{x}_{n})$, let $x=\mathrm{max}\{{x}_{1},\mathrm{\dots},{x}_{n}\}$, and for any $y$, assume $z=\mathrm{max}\{x,y\}>1$. Since $g\in A$, let $t\in \mathbb{N}$ be such that $g(\bm{x},y)\le f(z,t)$, where $z$ is as described above.
Let ${g}_{s}(\bm{x},y):={\sum}_{i=0}^{y}g(\bm{x},i)$. We break this down into cases:

(a)
$x>1$. Then $$ where ${z}_{i}=\mathrm{max}\{x,i\}>1$ for each $i$. Let $f({z}_{j},t)$ be the maximum among the $f({z}_{i},t)$. Then ${g}_{s}(\bm{x},y)\le (y+1)f({z}_{j},t)\le (y+1)f(z,t)$, as $j\le y$. Since $$, we see that $$, where ${t}_{1}=1+\mathrm{max}\{1,t\}$.

(b)
$x=1$. Then $y>1$. So ${g}_{s}(\bm{x},y)=h(\bm{x})+{\sum}_{i=2}^{y}g(\bm{x},i)$, where $h(\bm{x})=g(\bm{x},0)+g(\bm{x},1)$. Let $v=\mathrm{max}\{h({v}_{1},\mathrm{\dots},{v}_{n})\mid {v}_{i}\in \{0,1\}\}$. Then ${g}_{s}(\bm{x},y)\le v+{\sum}_{i=2}^{y}g(\bm{x},i)$. As before, $g(\bm{x},i)\le f({z}_{i},t)$ for each $i\le 2$, so pick the largest $f({z}_{j},t)$ among the $f({z}_{i},t)$. Then $$. Therefore, $$, where ${t}_{2}=1+\mathrm{max}\{v,t+1\}$.
In each case, pick ${t}_{3}=\mathrm{max}\{{t}_{1},{t}_{2}\}$, so that $$.

(a)

•
Let ${g}_{p}(\bm{x},y):={\prod}_{i=0}^{y}g(\bm{x},i)$. We again break down the proof into cases:

(a)
$x>1$. Then each $$ where ${z}_{i}=\mathrm{max}\{x,i\}>1$. Let $f({z}_{j},t)$ be the maximum among the $f({z}_{i},t)$. Then ${g}_{s}(\bm{x},y)\le f{({z}_{j},t)}^{(y+1)}\le f{(z,t)}^{(y+1)}$. Since $$, we see that $$, where ${t}_{1}=2+\mathrm{max}\{1,t\}$.

(b)
$x=1$. Then $y>1$. So ${g}_{p}(\bm{x},y)=h(\bm{x}){\prod}_{i=2}^{y}g(\bm{x},i)$, where $h(\bm{x})=g(\bm{x},0)g(\bm{x},1)$. Let $v=\mathrm{max}\{h({v}_{1},\mathrm{\dots},{v}_{n})\mid {v}_{i}\in \{0,1\}\}$. Then ${g}_{p}(\bm{x},y)\le v{\prod}_{i=2}^{y}g(\bm{x},i)$. As before, each $g(\bm{x},i)\le f({z}_{i},t)$, so pick the largest $f({z}_{j},t)$ among the $f({x}_{i},t)$. Then $$. Therefore, $$, where ${t}_{2}=1+\mathrm{max}\{v,t+2\}$.
In each case, pick ${t}_{3}=\mathrm{max}\{{t}_{1},{t}_{2}\}$, so that $$.

(a)
As a result, $\mathcal{E}\mathcal{R}\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)=\mathrm{exp}(m,f(m,n))=\mathrm{exp}({p}_{1}^{1}(m),{f}_{n}(m))$, since $\mathrm{exp}$ is elementary, and elementary recursiveness preserves composition.
Using this fact, one may in fact show that $\mathcal{E}\mathcal{R}=\mathcal{A}\cap \mathcal{P}\mathcal{R}$, where $\mathcal{P}\mathcal{R}$ is the set of all primitive recursive functions^{}.
Title  superexponentiation is not elementary 

Canonical name  SuperexponentiationIsNotElementary 
Date of creation  20130322 19:07:14 
Last modified on  20130322 19:07:14 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  29 
Author  CWoo (3771) 
Entry type  Result 
Classification  msc 03D20 
Related topic  PropertiesOfSuperexponentiation 