I prove the following equation comparing the up-arrow notation with the hyper-E notation.
- (T1) \(a \uparrow^{c}b = E(a)\underbrace{1\#1\#...1\#}_{(1\#) \times (c-1)}b\)
for positive integers a, b, c. For example,
- a↑b = E(a)b
- a↑↑b = E(a)1#b
- a↑↑↑b = E(a)1#1#b
- a↑↑↑↑b = E(a)1#1#1#b
Notation and definition[]
From the definition of up-arrow notation,
- (A1) a↑b = ab
- (A2) a↑c+11 = a
- (A3) a↑c+1(b+1) = a↑c(a↑c+1b)
Denote X as a string of subarray, where subarray is a string inductively defined as
- Positive integer or
- Concatenation of subarray Y, hyperion # and a positive integer a, i.e., Y#a.
From the definition of hyper-E notation,
- (E1) E(a)b = ab
- (E2) E(a)X#1 = E(a)X
- (E3) E(a)c#(b+1) = E(a)(E(a)c#b)
- (E4) E(a)X#c#(b+1) = E(a)X#(E(a)X#c#b)
Note: (E3) and (E4) can be combined if we regard (E3) as empty (X#) of E4. Actually (E3) is the difficult part of reading the original definition, E[b]a1#a2#a3⋯#an−2#an−1#an= E[b]a1#a2#a3⋯#an−2#(E[b]a1#a2#a3⋯#an−2#an−1#(an−1)), because when n=2 the whole part of (a1#a2#a3⋯#an−2#) is eliminated, but it looks as if # remains. So the definition of (E3) and (E4) were separated for clarification.
We denote (a#)n for repetition of a# for n times, where it becomes empty string when n=0. Then T1 can be written as
- (T1) a↑cb = E(a)((1#)(c-1))b
Proof[]
T1 will be proved by induction of c.
For c=1, T1 is obvious from A1 and E1.
Assuming T1 is true for a specified c, we prove T1 for c+1, which is
(T1a) a↑c+1b = E(a)((1#)c)b
T1a is proved by induction for b.
- For b=1, a↑c+11 = a (from A2) = E(a)1 (E1) = E(a)1#1 (E2) = E(a)((1#)c)1 (induction of E2) //
- For b+1, a↑c+1(b+1) = a↑c(a↑c+1b) (A3) = E(a)((1#)(c-1))(a↑c+1b) (induction hypothesis = IH for c, T1) = E(a)((1#)(c-1))(E(a)((1#)c)b) (IH for b, T1a) = E(a)((1#)c)(b+1) (E3 or E4) //
Therefore T1 was proved.