properties of superexponentiation

In this entry, we list some basic properties of the superexponetial functionMathworldPlanetmath f:2, defined recursively by


Furthermore, we set f(0,n):=0 for all n.

Given m, the values of f are


where the evaluation of these values start from the top, for example: 333=381.

Proposition 1.

Suppose x,y,zN (including 0), and for all except the first assertion, x>1.

  1. 1.


  2. 2.

    f(x,y) is increasing in both arguments.

  3. 3.


  4. 4.


  5. 5.


  6. 6.


  7. 7.


  8. 8.


  9. 9.


  10. 10.



Most of the proofs are done by inductionMathworldPlanetmath.

  1. 1.

    The case when x=0 is obvious. Assume now that x0. Induct on y. The case y=0 is clear. Suppose xf(x,y). Then xxxxf(x,y)=f(x,y+1).

  2. 2.

    To see f(x,y)<f(x,y+1) for x>1, induct on y. First, f(x,0)=x<xx=f(x,1). Next, assume f(x,y)<f(x,y+1). Then f(x,y+1)=xf(x,y)<xf(x,y+1)=f(x,y+1).

    To see f(x,y)<f(x+1,y) for x>1, again induct on y. First, f(x,0)=x<x+1=f(x+1,y). Next, assume f(x,y)<f(x+1,y). Then f(x,y+1)=xf(x,y)<(x+1)f(x,y)<(x+1)f(x+1,y)=f(x+1,y+1).

  3. 3.

    Induct on y: if y=0, then 2f(x,0)=2xx2xx=f(x,1). Next, assume 2f(x,y)f(x,y+1). Then 2f(x,y+1)=xf(x,y)x2f(x,y)xf(x,y+1)=f(x,y+2).

  4. 4.

    If y=0, then f(x,0)2=x2xx=xf(x,0)=f(x,1). Otherwise, y=z+1. Then f(x,y)2=f(x,z+1)2=x2f(x,z)xf(x,z+1)=xf(x,y)=f(x,y+1). The inequality 2f(x,z)f(x,z+1) is derived previously.

  5. 5.

    If y=0, then f(x,0)f(x,0)=xx=f(x,1)f(x,2). Otherwise, y=z+1. Then f(x,y)f(x,y)=f(x,z+1)f(x,z+1)=xf(x,z)f(x,z+1)xf(x,z+1)2=xf(x,z+2)=f(x,z+3)=f(x,y+2).

From the last three statements, the next three proofs can be easily settled, fisrt, let t=max{y,z}. Then

  1. 6.


  2. 7.


  3. 8.


  4. 9.

    Induct on z. If z=0, then f(f(x,y),0)=f(x,y). Next, assume f(f(x,y),z)f(x,y+2z). Then f(f(x,y),z+1)=f(x,y)f(f(x,y),z)=f(x,y)f(x,y+2z)f(x,y+1)f(x,y+2z)xf(x,y)f(x,y+2z)xf(x,y+2z+1)=f(x,y+2z+2).

  5. 10.

    Induct on y. The case when y=0 is obvious. Next, if y<f(x,y), then y+1<f(x,y)+1<f(x,y)+f(x,0)f(x,y+1).

Concerning the recursiveness of f, here is another basic property of f:

Proposition 2.

Since f(m,0)=m=p11(m) and f(m,n+1)=exp(m,f(m,n))=g(m,n,f(m,n)), where g(x,y,z)=exp(p13(x,y,z),p33(x,y,z)), are defined by primitive recursion via functions p11 and g, and since the projection functions pij, the exponential functionDlmfDlmfMathworld exp, and consequently g, are primitive recursive (g obtained by composition), we see that f is primitive recursive. ∎

Remark. Another recursive property of f is that f is not elementary recursive. The proof uses the properties listed above. It is a bit lengthy, and is done in the link below.

Title properties of superexponentiation
Canonical name PropertiesOfSuperexponentiation
Date of creation 2013-03-22 19:07:21
Last modified on 2013-03-22 19:07:21
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Result
Classification msc 40-00
Classification msc 03D20
Related topic SuperexponentiationIsNotElementary