[GOAL]
n : ℕ
⊢ ack 0 n = n + 1
[PROOFSTEP]
rw [ack]
[GOAL]
m : ℕ
⊢ ack (m + 1) 0 = ack m 1
[PROOFSTEP]
rw [ack]
[GOAL]
m n : ℕ
⊢ ack (m + 1) (n + 1) = ack m (ack (m + 1) n)
[PROOFSTEP]
rw [ack]
[GOAL]
n : ℕ
⊢ ack 1 n = n + 2
[PROOFSTEP]
induction' n with n IH
[GOAL]
case zero
⊢ ack 1 zero = zero + 2
[PROOFSTEP]
rfl
[GOAL]
case succ
n : ℕ
IH : ack 1 n = n + 2
⊢ ack 1 (succ n) = succ n + 2
[PROOFSTEP]
simp [IH]
[GOAL]
n : ℕ
⊢ ack 2 n = 2 * n + 3
[PROOFSTEP]
induction' n with n IH
[GOAL]
case zero
⊢ ack 2 zero = 2 * zero + 3
[PROOFSTEP]
rfl
[GOAL]
case succ
n : ℕ
IH : ack 2 n = 2 * n + 3
⊢ ack 2 (succ n) = 2 * succ n + 3
[PROOFSTEP]
simpa [mul_succ]
[GOAL]
n : ℕ
⊢ ack 3 n = 2 ^ (n + 3) - 3
[PROOFSTEP]
induction' n with n IH
[GOAL]
case zero
⊢ ack 3 zero = 2 ^ (zero + 3) - 3
[PROOFSTEP]
rfl
[GOAL]
case succ
n : ℕ
IH : ack 3 n = 2 ^ (n + 3) - 3
⊢ ack 3 (succ n) = 2 ^ (succ n + 3) - 3
[PROOFSTEP]
rw [ack_succ_succ, IH, ack_two, Nat.succ_add, Nat.pow_succ 2 (n + 3), mul_comm _ 2, Nat.mul_sub_left_distrib, ←
  Nat.sub_add_comm, two_mul 3, Nat.add_sub_add_right]
