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})<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, $|x-y|\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:
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<f(x,y)$ .
2. (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:
1. (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\}$ .
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)<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:
1. (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\}$ .
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)}<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.

Title	superexponentiation is not elementary
Canonical name	SuperexponentiationIsNotElementary
Date of creation	2013-03-22 19:07:14
Last modified on	2013-03-22 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