superexponentiation is not elementary


In this entry, we will show that the superexponetial function f:2, given by

f(m,0)=m,f(m,n+1)=mf(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 completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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 2x is larger than, say, x100 for large enough x. Formally,

Definition. A function h:2 is said to majorize g:k if there is a b, such that for any a1,,ak:

g(a1,,ak)<h(a,b),where a=max{a1,,ak}>1.

It is easy to see that no binary function majorizes itself:

Proposition 1.

h:2 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 contradictionMathworldPlanetmathPlanetmath. ∎

Let be the set of all elementary recursive functions.

Proposition 2.

Let A be the set of all functions majorized by f. Then ERA.

Proof.

We simply show that 𝒜 contains the additionPlanetmathPlanetmath, multiplication, differencePlanetmathPlanetmath, quotientPlanetmathPlanetmath, and the projection functions, and that 𝒜 is closed under compositionMathworldPlanetmath, 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 x+y2t=2f(t,0)f(t,1)<f(t,2), and xyt2=f(t,0)2f(t,1)<f(t,2). Moreover, |x-y|t=f(t,0)<f(t,1), and quo(x,y)t=f(t,0)<f(t,1).

  • For projection functions pmk, suppose t=max{x1,,xk}>1. Then pmk(𝒙)=xmt=f(t,0)<f(t,1).

  • Suppose g1,,gmA are n-ary, and hA is m-ary. Let u=h(g1,,gm) and suppose x={x1,,xn}>1. Given u(𝒙)=h(g1(𝒙),,gm(𝒙)), let z=max{g1(𝒙),,gm(𝒙)}. We have two cases:

    1. (a)

      z1. Let y=max{h(y1,,ym)yi{0,1}}. Then u(𝒙)y<f(x,y).

    2. (b)

      z>1. Then, for some i, z=gi(𝒙)<f(x,s) for some s, since giA. Then u(𝒙)=h(g1(𝒙),,gm(𝒙))f(z,t) for some t since h𝒜. Now, f(z,t)=f(gi(𝒙),t)<f(f(x,s),t)f(x,s+2t). As a result, u(𝒙)<f(x,s+2t).

    In either case, let r=max{y,s+2t}. We see that u(𝒙)<f(x,r).

  • For the next two parts, suppose gA is (n+1)-ary. For any 𝒙=(x1,,xn), let x=max{x1,,xn}, and for any y, assume z=max{x,y}>1. Since gA, let t be such that g(𝒙,y)f(z,t), where z is as described above.

    Let gs(𝒙,y):=i=0yg(𝒙,i). We break this down into cases:

    1. (a)

      x>1. Then g(𝒙,i)<f(zi,t) where zi=max{x,i}>1 for each i. Let f(zj,t) be the maximum among the f(zi,t). Then gs(𝒙,y)(y+1)f(zj,t)(y+1)f(z,t), as jy. Since y+1z+1<2z=2f(z,0)f(z,1), we see that gs(𝒙,y)<f(z,1)f(z,t)f(z,t1), where t1=1+max{1,t}.

    2. (b)

      x=1. Then y>1. So gs(𝒙,y)=h(𝒙)+i=2yg(𝒙,i), where h(𝒙)=g(𝒙,0)+g(𝒙,1). Let v=max{h(v1,,vn)vi{0,1}}. Then gs(𝒙,y)v+i=2yg(𝒙,i). As before, g(𝒙,i)f(zi,t) for each i2, so pick the largest f(zj,t) among the f(zi,t). Then i=2yg(𝒙,i)(y-1)f(zj,t)(y-1)f(z,t)<zf(z,t)=f(z,0)f(z,t)f(z,t+1). Therefore, gs(𝒙,y)<v+f(z,t+1)<f(z,v)+f(z,t+1)f(z,t2), where t2=1+max{v,t+1}.

    In each case, pick t3=max{t1,t2}, so that gs(𝒙,y)<f(z,t3).

  • Let gp(𝒙,y):=i=0yg(𝒙,i). We again break down the proof into cases:

    1. (a)

      x>1. Then each g(𝒙,i)<f(zi,t) where zi=max{x,i}>1. Let f(zj,t) be the maximum among the f(zi,t). Then gs(𝒙,y)f(zj,t)(y+1)f(z,t)(y+1). Since y+1z+1<2z=2f(z,0)f(z,1), we see that gs(𝒙,y)<f(z,t)f(z,1)f(z,t1), where t1=2+max{1,t}.

    2. (b)

      x=1. Then y>1. So gp(𝒙,y)=h(𝒙)i=2yg(𝒙,i), where h(𝒙)=g(𝒙,0)g(𝒙,1). Let v=max{h(v1,,vn)vi{0,1}}. Then gp(𝒙,y)vi=2yg(𝒙,i). As before, each g(𝒙,i)f(zi,t), so pick the largest f(zj,t) among the f(xi,t). Then i=2yg(𝒙,i)f(zj,t)(y-1)f(z,t)(y-1)<f(z,t)z=f(z,t)f(z,0)f(z,t+2). Therefore, gp(𝒙,y)<vf(z,t+2)<f(z,v)f(z,t+2)f(z,t2), where t2=1+max{v,t+2}.

    In each case, pick t3=max{t1,t2}, so that gp(𝒙,y)<f(z,t3).

As a result, 𝒜. In other words, every elementary function is majorized by f. ∎

In conclusionMathworldPlanetmath, 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 fn: defined by fn(m):=f(m,n) is elementary. This can be done by inductionMathworldPlanetmath on n:

f0(m)=f(m,0)=m=p11(m) is elementary, and if fn(m) is elementary, so is fn+1(m)=f(m,n+1)=exp(m,f(m,n))=exp(p11(m),fn(m)), since exp is elementary, and elementary recursiveness preserves composition.

Using this fact, one may in fact show that =𝒜𝒫, where 𝒫 is the set of all primitive recursive functionsMathworldPlanetmath.

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