[GOAL]
case succ
n : ℕ
IH : ack 3 n = 2 ^ (n + 3) - 3
⊢ 2 * 3 ≤ 2 * 2 ^ (n + 3)
[PROOFSTEP]
have H : 2 * 3 ≤ 2 * 2 ^ 3 := by norm_num
[GOAL]
n : ℕ
IH : ack 3 n = 2 ^ (n + 3) - 3
⊢ 2 * 3 ≤ 2 * 2 ^ 3
[PROOFSTEP]
norm_num
[GOAL]
case succ
n : ℕ
IH : ack 3 n = 2 ^ (n + 3) - 3
H : 2 * 3 ≤ 2 * 2 ^ 3
⊢ 2 * 3 ≤ 2 * 2 ^ (n + 3)
[PROOFSTEP]
apply H.trans
[GOAL]
case succ
n : ℕ
IH : ack 3 n = 2 ^ (n + 3) - 3
H : 2 * 3 ≤ 2 * 2 ^ 3
⊢ 2 * 2 ^ 3 ≤ 2 * 2 ^ (n + 3)
[PROOFSTEP]
simp [pow_le_pow]
[GOAL]
n : ℕ
⊢ 0 < ack 0 n
[PROOFSTEP]
simp
[GOAL]
m : ℕ
⊢ 0 < ack (m + 1) 0
[PROOFSTEP]
rw [ack_succ_zero]
[GOAL]
m : ℕ
⊢ 0 < ack m 1
[PROOFSTEP]
apply ack_pos
[GOAL]
m n : ℕ
⊢ 0 < ack (m + 1) (n + 1)
[PROOFSTEP]
rw [ack_succ_succ]
[GOAL]
m n : ℕ
⊢ 0 < ack m (ack (m + 1) n)
[PROOFSTEP]
apply ack_pos
[GOAL]
n : ℕ
⊢ 1 < ack (0 + 1) n
[PROOFSTEP]
simp
[GOAL]
m : ℕ
⊢ 1 < ack (m + 1 + 1) 0
[PROOFSTEP]
rw [ack_succ_zero]
[GOAL]
m : ℕ
⊢ 1 < ack (m + 1) 1
[PROOFSTEP]
apply one_lt_ack_succ_left
[GOAL]
m n : ℕ
⊢ 1 < ack (m + 1 + 1) (n + 1)
[PROOFSTEP]
rw [ack_succ_succ]
[GOAL]
m n : ℕ
⊢ 1 < ack (m + 1) (ack (m + 1 + 1) n)
[PROOFSTEP]
apply one_lt_ack_succ_left
[GOAL]
n : ℕ
⊢ 1 < ack 0 (n + 1)
[PROOFSTEP]
simp
[GOAL]
m n : ℕ
⊢ 1 < ack (m + 1) (n + 1)
[PROOFSTEP]
rw [ack_succ_succ]
[GOAL]
m n : ℕ
⊢ 1 < ack m (ack (m + 1) n)
[PROOFSTEP]
cases' exists_eq_succ_of_ne_zero (ack_pos (m + 1) n).ne' with h h
[GOAL]
case intro
m n h✝ : ℕ
h : ack (m + 1) n = succ h✝
⊢ 1 < ack m (ack (m + 1) n)
[PROOFSTEP]
rw [h]
[GOAL]
case intro
m n h✝ : ℕ
h : ack (m + 1) n = succ h✝
⊢ 1 < ack m (succ h✝)
[PROOFSTEP]
apply one_lt_ack_succ_right
[GOAL]
n₁ n₂ : ℕ
h : n₁ < n₂
⊢ ack 0 n₁ < ack 0 n₂
[PROOFSTEP]
simpa using h
[GOAL]
m n : ℕ
_h : 0 < n + 1
⊢ ack (m + 1) 0 < ack (m + 1) (n + 1)
[PROOFSTEP]
rw [ack_succ_zero, ack_succ_succ]
[GOAL]
m n : ℕ
_h : 0 < n + 1
⊢ ack m 1 < ack m (ack (m + 1) n)
[PROOFSTEP]
exact ack_strictMono_right _ (one_lt_ack_succ_left m n)
[GOAL]
m n₁ n₂ : ℕ
h : n₁ + 1 < n₂ + 1
⊢ ack (m + 1) (n₁ + 1) < ack (m + 1) (n₂ + 1)
[PROOFSTEP]
rw [ack_succ_succ, ack_succ_succ]
[GOAL]
m n₁ n₂ : ℕ
h : n₁ + 1 < n₂ + 1
⊢ ack m (ack (m + 1) n₁) < ack m (ack (m + 1) n₂)
[PROOFSTEP]
apply ack_strictMono_right _ (ack_strictMono_right _ _)
[GOAL]
m n₁ n₂ : ℕ
h : n₁ + 1 < n₂ + 1
⊢ n₁ < n₂
[PROOFSTEP]
rwa [add_lt_add_iff_right] at h 
[GOAL]
n : ℕ
⊢ 0 + n < ack 0 n
[PROOFSTEP]
simp
[GOAL]
m : ℕ
⊢ m + 1 + 0 < ack (m + 1) 0
[PROOFSTEP]
simpa using add_lt_ack m 1
[GOAL]
m n : ℕ
⊢ m + 1 + n + 1 ≤ m + (m + n + 2)
[PROOFSTEP]
linarith
[GOAL]
m n : ℕ
⊢ m + n + 2 = succ (m + 1 + n)
[PROOFSTEP]
rw [succ_eq_add_one]
[GOAL]
m n : ℕ
⊢ m + n + 2 = m + 1 + n + 1
[PROOFSTEP]
ring_nf
[GOAL]
m : ℕ
_h : 0 < m + 1
⊢ ack 0 0 < ack (m + 1) 0
[PROOFSTEP]
simpa using one_lt_ack_succ_right m 0
[GOAL]
m n : ℕ
h : 0 < m + 1
⊢ ack 0 (n + 1) < ack (m + 1) (n + 1)
[PROOFSTEP]
rw [ack_zero, ack_succ_succ]
[GOAL]
m n : ℕ
h : 0 < m + 1
⊢ n + 1 + 1 < ack m (ack (m + 1) n)
[PROOFSTEP]
apply lt_of_le_of_lt (le_trans _ <| add_le_add_left (add_add_one_le_ack _ _) m) (add_lt_ack _ _)
[GOAL]
m n : ℕ
h : 0 < m + 1
⊢ n + 1 + 1 ≤ m + (m + 1 + n + 1)
[PROOFSTEP]
linarith
[GOAL]
m₁ m₂ : ℕ
h : m₁ + 1 < m₂ + 1
⊢ ack (m₁ + 1) 0 < ack (m₂ + 1) 0
[PROOFSTEP]
simpa using ack_strict_mono_left' 1 ((add_lt_add_iff_right 1).1 h)
[GOAL]
m₁ m₂ n : ℕ
h : m₁ + 1 < m₂ + 1
⊢ ack (m₁ + 1) (n + 1) < ack (m₂ + 1) (n + 1)
[PROOFSTEP]
rw [ack_succ_succ, ack_succ_succ]
[GOAL]
m₁ m₂ n : ℕ
h : m₁ + 1 < m₂ + 1
⊢ ack m₁ (ack (m₁ + 1) n) < ack m₂ (ack (m₂ + 1) n)
[PROOFSTEP]
exact
  (ack_strict_mono_left' _ <| (add_lt_add_iff_right 1).1 h).trans (ack_strictMono_right _ <| ack_strict_mono_left' n h)
