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=\max \{x,y\}>1$. Let $c=\max \{a,b\}>1$. Then , a contradiction.∎

Let $ℰℛ$ 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 $𝒜$ contains the addition, multiplication, difference, quotient, and the projection functions, and that $𝒜$ is closed under composition, bounded sum, and bounded product. And since $ℰℛ$ is the smallest such set, the proof completes.

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

• For projection functions $p_m^k$, suppose $t=\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(𝒙)=h(g_1(𝒙),\mathrm{\dots },g_m(𝒙))$, let $z=\max \{g_1(𝒙),\mathrm{\dots },g_m(𝒙)\}$. We have two cases:

  1. $z\le 1$. Let $y=\max \{h(y_1,\mathrm{\dots },y_m)\mid y_i\in \{0,1\}\}$. Then .

  2. $z>1$. Then, for some $i$, for some $s$, since $g_i\in A$. Then $u(𝒙)=h(g_1(𝒙),\mathrm{\dots },g_m(𝒙))\le f(z,t)$ for some $t$ since $h\in 𝒜$. Now, . As a result, .

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

• For the next two parts, suppose $g\in A$ is $(n+1)$-ary. For any $𝒙=(x_1,\mathrm{\dots },x_n)$, let $x=\max \{x_1,\mathrm{\dots },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(𝒙,y)\le f(z,t)$, where $z$ is as described above.

  Let $g_s(𝒙,y):={\sum }_{i=0}^{y}g(𝒙,i)$. We break this down into cases:

  1. $x>1$. Then 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(𝒙,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+\max \{1,t\}$.

  2. $x=1$. Then $y>1$. So $g_s(𝒙,y)=h(𝒙)+{\sum }_{i=2}^{y}g(𝒙,i)$, where $h(𝒙)=g(𝒙,0)+g(𝒙,1)$. Let $v=\max \{h(v_1,\mathrm{\dots },v_n)\mid v_i\in \{0,1\}\}$. Then $g_s(𝒙,y)\le v+{\sum }_{i=2}^{y}g(𝒙,i)$. As before, $g(𝒙,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+\max \{v,t+1\}$.

  In each case, pick $t_3=\max \{t_1,t_2\}$, so that .

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

  1. $x>1$. Then each where $z_i=\max \{x,i\}>1$. Let $f(z_j,t)$ be the maximum among the $f(z_i,t)$. Then $g_s(𝒙,y)\le f{(z_j,t)}^{(y+1)}\le f{(z,t)}^{(y+1)}$. Since , we see that , where $t_1=2+\max \{1,t\}$.

  2. $x=1$. Then $y>1$. So $g_p(𝒙,y)=h(𝒙){\prod }_{i=2}^{y}g(𝒙,i)$, where $h(𝒙)=g(𝒙,0)g(𝒙,1)$. Let $v=\max \{h(v_1,\mathrm{\dots },v_n)\mid v_i\in \{0,1\}\}$. Then $g_p(𝒙,y)\le v{\prod }_{i=2}^{y}g(𝒙,i)$. As before, each $g(𝒙,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+\max \{v,t+2\}$.

  In each case, pick $t_3=\max \{t_1,t_2\}$, so that .

As a result, $ℰℛ\subseteq 𝒜$. 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 $ℰℛ=𝒜\cap 𝒫ℛ$, where $𝒫ℛ$ is the set of all primitive recursive functions.