Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

9b2660e1

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

75be6b61

bump to nightly-2024-04-06-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

e34029c9

Diff

@@ -112,7 +112,7 @@ private theorem ack_three_aux (n : ℕ) : (ack 3 n : ℤ) = 2 ^ (n + 3) - 3 :=
   by
   induction' n with n IH
   · simp; norm_num
-  · simp [IH, pow_succ]
+  · simp [IH, pow_succ']
     rw [mul_sub, sub_add]
     norm_num
 
@@ -325,14 +325,14 @@ private theorem sq_le_two_pow_add_one_minus_three (n : ℕ) : n ^ 2 ≤ 2 ^ (n +
   · norm_num
   · cases k
     · norm_num
-    · rw [succ_eq_add_one, add_sq, pow_succ 2, two_mul (2 ^ _), add_tsub_assoc_of_le,
+    · rw [succ_eq_add_one, add_sq, pow_succ' 2, two_mul (2 ^ _), add_tsub_assoc_of_le,
         add_comm (2 ^ _), add_assoc]
       · apply add_le_add hk
         norm_num
         apply succ_le_of_lt
-        rw [pow_succ, mul_lt_mul_left (zero_lt_two' ℕ)]
+        rw [pow_succ', mul_lt_mul_left (zero_lt_two' ℕ)]
         apply lt_two_pow
-      · rw [pow_succ, pow_succ]
+      · rw [pow_succ', pow_succ']
         linarith [one_le_pow k 2 zero_lt_two]
 
 #print ack_add_one_sq_lt_ack_add_three /-

75be6b61

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -164,7 +164,7 @@ theorem ack_strictMono_right : ∀ m, StrictMono (ack m)
   | m + 1, n₁ + 1, n₂ + 1, h => by
     rw [ack_succ_succ, ack_succ_succ]
     apply ack_strictMono_right _ (ack_strictMono_right _ _)
-    rwa [add_lt_add_iff_right] at h 
+    rwa [add_lt_add_iff_right] at h
 #align ack_strict_mono_right ack_strictMono_right
 -/

75be6b61

bump to nightly-2023-12-20-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

058cd493

Diff

@@ -124,7 +124,7 @@ theorem ack_three (n : ℕ) : ack 3 n = 2 ^ (n + 3) - 3 :=
   rw [cast_sub]
   · exact_mod_cast ack_three_aux n
   · have H : 3 ≤ 2 ^ 3 := by norm_num
-    exact H.trans (pow_mono one_le_two <| le_add_left le_rfl)
+    exact H.trans (pow_right_mono one_le_two <| le_add_left le_rfl)
 #align ack_three ack_three
 -/
 
@@ -361,7 +361,7 @@ theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m
 theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (m + 4) n :=
   calc
     ack m ((n + 1) ^ 2) < ack m ((ack m n + 1) ^ 2) :=
-      ack_strictMono_right m <| pow_lt_pow_of_lt_left (succ_lt_succ <| lt_ack_right m n) zero_lt_two
+      ack_strictMono_right m <| pow_lt_pow_left (succ_lt_succ <| lt_ack_right m n) zero_lt_two
     _ ≤ ack m (ack (m + 3) n) := (ack_mono_right m <| ack_add_one_sq_lt_ack_add_three m n)
     _ ≤ ack (m + 2) (ack (m + 3) n) := (ack_mono_left _ <| by linarith)
     _ = ack (m + 3) (n + 1) := (ack_succ_succ _ n).symm
@@ -399,7 +399,7 @@ theorem exists_lt_ack_of_nat_primrec {f : ℕ → ℕ} (hf : Nat.Primrec f) : 
   · refine'
       ⟨max a b + 3, fun n =>
         (mkpair_lt_max_add_one_sq _ _).trans_le <|
-          (Nat.pow_le_pow_of_le_left (add_le_add_right _ _) 2).trans <|
+          (Nat.pow_le_pow_left (add_le_add_right _ _) 2).trans <|
             ack_add_one_sq_lt_ack_add_three _ _⟩
     rw [max_ack_left]
     exact max_le_max (ha n).le (hb n).le

75be6b61

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2022 Violeta Hernández Palacios. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Violeta Hernández Palacios
 -/
-import Mathbin.Computability.Primrec
+import Computability.Primrec
 import Mathbin.Tactic.Linarith.Default
 
 #align_import computability.ackermann from "leanprover-community/mathlib"@"75be6b616681ab6ca66d798ead117e75cd64f125"

75be6b61

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2022 Violeta Hernández Palacios. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Violeta Hernández Palacios
-
-! This file was ported from Lean 3 source module computability.ackermann
-! leanprover-community/mathlib commit 75be6b616681ab6ca66d798ead117e75cd64f125
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Computability.Primrec
 import Mathbin.Tactic.Linarith.Default
 
+#align_import computability.ackermann from "leanprover-community/mathlib"@"75be6b616681ab6ca66d798ead117e75cd64f125"
+
 /-!
 # Ackermann function

75be6b61

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -204,9 +204,11 @@ theorem ack_inj_right {m n₁ n₂ : ℕ} : ack m n₁ = ack m n₂ ↔ n₁ = n
 #align ack_inj_right ack_inj_right
 -/
 
+#print max_ack_right /-
 theorem max_ack_right (m n₁ n₂ : ℕ) : ack m (max n₁ n₂) = max (ack m n₁) (ack m n₂) :=
   (ack_mono_right m).map_max
 #align max_ack_right max_ack_right
+-/
 
 #print add_lt_ack /-
 theorem add_lt_ack : ∀ m n, m + n < ack m n
@@ -296,9 +298,11 @@ theorem ack_inj_left {m₁ m₂ n : ℕ} : ack m₁ n = ack m₂ n ↔ m₁ = m
 #align ack_inj_left ack_inj_left
 -/
 
+#print max_ack_left /-
 theorem max_ack_left (m₁ m₂ n : ℕ) : ack (max m₁ m₂) n = max (ack m₁ n) (ack m₂ n) :=
   (ack_mono_left n).map_max
 #align max_ack_left max_ack_left
+-/
 
 #print ack_le_ack /-
 theorem ack_le_ack {m₁ m₂ n₁ n₂ : ℕ} (hm : m₁ ≤ m₂) (hn : n₁ ≤ n₂) : ack m₁ n₁ ≤ ack m₂ n₂ :=
@@ -345,6 +349,7 @@ theorem ack_add_one_sq_lt_ack_add_three : ∀ m n, (ack m n + 1) ^ 2 ≤ ack (m
 #align ack_add_one_sq_lt_ack_add_three ack_add_one_sq_lt_ack_add_three
 -/
 
+#print ack_ack_lt_ack_max_add_two /-
 theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m n + 2) k :=
   calc
     ack m (ack n k) ≤ ack (max m n) (ack n k) := ack_mono_left _ (le_max_left _ _)
@@ -353,6 +358,7 @@ theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m
     _ = ack (max m n + 1) (k + 1) := (ack_succ_succ _ _).symm
     _ ≤ ack (max m n + 2) k := ack_succ_right_le_ack_succ_left _ _
 #align ack_ack_lt_ack_max_add_two ack_ack_lt_ack_max_add_two
+-/
 
 #print ack_add_one_sq_lt_ack_add_four /-
 theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (m + 4) n :=
@@ -366,9 +372,11 @@ theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (
 #align ack_add_one_sq_lt_ack_add_four ack_add_one_sq_lt_ack_add_four
 -/
 
+#print ack_pair_lt /-
 theorem ack_pair_lt (m n k : ℕ) : ack m (pair n k) < ack (m + 4) (max n k) :=
   (ack_strictMono_right m <| pair_lt_max_add_one_sq n k).trans <| ack_add_one_sq_lt_ack_add_four _ _
 #align ack_mkpair_lt ack_pair_lt
+-/
 
 #print exists_lt_ack_of_nat_primrec /-
 /-- If `f` is primitive recursive, there exists `m` such that `f n < ack m n` for all `n`. -/

75be6b61

bump to nightly-2023-06-09-07

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

16afdc39

Diff

@@ -219,7 +219,6 @@ theorem add_lt_ack : ∀ m n, m + n < ack m n
       _ ≤ ack m (ack (m + 1) n) :=
         (ack_mono_right m <| le_of_eq_of_le (by ring_nf) <| succ_le_of_lt <| add_lt_ack (m + 1) n)
       _ = ack (m + 1) (n + 1) := (ack_succ_succ m n).symm
-      
 #align add_lt_ack add_lt_ack
 -/
 
@@ -353,7 +352,6 @@ theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m
       (ack_strictMono_right _ <| ack_strictMono_left k <| lt_succ_of_le <| le_max_right m n)
     _ = ack (max m n + 1) (k + 1) := (ack_succ_succ _ _).symm
     _ ≤ ack (max m n + 2) k := ack_succ_right_le_ack_succ_left _ _
-    
 #align ack_ack_lt_ack_max_add_two ack_ack_lt_ack_max_add_two
 
 #print ack_add_one_sq_lt_ack_add_four /-
@@ -365,7 +363,6 @@ theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (
     _ ≤ ack (m + 2) (ack (m + 3) n) := (ack_mono_left _ <| by linarith)
     _ = ack (m + 3) (n + 1) := (ack_succ_succ _ n).symm
     _ ≤ ack (m + 4) n := ack_succ_right_le_ack_succ_left _ n
-    
 #align ack_add_one_sq_lt_ack_add_four ack_add_one_sq_lt_ack_add_four
 -/

75be6b61

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -167,7 +167,7 @@ theorem ack_strictMono_right : ∀ m, StrictMono (ack m)
   | m + 1, n₁ + 1, n₂ + 1, h => by
     rw [ack_succ_succ, ack_succ_succ]
     apply ack_strictMono_right _ (ack_strictMono_right _ _)
-    rwa [add_lt_add_iff_right] at h
+    rwa [add_lt_add_iff_right] at h 
 #align ack_strict_mono_right ack_strictMono_right
 -/

75be6b61

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -204,12 +204,6 @@ theorem ack_inj_right {m n₁ n₂ : ℕ} : ack m n₁ = ack m n₂ ↔ n₁ = n
 #align ack_inj_right ack_inj_right
 -/
 
-/- warning: max_ack_right -> max_ack_right is a dubious translation:
-lean 3 declaration is
-  forall (m : Nat) (n₁ : Nat) (n₂ : Nat), Eq.{1} Nat (ack m (LinearOrder.max.{0} Nat Nat.linearOrder n₁ n₂)) (LinearOrder.max.{0} Nat Nat.linearOrder (ack m n₁) (ack m n₂))
-but is expected to have type
-  forall (m : Nat) (n₁ : Nat) (n₂ : Nat), Eq.{1} Nat (ack m (Max.max.{0} Nat Nat.instMaxNat n₁ n₂)) (Max.max.{0} Nat Nat.instMaxNat (ack m n₁) (ack m n₂))
-Case conversion may be inaccurate. Consider using '#align max_ack_right max_ack_rightₓ'. -/
 theorem max_ack_right (m n₁ n₂ : ℕ) : ack m (max n₁ n₂) = max (ack m n₁) (ack m n₂) :=
   (ack_mono_right m).map_max
 #align max_ack_right max_ack_right
@@ -303,12 +297,6 @@ theorem ack_inj_left {m₁ m₂ n : ℕ} : ack m₁ n = ack m₂ n ↔ m₁ = m
 #align ack_inj_left ack_inj_left
 -/
 
-/- warning: max_ack_left -> max_ack_left is a dubious translation:
-lean 3 declaration is
-  forall (m₁ : Nat) (m₂ : Nat) (n : Nat), Eq.{1} Nat (ack (LinearOrder.max.{0} Nat Nat.linearOrder m₁ m₂) n) (LinearOrder.max.{0} Nat Nat.linearOrder (ack m₁ n) (ack m₂ n))
-but is expected to have type
-  forall (m₁ : Nat) (m₂ : Nat) (n : Nat), Eq.{1} Nat (ack (Max.max.{0} Nat Nat.instMaxNat m₁ m₂) n) (Max.max.{0} Nat Nat.instMaxNat (ack m₁ n) (ack m₂ n))
-Case conversion may be inaccurate. Consider using '#align max_ack_left max_ack_leftₓ'. -/
 theorem max_ack_left (m₁ m₂ n : ℕ) : ack (max m₁ m₂) n = max (ack m₁ n) (ack m₂ n) :=
   (ack_mono_left n).map_max
 #align max_ack_left max_ack_left
@@ -358,12 +346,6 @@ theorem ack_add_one_sq_lt_ack_add_three : ∀ m n, (ack m n + 1) ^ 2 ≤ ack (m
 #align ack_add_one_sq_lt_ack_add_three ack_add_one_sq_lt_ack_add_three
 -/
 
-/- warning: ack_ack_lt_ack_max_add_two -> ack_ack_lt_ack_max_add_two is a dubious translation:
-lean 3 declaration is
-  forall (m : Nat) (n : Nat) (k : Nat), LT.lt.{0} Nat Nat.hasLt (ack m (ack n k)) (ack (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (LinearOrder.max.{0} Nat Nat.linearOrder m n) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))) k)
-but is expected to have type
-  forall (m : Nat) (n : Nat) (k : Nat), LT.lt.{0} Nat instLTNat (ack m (ack n k)) (ack (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (Max.max.{0} Nat Nat.instMaxNat m n) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))) k)
-Case conversion may be inaccurate. Consider using '#align ack_ack_lt_ack_max_add_two ack_ack_lt_ack_max_add_twoₓ'. -/
 theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m n + 2) k :=
   calc
     ack m (ack n k) ≤ ack (max m n) (ack n k) := ack_mono_left _ (le_max_left _ _)
@@ -387,12 +369,6 @@ theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (
 #align ack_add_one_sq_lt_ack_add_four ack_add_one_sq_lt_ack_add_four
 -/
 
-/- warning: ack_mkpair_lt -> ack_pair_lt is a dubious translation:
-lean 3 declaration is
-  forall (m : Nat) (n : Nat) (k : Nat), LT.lt.{0} Nat Nat.hasLt (ack m (Nat.pair n k)) (ack (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 4 (OfNat.mk.{0} Nat 4 (bit0.{0} Nat Nat.hasAdd (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) (LinearOrder.max.{0} Nat Nat.linearOrder n k))
-but is expected to have type
-  forall (m : Nat) (n : Nat) (k : Nat), LT.lt.{0} Nat instLTNat (ack m (Nat.pair n k)) (ack (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 4 (instOfNatNat 4))) (Max.max.{0} Nat Nat.instMaxNat n k))
-Case conversion may be inaccurate. Consider using '#align ack_mkpair_lt ack_pair_ltₓ'. -/
 theorem ack_pair_lt (m n k : ℕ) : ack m (pair n k) < ack (m + 4) (max n k) :=
   (ack_strictMono_right m <| pair_lt_max_add_one_sq n k).trans <| ack_add_one_sq_lt_ack_add_four _ _
 #align ack_mkpair_lt ack_pair_lt

75be6b61

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -114,8 +114,7 @@ theorem ack_two (n : ℕ) : ack 2 n = 2 * n + 3 :=
 private theorem ack_three_aux (n : ℕ) : (ack 3 n : ℤ) = 2 ^ (n + 3) - 3 :=
   by
   induction' n with n IH
-  · simp
-    norm_num
+  · simp; norm_num
   · simp [IH, pow_succ]
     rw [mul_sub, sub_add]
     norm_num
@@ -135,24 +134,16 @@ theorem ack_three (n : ℕ) : ack 3 n = 2 ^ (n + 3) - 3 :=
 #print ack_pos /-
 theorem ack_pos : ∀ m n, 0 < ack m n
   | 0, n => by simp
-  | m + 1, 0 => by
-    rw [ack_succ_zero]
-    apply ack_pos
-  | m + 1, n + 1 => by
-    rw [ack_succ_succ]
-    apply ack_pos
+  | m + 1, 0 => by rw [ack_succ_zero]; apply ack_pos
+  | m + 1, n + 1 => by rw [ack_succ_succ]; apply ack_pos
 #align ack_pos ack_pos
 -/
 
 #print one_lt_ack_succ_left /-
 theorem one_lt_ack_succ_left : ∀ m n, 1 < ack (m + 1) n
   | 0, n => by simp
-  | m + 1, 0 => by
-    rw [ack_succ_zero]
-    apply one_lt_ack_succ_left
-  | m + 1, n + 1 => by
-    rw [ack_succ_succ]
-    apply one_lt_ack_succ_left
+  | m + 1, 0 => by rw [ack_succ_zero]; apply one_lt_ack_succ_left
+  | m + 1, n + 1 => by rw [ack_succ_succ]; apply one_lt_ack_succ_left
 #align one_lt_ack_succ_left one_lt_ack_succ_left
 -/
 
@@ -359,9 +350,7 @@ private theorem sq_le_two_pow_add_one_minus_three (n : ℕ) : n ^ 2 ≤ 2 ^ (n +
 #print ack_add_one_sq_lt_ack_add_three /-
 theorem ack_add_one_sq_lt_ack_add_three : ∀ m n, (ack m n + 1) ^ 2 ≤ ack (m + 3) n
   | 0, n => by simpa using sq_le_two_pow_add_one_minus_three (n + 2)
-  | m + 1, 0 => by
-    rw [ack_succ_zero, ack_succ_zero]
-    apply ack_add_one_sq_lt_ack_add_three
+  | m + 1, 0 => by rw [ack_succ_zero, ack_succ_zero]; apply ack_add_one_sq_lt_ack_add_three
   | m + 1, n + 1 => by
     rw [ack_succ_succ, ack_succ_succ]
     apply (ack_add_one_sq_lt_ack_add_three _ _).trans (ack_mono_right _ <| ack_mono_left _ _)
@@ -480,17 +469,13 @@ theorem exists_lt_ack_of_nat_primrec {f : ℕ → ℕ} (hf : Nat.Primrec f) : 
 -/
 
 #print not_nat_primrec_ack_self /-
-theorem not_nat_primrec_ack_self : ¬Nat.Primrec fun n => ack n n := fun h =>
-  by
-  cases' exists_lt_ack_of_nat_primrec h with m hm
-  exact (hm m).False
+theorem not_nat_primrec_ack_self : ¬Nat.Primrec fun n => ack n n := fun h => by
+  cases' exists_lt_ack_of_nat_primrec h with m hm; exact (hm m).False
 #align not_nat_primrec_ack_self not_nat_primrec_ack_self
 -/
 
 #print not_primrec_ack_self /-
-theorem not_primrec_ack_self : ¬Primrec fun n => ack n n :=
-  by
-  rw [Primrec.nat_iff]
+theorem not_primrec_ack_self : ¬Primrec fun n => ack n n := by rw [Primrec.nat_iff];
   exact not_nat_primrec_ack_self
 #align not_primrec_ack_self not_primrec_ack_self
 -/

75be6b61

bump to nightly-2023-05-28-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6c6011cf

Diff

@@ -119,7 +119,6 @@ private theorem ack_three_aux (n : ℕ) : (ack 3 n : ℤ) = 2 ^ (n + 3) - 3 :=
   · simp [IH, pow_succ]
     rw [mul_sub, sub_add]
     norm_num
-#align ack_three_aux ack_three_aux
 
 #print ack_three /-
 @[simp]
@@ -273,7 +272,6 @@ private theorem ack_strict_mono_left' : ∀ {m₁ m₂} (n), m₁ < m₂ → ack
     exact
       (ack_strict_mono_left' _ <| (add_lt_add_iff_right 1).1 h).trans
         (ack_strictMono_right _ <| ack_strict_mono_left' n h)
-#align ack_strict_mono_left' ack_strict_mono_left'
 
 #print ack_strictMono_left /-
 theorem ack_strictMono_left (n : ℕ) : StrictMono fun m => ack m n := fun m₁ m₂ =>
@@ -357,7 +355,6 @@ private theorem sq_le_two_pow_add_one_minus_three (n : ℕ) : n ^ 2 ≤ 2 ^ (n +
         apply lt_two_pow
       · rw [pow_succ, pow_succ]
         linarith [one_le_pow k 2 zero_lt_two]
-#align sq_le_two_pow_add_one_minus_three sq_le_two_pow_add_one_minus_three
 
 #print ack_add_one_sq_lt_ack_add_three /-
 theorem ack_add_one_sq_lt_ack_add_three : ∀ m n, (ack m n + 1) ^ 2 ≤ ack (m + 3) n

75be6b61

bump to nightly-2023-04-07-02

mathlib commit https://github.com/leanprover-community/mathlib/commit/5ec62c8106221a3f9160e4e4fcc3eed79fe213e9

3f979973

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Violeta Hernández Palacios
 
 ! This file was ported from Lean 3 source module computability.ackermann
-! leanprover-community/mathlib commit 9b2660e1b25419042c8da10bf411aa3c67f14383
+! leanprover-community/mathlib commit 75be6b616681ab6ca66d798ead117e75cd64f125
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -14,6 +14,9 @@ import Mathbin.Tactic.Linarith.Default
 /-!
 # Ackermann function
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 In this file, we define the two-argument Ackermann function `ack`. Despite having a recursive
 definition, we show that this isn't a primitive recursive function.

9b2660e1

bump to nightly-2023-04-05-10

mathlib commit https://github.com/leanprover-community/mathlib/commit/1a4df69ca1a9a0e5e26bfe12e2b92814216016d0

5fef5172

Diff

@@ -54,6 +54,7 @@ which bump up our constant to `9`.
 
 open Nat
 
+#print ack /-
 /-- The two-argument Ackermann function, defined so that
 
 - `ack 0 n = n + 1`
@@ -67,19 +68,27 @@ def ack : ℕ → ℕ → ℕ
   | m + 1, 0 => ack m 1
   | m + 1, n + 1 => ack m (ack (m + 1) n)
 #align ack ack
+-/
 
+#print ack_zero /-
 @[simp]
 theorem ack_zero (n : ℕ) : ack 0 n = n + 1 := by rw [ack]
 #align ack_zero ack_zero
+-/
 
+#print ack_succ_zero /-
 @[simp]
 theorem ack_succ_zero (m : ℕ) : ack (m + 1) 0 = ack m 1 := by rw [ack]
 #align ack_succ_zero ack_succ_zero
+-/
 
+#print ack_succ_succ /-
 @[simp]
 theorem ack_succ_succ (m n : ℕ) : ack (m + 1) (n + 1) = ack m (ack (m + 1) n) := by rw [ack]
 #align ack_succ_succ ack_succ_succ
+-/
 
+#print ack_one /-
 @[simp]
 theorem ack_one (n : ℕ) : ack 1 n = n + 2 :=
   by
@@ -87,7 +96,9 @@ theorem ack_one (n : ℕ) : ack 1 n = n + 2 :=
   · simp
   · simp [IH]
 #align ack_one ack_one
+-/
 
+#print ack_two /-
 @[simp]
 theorem ack_two (n : ℕ) : ack 2 n = 2 * n + 3 :=
   by
@@ -95,6 +106,7 @@ theorem ack_two (n : ℕ) : ack 2 n = 2 * n + 3 :=
   · simp
   · simp [IH, mul_succ]
 #align ack_two ack_two
+-/
 
 private theorem ack_three_aux (n : ℕ) : (ack 3 n : ℤ) = 2 ^ (n + 3) - 3 :=
   by
@@ -106,6 +118,7 @@ private theorem ack_three_aux (n : ℕ) : (ack 3 n : ℤ) = 2 ^ (n + 3) - 3 :=
     norm_num
 #align ack_three_aux ack_three_aux
 
+#print ack_three /-
 @[simp]
 theorem ack_three (n : ℕ) : ack 3 n = 2 ^ (n + 3) - 3 :=
   by
@@ -115,7 +128,9 @@ theorem ack_three (n : ℕ) : ack 3 n = 2 ^ (n + 3) - 3 :=
   · have H : 3 ≤ 2 ^ 3 := by norm_num
     exact H.trans (pow_mono one_le_two <| le_add_left le_rfl)
 #align ack_three ack_three
+-/
 
+#print ack_pos /-
 theorem ack_pos : ∀ m n, 0 < ack m n
   | 0, n => by simp
   | m + 1, 0 => by
@@ -125,7 +140,9 @@ theorem ack_pos : ∀ m n, 0 < ack m n
     rw [ack_succ_succ]
     apply ack_pos
 #align ack_pos ack_pos
+-/
 
+#print one_lt_ack_succ_left /-
 theorem one_lt_ack_succ_left : ∀ m n, 1 < ack (m + 1) n
   | 0, n => by simp
   | m + 1, 0 => by
@@ -135,7 +152,9 @@ theorem one_lt_ack_succ_left : ∀ m n, 1 < ack (m + 1) n
     rw [ack_succ_succ]
     apply one_lt_ack_succ_left
 #align one_lt_ack_succ_left one_lt_ack_succ_left
+-/
 
+#print one_lt_ack_succ_right /-
 theorem one_lt_ack_succ_right : ∀ m n, 1 < ack m (n + 1)
   | 0, n => by simp
   | m + 1, n => by
@@ -144,7 +163,9 @@ theorem one_lt_ack_succ_right : ∀ m n, 1 < ack m (n + 1)
     rw [h]
     apply one_lt_ack_succ_right
 #align one_lt_ack_succ_right one_lt_ack_succ_right
+-/
 
+#print ack_strictMono_right /-
 theorem ack_strictMono_right : ∀ m, StrictMono (ack m)
   | 0, n₁, n₂, h => by simpa using h
   | m + 1, 0, n + 1, h => by
@@ -155,34 +176,52 @@ theorem ack_strictMono_right : ∀ m, StrictMono (ack m)
     apply ack_strictMono_right _ (ack_strictMono_right _ _)
     rwa [add_lt_add_iff_right] at h
 #align ack_strict_mono_right ack_strictMono_right
+-/
 
+#print ack_mono_right /-
 theorem ack_mono_right (m : ℕ) : Monotone (ack m) :=
   (ack_strictMono_right m).Monotone
 #align ack_mono_right ack_mono_right
+-/
 
+#print ack_injective_right /-
 theorem ack_injective_right (m : ℕ) : Function.Injective (ack m) :=
   (ack_strictMono_right m).Injective
 #align ack_injective_right ack_injective_right
+-/
 
+#print ack_lt_iff_right /-
 @[simp]
 theorem ack_lt_iff_right {m n₁ n₂ : ℕ} : ack m n₁ < ack m n₂ ↔ n₁ < n₂ :=
   (ack_strictMono_right m).lt_iff_lt
 #align ack_lt_iff_right ack_lt_iff_right
+-/
 
+#print ack_le_iff_right /-
 @[simp]
 theorem ack_le_iff_right {m n₁ n₂ : ℕ} : ack m n₁ ≤ ack m n₂ ↔ n₁ ≤ n₂ :=
   (ack_strictMono_right m).le_iff_le
 #align ack_le_iff_right ack_le_iff_right
+-/
 
+#print ack_inj_right /-
 @[simp]
 theorem ack_inj_right {m n₁ n₂ : ℕ} : ack m n₁ = ack m n₂ ↔ n₁ = n₂ :=
   (ack_injective_right m).eq_iff
 #align ack_inj_right ack_inj_right
+-/
 
+/- warning: max_ack_right -> max_ack_right is a dubious translation:
+lean 3 declaration is
+  forall (m : Nat) (n₁ : Nat) (n₂ : Nat), Eq.{1} Nat (ack m (LinearOrder.max.{0} Nat Nat.linearOrder n₁ n₂)) (LinearOrder.max.{0} Nat Nat.linearOrder (ack m n₁) (ack m n₂))
+but is expected to have type
+  forall (m : Nat) (n₁ : Nat) (n₂ : Nat), Eq.{1} Nat (ack m (Max.max.{0} Nat Nat.instMaxNat n₁ n₂)) (Max.max.{0} Nat Nat.instMaxNat (ack m n₁) (ack m n₂))
+Case conversion may be inaccurate. Consider using '#align max_ack_right max_ack_rightₓ'. -/
 theorem max_ack_right (m n₁ n₂ : ℕ) : ack m (max n₁ n₂) = max (ack m n₁) (ack m n₂) :=
   (ack_mono_right m).map_max
 #align max_ack_right max_ack_right
 
+#print add_lt_ack /-
 theorem add_lt_ack : ∀ m n, m + n < ack m n
   | 0, n => by simp
   | m + 1, 0 => by simpa using add_lt_ack m 1
@@ -195,18 +234,25 @@ theorem add_lt_ack : ∀ m n, m + n < ack m n
       _ = ack (m + 1) (n + 1) := (ack_succ_succ m n).symm
       
 #align add_lt_ack add_lt_ack
+-/
 
+#print add_add_one_le_ack /-
 theorem add_add_one_le_ack (m n : ℕ) : m + n + 1 ≤ ack m n :=
   succ_le_of_lt (add_lt_ack m n)
 #align add_add_one_le_ack add_add_one_le_ack
+-/
 
+#print lt_ack_left /-
 theorem lt_ack_left (m n : ℕ) : m < ack m n :=
   (self_le_add_right m n).trans_lt <| add_lt_ack m n
 #align lt_ack_left lt_ack_left
+-/
 
+#print lt_ack_right /-
 theorem lt_ack_right (m n : ℕ) : n < ack m n :=
   (self_le_add_left n m).trans_lt <| add_lt_ack m n
 #align lt_ack_right lt_ack_right
+-/
 
 -- we reorder the arguments to appease the equation compiler
 private theorem ack_strict_mono_left' : ∀ {m₁ m₂} (n), m₁ < m₂ → ack m₁ n < ack m₂ n
@@ -226,41 +272,62 @@ private theorem ack_strict_mono_left' : ∀ {m₁ m₂} (n), m₁ < m₂ → ack
         (ack_strictMono_right _ <| ack_strict_mono_left' n h)
 #align ack_strict_mono_left' ack_strict_mono_left'
 
+#print ack_strictMono_left /-
 theorem ack_strictMono_left (n : ℕ) : StrictMono fun m => ack m n := fun m₁ m₂ =>
   ack_strict_mono_left' n
 #align ack_strict_mono_left ack_strictMono_left
+-/
 
+#print ack_mono_left /-
 theorem ack_mono_left (n : ℕ) : Monotone fun m => ack m n :=
   (ack_strictMono_left n).Monotone
 #align ack_mono_left ack_mono_left
+-/
 
+#print ack_injective_left /-
 theorem ack_injective_left (n : ℕ) : Function.Injective fun m => ack m n :=
   (ack_strictMono_left n).Injective
 #align ack_injective_left ack_injective_left
+-/
 
+#print ack_lt_iff_left /-
 @[simp]
 theorem ack_lt_iff_left {m₁ m₂ n : ℕ} : ack m₁ n < ack m₂ n ↔ m₁ < m₂ :=
   (ack_strictMono_left n).lt_iff_lt
 #align ack_lt_iff_left ack_lt_iff_left
+-/
 
+#print ack_le_iff_left /-
 @[simp]
 theorem ack_le_iff_left {m₁ m₂ n : ℕ} : ack m₁ n ≤ ack m₂ n ↔ m₁ ≤ m₂ :=
   (ack_strictMono_left n).le_iff_le
 #align ack_le_iff_left ack_le_iff_left
+-/
 
+#print ack_inj_left /-
 @[simp]
 theorem ack_inj_left {m₁ m₂ n : ℕ} : ack m₁ n = ack m₂ n ↔ m₁ = m₂ :=
   (ack_injective_left n).eq_iff
 #align ack_inj_left ack_inj_left
+-/
 
+/- warning: max_ack_left -> max_ack_left is a dubious translation:
+lean 3 declaration is
+  forall (m₁ : Nat) (m₂ : Nat) (n : Nat), Eq.{1} Nat (ack (LinearOrder.max.{0} Nat Nat.linearOrder m₁ m₂) n) (LinearOrder.max.{0} Nat Nat.linearOrder (ack m₁ n) (ack m₂ n))
+but is expected to have type
+  forall (m₁ : Nat) (m₂ : Nat) (n : Nat), Eq.{1} Nat (ack (Max.max.{0} Nat Nat.instMaxNat m₁ m₂) n) (Max.max.{0} Nat Nat.instMaxNat (ack m₁ n) (ack m₂ n))
+Case conversion may be inaccurate. Consider using '#align max_ack_left max_ack_leftₓ'. -/
 theorem max_ack_left (m₁ m₂ n : ℕ) : ack (max m₁ m₂) n = max (ack m₁ n) (ack m₂ n) :=
   (ack_mono_left n).map_max
 #align max_ack_left max_ack_left
 
+#print ack_le_ack /-
 theorem ack_le_ack {m₁ m₂ n₁ n₂ : ℕ} (hm : m₁ ≤ m₂) (hn : n₁ ≤ n₂) : ack m₁ n₁ ≤ ack m₂ n₂ :=
   (ack_mono_left n₁ hm).trans <| ack_mono_right m₂ hn
 #align ack_le_ack ack_le_ack
+-/
 
+#print ack_succ_right_le_ack_succ_left /-
 theorem ack_succ_right_le_ack_succ_left (m n : ℕ) : ack m (n + 1) ≤ ack (m + 1) n :=
   by
   cases n
@@ -269,6 +336,7 @@ theorem ack_succ_right_le_ack_succ_left (m n : ℕ) : ack m (n + 1) ≤ ack (m +
     apply ack_mono_right m (le_trans _ <| add_add_one_le_ack _ n)
     linarith
 #align ack_succ_right_le_ack_succ_left ack_succ_right_le_ack_succ_left
+-/
 
 -- All the inequalities from this point onwards are specific to the main proof.
 private theorem sq_le_two_pow_add_one_minus_three (n : ℕ) : n ^ 2 ≤ 2 ^ (n + 1) - 3 :=
@@ -288,6 +356,7 @@ private theorem sq_le_two_pow_add_one_minus_three (n : ℕ) : n ^ 2 ≤ 2 ^ (n +
         linarith [one_le_pow k 2 zero_lt_two]
 #align sq_le_two_pow_add_one_minus_three sq_le_two_pow_add_one_minus_three
 
+#print ack_add_one_sq_lt_ack_add_three /-
 theorem ack_add_one_sq_lt_ack_add_three : ∀ m n, (ack m n + 1) ^ 2 ≤ ack (m + 3) n
   | 0, n => by simpa using sq_le_two_pow_add_one_minus_three (n + 2)
   | m + 1, 0 => by
@@ -298,7 +367,14 @@ theorem ack_add_one_sq_lt_ack_add_three : ∀ m n, (ack m n + 1) ^ 2 ≤ ack (m
     apply (ack_add_one_sq_lt_ack_add_three _ _).trans (ack_mono_right _ <| ack_mono_left _ _)
     linarith
 #align ack_add_one_sq_lt_ack_add_three ack_add_one_sq_lt_ack_add_three
+-/
 
+/- warning: ack_ack_lt_ack_max_add_two -> ack_ack_lt_ack_max_add_two is a dubious translation:
+lean 3 declaration is
+  forall (m : Nat) (n : Nat) (k : Nat), LT.lt.{0} Nat Nat.hasLt (ack m (ack n k)) (ack (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (LinearOrder.max.{0} Nat Nat.linearOrder m n) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))) k)
+but is expected to have type
+  forall (m : Nat) (n : Nat) (k : Nat), LT.lt.{0} Nat instLTNat (ack m (ack n k)) (ack (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (Max.max.{0} Nat Nat.instMaxNat m n) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))) k)
+Case conversion may be inaccurate. Consider using '#align ack_ack_lt_ack_max_add_two ack_ack_lt_ack_max_add_twoₓ'. -/
 theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m n + 2) k :=
   calc
     ack m (ack n k) ≤ ack (max m n) (ack n k) := ack_mono_left _ (le_max_left _ _)
@@ -309,6 +385,7 @@ theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m
     
 #align ack_ack_lt_ack_max_add_two ack_ack_lt_ack_max_add_two
 
+#print ack_add_one_sq_lt_ack_add_four /-
 theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (m + 4) n :=
   calc
     ack m ((n + 1) ^ 2) < ack m ((ack m n + 1) ^ 2) :=
@@ -319,11 +396,19 @@ theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (
     _ ≤ ack (m + 4) n := ack_succ_right_le_ack_succ_left _ n
     
 #align ack_add_one_sq_lt_ack_add_four ack_add_one_sq_lt_ack_add_four
+-/
 
+/- warning: ack_mkpair_lt -> ack_pair_lt is a dubious translation:
+lean 3 declaration is
+  forall (m : Nat) (n : Nat) (k : Nat), LT.lt.{0} Nat Nat.hasLt (ack m (Nat.pair n k)) (ack (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 4 (OfNat.mk.{0} Nat 4 (bit0.{0} Nat Nat.hasAdd (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) (LinearOrder.max.{0} Nat Nat.linearOrder n k))
+but is expected to have type
+  forall (m : Nat) (n : Nat) (k : Nat), LT.lt.{0} Nat instLTNat (ack m (Nat.pair n k)) (ack (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 4 (instOfNatNat 4))) (Max.max.{0} Nat Nat.instMaxNat n k))
+Case conversion may be inaccurate. Consider using '#align ack_mkpair_lt ack_pair_ltₓ'. -/
 theorem ack_pair_lt (m n k : ℕ) : ack m (pair n k) < ack (m + 4) (max n k) :=
   (ack_strictMono_right m <| pair_lt_max_add_one_sq n k).trans <| ack_add_one_sq_lt_ack_add_four _ _
 #align ack_mkpair_lt ack_pair_lt
 
+#print exists_lt_ack_of_nat_primrec /-
 /-- If `f` is primitive recursive, there exists `m` such that `f n < ack m n` for all `n`. -/
 theorem exists_lt_ack_of_nat_primrec {f : ℕ → ℕ} (hf : Nat.Primrec f) : ∃ m, ∀ n, f n < ack m n :=
   by
@@ -392,21 +477,28 @@ theorem exists_lt_ack_of_nat_primrec {f : ℕ → ℕ} (hf : Nat.Primrec f) : 
     -- The proof is now simple.
     exact ⟨max a b + 9, fun n => this.trans_le <| ack_mono_right _ <| unpair_add_le n⟩
 #align exists_lt_ack_of_nat_primrec exists_lt_ack_of_nat_primrec
+-/
 
+#print not_nat_primrec_ack_self /-
 theorem not_nat_primrec_ack_self : ¬Nat.Primrec fun n => ack n n := fun h =>
   by
   cases' exists_lt_ack_of_nat_primrec h with m hm
   exact (hm m).False
 #align not_nat_primrec_ack_self not_nat_primrec_ack_self
+-/
 
+#print not_primrec_ack_self /-
 theorem not_primrec_ack_self : ¬Primrec fun n => ack n n :=
   by
   rw [Primrec.nat_iff]
   exact not_nat_primrec_ack_self
 #align not_primrec_ack_self not_primrec_ack_self
+-/
 
+#print not_primrec₂_ack /-
 /-- The Ackermann function is not primitive recursive. -/
 theorem not_primrec₂_ack : ¬Primrec₂ ack := fun h =>
   not_primrec_ack_self <| h.comp Primrec.id Primrec.id
 #align not_primrec₂_ack not_primrec₂_ack
+-/

9b2660e1

bump to nightly-2023-03-29-02

mathlib commit https://github.com/leanprover-community/mathlib/commit/0148d455199ed64bf8eb2f493a1e7eb9211ce170

5cbaeba8

Diff

@@ -320,10 +320,9 @@ theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (
     
 #align ack_add_one_sq_lt_ack_add_four ack_add_one_sq_lt_ack_add_four
 
-theorem ack_mkpair_lt (m n k : ℕ) : ack m (mkpair n k) < ack (m + 4) (max n k) :=
-  (ack_strictMono_right m <| mkpair_lt_max_add_one_sq n k).trans <|
-    ack_add_one_sq_lt_ack_add_four _ _
-#align ack_mkpair_lt ack_mkpair_lt
+theorem ack_pair_lt (m n k : ℕ) : ack m (pair n k) < ack (m + 4) (max n k) :=
+  (ack_strictMono_right m <| pair_lt_max_add_one_sq n k).trans <| ack_add_one_sq_lt_ack_add_four _ _
+#align ack_mkpair_lt ack_pair_lt
 
 /-- If `f` is primitive recursive, there exists `m` such that `f n < ack m n` for all `n`. -/
 theorem exists_lt_ack_of_nat_primrec {f : ℕ → ℕ} (hf : Nat.Primrec f) : ∃ m, ∀ n, f n < ack m n :=
@@ -371,14 +370,14 @@ theorem exists_lt_ack_of_nat_primrec {f : ℕ → ℕ} (hf : Nat.Primrec f) : 
         linarith
       · -- We get rid of the first `mkpair`.
         rw [elim_succ]
-        apply (hb _).trans ((ack_mkpair_lt _ _ _).trans_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 (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 `mkpair`.
-        apply (ack_mkpair_lt _ _ _).le.trans
+        apply (ack_pair_lt _ _ _).le.trans
         -- If n is the maximum, we get a very weak inequality.
         cases' lt_or_le _ n with h₂ h₂
         · rw [max_eq_left h₂.le, add_assoc]

9b2660e1

bump to nightly-2023-03-01-20

mathlib commit https://github.com/leanprover-community/mathlib/commit/4c586d291f189eecb9d00581aeb3dd998ac34442

20cadee0

Diff

@@ -189,9 +189,9 @@ theorem add_lt_ack : ∀ m n, m + n < ack m n
   | m + 1, n + 1 =>
     calc
       m + 1 + n + 1 ≤ m + (m + n + 2) := by linarith
-      _ < ack m (m + n + 2) := add_lt_ack _ _
+      _ < ack m (m + n + 2) := (add_lt_ack _ _)
       _ ≤ ack m (ack (m + 1) n) :=
-        ack_mono_right m <| le_of_eq_of_le (by ring_nf) <| succ_le_of_lt <| add_lt_ack (m + 1) n
+        (ack_mono_right m <| le_of_eq_of_le (by ring_nf) <| succ_le_of_lt <| add_lt_ack (m + 1) n)
       _ = ack (m + 1) (n + 1) := (ack_succ_succ m n).symm
       
 #align add_lt_ack add_lt_ack
@@ -303,7 +303,7 @@ theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m
   calc
     ack m (ack n k) ≤ ack (max m n) (ack n k) := ack_mono_left _ (le_max_left _ _)
     _ < ack (max m n) (ack (max m n + 1) k) :=
-      ack_strictMono_right _ <| ack_strictMono_left k <| lt_succ_of_le <| le_max_right m n
+      (ack_strictMono_right _ <| ack_strictMono_left k <| lt_succ_of_le <| le_max_right m n)
     _ = ack (max m n + 1) (k + 1) := (ack_succ_succ _ _).symm
     _ ≤ ack (max m n + 2) k := ack_succ_right_le_ack_succ_left _ _
     
@@ -313,8 +313,8 @@ theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (
   calc
     ack m ((n + 1) ^ 2) < ack m ((ack m n + 1) ^ 2) :=
       ack_strictMono_right m <| pow_lt_pow_of_lt_left (succ_lt_succ <| lt_ack_right m n) zero_lt_two
-    _ ≤ ack m (ack (m + 3) n) := ack_mono_right m <| ack_add_one_sq_lt_ack_add_three m n
-    _ ≤ ack (m + 2) (ack (m + 3) n) := ack_mono_left _ <| by linarith
+    _ ≤ ack m (ack (m + 3) n) := (ack_mono_right m <| ack_add_one_sq_lt_ack_add_three m n)
+    _ ≤ ack (m + 2) (ack (m + 3) n) := (ack_mono_left _ <| by linarith)
     _ = ack (m + 3) (n + 1) := (ack_succ_succ _ n).symm
     _ ≤ ack (m + 4) n := ack_succ_right_le_ack_succ_left _ n

9b2660e1

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

9b2660e1

chore(Data/Nat/Defs): Integrate Nat.sqrt material (#11866)

Move the content of Data.Nat.ForSqrt and Data.Nat.Sqrt to Data.Nat.Defs by using Nat-specific Std lemmas rather than the mathlib general ones. This makes it ready to move to Std if wanted.

d4b9a267

Diff

@@ -3,6 +3,7 @@ Copyright (c) 2022 Violeta Hernández Palacios. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Violeta Hernández Palacios
 -/
+import Mathlib.Algebra.GroupPower.Order
 import Mathlib.Computability.Primrec
 import Mathlib.Tactic.Ring
 import Mathlib.Tactic.Linarith

9b2660e1

chore(Data/Nat): Use Std lemmas (#11661)

Move basic Nat lemmas from Data.Nat.Order.Basic and Data.Nat.Pow to Data.Nat.Defs. Most proofs need adapting, but that's easily solved by replacing the general mathlib lemmas by the new Std Nat-specific lemmas and using omega.

Other changes

Move the last few lemmas left in Data.Nat.Pow to Algebra.GroupPower.Order
Move the deprecated aliases from Data.Nat.Pow to Algebra.GroupPower.Order
Move the bit/bit0/bit1 lemmas from Data.Nat.Order.Basic to Data.Nat.Bits
Fix some fallout from not importing Data.Nat.Order.Basic anymore
Add a few Nat-specific lemmas to help fix the fallout (look for nolint simpNF)
Turn Nat.mul_self_le_mul_self_iff and Nat.mul_self_lt_mul_self_iff around (they were misnamed)
Make more arguments to Nat.one_lt_pow implicit

5bc68d9f

Diff

@@ -6,8 +6,6 @@ Authors: Violeta Hernández Palacios
 import Mathlib.Computability.Primrec
 import Mathlib.Tactic.Ring
 import Mathlib.Tactic.Linarith
-import Mathlib.Algebra.GroupPower.Order
-import Mathlib.Data.Nat.Pow
 
 #align_import computability.ackermann from "leanprover-community/mathlib"@"9b2660e1b25419042c8da10bf411aa3c67f14383"

9b2660e1

chore: remove unneeded decreasing_by and termination_by (#11386)

The termination checker has been getting more capable, and many of the termination_by or decreasing_by clauses in Mathlib are no longer needed.

(Note that termination_by? will show the automatically derived termination expression, so no information is being lost by removing these.)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

c7950e4e

Diff

@@ -65,7 +65,6 @@ def ack : ℕ → ℕ → ℕ
   | 0, n => n + 1
   | m + 1, 0 => ack m 1
   | m + 1, n + 1 => ack m (ack (m + 1) n)
-  termination_by m n => (m, n)
 #align ack ack
 
 @[simp]
@@ -145,7 +144,6 @@ theorem ack_strictMono_right : ∀ m, StrictMono (ack m)
     rw [ack_succ_succ, ack_succ_succ]
     apply ack_strictMono_right _ (ack_strictMono_right _ _)
     rwa [add_lt_add_iff_right] at h
-  termination_by m x => (m, x)
 #align ack_strict_mono_right ack_strictMono_right
 
 theorem ack_mono_right (m : ℕ) : Monotone (ack m) :=
@@ -186,7 +184,6 @@ theorem add_lt_ack : ∀ m n, m + n < ack m n
         ack_mono_right m <| le_of_eq_of_le (by rw [succ_eq_add_one]; ring_nf)
         <| succ_le_of_lt <| add_lt_ack (m + 1) n
       _ = ack (m + 1) (n + 1) := (ack_succ_succ m n).symm
-  termination_by m n => (m, n)
 #align add_lt_ack add_lt_ack
 
 theorem add_add_one_le_ack (m n : ℕ) : m + n + 1 ≤ ack m n :=
@@ -216,7 +213,6 @@ private theorem ack_strict_mono_left' : ∀ {m₁ m₂} (n), m₁ < m₂ → ack
     exact
       (ack_strict_mono_left' _ <| (add_lt_add_iff_right 1).1 h).trans
         (ack_strictMono_right _ <| ack_strict_mono_left' n h)
-  termination_by _ m n => (m, n)
 
 theorem ack_strictMono_left (n : ℕ) : StrictMono fun m => ack m n := fun _m₁ _m₂ =>
   ack_strict_mono_left' n

9b2660e1

refactor(Data.Finset.Card): termination_by change (#11370)

this will break once https://github.com/leanprover/lean4/pull/3658 lands, so let's fix this now.

Also avoids binding unused variables in termination_by.

9c2d8e0b

Diff

@@ -145,7 +145,7 @@ theorem ack_strictMono_right : ∀ m, StrictMono (ack m)
     rw [ack_succ_succ, ack_succ_succ]
     apply ack_strictMono_right _ (ack_strictMono_right _ _)
     rwa [add_lt_add_iff_right] at h
-  termination_by m x y h => (m, x)
+  termination_by m x => (m, x)
 #align ack_strict_mono_right ack_strictMono_right
 
 theorem ack_mono_right (m : ℕ) : Monotone (ack m) :=

9b2660e1

refactor: optimize proofs with omega (#11093)

I ran tryAtEachStep on all files under Mathlib to find all locations where omega succeeds. For each that was a linarith without an only, I tried replacing it with omega, and I verified that elaboration time got smaller. (In almost all cases, there was a noticeable speedup.) I also replaced some slow aesops along the way.

37bc4aba

Diff

@@ -180,7 +180,7 @@ theorem add_lt_ack : ∀ m n, m + n < ack m n
   | m + 1, 0 => by simpa using add_lt_ack m 1
   | m + 1, n + 1 =>
     calc
-      m + 1 + n + 1 ≤ m + (m + n + 2) := by linarith
+      m + 1 + n + 1 ≤ m + (m + n + 2) := by omega
       _ < ack m (m + n + 2) := add_lt_ack _ _
       _ ≤ ack m (ack (m + 1) n) :=
         ack_mono_right m <| le_of_eq_of_le (by rw [succ_eq_add_one]; ring_nf)
@@ -208,7 +208,7 @@ private theorem ack_strict_mono_left' : ∀ {m₁ m₂} (n), m₁ < m₂ → ack
   | 0, m + 1, n + 1 => fun h => by
     rw [ack_zero, ack_succ_succ]
     apply lt_of_le_of_lt (le_trans _ <| add_le_add_left (add_add_one_le_ack _ _) m) (add_lt_ack _ _)
-    linarith
+    omega
   | m₁ + 1, m₂ + 1, 0 => fun h => by
     simpa using ack_strict_mono_left' 1 ((add_lt_add_iff_right 1).1 h)
   | m₁ + 1, m₂ + 1, n + 1 => fun h => by
@@ -258,7 +258,7 @@ theorem ack_succ_right_le_ack_succ_left (m n : ℕ) : ack m (n + 1) ≤ ack (m +
   · simp
   · rw [ack_succ_succ, succ_eq_add_one]
     apply ack_mono_right m (le_trans _ <| add_add_one_le_ack _ n)
-    linarith
+    omega
 #align ack_succ_right_le_ack_succ_left ack_succ_right_le_ack_succ_left
 
 -- All the inequalities from this point onwards are specific to the main proof.
@@ -285,7 +285,7 @@ theorem ack_add_one_sq_lt_ack_add_three : ∀ m n, (ack m n + 1) ^ 2 ≤ ack (m
   | m + 1, n + 1 => by
     rw [ack_succ_succ, ack_succ_succ]
     apply (ack_add_one_sq_lt_ack_add_three _ _).trans (ack_mono_right _ <| ack_mono_left _ _)
-    linarith
+    omega
 #align ack_add_one_sq_lt_ack_add_three ack_add_one_sq_lt_ack_add_three
 
 theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m n + 2) k :=
@@ -302,7 +302,7 @@ theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (
     ack m ((n + 1) ^ 2) < ack m ((ack m n + 1) ^ 2) :=
       ack_strictMono_right m <| Nat.pow_lt_pow_left (succ_lt_succ <| lt_ack_right m n) two_ne_zero
     _ ≤ ack m (ack (m + 3) n) := ack_mono_right m <| ack_add_one_sq_lt_ack_add_three m n
-    _ ≤ ack (m + 2) (ack (m + 3) n) := ack_mono_left _ <| by linarith
+    _ ≤ ack (m + 2) (ack (m + 3) n) := ack_mono_left _ <| by omega
     _ = ack (m + 3) (n + 1) := (ack_succ_succ _ n).symm
     _ ≤ ack (m + 4) n := ack_succ_right_le_ack_succ_left _ n
 #align ack_add_one_sq_lt_ack_add_four ack_add_one_sq_lt_ack_add_four
@@ -353,7 +353,7 @@ theorem exists_lt_ack_of_nat_primrec {f : ℕ → ℕ} (hf : Nat.Primrec f) :
       induction' n with n IH
       -- The base case is easy.
       · apply (ha m).trans (ack_strictMono_left m <| (le_max_left a b).trans_lt _)
-        linarith
+        omega
       · -- We get rid of the first `pair`.
         simp only [ge_iff_le]
         apply (hb _).trans ((ack_pair_lt _ _ _).trans_le _)

9b2660e1

chore: bump Std (#10482)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

9afd0027

Diff

@@ -7,6 +7,7 @@ import Mathlib.Computability.Primrec
 import Mathlib.Tactic.Ring
 import Mathlib.Tactic.Linarith
 import Mathlib.Algebra.GroupPower.Order
+import Mathlib.Data.Nat.Pow
 
 #align_import computability.ackermann from "leanprover-community/mathlib"@"9b2660e1b25419042c8da10bf411aa3c67f14383"

9b2660e1

chore: bump dependencies (#10315)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

ba9f2e5b

Diff

@@ -323,11 +323,11 @@ theorem exists_lt_ack_of_nat_primrec {f : ℕ → ℕ} (hf : Nat.Primrec f) :
     apply add_lt_ack
   -- Left projection:
   · refine' ⟨0, fun n => _⟩
-    rw [ack_zero, lt_succ_iff]
+    rw [ack_zero, Nat.lt_succ_iff]
     exact unpair_left_le n
   -- Right projection:
   · refine' ⟨0, fun n => _⟩
-    rw [ack_zero, lt_succ_iff]
+    rw [ack_zero, Nat.lt_succ_iff]
     exact unpair_right_le n
   all_goals cases' IHf with a ha; cases' IHg with b hb
   -- Pairing:

9b2660e1

chore: move to v4.6.0-rc1, merging adaptations from bump/v4.6.0 (#10176)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Joachim Breitner <mail@joachim-breitner.de>

490d2d48

Diff

@@ -64,7 +64,7 @@ def ack : ℕ → ℕ → ℕ
   | 0, n => n + 1
   | m + 1, 0 => ack m 1
   | m + 1, n + 1 => ack m (ack (m + 1) n)
-  termination_by ack m n => (m, n)
+  termination_by m n => (m, n)
 #align ack ack
 
 @[simp]
@@ -102,6 +102,7 @@ theorem ack_three (n : ℕ) : ack 3 n = 2 ^ (n + 3) - 3 := by
         Nat.mul_sub_left_distrib, ← Nat.sub_add_comm, two_mul 3, Nat.add_sub_add_right]
     have H : 2 * 3 ≤ 2 * 2 ^ 3 := by norm_num
     apply H.trans
+    set_option simprocs false in
     simp [pow_le_pow_right (show 1 ≤ 2 by norm_num)]
 #align ack_three ack_three
 
@@ -143,7 +144,7 @@ theorem ack_strictMono_right : ∀ m, StrictMono (ack m)
     rw [ack_succ_succ, ack_succ_succ]
     apply ack_strictMono_right _ (ack_strictMono_right _ _)
     rwa [add_lt_add_iff_right] at h
-  termination_by ack_strictMono_right m x y h => (m, x)
+  termination_by m x y h => (m, x)
 #align ack_strict_mono_right ack_strictMono_right
 
 theorem ack_mono_right (m : ℕ) : Monotone (ack m) :=
@@ -184,7 +185,7 @@ theorem add_lt_ack : ∀ m n, m + n < ack m n
         ack_mono_right m <| le_of_eq_of_le (by rw [succ_eq_add_one]; ring_nf)
         <| succ_le_of_lt <| add_lt_ack (m + 1) n
       _ = ack (m + 1) (n + 1) := (ack_succ_succ m n).symm
-  termination_by add_lt_ack m n => (m, n)
+  termination_by m n => (m, n)
 #align add_lt_ack add_lt_ack
 
 theorem add_add_one_le_ack (m n : ℕ) : m + n + 1 ≤ ack m n :=
@@ -214,7 +215,7 @@ private theorem ack_strict_mono_left' : ∀ {m₁ m₂} (n), m₁ < m₂ → ack
     exact
       (ack_strict_mono_left' _ <| (add_lt_add_iff_right 1).1 h).trans
         (ack_strictMono_right _ <| ack_strict_mono_left' n h)
-  termination_by ack_strict_mono_left' x y => (x, y)
+  termination_by _ m n => (m, n)
 
 theorem ack_strictMono_left (n : ℕ) : StrictMono fun m => ack m n := fun _m₁ _m₂ =>
   ack_strict_mono_left' n

9b2660e1

fix: shake the import tree (#9749)

cherry-picked from #9347

Co-Authored-By: @digama0

1d3b4790

Diff

@@ -6,6 +6,7 @@ Authors: Violeta Hernández Palacios
 import Mathlib.Computability.Primrec
 import Mathlib.Tactic.Ring
 import Mathlib.Tactic.Linarith
+import Mathlib.Algebra.GroupPower.Order
 
 #align_import computability.ackermann from "leanprover-community/mathlib"@"9b2660e1b25419042c8da10bf411aa3c67f14383"

9b2660e1

chore: Rename pow monotonicity lemmas (#9095)

The names for lemmas about monotonicity of (a ^ ·) and (· ^ n) were a mess. This PR tidies up everything related by following the naming convention for (a * ·) and (· * b). Namely, (a ^ ·) is pow_right and (· ^ n) is pow_left in lemma names. All lemma renames follow the corresponding multiplication lemma names closely.

Renames

`Algebra.GroupPower.Order`

pow_mono → pow_right_mono
pow_le_pow → pow_le_pow_right
pow_le_pow_of_le_left → pow_le_pow_left
pow_lt_pow_of_lt_left → pow_lt_pow_left
strictMonoOn_pow → pow_left_strictMonoOn
pow_strictMono_right → pow_right_strictMono
pow_lt_pow → pow_lt_pow_right
pow_lt_pow_iff → pow_lt_pow_iff_right
pow_le_pow_iff → pow_le_pow_iff_right
self_lt_pow → lt_self_pow
strictAnti_pow → pow_right_strictAnti
pow_lt_pow_iff_of_lt_one → pow_lt_pow_iff_right_of_lt_one
pow_lt_pow_of_lt_one → pow_lt_pow_right_of_lt_one
lt_of_pow_lt_pow → lt_of_pow_lt_pow_left
le_of_pow_le_pow → le_of_pow_le_pow_left
pow_lt_pow₀ → pow_lt_pow_right₀

`Algebra.GroupPower.CovariantClass`

pow_le_pow_of_le_left' → pow_le_pow_left'
nsmul_le_nsmul_of_le_right → nsmul_le_nsmul_right
pow_lt_pow' → pow_lt_pow_right'
nsmul_lt_nsmul → nsmul_lt_nsmul_left
pow_strictMono_left → pow_right_strictMono'
nsmul_strictMono_right → nsmul_left_strictMono
StrictMono.pow_right' → StrictMono.pow_const
StrictMono.nsmul_left → StrictMono.const_nsmul
pow_strictMono_right' → pow_left_strictMono
nsmul_strictMono_left → nsmul_right_strictMono
Monotone.pow_right → Monotone.pow_const
Monotone.nsmul_left → Monotone.const_nsmul
lt_of_pow_lt_pow' → lt_of_pow_lt_pow_left'
lt_of_nsmul_lt_nsmul → lt_of_nsmul_lt_nsmul_right
pow_le_pow' → pow_le_pow_right'
nsmul_le_nsmul → nsmul_le_nsmul_left
pow_le_pow_of_le_one' → pow_le_pow_right_of_le_one'
nsmul_le_nsmul_of_nonpos → nsmul_le_nsmul_left_of_nonpos
le_of_pow_le_pow' → le_of_pow_le_pow_left'
le_of_nsmul_le_nsmul' → le_of_nsmul_le_nsmul_right'
pow_le_pow_iff' → pow_le_pow_iff_right'
nsmul_le_nsmul_iff → nsmul_le_nsmul_iff_left
pow_lt_pow_iff' → pow_lt_pow_iff_right'
nsmul_lt_nsmul_iff → nsmul_lt_nsmul_iff_left

`Data.Nat.Pow`

Nat.pow_lt_pow_of_lt_left → Nat.pow_lt_pow_left
Nat.pow_le_iff_le_left → Nat.pow_le_pow_iff_left
Nat.pow_lt_iff_lt_left → Nat.pow_lt_pow_iff_left

Lemmas added

pow_le_pow_iff_left
pow_lt_pow_iff_left
pow_right_injective
pow_right_inj
Nat.pow_le_pow_left to have the correct name since Nat.pow_le_pow_of_le_left is in Std.
Nat.pow_le_pow_right to have the correct name since Nat.pow_le_pow_of_le_right is in Std.

Lemmas removed

self_le_pow was a duplicate of le_self_pow.
Nat.pow_lt_pow_of_lt_right is defeq to pow_lt_pow_right.
Nat.pow_right_strictMono is defeq to pow_right_strictMono.
Nat.pow_le_iff_le_right is defeq to pow_le_pow_iff_right.
Nat.pow_lt_iff_lt_right is defeq to pow_lt_pow_iff_right.

Other changes

A bunch of proofs have been golfed.
Some lemma assumptions have been turned from 0 < n or 1 ≤ n to n ≠ 0.
A few Nat lemmas have been protected.
One docstring has been fixed.

d61c95e1

Diff

@@ -101,7 +101,7 @@ theorem ack_three (n : ℕ) : ack 3 n = 2 ^ (n + 3) - 3 := by
         Nat.mul_sub_left_distrib, ← Nat.sub_add_comm, two_mul 3, Nat.add_sub_add_right]
     have H : 2 * 3 ≤ 2 * 2 ^ 3 := by norm_num
     apply H.trans
-    simp [pow_le_pow (show 1 ≤ 2 by norm_num)]
+    simp [pow_le_pow_right (show 1 ≤ 2 by norm_num)]
 #align ack_three ack_three
 
 theorem ack_pos : ∀ m n, 0 < ack m n
@@ -297,7 +297,7 @@ theorem ack_ack_lt_ack_max_add_two (m n k : ℕ) : ack m (ack n k) < ack (max m
 theorem ack_add_one_sq_lt_ack_add_four (m n : ℕ) : ack m ((n + 1) ^ 2) < ack (m + 4) n :=
   calc
     ack m ((n + 1) ^ 2) < ack m ((ack m n + 1) ^ 2) :=
-      ack_strictMono_right m <| pow_lt_pow_of_lt_left (succ_lt_succ <| lt_ack_right m n) zero_lt_two
+      ack_strictMono_right m <| Nat.pow_lt_pow_left (succ_lt_succ <| lt_ack_right m n) two_ne_zero
     _ ≤ ack m (ack (m + 3) n) := ack_mono_right m <| ack_add_one_sq_lt_ack_add_three m n
     _ ≤ ack (m + 2) (ack (m + 3) n) := ack_mono_left _ <| by linarith
     _ = ack (m + 3) (n + 1) := (ack_succ_succ _ n).symm
@@ -332,7 +332,7 @@ theorem exists_lt_ack_of_nat_primrec {f : ℕ → ℕ} (hf : Nat.Primrec f) :
   · 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 <|
+          (Nat.pow_le_pow_left (add_le_add_right _ _) 2).trans <|
             ack_add_one_sq_lt_ack_add_three _ _⟩
     rw [max_ack_left]
     exact max_le_max (ha n).le (hb n).le

9b2660e1

chore: bump to v4.3.0-rc2 (#8366)

PR contents

This is the supremum of

#8284
#8056
#8023
#8332
#8226 (already approved)
#7834 (already approved)

along with some minor fixes from failures on nightly-testing as Mathlib master is merged into it.

Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.

I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0 branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.

Lean PRs involved in this bump

In particular this includes adjustments for the Lean PRs

leanprover/lean4#2778

We can get rid of all the

local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)

macros across Mathlib (and in any projects that want to write natural number powers of reals).

leanprover/lean4#2722

Changes the default behaviour of simp to (config := {decide := false}). This makes simp (and consequentially norm_num) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp or norm_num to decide or rfl, or adding (config := {decide := true}).

leanprover/lean4#2783

This changed the behaviour of simp so that simp [f] will only unfold "fully applied" occurrences of f. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true }). We may in future add a syntax for this, e.g. simp [!f]; please provide feedback! In the meantime, we have made the following changes:

switching to using explicit lemmas that have the intended level of application
(config := { unfoldPartialApp := true }) in some places, to recover the old behaviour
Using @[eqns] to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp and Function.flip.

This change in Lean may require further changes down the line (e.g. adding the !f syntax, and/or upstreaming the special treatment for Function.comp and Function.flip, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>

40b64f79

Diff

@@ -101,7 +101,7 @@ theorem ack_three (n : ℕ) : ack 3 n = 2 ^ (n + 3) - 3 := by
         Nat.mul_sub_left_distrib, ← Nat.sub_add_comm, two_mul 3, Nat.add_sub_add_right]
     have H : 2 * 3 ≤ 2 * 2 ^ 3 := by norm_num
     apply H.trans
-    simp [pow_le_pow]
+    simp [pow_le_pow (show 1 ≤ 2 by norm_num)]
 #align ack_three ack_three
 
 theorem ack_pos : ∀ m n, 0 < ack m n

9b2660e1

chore: linarith only needs ring1 (#7090)

I appreciate that this is "going backwards" in the sense of requiring more explicit imports of tactics (and making it more likely that users writing new files will need to import tactics rather than finding them already available).

However it's useful for me while I'm intensively working on refactoring and upstreaming tactics if I can minimise the dependencies between tactics. I'm very much aware that in the long run we don't want users to have to manage imports of tactics, and I am definitely going to tidy this all up again once I'm finished with this project!

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

37e6e50e

Diff

@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Violeta Hernández Palacios
 -/
 import Mathlib.Computability.Primrec
+import Mathlib.Tactic.Ring
 import Mathlib.Tactic.Linarith
 
 #align_import computability.ackermann from "leanprover-community/mathlib"@"9b2660e1b25419042c8da10bf411aa3c67f14383"

9b2660e1

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2022 Violeta Hernández Palacios. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Violeta Hernández Palacios
-
-! This file was ported from Lean 3 source module computability.ackermann
-! leanprover-community/mathlib commit 9b2660e1b25419042c8da10bf411aa3c67f14383
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Computability.Primrec
 import Mathlib.Tactic.Linarith
 
+#align_import computability.ackermann from "leanprover-community/mathlib"@"9b2660e1b25419042c8da10bf411aa3c67f14383"
+
 /-!
 # Ackermann function

9b2660e1

feat: Port Computability.Ackermann (#2922)

Co-authored-by: Parcly Taxel <reddeloostw@gmail.com>

7d522d3c

`computability.ackermann` ⟷ `Mathlib.Computability.Ackermann`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Other changes

Renames

`Algebra.GroupPower.Order`

`Algebra.GroupPower.CovariantClass`

`Data.Nat.Pow`

Lemmas added

Lemmas removed

Other changes

PR contents

Lean PRs involved in this bump

leanprover/lean4#2778

leanprover/lean4#2722

leanprover/lean4#2783

Dependencies 6 + 214

computability.ackermann ⟷ Mathlib.Computability.Ackermann

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Other changes

Renames

Algebra.GroupPower.Order

Algebra.GroupPower.CovariantClass

Data.Nat.Pow

Lemmas added

Lemmas removed

Other changes

PR contents

Lean PRs involved in this bump

leanprover/lean4#2778

leanprover/lean4#2722

leanprover/lean4#2783

Dependencies 6 + 214

`computability.ackermann` ⟷ `Mathlib.Computability.Ackermann`

`Algebra.GroupPower.Order`

`Algebra.GroupPower.CovariantClass`

`Data.Nat.Pow`