[GOAL]
m n : ℕ
⊢ ack m (n + 1) ≤ ack (m + 1) n
[PROOFSTEP]
cases' n with n n
[GOAL]
case zero
m : ℕ
⊢ ack m (zero + 1) ≤ ack (m + 1) zero
[PROOFSTEP]
simp
[GOAL]
case succ
m n : ℕ
⊢ ack m (succ n + 1) ≤ ack (m + 1) (succ n)
[PROOFSTEP]
rw [ack_succ_succ, succ_eq_add_one]
[GOAL]
case succ
m n : ℕ
⊢ ack m (n + 1 + 1) ≤ ack m (ack (m + 1) n)
[PROOFSTEP]
apply ack_mono_right m (le_trans _ <| add_add_one_le_ack _ n)
[GOAL]
m n : ℕ
⊢ n + 1 + 1 ≤ m + 1 + n + 1
[PROOFSTEP]
linarith
[GOAL]
n : ℕ
⊢ n ^ 2 ≤ 2 ^ (n + 1) - 3
[PROOFSTEP]
induction' n with k hk
[GOAL]
case zero
⊢ zero ^ 2 ≤ 2 ^ (zero + 1) - 3
[PROOFSTEP]
norm_num
[GOAL]
case succ
k : ℕ
hk : k ^ 2 ≤ 2 ^ (k + 1) - 3
⊢ succ k ^ 2 ≤ 2 ^ (succ k + 1) - 3
[PROOFSTEP]
cases' k with k k
[GOAL]
case succ.zero
hk : zero ^ 2 ≤ 2 ^ (zero + 1) - 3
⊢ succ zero ^ 2 ≤ 2 ^ (succ zero + 1) - 3
[PROOFSTEP]
norm_num
[GOAL]
case succ.succ
k : ℕ
hk : succ k ^ 2 ≤ 2 ^ (succ k + 1) - 3
⊢ succ (succ k) ^ 2 ≤ 2 ^ (succ (succ k) + 1) - 3
[PROOFSTEP]
rw [succ_eq_add_one, add_sq, Nat.pow_succ 2, mul_comm _ 2, two_mul (2 ^ _), add_tsub_assoc_of_le, add_comm (2 ^ _),
  add_assoc]
