I prove the following inequality where f is the fast-growing hierarchy with Wainer hierarchy and G is the Graham's number:
- fω+1(64) > G
List of lemmas and a theorem.
- Lemma 1: fn(m) > 2↑n-1m for n>1, m>1
- Lemma 2: fn(m) > 3↑n-2m + 2 for n>2, m>1
- Lemma 3: fω(n) > 3↑n-23 + 2 for n>2
- Lemma 4: fωn(64) > g(n) + 2 for n>0
- Theorem: fω+1(64) > G
Variables and definition[]
- m, n, a are nonnegative integers.
- α is an ordinal.
Definition of arrow notation for a>0, m>0, n>0
- (A1) a↑1n = an
- (A2) a↑n+11 = a
- (A3) a↑n+1(m+1) = a↑n(a↑n+1m)
- ↑1 is abbreviated as ↑
Definition of Graham's number, G
- (G1) g(0) = 4
- (G2) g(n+1) =
- (G3) G = g(64)
Definition of fast growing hierarchy for α<ω×2
- (F1) f0(n) = n+1
- (F2) fα+1(n) = fαn(n)
- (F3) fω(n) = fn(n)
Lemmas[]
Lemma 1: fn(m) > 2↑n-1m for n>1, m>1[]
First I calculate f1(n) and f2(n) from F1 and F2 and show an inequality L1a.
- f1(n) = f0n(n) (from F2) = n+1+1+1+...+1 = 2n
- f2(n) = f1n(n) = 2(2(2(...(2n)...))) = 2nn
- (L1a) fn(m) > fn-1(fn(m-1))
Proof of L1a: fn(m) = fn-1m(m) (F2) = fn-1(fn-1m-1(m)) > fn-1(fn-1m-1(m-1)) = fn-1(fn(m-1)) (F2)
I prove Lemma 1 by induction on n.
- (L1b) Lemma 1 for n=2 is shown as f2(m) = 2mm > 2↑m //
- (L1c) For n>2, induction hypothesis (IH) is that Lemma 1 is true for n = 2,3,...,n-1. Therefore we have IH that Lemma 1 is true for n-1; fn-1(m) > 2↑n-2m for m>1. I prove Lemma 1 for n>2 by another induction; induction on m.
- For m=2, Lemma 1 is shown as fn(2) > f2(2) = 8 and 2↑n-12 = 2↑n-22 = 2↑2 = 4.
- For m>2, we have IH of fn(m-1) > 2↑n-1(m-1). Therefore fn(m) > fn-1(fn(m-1)) (L1a) > fn-1(2↑n-1(m-1)) (IH for m) > 2↑n-2(2↑n-1(m-1)) (IH for n) = 2↑n-1m (A3) //
From L1b and L1c, Lemma 1 has been proven.
Lemma 2: fn(m) > 3↑n-2m + 2 for n>2, m>1[]
I prove Lemma 2 by induction on n.
- (L2a) For n=3, f3(m) > 3m + 2 for m>1. It is proven by induction on m as follows.
- For m=2, as f3(2) = f22(2) (F2) = f2(f2(2)) = f2(8) = 2048 and 32 + 2 = 11, L2a is true.
- For m>2, f3(m) > f2(f3(m-1)) (L1a) > f2(3m-1 + 2) (IH for m) > 2↑(3m-1 + 2) (f2(n) > 2↑n) = 4 × 2↑3m-1 (exponential law) = 3 × 2↑3m-1 + 2↑3m-1 > 3 × 3m-1 + 2 = 3m + 2 //
- (L2b) For n>3, it is proven by induction on m as follows.
- For m=2, fn(2) = fn-12(2) (F2) = fn-1(fn-1(2)) > fn-1(3↑n-32) (IH for n) > 3↑n-33↑n-32 + 2 (IH for n) > 3↑n-33 + 2 = 3↑n-22 + 2 (A3 and A2) //
- For m>2, fn(m) > fn-1(fn(m-1)) (L1a) > fn-1(3↑n-2(m-1)) (IH for m) > 3↑n-3(3↑n-2(m-1)) + 2 (IH for n) = 3↑n-2m + 2 (A3) //
From L2a and L2b, Lemma 2 has been proven.
Lemma 3: fω(n) > 3↑n-23 + 2 for n>2[]
Lemma 3 is proven as
- fω(n) = fn(n) (F3) > 3↑n-2n + 2 (Lemma 2) ≥ 3↑n-23 + 2 (n≥3) //
Lemma 4: fωn(64) > g(n) + 2 for n>0[]
I prove Lemma 4 by induction on n.
- (L4a) For n=1, fω(64) = f64(64) (F3) > 3↑6264 + 2 (Lemma 2) > 3↑43 + 2 = g(1) + 2 (G1 and G2) //
- (L4b) For n>1, fωn(64) = fω(fωn-1(64)) > fω(g(n-1) + 2) (IH) > + 2 (Lemma 3) = g(n) + 2 (G2) //
From L4a and L4b, Lemma 4 has been proven.
Theorem: fω+1(64) > G[]
- fω+1(64) = fω64(64) (F2) > g(64) + 2 (Lemma 4) > g(64) = G (G3) //
Now the theorem has been proven.
Acknowledgement[]
The reviewer p進大好きbot gave me helpful suggestions and the proof was revised as shown in the revision history of this page.