Googology Wiki
Register
Advertisement
Googology Wiki

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
Last update: July 11, 2021

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.

Advertisement