[GOAL]
case succ.succ
k : ℕ
hk : succ k ^ 2 ≤ 2 ^ (succ k + 1) - 3
⊢ (k + 1) ^ 2 + (2 * (k + 1) * 1 + 1 ^ 2) ≤ 2 ^ (k + 2) - 3 + 2 ^ (k + 2)
[PROOFSTEP]
apply Nat.add_le_add hk
[GOAL]
case succ.succ
k : ℕ
hk : succ k ^ 2 ≤ 2 ^ (succ k + 1) - 3
⊢ 2 * (k + 1) * 1 + 1 ^ 2 ≤ 2 ^ (k + 2)
[PROOFSTEP]
norm_num
[GOAL]
case succ.succ
k : ℕ
hk : succ k ^ 2 ≤ 2 ^ (succ k + 1) - 3
⊢ 2 * (k + 1) + 1 ≤ 2 ^ (k + 2)
[PROOFSTEP]
apply succ_le_of_lt
[GOAL]
case succ.succ.h
k : ℕ
hk : succ k ^ 2 ≤ 2 ^ (succ k + 1) - 3
⊢ 2 * (k + 1) < 2 ^ (k + 2)
[PROOFSTEP]
rw [Nat.pow_succ, mul_comm _ 2, mul_lt_mul_left (zero_lt_two' ℕ)]
[GOAL]
case succ.succ.h
k : ℕ
hk : succ k ^ 2 ≤ 2 ^ (succ k + 1) - 3
⊢ k + 1 < 2 ^ (k + 1)
[PROOFSTEP]
apply lt_two_pow
[GOAL]
case succ.succ.h
k : ℕ
hk : succ k ^ 2 ≤ 2 ^ (succ k + 1) - 3
⊢ 3 ≤ 2 ^ (k + 2)
[PROOFSTEP]
rw [Nat.pow_succ, Nat.pow_succ]
[GOAL]
case succ.succ.h
k : ℕ
hk : succ k ^ 2 ≤ 2 ^ (succ k + 1) - 3
⊢ 3 ≤ 2 ^ k * 2 * 2
[PROOFSTEP]
linarith [one_le_pow k 2 zero_lt_two]
[GOAL]
n : ℕ
⊢ (ack 0 n + 1) ^ 2 ≤ ack (0 + 3) n
[PROOFSTEP]
simpa using sq_le_two_pow_add_one_minus_three (n + 2)
[GOAL]
m : ℕ
⊢ (ack (m + 1) 0 + 1) ^ 2 ≤ ack (m + 1 + 3) 0
[PROOFSTEP]
rw [ack_succ_zero, ack_succ_zero]
[GOAL]
m : ℕ
⊢ (ack m 1 + 1) ^ 2 ≤ ack (m + 3) 1
[PROOFSTEP]
apply ack_add_one_sq_lt_ack_add_three
[GOAL]
m n : ℕ
⊢ (ack (m + 1) (n + 1) + 1) ^ 2 ≤ ack (m + 1 + 3) (n + 1)
[PROOFSTEP]
rw [ack_succ_succ, ack_succ_succ]
[GOAL]
m n : ℕ
⊢ (ack m (ack (m + 1) n) + 1) ^ 2 ≤ ack (m + 3) (ack (m + 3 + 1) n)
[PROOFSTEP]
apply (ack_add_one_sq_lt_ack_add_three _ _).trans (ack_mono_right _ <| ack_mono_left _ _)
[GOAL]
m n : ℕ
⊢ m + 1 ≤ m + 3 + 1
[PROOFSTEP]
linarith
[GOAL]
m n : ℕ
⊢ m ≤ m + 2
[PROOFSTEP]
linarith
[GOAL]
f : ℕ → ℕ
hf : Nat.Primrec f
⊢ ∃ m, ∀ (n : ℕ), f n < ack m n
[PROOFSTEP]
induction' hf with f g hf hg IHf IHg f g hf hg IHf IHg f g hf hg IHf IHg
[GOAL]
case zero
f : ℕ → ℕ
⊢ ∃ m, ∀ (n : ℕ), (fun x => 0) n < ack m n
[PROOFSTEP]
exact
  ⟨0, ack_pos 0⟩
    -- Successor function:
[GOAL]
case succ
f : ℕ → ℕ
⊢ ∃ m, ∀ (n : ℕ), succ n < ack m n
[PROOFSTEP]
refine' ⟨1, fun n => _⟩
[GOAL]
case succ
f : ℕ → ℕ
n : ℕ
⊢ succ n < ack 1 n
[PROOFSTEP]
rw [succ_eq_one_add]
[GOAL]
case succ
f : ℕ → ℕ
n : ℕ
⊢ 1 + n < ack 1 n
[PROOFSTEP]
apply add_lt_ack
[GOAL]
case left
f : ℕ → ℕ
⊢ ∃ m, ∀ (n : ℕ), (fun n => (unpair n).fst) n < ack m n
[PROOFSTEP]
refine' ⟨0, fun n => _⟩
[GOAL]
case left
f : ℕ → ℕ
n : ℕ
⊢ (fun n => (unpair n).fst) n < ack 0 n
[PROOFSTEP]
rw [ack_zero, lt_succ_iff]
[GOAL]
case left
f : ℕ → ℕ
n : ℕ
⊢ (fun n => (unpair n).fst) n ≤ n
[PROOFSTEP]
exact unpair_left_le n
[GOAL]
case right
f : ℕ → ℕ
⊢ ∃ m, ∀ (n : ℕ), (fun n => (unpair n).snd) n < ack m n
[PROOFSTEP]
refine' ⟨0, fun n => _⟩
[GOAL]
case right
f : ℕ → ℕ
n : ℕ
⊢ (fun n => (unpair n).snd) n < ack 0 n
[PROOFSTEP]
rw [ack_zero, lt_succ_iff]
[GOAL]
case right
f : ℕ → ℕ
n : ℕ
⊢ (fun n => (unpair n).snd) n ≤ n
[PROOFSTEP]
exact unpair_right_le n
[GOAL]
case pair
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
IHf : ∃ m, ∀ (n : ℕ), f n < ack m n
IHg : ∃ m, ∀ (n : ℕ), g n < ack m n
⊢ ∃ m, ∀ (n : ℕ), (fun n => pair (f n) (g n)) n < ack m n
case comp
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
IHf : ∃ m, ∀ (n : ℕ), f n < ack m n
IHg : ∃ m, ∀ (n : ℕ), g n < ack m n
⊢ ∃ m, ∀ (n : ℕ), (fun n => f (g n)) n < ack m n
case prec
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
IHf : ∃ m, ∀ (n : ℕ), f n < ack m n
IHg : ∃ m, ∀ (n : ℕ), g n < ack m n
⊢ ∃ m, ∀ (n : ℕ), unpaired (fun z n => rec (f z) (fun y IH => g (pair z (pair y IH))) n) n < ack m n
[PROOFSTEP]
all_goals cases' IHf with a ha; cases' IHg with b hb
[GOAL]
case pair
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
IHf : ∃ m, ∀ (n : ℕ), f n < ack m n
IHg : ∃ m, ∀ (n : ℕ), g n < ack m n
⊢ ∃ m, ∀ (n : ℕ), (fun n => pair (f n) (g n)) n < ack m n
[PROOFSTEP]
cases' IHf with a ha
[GOAL]
case pair.intro
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
IHg : ∃ m, ∀ (n : ℕ), g n < ack m n
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
⊢ ∃ m, ∀ (n : ℕ), (fun n => pair (f n) (g n)) n < ack m n
[PROOFSTEP]
cases' IHg with b hb
[GOAL]
case comp
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
IHf : ∃ m, ∀ (n : ℕ), f n < ack m n
IHg : ∃ m, ∀ (n : ℕ), g n < ack m n
⊢ ∃ m, ∀ (n : ℕ), (fun n => f (g n)) n < ack m n
[PROOFSTEP]
cases' IHf with a ha
[GOAL]
case comp.intro
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
IHg : ∃ m, ∀ (n : ℕ), g n < ack m n
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
⊢ ∃ m, ∀ (n : ℕ), (fun n => f (g n)) n < ack m n
[PROOFSTEP]
cases' IHg with b hb
[GOAL]
case prec
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
IHf : ∃ m, ∀ (n : ℕ), f n < ack m n
IHg : ∃ m, ∀ (n : ℕ), g n < ack m n
⊢ ∃ m, ∀ (n : ℕ), unpaired (fun z n => rec (f z) (fun y IH => g (pair z (pair y IH))) n) n < ack m n
[PROOFSTEP]
cases' IHf with a ha
[GOAL]
case prec.intro
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
IHg : ∃ m, ∀ (n : ℕ), g n < ack m n
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
⊢ ∃ m, ∀ (n : ℕ), unpaired (fun z n => rec (f z) (fun y IH => g (pair z (pair y IH))) n) n < ack m n
[PROOFSTEP]
cases' IHg with b hb
[GOAL]
case pair.intro.intro
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
⊢ ∃ m, ∀ (n : ℕ), (fun n => pair (f n) (g n)) n < ack m n
[PROOFSTEP]
refine'
  ⟨max a b + 3, fun n =>
    (pair_lt_max_add_one_sq _ _).trans_le <|
      (pow_le_pow_of_le_left (add_le_add_right _ _) 2).trans <| ack_add_one_sq_lt_ack_add_three _ _⟩
[GOAL]
case pair.intro.intro
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
n : ℕ
⊢ max (f n) (g n) ≤ ack (max a b) n
[PROOFSTEP]
rw [max_ack_left]
[GOAL]
case pair.intro.intro
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
n : ℕ
⊢ max (f n) (g n) ≤ max (ack a n) (ack b n)
[PROOFSTEP]
exact max_le_max (ha n).le (hb n).le
[GOAL]
case comp.intro.intro
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
⊢ ∃ m, ∀ (n : ℕ), (fun n => f (g n)) n < ack m n
[PROOFSTEP]
exact
  ⟨max a b + 2, fun n => (ha _).trans <| (ack_strictMono_right a <| hb n).trans <| ack_ack_lt_ack_max_add_two a b n⟩
    -- Primitive recursion operator:
[GOAL]
case prec.intro.intro
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
⊢ ∃ m, ∀ (n : ℕ), unpaired (fun z n => rec (f z) (fun y IH => g (pair z (pair y IH))) n) n < ack m n
[PROOFSTEP]
have : ∀ {m n}, rec (f m) (fun y IH => g <| pair m <| pair y IH) n < ack (max a b + 9) (m + n) :=
  by
  intro m n
  induction' n with n IH
  · apply (ha m).trans (ack_strictMono_left m <| (le_max_left a b).trans_lt _)
    linarith
  ·
    -- We get rid of the first `pair`.
    simp only [ge_iff_le]
    apply
      (hb _).trans
        ((ack_pair_lt _ _ _).trans_le _)
          -- If m is the maximum, we get a very weak inequality.
    cases' lt_or_le _ m with h₁ h₁
    · rw [max_eq_left h₁.le]
      exact ack_le_ack (Nat.add_le_add (le_max_right a b) <| by norm_num) (self_le_add_right m _)
    rw [max_eq_right h₁]
      -- We get rid of the second `pair`.
    apply (ack_pair_lt _ _ _).le.trans
    cases' lt_or_le _ n with h₂ h₂
    · rw [max_eq_left h₂.le, add_assoc]
      exact ack_le_ack (Nat.add_le_add (le_max_right a b) <| by norm_num) ((le_succ n).trans <| self_le_add_left _ _)
    rw [max_eq_right h₂]
      -- We now use the inductive hypothesis, and some simple algebraic manipulation.
    apply (ack_strictMono_right _ IH).le.trans
    rw [add_succ m, add_succ _ 8, succ_eq_add_one, succ_eq_add_one, ack_succ_succ (_ + 8), add_assoc]
    exact
      ack_mono_left _
        (Nat.add_le_add (le_max_right a b) le_rfl)
          -- The proof is now simple.
[GOAL]
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
⊢ ∀ {m n : ℕ}, rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
[PROOFSTEP]
intro m n
[GOAL]
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
⊢ rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
[PROOFSTEP]
induction' n with n IH
[GOAL]
case zero
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m : ℕ
⊢ rec (f m) (fun y IH => g (pair m (pair y IH))) zero < ack (max a b + 9) (m + zero)
[PROOFSTEP]
apply (ha m).trans (ack_strictMono_left m <| (le_max_left a b).trans_lt _)
[GOAL]
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m : ℕ
⊢ max a b < max a b + 9
[PROOFSTEP]
linarith
[GOAL]
case succ
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
⊢ rec (f m) (fun y IH => g (pair m (pair y IH))) (succ n) < ack (max a b + 9) (m + succ n)
[PROOFSTEP]
simp only [ge_iff_le]
[GOAL]
case succ
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
⊢ g (pair m (pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n))) < ack (max a b + 9) (m + succ n)
[PROOFSTEP]
apply
  (hb _).trans
    ((ack_pair_lt _ _ _).trans_le _)
      -- If m is the maximum, we get a very weak inequality.
[GOAL]
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
⊢ ack (b + 4) (max m (pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n))) ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
cases' lt_or_le _ m with h₁ h₁
[GOAL]
case inl
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : ?m.127608 < m
⊢ ack (b + 4) (max m (pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n))) ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
rw [max_eq_left h₁.le]
[GOAL]
case inl
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n) < m
⊢ ack (b + 4) m ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
exact ack_le_ack (Nat.add_le_add (le_max_right a b) <| by norm_num) (self_le_add_right m _)
[GOAL]
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n) < m
⊢ 4 ≤ 9
[PROOFSTEP]
norm_num
[GOAL]
case inr
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
⊢ ack (b + 4) (max m (pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n))) ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
rw [max_eq_right h₁]
  -- We get rid of the second `pair`.
