properties of superexponentiation
In this entry, we list some basic properties of the superexponetial function , defined recursively by
Furthermore, we set for all .
Given , the values of are
where the evaluation of these values start from the top, for example: .
Proposition 1.
Suppose (including ), and for all except the first assertion, .
- 1.
.
- 2.
is increasing in both arguments.
- 3.
.
- 4.
.
- 5.
- 6.
.
- 7.
.
- 8.
.
- 9.
.
- 10.
.
Proof.
Most of the proofs are done by induction.
- 1.
The case when is obvious. Assume now that . Induct on . The case is clear. Suppose . Then .
- 2.
To see for , induct on . First, . Next, assume . Then .
To see for , again induct on . First, . Next, assume . Then .
- 3.
Induct on : if , then . Next, assume . Then .
- 4.
If , then . Otherwise, . Then . The inequality is derived previously.
- 5.
If , then . Otherwise, . Then .
From the last three statements, the next three proofs can be easily settled, fisrt, let . Then
- 6.
.
- 7.
.
- 8.
.
- 9.
Induct on . If , then . Next, assume . Then .
- 10.
Induct on . The case when is obvious. Next, if , then .
∎
Concerning the recursiveness of , here is another basic property of :
Proposition 2.
is primitive recursive.
Proof.
Since and , where , are defined by primitive recursion via functions and , and since the projection functions , the exponential function , and consequently , are primitive recursive ( obtained by composition), we see that is primitive recursive.∎
Remark. Another recursive property of is that is not elementary recursive. The proof uses the properties listed above. It is a bit lengthy, and is done in the link below.