# 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 (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},\ldots,a_{k}\in\mathbb{N}$:

 $g(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) where $a=\max\{x,y\}>1$. Let $c=\max\{a,b\}>1$. Then $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), and $xy\leq t^{2}=f(t,0)^{2}\leq f(t,1). Moreover, $|x-y|\leq t=f(t,0), and $\operatorname{quo}(x,y)\leq t=f(t,0).

• 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).

• 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:

1. (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.

2. (b)

$z>1$. Then, for some $i$, $z=g_{i}(\boldsymbol{x}) 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). As a result, $u(\boldsymbol{x}).

In either case, let $r=\max\{y,s+2t\}$. We see that $u(\boldsymbol{x}).

• 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:

1. (a)

$x>1$. Then $g(\boldsymbol{x},i) 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), where $t_{1}=1+\max\{1,t\}$.

2. (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(y-1)f(z_{j},t)\leq(y-1)f(z,t). Therefore, $g_{s}(\boldsymbol{x},y), 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).

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

1. (a)

$x>1$. Then each $g(\boldsymbol{x},i) 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), where $t_{1}=2+\max\{1,t\}$.

2. (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)^{(y-1)}\leq f(z,t)^{(y-1)}. Therefore, $g_{p}(\boldsymbol{x},y), 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).

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.

Title superexponentiation is not elementary SuperexponentiationIsNotElementary 2013-03-22 19:07:14 2013-03-22 19:07:14 CWoo (3771) CWoo (3771) 29 CWoo (3771) Result msc 03D20 PropertiesOfSuperexponentiation