[GOAL]
case inr
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
⊢ ack (b + 4) (pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)) ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
apply (ack_pair_lt _ _ _).le.trans
[GOAL]
case inr
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
⊢ ack (b + 4 + 4) (max n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)) ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
cases' lt_or_le _ n with h₂ h₂
[GOAL]
case inr.inl
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
h₂ : ?m.127977 < n
⊢ ack (b + 4 + 4) (max n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)) ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
rw [max_eq_left h₂.le, add_assoc]
[GOAL]
case inr.inl
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
h₂ : rec (f m) (fun y IH => g (pair m (pair y IH))) n < n
⊢ ack (b + (4 + 4)) n ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
exact ack_le_ack (Nat.add_le_add (le_max_right a b) <| by norm_num) ((le_succ n).trans <| self_le_add_left _ _)
[GOAL]
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
h₂ : rec (f m) (fun y IH => g (pair m (pair y IH))) n < n
⊢ 4 + 4 ≤ 9
[PROOFSTEP]
norm_num
[GOAL]
case inr.inr
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
h₂ : n ≤ rec (f m) (fun y IH => g (pair m (pair y IH))) n
⊢ ack (b + 4 + 4) (max n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)) ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
rw [max_eq_right h₂]
  -- We now use the inductive hypothesis, and some simple algebraic manipulation.
[GOAL]
case inr.inr
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
h₂ : n ≤ rec (f m) (fun y IH => g (pair m (pair y IH))) n
⊢ ack (b + 4 + 4) (rec (f m) (fun y IH => g (pair m (pair y IH))) n) ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
apply (ack_strictMono_right _ IH).le.trans
[GOAL]
case inr.inr
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
h₂ : n ≤ rec (f m) (fun y IH => g (pair m (pair y IH))) n
⊢ ack (b + 4 + 4) (ack (max a b + 9) (m + n)) ≤ ack (max a b + 9) (m + succ n)
[PROOFSTEP]
rw [add_succ m, add_succ _ 8, succ_eq_add_one, succ_eq_add_one, ack_succ_succ (_ + 8), add_assoc]
[GOAL]
case inr.inr
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
m n : ℕ
IH : rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
h₁ : m ≤ pair n (rec (f m) (fun y IH => g (pair m (pair y IH))) n)
h₂ : n ≤ rec (f m) (fun y IH => g (pair m (pair y IH))) n
⊢ ack (b + (4 + 4)) (ack (max a b + 8 + 1) (m + n)) ≤ ack (max a b + 8) (ack (max a b + 8 + 1) (m + n))
[PROOFSTEP]
exact
  ack_mono_left _
    (Nat.add_le_add (le_max_right a b) le_rfl)
      -- The proof is now simple.
[GOAL]
case prec.intro.intro
f✝ f g : ℕ → ℕ
hf : Nat.Primrec f
hg : Nat.Primrec g
a : ℕ
ha : ∀ (n : ℕ), f n < ack a n
b : ℕ
hb : ∀ (n : ℕ), g n < ack b n
this : ∀ {m n : ℕ}, rec (f m) (fun y IH => g (pair m (pair y IH))) n < ack (max a b + 9) (m + n)
⊢ ∃ m, ∀ (n : ℕ), unpaired (fun z n => rec (f z) (fun y IH => g (pair z (pair y IH))) n) n < ack m n
[PROOFSTEP]
exact ⟨max a b + 9, fun n => this.trans_le <| ack_mono_right _ <| unpair_add_le n⟩
[GOAL]
h : Nat.Primrec fun n => ack n n
⊢ False
[PROOFSTEP]
cases' exists_lt_ack_of_nat_primrec h with m hm
[GOAL]
case intro
h : Nat.Primrec fun n => ack n n
m : ℕ
hm : ∀ (n : ℕ), ack n n < ack m n
⊢ False
[PROOFSTEP]
exact (hm m).false
[GOAL]
⊢ ¬Primrec fun n => ack n n
[PROOFSTEP]
rw [Primrec.nat_iff]
[GOAL]
⊢ ¬Nat.Primrec fun n => ack n n
[PROOFSTEP]
exact not_nat_primrec_ack_self
