data.nat.order.basic | Mathlib porting status

(last sync)

feat(data/nat/order/basic): a + b - 1 ≤ a * b (#18737)

and golf max_eq_zero_iff/min_eq_zero_iff

To be used for Kneser's addition theorem.

Co-authored-by: Yury G. Kudryashov <urkud@urkud.name>

Diff

@@ -94,29 +94,9 @@ lemma eq_zero_of_mul_le (hb : 2 ≤ n) (h : n * m ≤ m) : m = 0 :=
 eq_zero_of_double_le $ le_trans (nat.mul_le_mul_right _ hb) h
 
 lemma zero_max : max 0 n = n := max_eq_right (zero_le _)
-@[simp] lemma min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 :=
-begin
-  split,
-  { intro h,
-    cases le_total m n with H H,
-    { simpa [H] using or.inl h },
-    { simpa [H] using or.inr h } },
-  { rintro (rfl|rfl);
-    simp }
-end
 
-@[simp] lemma max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 :=
-begin
-  split,
-  { intro h,
-    cases le_total m n with H H,
-    { simp only [H, max_eq_right] at h,
-      exact ⟨le_antisymm (H.trans h.le) (zero_le _), h⟩ },
-    { simp only [H, max_eq_left] at h,
-      exact ⟨h, le_antisymm (H.trans h.le) (zero_le _)⟩ } },
-  { rintro ⟨rfl, rfl⟩,
-    simp }
-end
+@[simp] lemma min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 := min_eq_bot
+@[simp] lemma max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 := max_eq_bot
 
 lemma add_eq_max_iff : m + n = max m n ↔ m = 0 ∨ n = 0 :=
 begin
@@ -286,6 +266,14 @@ end
 | 0 := iff_of_false (lt_irrefl _) zero_le_one.not_lt
 | (n + 1) := lt_mul_iff_one_lt_left n.succ_pos
 
+lemma add_sub_one_le_mul (hm : m ≠ 0) (hn : n ≠ 0) : m + n - 1 ≤ m * n :=
+begin
+  cases m,
+  { cases hm rfl },
+  { rw [succ_add, succ_sub_one, succ_mul],
+    exact add_le_add_right (le_mul_of_one_le_right' $ pos_iff_ne_zero.2 hn) _ }
+end
+
 /-!
 ### Recursion and induction principles

feat(algebra/divisibility/basic): Dot notation aliases (#18698)

A few convenience shortcuts for dvd along with some simple nat lemmas. Also

Drop neg_dvd_of_dvd/dvd_of_neg_dvd/dvd_neg_of_dvd/dvd_of_dvd_neg in favor of the aforementioned shortcuts.
Remove explicit arguments to dvd_neg/neg_dvd.
Drop int.of_nat_dvd_of_dvd_nat_abs/int.dvd_nat_abs_of_of_nat_dvd because they are the two directions of int.coe_nat_dvd_left.
Move group_with_zero.to_cancel_monoid_with_zero from algebra.group_with_zero.units.basic back to algebra.group_with_zero.basic. It was erroneously moved during the Great Splits.

Diff

@@ -65,7 +65,7 @@ instance : canonically_linear_ordered_add_monoid ℕ :=
 { .. (infer_instance : canonically_ordered_add_monoid ℕ),
   .. nat.linear_order }
 
-variables {m n k l : ℕ}
+variables {a b m n k l : ℕ}
 namespace nat
 
 /-! ### Equalities and inequalities involving zero and one -/
@@ -94,7 +94,6 @@ lemma eq_zero_of_mul_le (hb : 2 ≤ n) (h : n * m ≤ m) : m = 0 :=
 eq_zero_of_double_le $ le_trans (nat.mul_le_mul_right _ hb) h
 
 lemma zero_max : max 0 n = n := max_eq_right (zero_le _)
-
 @[simp] lemma min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 :=
 begin
   split,
@@ -243,17 +242,6 @@ lemma sub_succ' (m n : ℕ) : m - n.succ = m - n - 1 := rfl
 
 /-! ### `mul` -/
 
-lemma mul_eq_one_iff : ∀ {m n : ℕ}, m * n = 1 ↔ m = 1 ∧ n = 1
-| 0     0     := dec_trivial
-| 0     1     := dec_trivial
-| 1     0     := dec_trivial
-| (m+2) 0     := by simp
-| 0     (n+2) := by simp
-| (m+1) (n+1) := ⟨
-  λ h, by simp only [add_mul, mul_add, mul_add, one_mul, mul_one,
-    (add_assoc _ _ _).symm, nat.succ_inj', add_eq_zero_iff] at h; simp [h.1.2, h.2],
-  λ h, by simp only [h, mul_one]⟩
-
 lemma succ_mul_pos (m : ℕ) (hn : 0 < n) : 0 < (succ m) * n := mul_pos (succ_pos m) hn
 
 theorem mul_self_le_mul_self (h : m ≤ n) : m * m ≤ n * n := mul_le_mul h h (zero_le _) (zero_le _)

(no changes)

75bf5660

feat(data/zmod): a lemma on zmod.val_min_abs on negations (#17584)

And two necessary lemmas about nat, courtesy of @kmill .

Co-authored-by: Kyle Miller @kmill

Co-authored-by: Junyan Xu <junyanxu.math@gmail.com>

Diff

@@ -381,6 +381,22 @@ begin
       nat.mul_div_cancel_left _ (mul_pos hk0 hl0)]
 end
 
+lemma le_half_of_half_lt_sub {a b : ℕ} (h : a / 2 < a - b) : b ≤ a / 2 :=
+begin
+  rw nat.le_div_iff_mul_le two_pos,
+  rw [nat.div_lt_iff_lt_mul two_pos, nat.mul_sub_right_distrib, lt_tsub_iff_right,
+    mul_two a] at h,
+  exact le_of_lt (nat.lt_of_add_lt_add_left h)
+end
+
+lemma half_le_of_sub_le_half {a b : ℕ} (h : a - b ≤ a / 2) : a / 2 ≤ b :=
+begin
+  rw [nat.le_div_iff_mul_le two_pos, nat.mul_sub_right_distrib, tsub_le_iff_right,
+    mul_two, add_le_add_iff_left] at h,
+  rw [← nat.mul_div_left b two_pos],
+  exact nat.div_le_div_right h,
+end
+
 /-! ### `mod`, `dvd` -/
 
 lemma two_mul_odd_div_two (hn : n % 2 = 1) : 2 * (n / 2) = n - 1 :=

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

bump to nightly-2024-04-24-08

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

5d423ded

Diff

@@ -26,15 +26,15 @@ universe u v
 /-! ### instances -/
 
 
-#print Nat.orderBot /-
-instance Nat.orderBot : OrderBot ℕ where
+#print Nat.instOrderBot /-
+instance Nat.instOrderBot : OrderBot ℕ where
   bot := 0
   bot_le := Nat.zero_le
-#align nat.order_bot Nat.orderBot
+#align nat.order_bot Nat.instOrderBot
 -/
 
 instance : LinearOrderedCommSemiring ℕ :=
-  { Nat.commSemiring, Nat.linearOrder with
+  { Nat.commSemiring, Nat.instLinearOrder with
     lt := Nat.lt
     add_le_add_left := @Nat.add_le_add_left
     le_of_add_le_add_left := @Nat.le_of_add_le_add_left
@@ -71,7 +71,7 @@ instance : LinearOrderedCancelAddCommMonoid ℕ :=
   inferInstance
 
 instance : CanonicallyOrderedCommSemiring ℕ :=
-  { Nat.nontrivial, Nat.orderBot, (inferInstance : OrderedAddCommMonoid ℕ),
+  { Nat.nontrivial, Nat.instOrderBot, (inferInstance : OrderedAddCommMonoid ℕ),
     (inferInstance : LinearOrderedSemiring ℕ),
     (inferInstance :
       CommSemiring
@@ -81,7 +81,7 @@ instance : CanonicallyOrderedCommSemiring ℕ :=
     eq_zero_or_eq_zero_of_mul_eq_zero := fun a b => Nat.eq_zero_of_mul_eq_zero }
 
 instance : CanonicallyLinearOrderedAddCommMonoid ℕ :=
-  { (inferInstance : CanonicallyOrderedAddCommMonoid ℕ), Nat.linearOrder with }
+  { (inferInstance : CanonicallyOrderedAddCommMonoid ℕ), Nat.instLinearOrder with }
 
 variable {a b m n k l : ℕ}

bump to nightly-2024-04-10-08

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

cd0c1af5

Diff

@@ -982,7 +982,7 @@ instance decidableLoHi (lo hi : ℕ) (P : ℕ → Prop) [H : DecidablePred P] :
 instance decidableLoHiLe (lo hi : ℕ) (P : ℕ → Prop) [H : DecidablePred P] :
     Decidable (∀ x, lo ≤ x → x ≤ hi → P x) :=
   decidable_of_iff (∀ x, lo ≤ x → x < hi + 1 → P x) <|
-    ball_congr fun x hl => imp_congr lt_succ_iff Iff.rfl
+    forall₂_congr fun x hl => imp_congr lt_succ_iff Iff.rfl
 #align nat.decidable_lo_hi_le Nat.decidableLoHiLe
 -/

bump to nightly-2024-04-09-08

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

659ec6f7

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
 import Algebra.Order.Ring.Canonical
-import Data.Nat.Defs
+import Algebra.Group.Nat
 
 #align_import data.nat.order.basic from "leanprover-community/mathlib"@"3ed3f98a1e836241990d3d308f1577e434977130"

bump to nightly-2024-04-06-08

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

e34029c9

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
 import Algebra.Order.Ring.Canonical
-import Data.Nat.Basic
+import Data.Nat.Defs
 
 #align_import data.nat.order.basic from "leanprover-community/mathlib"@"3ed3f98a1e836241990d3d308f1577e434977130"

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -231,7 +231,7 @@ theorem add_pos_iff_pos_or_pos (m n : ℕ) : 0 < m + n ↔ 0 < m ∨ 0 < n :=
     (by
       intro h
       cases' m with m
-      · simp [zero_add] at h ; exact Or.inr h
+      · simp [zero_add] at h; exact Or.inr h
       exact Or.inl (succ_pos _))
     (by
       intro h; cases' h with mpos npos
@@ -324,9 +324,9 @@ theorem le_or_le_of_add_eq_add_pred (h : k + l = m + n - 1) : m ≤ k ∨ n ≤
   by
   cases' le_or_lt m k with h' h' <;> [left; right]
   · exact h'
-  · replace h' := add_lt_add_right h' l; rw [h] at h' 
+  · replace h' := add_lt_add_right h' l; rw [h] at h'
     cases' n.eq_zero_or_pos with hn hn; · rw [hn]; exact zero_le l
-    rw [m.add_sub_assoc hn, add_lt_add_iff_left] at h' 
+    rw [m.add_sub_assoc hn, add_lt_add_iff_left] at h'
     exact Nat.le_of_pred_lt h'
 #align nat.le_or_le_of_add_eq_add_pred Nat.le_or_le_of_add_eq_add_pred
 -/
@@ -555,7 +555,7 @@ theorem mul_div_mul_comm_of_dvd_dvd (hmk : k ∣ m) (hnl : l ∣ n) :
 theorem le_half_of_half_lt_sub {a b : ℕ} (h : a / 2 < a - b) : b ≤ a / 2 :=
   by
   rw [Nat.le_div_iff_mul_le two_pos]
-  rw [Nat.div_lt_iff_lt_mul two_pos, Nat.mul_sub_right_distrib, lt_tsub_iff_right, mul_two a] at h 
+  rw [Nat.div_lt_iff_lt_mul two_pos, Nat.mul_sub_right_distrib, lt_tsub_iff_right, mul_two a] at h
   exact le_of_lt (Nat.lt_of_add_lt_add_left h)
 #align nat.le_half_of_half_lt_sub Nat.le_half_of_half_lt_sub
 -/
@@ -564,7 +564,7 @@ theorem le_half_of_half_lt_sub {a b : ℕ} (h : a / 2 < a - b) : b ≤ a / 2 :=
 theorem half_le_of_sub_le_half {a b : ℕ} (h : a - b ≤ a / 2) : a / 2 ≤ b :=
   by
   rw [Nat.le_div_iff_mul_le two_pos, Nat.mul_sub_right_distrib, tsub_le_iff_right, mul_two,
-    add_le_add_iff_left] at h 
+    add_le_add_iff_left] at h
   rw [← Nat.mul_div_left b two_pos]
   exact Nat.div_le_div_right h
 #align nat.half_le_of_sub_le_half Nat.half_le_of_sub_le_half
@@ -591,7 +591,7 @@ theorem div_dvd_of_dvd (h : n ∣ m) : m / n ∣ m :=
 protected theorem div_div_self (h : n ∣ m) (hm : m ≠ 0) : m / (m / n) = n :=
   by
   rcases h with ⟨_, rfl⟩
-  rw [mul_ne_zero_iff] at hm 
+  rw [mul_ne_zero_iff] at hm
   rw [mul_div_right _ (Nat.pos_of_ne_zero hm.1), mul_div_left _ (Nat.pos_of_ne_zero hm.2)]
 #align nat.div_div_self Nat.div_div_self
 -/
@@ -911,7 +911,7 @@ theorem bit_lt_bit (a b) (h : m < n) : bit a m < bit b n :=
 theorem bit0_le_bit1_iff : bit0 m ≤ bit1 n ↔ m ≤ n :=
   ⟨fun h => by
     rwa [← Nat.lt_succ_iff, n.bit1_eq_succ_bit0, ← n.bit0_succ_eq, bit0_lt_bit0, Nat.lt_succ_iff] at
-      h ,
+      h,
     fun h => le_of_lt (Nat.bit0_lt_bit1 h)⟩
 #align nat.bit0_le_bit1_iff Nat.bit0_le_bit1_iff
 -/
@@ -926,7 +926,7 @@ theorem bit0_lt_bit1_iff : bit0 m < bit1 n ↔ m ≤ n :=
 #print Nat.bit1_le_bit0_iff /-
 @[simp]
 theorem bit1_le_bit0_iff : bit1 m ≤ bit0 n ↔ m < n :=
-  ⟨fun h => by rwa [m.bit1_eq_succ_bit0, succ_le_iff, bit0_lt_bit0] at h , fun h =>
+  ⟨fun h => by rwa [m.bit1_eq_succ_bit0, succ_le_iff, bit0_lt_bit0] at h, fun h =>
     le_of_lt (Nat.bit1_lt_bit0 h)⟩
 #align nat.bit1_le_bit0_iff Nat.bit1_le_bit0_iff
 -/
@@ -973,7 +973,7 @@ instance decidableLoHi (lo hi : ℕ) (P : ℕ → Prop) [H : DecidablePred P] :
   decidable_of_iff (∀ x < hi - lo, P (lo + x))
     ⟨fun al x hl hh => by
       have := al (x - lo) ((tsub_lt_tsub_iff_right hl).mpr hh)
-      rwa [add_tsub_cancel_of_le hl] at this , fun al x h =>
+      rwa [add_tsub_cancel_of_le hl] at this, fun al x h =>
       al _ (Nat.le_add_right _ _) (lt_tsub_iff_left.mp h)⟩
 #align nat.decidable_lo_hi Nat.decidableLoHi
 -/

bump to nightly-2024-02-05-08

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

516c6ec2

Diff

@@ -440,7 +440,7 @@ proved above, and some of the results in later sections depend on the definition
 -/
 
 
-/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
+/- ./././Mathport/Syntax/Translate/Command.lean:299:8: warning: using_well_founded used, estimated equivalent -/
 #print Nat.diag_induction /-
 /-- Given a predicate on two naturals `P : ℕ → ℕ → Prop`, `P a b` is true for all `a < b` if
 `P (a + 1) (a + 1)` is true for all `a`, `P 0 (b + 1)` is true for all `b` and for all
@@ -457,8 +457,7 @@ theorem diag_induction (P : ℕ → ℕ → Prop) (ha : ∀ a, P (a + 1) (a + 1)
       apply diag_induction (a + 1) b this
     apply diag_induction a (b + 1)
     apply lt_of_le_of_lt (Nat.le_succ _) h
-termination_by
-  _ x => WellFounded.wrap (measure_wf fun p => p.1 + p.2.1) x
+termination_by x => WellFounded.wrap (measure_wf fun p => p.1 + p.2.1) x
 #align nat.diag_induction Nat.diag_induction
 -/

bump to nightly-2023-12-23-06

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

b8c74971

Diff

@@ -440,6 +440,7 @@ proved above, and some of the results in later sections depend on the definition
 -/
 
 
+/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
 #print Nat.diag_induction /-
 /-- Given a predicate on two naturals `P : ℕ → ℕ → Prop`, `P a b` is true for all `a < b` if
 `P (a + 1) (a + 1)` is true for all `a`, `P 0 (b + 1)` is true for all `b` and for all
@@ -456,7 +457,8 @@ theorem diag_induction (P : ℕ → ℕ → Prop) (ha : ∀ a, P (a + 1) (a + 1)
       apply diag_induction (a + 1) b this
     apply diag_induction a (b + 1)
     apply lt_of_le_of_lt (Nat.le_succ _) h
-termination_by' ⟨_, measure_wf fun p => p.1 + p.2.1⟩
+termination_by
+  _ x => WellFounded.wrap (measure_wf fun p => p.1 + p.2.1) x
 #align nat.diag_induction Nat.diag_induction
 -/

bump to nightly-2023-10-18-06

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

f56d31a0

Diff

@@ -527,7 +527,7 @@ theorem div_mul_div_le_div (m n k : ℕ) : m / k * n / m ≤ n / k :=
         Nat.div_le_div_right (by rw [mul_comm] <;> exact mul_div_le_mul_div_assoc _ _ _)
       _ = n / k := by
         rw [Nat.div_div_eq_div_mul, mul_comm n, mul_comm k,
-          Nat.mul_div_mul _ _ (Nat.pos_of_ne_zero hm0)]
+          Nat.mul_div_mul_left _ _ (Nat.pos_of_ne_zero hm0)]
 #align nat.div_mul_div_le_div Nat.div_mul_div_le_div
 -/

bump to nightly-2023-10-07-06

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

d191b687

Diff

@@ -80,8 +80,8 @@ instance : CanonicallyOrderedCommSemiring ℕ :=
     le_self_add := Nat.le_add_right
     eq_zero_or_eq_zero_of_mul_eq_zero := fun a b => Nat.eq_zero_of_mul_eq_zero }
 
-instance : CanonicallyLinearOrderedAddMonoid ℕ :=
-  { (inferInstance : CanonicallyOrderedAddMonoid ℕ), Nat.linearOrder with }
+instance : CanonicallyLinearOrderedAddCommMonoid ℕ :=
+  { (inferInstance : CanonicallyOrderedAddCommMonoid ℕ), Nat.linearOrder with }
 
 variable {a b m n k l : ℕ}

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2014 Floris van Doorn (c) 2016 Microsoft Corporation. All rights r
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
-import Mathbin.Algebra.Order.Ring.Canonical
-import Mathbin.Data.Nat.Basic
+import Algebra.Order.Ring.Canonical
+import Data.Nat.Basic
 
 #align_import data.nat.order.basic from "leanprover-community/mathlib"@"3ed3f98a1e836241990d3d308f1577e434977130"
 
@@ -695,7 +695,7 @@ theorem div_eq_self : m / n = m ↔ m = 0 ∨ n = 1 :=
 #align nat.div_eq_self Nat.div_eq_self
 -/
 
-/- ./././Mathport/Syntax/Translate/Tactic/Lean3.lean:132:4: warning: unsupported: rw with cfg: { occs := occurrences.pos[occurrences.pos] «expr[ ,]»([2]) } -/
+/- ./././Mathport/Syntax/Translate/Tactic/Lean3.lean:133:4: warning: unsupported: rw with cfg: { occs := occurrences.pos[occurrences.pos] «expr[ ,]»([2]) } -/
 #print Nat.div_eq_sub_mod_div /-
 theorem div_eq_sub_mod_div : m / n = (m - m % n) / n :=
   by

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) 2014 Floris van Doorn (c) 2016 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.order.basic
-! leanprover-community/mathlib commit 3ed3f98a1e836241990d3d308f1577e434977130
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Algebra.Order.Ring.Canonical
 import Mathbin.Data.Nat.Basic
 
+#align_import data.nat.order.basic from "leanprover-community/mathlib"@"3ed3f98a1e836241990d3d308f1577e434977130"
+
 /-!
 # The natural numbers as a linearly ordered commutative semiring

bump to nightly-2023-07-16-17

mathlib commit https://github.com/leanprover-community/mathlib/commit/2fe465deb81bcd7ccafa065bb686888a82f15372

6db63fa6

Diff

@@ -425,6 +425,7 @@ theorem lt_mul_self_iff : ∀ {n : ℕ}, n < n * n ↔ 1 < n
 #align nat.lt_mul_self_iff Nat.lt_mul_self_iff
 -/
 
+#print Nat.add_sub_one_le_mul /-
 theorem add_sub_one_le_mul (hm : m ≠ 0) (hn : n ≠ 0) : m + n - 1 ≤ m * n :=
   by
   cases m
@@ -432,6 +433,7 @@ theorem add_sub_one_le_mul (hm : m ≠ 0) (hn : n ≠ 0) : m + n - 1 ≤ m * n :
   · rw [succ_add, succ_sub_one, succ_mul]
     exact add_le_add_right (le_mul_of_one_le_right' <| pos_iff_ne_zero.2 hn) _
 #align nat.add_sub_one_le_mul Nat.add_sub_one_le_mul
+-/
 
 /-!
 ### Recursion and induction principles

bump to nightly-2023-07-12-03

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

403fa41d

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.nat.order.basic
-! leanprover-community/mathlib commit e8638a0fcaf73e4500469f368ef9494e495099b3
+! leanprover-community/mathlib commit 3ed3f98a1e836241990d3d308f1577e434977130
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -147,29 +147,14 @@ theorem zero_max : max 0 n = n :=
 #print Nat.min_eq_zero_iff /-
 @[simp]
 theorem min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 :=
-  by
-  constructor
-  · intro h
-    cases' le_total m n with H H
-    · simpa [H] using Or.inl h
-    · simpa [H] using Or.inr h
-  · rintro (rfl | rfl) <;> simp
+  min_eq_bot
 #align nat.min_eq_zero_iff Nat.min_eq_zero_iff
 -/
 
 #print Nat.max_eq_zero_iff /-
 @[simp]
 theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 :=
-  by
-  constructor
-  · intro h
-    cases' le_total m n with H H
-    · simp only [H, max_eq_right] at h 
-      exact ⟨le_antisymm (H.trans h.le) (zero_le _), h⟩
-    · simp only [H, max_eq_left] at h 
-      exact ⟨h, le_antisymm (H.trans h.le) (zero_le _)⟩
-  · rintro ⟨rfl, rfl⟩
-    simp
+  max_eq_bot
 #align nat.max_eq_zero_iff Nat.max_eq_zero_iff
 -/
 
@@ -440,6 +425,14 @@ theorem lt_mul_self_iff : ∀ {n : ℕ}, n < n * n ↔ 1 < n
 #align nat.lt_mul_self_iff Nat.lt_mul_self_iff
 -/
 
+theorem add_sub_one_le_mul (hm : m ≠ 0) (hn : n ≠ 0) : m + n - 1 ≤ m * n :=
+  by
+  cases m
+  · cases hm rfl
+  · rw [succ_add, succ_sub_one, succ_mul]
+    exact add_le_add_right (le_mul_of_one_le_right' <| pos_iff_ne_zero.2 hn) _
+#align nat.add_sub_one_le_mul Nat.add_sub_one_le_mul
+
 /-!
 ### Recursion and induction principles

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -107,9 +107,11 @@ theorem one_lt_iff_ne_zero_and_ne_one : ∀ {n : ℕ}, 1 < n ↔ n ≠ 0 ∧ n 
 #align nat.one_lt_iff_ne_zero_and_ne_one Nat.one_lt_iff_ne_zero_and_ne_one
 -/
 
+#print Nat.mul_ne_zero /-
 protected theorem mul_ne_zero (n0 : n ≠ 0) (m0 : m ≠ 0) : n * m ≠ 0
   | nm => (eq_zero_of_mul_eq_zero nm).elim n0 m0
 #align nat.mul_ne_zero Nat.mul_ne_zero
+-/
 
 #print Nat.mul_eq_zero /-
 @[simp]
@@ -136,10 +138,13 @@ theorem eq_zero_of_mul_le (hb : 2 ≤ n) (h : n * m ≤ m) : m = 0 :=
 #align nat.eq_zero_of_mul_le Nat.eq_zero_of_mul_le
 -/
 
+#print Nat.zero_max /-
 theorem zero_max : max 0 n = n :=
   max_eq_right (zero_le _)
 #align nat.zero_max Nat.zero_max
+-/
 
+#print Nat.min_eq_zero_iff /-
 @[simp]
 theorem min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 :=
   by
@@ -150,7 +155,9 @@ theorem min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 :=
     · simpa [H] using Or.inr h
   · rintro (rfl | rfl) <;> simp
 #align nat.min_eq_zero_iff Nat.min_eq_zero_iff
+-/
 
+#print Nat.max_eq_zero_iff /-
 @[simp]
 theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 :=
   by
@@ -164,18 +171,23 @@ theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 :=
   · rintro ⟨rfl, rfl⟩
     simp
 #align nat.max_eq_zero_iff Nat.max_eq_zero_iff
+-/
 
+#print Nat.add_eq_max_iff /-
 theorem add_eq_max_iff : m + n = max m n ↔ m = 0 ∨ n = 0 :=
   by
   rw [← min_eq_zero_iff]
   cases' le_total m n with H H <;> simp [H]
 #align nat.add_eq_max_iff Nat.add_eq_max_iff
+-/
 
+#print Nat.add_eq_min_iff /-
 theorem add_eq_min_iff : m + n = min m n ↔ m = 0 ∧ n = 0 :=
   by
   rw [← max_eq_zero_iff]
   cases' le_total m n with H H <;> simp [H]
 #align nat.add_eq_min_iff Nat.add_eq_min_iff
+-/
 
 #print Nat.one_le_of_lt /-
 theorem one_le_of_lt (h : n < m) : 1 ≤ m :=
@@ -225,9 +237,11 @@ theorem add_pos_left {m : ℕ} (h : 0 < m) (n : ℕ) : 0 < m + n :=
 #align nat.add_pos_left Nat.add_pos_left
 -/
 
+#print Nat.add_pos_right /-
 theorem add_pos_right (m : ℕ) {n : ℕ} (h : 0 < n) : 0 < m + n := by rw [add_comm];
   exact add_pos_left h m
 #align nat.add_pos_right Nat.add_pos_right
+-/
 
 #print Nat.add_pos_iff_pos_or_pos /-
 theorem add_pos_iff_pos_or_pos (m n : ℕ) : 0 < m + n ↔ 0 < m ∨ 0 < n :=
@@ -637,6 +651,7 @@ theorem dvd_sub_mod (k : ℕ) : n ∣ k - k % n :=
 #align nat.dvd_sub_mod Nat.dvd_sub_mod
 -/
 
+#print Nat.add_mod_eq_ite /-
 theorem add_mod_eq_ite :
     (m + n) % k = if k ≤ m % k + n % k then m % k + n % k - k else m % k + n % k :=
   by
@@ -648,6 +663,7 @@ theorem add_mod_eq_ite :
       (tsub_lt_iff_right h).mpr (Nat.add_lt_add (m.mod_lt k.zero_lt_succ) (n.mod_lt k.zero_lt_succ))
   · exact Nat.mod_eq_of_lt (lt_of_not_ge h)
 #align nat.add_mod_eq_ite Nat.add_mod_eq_ite
+-/
 
 #print Nat.div_mul_div_comm /-
 theorem div_mul_div_comm (hmn : n ∣ m) (hkl : l ∣ k) : m / n * (k / l) = m * k / (n * l) :=

bump to nightly-2023-06-09-07

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

16afdc39

Diff

@@ -222,7 +222,6 @@ theorem add_pos_left {m : ℕ} (h : 0 < m) (n : ℕ) : 0 < m + n :=
     m + n > 0 + n := Nat.add_lt_add_right h n
     _ = n := (Nat.zero_add n)
     _ ≥ 0 := zero_le n
-    
 #align nat.add_pos_left Nat.add_pos_left
 -/
 
@@ -482,7 +481,6 @@ protected theorem div_le_of_le_mul' (h : m ≤ k * n) : m / k ≤ n :=
         k * (m / k) ≤ m % k + k * (m / k) := Nat.le_add_left _ _
         _ = m := (mod_add_div _ _)
         _ ≤ k * n := h
-        
 #align nat.div_le_of_le_mul' Nat.div_le_of_le_mul'
 -/
 
@@ -493,7 +491,6 @@ protected theorem div_le_self' (m n : ℕ) : m / n ≤ m :=
       calc
         m = 1 * m := (one_mul _).symm
         _ ≤ n * m := Nat.mul_le_mul_right _ n0
-        
 #align nat.div_le_self' Nat.div_le_self'
 -/
 
@@ -503,8 +500,7 @@ protected theorem div_lt_of_lt_mul (h : m < n * k) : m / n < k :=
     (calc
       n * (m / n) ≤ m % n + n * (m / n) := Nat.le_add_left _ _
       _ = m := (mod_add_div _ _)
-      _ < n * k := h
-      )
+      _ < n * k := h)
     (Nat.zero_le n)
 #align nat.div_lt_of_lt_mul Nat.div_lt_of_lt_mul
 -/
@@ -526,7 +522,6 @@ theorem div_mul_div_le_div (m n k : ℕ) : m / k * n / m ≤ n / k :=
       _ = n / k := by
         rw [Nat.div_div_eq_div_mul, mul_comm n, mul_comm k,
           Nat.mul_div_mul _ _ (Nat.pos_of_ne_zero hm0)]
-      
 #align nat.div_mul_div_le_div Nat.div_mul_div_le_div
 -/

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -157,9 +157,9 @@ theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 :=
   constructor
   · intro h
     cases' le_total m n with H H
-    · simp only [H, max_eq_right] at h
+    · simp only [H, max_eq_right] at h 
       exact ⟨le_antisymm (H.trans h.le) (zero_le _), h⟩
-    · simp only [H, max_eq_left] at h
+    · simp only [H, max_eq_left] at h 
       exact ⟨h, le_antisymm (H.trans h.le) (zero_le _)⟩
   · rintro ⟨rfl, rfl⟩
     simp
@@ -236,7 +236,7 @@ theorem add_pos_iff_pos_or_pos (m n : ℕ) : 0 < m + n ↔ 0 < m ∨ 0 < n :=
     (by
       intro h
       cases' m with m
-      · simp [zero_add] at h; exact Or.inr h
+      · simp [zero_add] at h ; exact Or.inr h
       exact Or.inl (succ_pos _))
     (by
       intro h; cases' h with mpos npos
@@ -327,11 +327,11 @@ theorem lt_of_lt_pred (h : m < n - 1) : m < n :=
 #print Nat.le_or_le_of_add_eq_add_pred /-
 theorem le_or_le_of_add_eq_add_pred (h : k + l = m + n - 1) : m ≤ k ∨ n ≤ l :=
   by
-  cases' le_or_lt m k with h' h' <;> [left;right]
+  cases' le_or_lt m k with h' h' <;> [left; right]
   · exact h'
-  · replace h' := add_lt_add_right h' l; rw [h] at h'
+  · replace h' := add_lt_add_right h' l; rw [h] at h' 
     cases' n.eq_zero_or_pos with hn hn; · rw [hn]; exact zero_le l
-    rw [m.add_sub_assoc hn, add_lt_add_iff_left] at h'
+    rw [m.add_sub_assoc hn, add_lt_add_iff_left] at h' 
     exact Nat.le_of_pred_lt h'
 #align nat.le_or_le_of_add_eq_add_pred Nat.le_or_le_of_add_eq_add_pred
 -/
@@ -450,7 +450,8 @@ theorem diag_induction (P : ℕ → ℕ → Prop) (ha : ∀ a, P (a + 1) (a + 1)
       · exact ha _
       apply diag_induction (a + 1) b this
     apply diag_induction a (b + 1)
-    apply lt_of_le_of_lt (Nat.le_succ _) h termination_by' ⟨_, measure_wf fun p => p.1 + p.2.1⟩
+    apply lt_of_le_of_lt (Nat.le_succ _) h
+termination_by' ⟨_, measure_wf fun p => p.1 + p.2.1⟩
 #align nat.diag_induction Nat.diag_induction
 -/
 
@@ -552,7 +553,7 @@ theorem mul_div_mul_comm_of_dvd_dvd (hmk : k ∣ m) (hnl : l ∣ n) :
 theorem le_half_of_half_lt_sub {a b : ℕ} (h : a / 2 < a - b) : b ≤ a / 2 :=
   by
   rw [Nat.le_div_iff_mul_le two_pos]
-  rw [Nat.div_lt_iff_lt_mul two_pos, Nat.mul_sub_right_distrib, lt_tsub_iff_right, mul_two a] at h
+  rw [Nat.div_lt_iff_lt_mul two_pos, Nat.mul_sub_right_distrib, lt_tsub_iff_right, mul_two a] at h 
   exact le_of_lt (Nat.lt_of_add_lt_add_left h)
 #align nat.le_half_of_half_lt_sub Nat.le_half_of_half_lt_sub
 -/
@@ -561,7 +562,7 @@ theorem le_half_of_half_lt_sub {a b : ℕ} (h : a / 2 < a - b) : b ≤ a / 2 :=
 theorem half_le_of_sub_le_half {a b : ℕ} (h : a - b ≤ a / 2) : a / 2 ≤ b :=
   by
   rw [Nat.le_div_iff_mul_le two_pos, Nat.mul_sub_right_distrib, tsub_le_iff_right, mul_two,
-    add_le_add_iff_left] at h
+    add_le_add_iff_left] at h 
   rw [← Nat.mul_div_left b two_pos]
   exact Nat.div_le_div_right h
 #align nat.half_le_of_sub_le_half Nat.half_le_of_sub_le_half
@@ -588,7 +589,7 @@ theorem div_dvd_of_dvd (h : n ∣ m) : m / n ∣ m :=
 protected theorem div_div_self (h : n ∣ m) (hm : m ≠ 0) : m / (m / n) = n :=
   by
   rcases h with ⟨_, rfl⟩
-  rw [mul_ne_zero_iff] at hm
+  rw [mul_ne_zero_iff] at hm 
   rw [mul_div_right _ (Nat.pos_of_ne_zero hm.1), mul_div_left _ (Nat.pos_of_ne_zero hm.2)]
 #align nat.div_div_self Nat.div_div_self
 -/
@@ -764,13 +765,13 @@ theorem findGreatest_eq_iff :
         exact ⟨le_rfl, fun _ => hk, fun n hlt hle => (hlt.not_le hle).elim⟩
       · rintro ⟨hle, h0, hm⟩
         rcases Decidable.eq_or_lt_of_le hle with (rfl | hlt)
-        exacts[rfl, (hm hlt le_rfl hk).elim]
+        exacts [rfl, (hm hlt le_rfl hk).elim]
     · rw [find_greatest_of_not hk, ihk]
       constructor
       · rintro ⟨hle, hP, hm⟩
         refine' ⟨hle.trans k.le_succ, hP, fun n hlt hle => _⟩
         rcases Decidable.eq_or_lt_of_le hle with (rfl | hlt')
-        exacts[hk, hm hlt <| lt_succ_iff.1 hlt']
+        exacts [hk, hm hlt <| lt_succ_iff.1 hlt']
       · rintro ⟨hle, hP, hm⟩
         refine' ⟨lt_succ_iff.1 (hle.lt_of_ne _), hP, fun n hlt hle => hm hlt (hle.trans k.le_succ)⟩
         rintro rfl
@@ -906,7 +907,7 @@ theorem bit_lt_bit (a b) (h : m < n) : bit a m < bit b n :=
 theorem bit0_le_bit1_iff : bit0 m ≤ bit1 n ↔ m ≤ n :=
   ⟨fun h => by
     rwa [← Nat.lt_succ_iff, n.bit1_eq_succ_bit0, ← n.bit0_succ_eq, bit0_lt_bit0, Nat.lt_succ_iff] at
-      h,
+      h ,
     fun h => le_of_lt (Nat.bit0_lt_bit1 h)⟩
 #align nat.bit0_le_bit1_iff Nat.bit0_le_bit1_iff
 -/
@@ -921,7 +922,7 @@ theorem bit0_lt_bit1_iff : bit0 m < bit1 n ↔ m ≤ n :=
 #print Nat.bit1_le_bit0_iff /-
 @[simp]
 theorem bit1_le_bit0_iff : bit1 m ≤ bit0 n ↔ m < n :=
-  ⟨fun h => by rwa [m.bit1_eq_succ_bit0, succ_le_iff, bit0_lt_bit0] at h, fun h =>
+  ⟨fun h => by rwa [m.bit1_eq_succ_bit0, succ_le_iff, bit0_lt_bit0] at h , fun h =>
     le_of_lt (Nat.bit1_lt_bit0 h)⟩
 #align nat.bit1_le_bit0_iff Nat.bit1_le_bit0_iff
 -/
@@ -968,7 +969,7 @@ instance decidableLoHi (lo hi : ℕ) (P : ℕ → Prop) [H : DecidablePred P] :
   decidable_of_iff (∀ x < hi - lo, P (lo + x))
     ⟨fun al x hl hh => by
       have := al (x - lo) ((tsub_lt_tsub_iff_right hl).mpr hh)
-      rwa [add_tsub_cancel_of_le hl] at this, fun al x h =>
+      rwa [add_tsub_cancel_of_le hl] at this , fun al x h =>
       al _ (Nat.le_add_right _ _) (lt_tsub_iff_left.mp h)⟩
 #align nat.decidable_lo_hi Nat.decidableLoHi
 -/

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -107,12 +107,6 @@ theorem one_lt_iff_ne_zero_and_ne_one : ∀ {n : ℕ}, 1 < n ↔ n ≠ 0 ∧ n 
 #align nat.one_lt_iff_ne_zero_and_ne_one Nat.one_lt_iff_ne_zero_and_ne_one
 -/
 
-/- warning: nat.mul_ne_zero -> Nat.mul_ne_zero is a dubious translation:
-lean 3 declaration is
-  forall {m : Nat} {n : Nat}, (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) -> (Ne.{1} Nat m (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) -> (Ne.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) n m) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))))
-but is expected to have type
-  forall {m : Nat} {n : Nat}, (Ne.{1} Nat m (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Ne.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) m n) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)))
-Case conversion may be inaccurate. Consider using '#align nat.mul_ne_zero Nat.mul_ne_zeroₓ'. -/
 protected theorem mul_ne_zero (n0 : n ≠ 0) (m0 : m ≠ 0) : n * m ≠ 0
   | nm => (eq_zero_of_mul_eq_zero nm).elim n0 m0
 #align nat.mul_ne_zero Nat.mul_ne_zero
@@ -142,22 +136,10 @@ theorem eq_zero_of_mul_le (hb : 2 ≤ n) (h : n * m ≤ m) : m = 0 :=
 #align nat.eq_zero_of_mul_le Nat.eq_zero_of_mul_le
 -/
 
-/- warning: nat.zero_max -> Nat.zero_max is a dubious translation:
-lean 3 declaration is
-  forall {n : Nat}, Eq.{1} Nat (LinearOrder.max.{0} Nat Nat.linearOrder (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) n) n
-but is expected to have type
-  forall {n : Nat}, Eq.{1} Nat (Max.max.{0} Nat Nat.instMaxNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) n) n
-Case conversion may be inaccurate. Consider using '#align nat.zero_max Nat.zero_maxₓ'. -/
 theorem zero_max : max 0 n = n :=
   max_eq_right (zero_le _)
 #align nat.zero_max Nat.zero_max
 
-/- warning: nat.min_eq_zero_iff -> Nat.min_eq_zero_iff is a dubious translation:
-lean 3 declaration is
-  forall {m : Nat} {n : Nat}, Iff (Eq.{1} Nat (LinearOrder.min.{0} Nat Nat.linearOrder m n) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (Or (Eq.{1} Nat m (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (Eq.{1} Nat n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))))
-but is expected to have type
-  forall {m : Nat} {n : Nat}, Iff (Eq.{1} Nat (Min.min.{0} Nat instMinNat m n) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (Or (Eq.{1} Nat m (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (Eq.{1} Nat n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))))
-Case conversion may be inaccurate. Consider using '#align nat.min_eq_zero_iff Nat.min_eq_zero_iffₓ'. -/
 @[simp]
 theorem min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 :=
   by
@@ -169,12 +151,6 @@ theorem min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 :=
   · rintro (rfl | rfl) <;> simp
 #align nat.min_eq_zero_iff Nat.min_eq_zero_iff
 
-/- warning: nat.max_eq_zero_iff -> Nat.max_eq_zero_iff is a dubious translation:
-lean 3 declaration is
-  forall {m : Nat} {n : Nat}, Iff (Eq.{1} Nat (LinearOrder.max.{0} Nat Nat.linearOrder m n) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (And (Eq.{1} Nat m (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (Eq.{1} Nat n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))))
-but is expected to have type
-  forall {m : Nat} {n : Nat}, Iff (Eq.{1} Nat (Max.max.{0} Nat Nat.instMaxNat m n) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (And (Eq.{1} Nat m (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (Eq.{1} Nat n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))))
-Case conversion may be inaccurate. Consider using '#align nat.max_eq_zero_iff Nat.max_eq_zero_iffₓ'. -/
 @[simp]
 theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 :=
   by
@@ -189,24 +165,12 @@ theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 :=
     simp
 #align nat.max_eq_zero_iff Nat.max_eq_zero_iff
 
-/- warning: nat.add_eq_max_iff -> Nat.add_eq_max_iff is a dubious translation:
-lean 3 declaration is
-  forall {m : Nat} {n : Nat}, Iff (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m n) (LinearOrder.max.{0} Nat Nat.linearOrder m n)) (Or (Eq.{1} Nat m (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (Eq.{1} Nat n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))))
-but is expected to have type
-  forall {m : Nat} {n : Nat}, Iff (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m n) (Max.max.{0} Nat Nat.instMaxNat m n)) (Or (Eq.{1} Nat m (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (Eq.{1} Nat n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))))
-Case conversion may be inaccurate. Consider using '#align nat.add_eq_max_iff Nat.add_eq_max_iffₓ'. -/
 theorem add_eq_max_iff : m + n = max m n ↔ m = 0 ∨ n = 0 :=
   by
   rw [← min_eq_zero_iff]
   cases' le_total m n with H H <;> simp [H]
 #align nat.add_eq_max_iff Nat.add_eq_max_iff
 
-/- warning: nat.add_eq_min_iff -> Nat.add_eq_min_iff is a dubious translation:
-lean 3 declaration is
-  forall {m : Nat} {n : Nat}, Iff (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m n) (LinearOrder.min.{0} Nat Nat.linearOrder m n)) (And (Eq.{1} Nat m (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (Eq.{1} Nat n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))))
-but is expected to have type
-  forall {m : Nat} {n : Nat}, Iff (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m n) (Min.min.{0} Nat instMinNat m n)) (And (Eq.{1} Nat m (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (Eq.{1} Nat n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))))
-Case conversion may be inaccurate. Consider using '#align nat.add_eq_min_iff Nat.add_eq_min_iffₓ'. -/
 theorem add_eq_min_iff : m + n = min m n ↔ m = 0 ∧ n = 0 :=
   by
   rw [← max_eq_zero_iff]
@@ -262,12 +226,6 @@ theorem add_pos_left {m : ℕ} (h : 0 < m) (n : ℕ) : 0 < m + n :=
 #align nat.add_pos_left Nat.add_pos_left
 -/
 
-/- warning: nat.add_pos_right -> Nat.add_pos_right is a dubious translation:
-lean 3 declaration is
-  forall (m : Nat) {n : Nat}, (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) n) -> (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m n))
-but is expected to have type
-  forall {m : Nat} (n : Nat), (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) m) -> (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) n m))
-Case conversion may be inaccurate. Consider using '#align nat.add_pos_right Nat.add_pos_rightₓ'. -/
 theorem add_pos_right (m : ℕ) {n : ℕ} (h : 0 < n) : 0 < m + n := by rw [add_comm];
   exact add_pos_left h m
 #align nat.add_pos_right Nat.add_pos_right
@@ -683,12 +641,6 @@ theorem dvd_sub_mod (k : ℕ) : n ∣ k - k % n :=
 #align nat.dvd_sub_mod Nat.dvd_sub_mod
 -/
 
-/- warning: nat.add_mod_eq_ite -> Nat.add_mod_eq_ite is a dubious translation:
-lean 3 declaration is
-  forall {m : Nat} {n : Nat} {k : Nat}, Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m n) k) (ite.{1} Nat (LE.le.{0} Nat Nat.hasLe k (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) m k) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) n k))) (Nat.decidableLe k (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) m k) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) n k))) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat Nat.hasSub) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) m k) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) n k)) k) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) m k) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) n k)))
-but is expected to have type
-  forall {m : Nat} {n : Nat} {k : Nat}, Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m n) k) (ite.{1} Nat (LE.le.{0} Nat instLENat k (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) m k) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) n k))) (Nat.decLe k (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) m k) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) n k))) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat instSubNat) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) m k) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) n k)) k) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) m k) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) n k)))
-Case conversion may be inaccurate. Consider using '#align nat.add_mod_eq_ite Nat.add_mod_eq_iteₓ'. -/
 theorem add_mod_eq_ite :
     (m + n) % k = if k ≤ m % k + n % k then m % k + n % k - k else m % k + n % k :=
   by

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -278,8 +278,7 @@ theorem add_pos_iff_pos_or_pos (m n : ℕ) : 0 < m + n ↔ 0 < m ∨ 0 < n :=
     (by
       intro h
       cases' m with m
-      · simp [zero_add] at h
-        exact Or.inr h
+      · simp [zero_add] at h; exact Or.inr h
       exact Or.inl (succ_pos _))
     (by
       intro h; cases' h with mpos npos
@@ -339,10 +338,7 @@ theorem add_succ_lt_add (hab : m < n) (hcd : k < l) : m + k + 1 < n + l :=
 
 #print Nat.pred_le_iff /-
 theorem pred_le_iff : pred m ≤ n ↔ m ≤ succ n :=
-  ⟨le_succ_of_pred_le, by
-    cases m
-    · exact fun _ => zero_le n
-    exact le_of_succ_le_succ⟩
+  ⟨le_succ_of_pred_le, by cases m; · exact fun _ => zero_le n; exact le_of_succ_le_succ⟩
 #align nat.pred_le_iff Nat.pred_le_iff
 -/
 
@@ -375,11 +371,8 @@ theorem le_or_le_of_add_eq_add_pred (h : k + l = m + n - 1) : m ≤ k ∨ n ≤
   by
   cases' le_or_lt m k with h' h' <;> [left;right]
   · exact h'
-  · replace h' := add_lt_add_right h' l
-    rw [h] at h'
-    cases' n.eq_zero_or_pos with hn hn
-    · rw [hn]
-      exact zero_le l
+  · replace h' := add_lt_add_right h' l; rw [h] at h'
+    cases' n.eq_zero_or_pos with hn hn; · rw [hn]; exact zero_le l
     rw [m.add_sub_assoc hn, add_lt_add_iff_left] at h'
     exact Nat.le_of_pred_lt h'
 #align nat.le_or_le_of_add_eq_add_pred Nat.le_or_le_of_add_eq_add_pred
@@ -737,8 +730,7 @@ theorem div_eq_self : m / n = m ↔ m = 0 ∨ n = 1 :=
     cases n
     · simp_all
     · cases n
-      · right
-        rfl
+      · right; rfl
       · left
         have : m / (n + 2) ≤ m / 2 := div_le_div_left (by simp) (by decide)
         refine' eq_zero_of_le_half _
@@ -815,8 +807,7 @@ theorem findGreatest_eq_iff :
     rintro rfl
     exact ⟨fun h => (h rfl).elim, fun n hlt heq => (hlt.Ne HEq.symm).elim⟩
   · by_cases hk : P (k + 1)
-    · rw [find_greatest_eq hk]
-      constructor
+    · rw [find_greatest_eq hk]; constructor
       · rintro rfl
         exact ⟨le_rfl, fun _ => hk, fun n hlt hle => (hlt.not_le hle).elim⟩
       · rintro ⟨hle, h0, hm⟩
@@ -845,8 +836,7 @@ theorem findGreatest_eq_zero_iff : Nat.findGreatest P k = 0 ↔ ∀ ⦃n⦄, 0 <
 theorem findGreatest_spec (hmb : m ≤ n) (hm : P m) : P (Nat.findGreatest P n) :=
   by
   by_cases h : Nat.findGreatest P n = 0
-  · cases m
-    · rwa [h]
+  · cases m; · rwa [h]
     exact ((find_greatest_eq_zero_iff.1 h) m.zero_lt_succ hmb hm).elim
   · exact (find_greatest_eq_iff.1 rfl).2.1 h
 #align nat.find_greatest_spec Nat.findGreatest_spec
@@ -992,17 +982,11 @@ theorem bit1_lt_bit0_iff : bit1 m < bit0 n ↔ m < n :=
 -/
 
 @[simp]
-theorem one_le_bit0_iff : 1 ≤ bit0 n ↔ 0 < n :=
-  by
-  convert bit1_le_bit0_iff
-  rfl
+theorem one_le_bit0_iff : 1 ≤ bit0 n ↔ 0 < n := by convert bit1_le_bit0_iff; rfl
 #align nat.one_le_bit0_iff Nat.one_le_bit0_iff
 
 @[simp]
-theorem one_lt_bit0_iff : 1 < bit0 n ↔ 1 ≤ n :=
-  by
-  convert bit1_lt_bit0_iff
-  rfl
+theorem one_lt_bit0_iff : 1 < bit0 n ↔ 1 ≤ n := by convert bit1_lt_bit0_iff; rfl
 #align nat.one_lt_bit0_iff Nat.one_lt_bit0_iff
 
 @[simp]

bump to nightly-2023-05-24-06

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

fbc7b476

Diff

@@ -373,7 +373,7 @@ theorem lt_of_lt_pred (h : m < n - 1) : m < n :=
 #print Nat.le_or_le_of_add_eq_add_pred /-
 theorem le_or_le_of_add_eq_add_pred (h : k + l = m + n - 1) : m ≤ k ∨ n ≤ l :=
   by
-  cases' le_or_lt m k with h' h' <;> [left, right]
+  cases' le_or_lt m k with h' h' <;> [left;right]
   · exact h'
   · replace h' := add_lt_add_right h' l
     rw [h] at h'

bump to nightly-2023-05-17-14

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

20ad7900

Diff

@@ -262,11 +262,15 @@ theorem add_pos_left {m : ℕ} (h : 0 < m) (n : ℕ) : 0 < m + n :=
 #align nat.add_pos_left Nat.add_pos_left
 -/
 
-#print Nat.add_pos_right /-
+/- warning: nat.add_pos_right -> Nat.add_pos_right is a dubious translation:
+lean 3 declaration is
+  forall (m : Nat) {n : Nat}, (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) n) -> (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m n))
+but is expected to have type
+  forall {m : Nat} (n : Nat), (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) m) -> (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) n m))
+Case conversion may be inaccurate. Consider using '#align nat.add_pos_right Nat.add_pos_rightₓ'. -/
 theorem add_pos_right (m : ℕ) {n : ℕ} (h : 0 < n) : 0 < m + n := by rw [add_comm];
   exact add_pos_left h m
 #align nat.add_pos_right Nat.add_pos_right
--/
 
 #print Nat.add_pos_iff_pos_or_pos /-
 theorem add_pos_iff_pos_or_pos (m n : ℕ) : 0 < m + n ↔ 0 < m ∨ 0 < n :=

bump to nightly-2023-04-06-02

mathlib commit https://github.com/leanprover-community/mathlib/commit/06a655b5fcfbda03502f9158bbf6c0f1400886f9

89485060

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.nat.order.basic
-! leanprover-community/mathlib commit 448144f7ae193a8990cb7473c9e9a01990f64ac7
+! leanprover-community/mathlib commit e8638a0fcaf73e4500469f368ef9494e495099b3
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -86,7 +86,7 @@ instance : CanonicallyOrderedCommSemiring ℕ :=
 instance : CanonicallyLinearOrderedAddMonoid ℕ :=
   { (inferInstance : CanonicallyOrderedAddMonoid ℕ), Nat.linearOrder with }
 
-variable {m n k l : ℕ}
+variable {a b m n k l : ℕ}
 
 namespace Nat
 
@@ -391,22 +391,6 @@ theorem sub_succ' (m n : ℕ) : m - n.succ = m - n - 1 :=
 /-! ### `mul` -/
 
 
-#print Nat.mul_eq_one_iff /-
-theorem mul_eq_one_iff : ∀ {m n : ℕ}, m * n = 1 ↔ m = 1 ∧ n = 1
-  | 0, 0 => by decide
-  | 0, 1 => by decide
-  | 1, 0 => by decide
-  | m + 2, 0 => by simp
-  | 0, n + 2 => by simp
-  | m + 1, n + 1 =>
-    ⟨fun h => by
-      simp only [add_mul, mul_add, mul_add, one_mul, mul_one, (add_assoc _ _ _).symm, Nat.succ_inj',
-          add_eq_zero_iff] at h <;>
-        simp [h.1.2, h.2],
-      fun h => by simp only [h, mul_one]⟩
-#align nat.mul_eq_one_iff Nat.mul_eq_one_iff
--/
-
 #print Nat.succ_mul_pos /-
 theorem succ_mul_pos (m : ℕ) (hn : 0 < n) : 0 < succ m * n :=
   mul_pos (succ_pos m) hn

448144f7

bump to nightly-2023-03-01-20

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

20cadee0

Diff

@@ -256,7 +256,7 @@ theorem lt_one_iff {n : ℕ} : n < 1 ↔ n = 0 :=
 theorem add_pos_left {m : ℕ} (h : 0 < m) (n : ℕ) : 0 < m + n :=
   calc
     m + n > 0 + n := Nat.add_lt_add_right h n
-    _ = n := Nat.zero_add n
+    _ = n := (Nat.zero_add n)
     _ ≥ 0 := zero_le n
     
 #align nat.add_pos_left Nat.add_pos_left
@@ -540,7 +540,7 @@ protected theorem div_le_of_le_mul' (h : m ≤ k * n) : m / k ≤ n :=
     (mul_le_mul_left k0).1 <|
       calc
         k * (m / k) ≤ m % k + k * (m / k) := Nat.le_add_left _ _
-        _ = m := mod_add_div _ _
+        _ = m := (mod_add_div _ _)
         _ ≤ k * n := h
         
 #align nat.div_le_of_le_mul' Nat.div_le_of_le_mul'
@@ -562,7 +562,7 @@ protected theorem div_lt_of_lt_mul (h : m < n * k) : m / n < k :=
   lt_of_mul_lt_mul_left
     (calc
       n * (m / n) ≤ m % n + n * (m / n) := Nat.le_add_left _ _
-      _ = m := mod_add_div _ _
+      _ = m := (mod_add_div _ _)
       _ < n * k := h
       )
     (Nat.zero_le n)

448144f7

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

chore: Move WithZero material depending on GroupWithZero (#12351)

Everything under Algebra.Group should be additivisable. Therefore I move the GroupWithZero instances for WithZero from Algebra.Group.WithOne.Defs and the whole of Algebra.Group.WithOne.Units to a new file Algebra.GroupWithZero.WithZero. I credit Mario for https://github.com/leanprover-community/mathlib/commit/ad92a9ba47f417916aab365d13db653fa8991a84 and Johan for https://github.com/leanprover-community/mathlib/pull/762.

Use the opportunity to slightly clean up the code:

Replace := by where in instance declarations
Add missing explicit arguments to coe lemmas
Add missing section ... end

03b47142

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
 import Mathlib.Algebra.Order.Group.Nat
-import Mathlib.Algebra.Order.Monoid.WithZero
+import Mathlib.Algebra.Order.GroupWithZero.Canonical
 import Mathlib.Algebra.Order.Ring.Canonical
 import Mathlib.Algebra.Ring.Nat

chore: Rename Int and Rat instances (#12235)

Fix a few names and deduplicate the AddCommGroup ℤ instance

de6ffbc2

Diff

@@ -22,18 +22,26 @@ namespace Nat
 
 /-! ### Instances -/
 
-instance linearOrderedCommSemiring : LinearOrderedCommSemiring ℕ :=
-  { Nat.commSemiring, Nat.linearOrder with
-    lt := Nat.lt, add_le_add_left := @Nat.add_le_add_left,
-    le_of_add_le_add_left := @Nat.le_of_add_le_add_left,
-    zero_le_one := Nat.le_of_lt (Nat.zero_lt_succ 0),
-    mul_lt_mul_of_pos_left := @Nat.mul_lt_mul_of_pos_left,
-    mul_lt_mul_of_pos_right := @Nat.mul_lt_mul_of_pos_right,
-    exists_pair_ne := ⟨0, 1, ne_of_lt Nat.zero_lt_one⟩ }
-
-instance linearOrderedCommMonoidWithZero : LinearOrderedCommMonoidWithZero ℕ :=
-  { Nat.linearOrderedCommSemiring, (inferInstance : CommMonoidWithZero ℕ) with
-    mul_le_mul_left := fun _ _ h c => Nat.mul_le_mul_left c h }
+instance instLinearOrderedCommSemiring : LinearOrderedCommSemiring ℕ where
+  __ := instCommSemiring
+  __ := instLinearOrder
+  add_le_add_left := @Nat.add_le_add_left
+  le_of_add_le_add_left := @Nat.le_of_add_le_add_left
+  zero_le_one := Nat.le_of_lt (Nat.zero_lt_succ 0)
+  mul_lt_mul_of_pos_left := @Nat.mul_lt_mul_of_pos_left
+  mul_lt_mul_of_pos_right := @Nat.mul_lt_mul_of_pos_right
+  exists_pair_ne := ⟨0, 1, ne_of_lt Nat.zero_lt_one⟩
+
+instance instLinearOrderedCommMonoidWithZero : LinearOrderedCommMonoidWithZero ℕ where
+  __ := instLinearOrderedCommSemiring
+  __ : CommMonoidWithZero ℕ := inferInstance
+  mul_le_mul_left _ _ h c := Nat.mul_le_mul_left c h
+
+instance instCanonicallyOrderedCommSemiring : CanonicallyOrderedCommSemiring ℕ where
+  __ := instLinearOrderedCommSemiring
+  exists_add_of_le h := (Nat.le.dest h).imp fun _ => Eq.symm
+  le_self_add := Nat.le_add_right
+  eq_zero_or_eq_zero_of_mul_eq_zero := Nat.eq_zero_of_mul_eq_zero
 
 /-!
 ### Extra instances to short-circuit type class resolution
@@ -41,26 +49,11 @@ instance linearOrderedCommMonoidWithZero : LinearOrderedCommMonoidWithZero ℕ :
 These also prevent non-computable instances being used to construct these instances non-computably.
 -/
 
-instance linearOrderedSemiring : LinearOrderedSemiring ℕ :=
-  inferInstance
-
-instance strictOrderedSemiring : StrictOrderedSemiring ℕ :=
-  inferInstance
-
-instance strictOrderedCommSemiring : StrictOrderedCommSemiring ℕ :=
-  inferInstance
-
-instance orderedSemiring : OrderedSemiring ℕ :=
-  StrictOrderedSemiring.toOrderedSemiring'
-
-instance orderedCommSemiring : OrderedCommSemiring ℕ :=
+instance instLinearOrderedSemiring : LinearOrderedSemiring ℕ := inferInstance
+instance instStrictOrderedSemiring : StrictOrderedSemiring ℕ := inferInstance
+instance instStrictOrderedCommSemiring : StrictOrderedCommSemiring ℕ := inferInstance
+instance instOrderedSemiring : OrderedSemiring ℕ := StrictOrderedSemiring.toOrderedSemiring'
+instance instOrderedCommSemiring : OrderedCommSemiring ℕ :=
   StrictOrderedCommSemiring.toOrderedCommSemiring'
 
-instance canonicallyOrderedCommSemiring : CanonicallyOrderedCommSemiring ℕ :=
-  { Nat.nontrivial, Nat.orderBot, (inferInstance : OrderedAddCommMonoid ℕ),
-    (inferInstance : LinearOrderedSemiring ℕ), (inferInstance : CommSemiring ℕ) with
-    exists_add_of_le := fun {_ _} h => (Nat.le.dest h).imp fun _ => Eq.symm,
-    le_self_add := Nat.le_add_right,
-    eq_zero_or_eq_zero_of_mul_eq_zero := Nat.eq_zero_of_mul_eq_zero }
-
 end Nat

chore: Rename Int and Rat instances (#12235)

Fix a few names and deduplicate the AddCommGroup ℤ instance

de6ffbc2

Diff

@@ -22,21 +22,20 @@ namespace Nat
 
 /-! ### Instances -/
 
-instance canonicallyLinearOrderedAddCommMonoid : CanonicallyLinearOrderedAddCommMonoid ℕ where
-  __ := linearOrder
+instance instCanonicallyLinearOrderedAddCommMonoid : CanonicallyLinearOrderedAddCommMonoid ℕ where
+  __ := instLinearOrder
   bot := 0
   bot_le := Nat.zero_le
   add_le_add_left := @Nat.add_le_add_left
   le_self_add := Nat.le_add_right
   exists_add_of_le := Nat.exists_eq_add_of_le
 
-instance linearOrderedCommMonoid : LinearOrderedCommMonoid ℕ where
-  __ := linearOrder
-  __ := commMonoid
+instance instLinearOrderedCommMonoid : LinearOrderedCommMonoid ℕ where
+  __ := instLinearOrder
   mul_le_mul_left _ _ h _ := mul_le_mul_left _ h
 
-instance linearOrderedCancelAddCommMonoid : LinearOrderedCancelAddCommMonoid ℕ where
-  __ := linearOrder
+instance instLinearOrderedCancelAddCommMonoid : LinearOrderedCancelAddCommMonoid ℕ where
+  __ := instLinearOrder
   add_le_add_left := @Nat.add_le_add_left
   le_of_add_le_add_left := @Nat.le_of_add_le_add_left
 
@@ -52,8 +51,8 @@ instance instOrderedSub : OrderedSub ℕ := by
 These also prevent non-computable instances being used to construct these instances non-computably.
 -/
 
-instance orderBot : OrderBot ℕ := by infer_instance
-#align nat.order_bot Nat.orderBot
+instance instOrderBot : OrderBot ℕ := by infer_instance
+#align nat.order_bot Nat.instOrderBot
 
 /-! ### Miscellaneous lemmas -/

chore: Split Data.{Nat,Int}{.Order}.Basic in group vs ring instances (#11924)

Scatter the content of Data.Nat.Basic across:

Data.Nat.Defs for the lemmas having no dependencies
Algebra.Group.Nat for the monoid instances and the few miscellaneous lemmas needing them.
Algebra.Ring.Nat for the semiring instance and the few miscellaneous lemmas following it.

Similarly, scatter

Data.Int.Basic across Data.Int.Defs, Algebra.Group.Int, Algebra.Ring.Int
Data.Nat.Order.Basic across Data.Nat.Defs, Algebra.Order.Group.Nat, Algebra.Order.Ring.Nat
Data.Int.Order.Basic across Data.Int.Defs, Algebra.Order.Group.Int, Algebra.Order.Ring.Int

Also move a few lemmas from Data.Nat.Order.Lemmas to Data.Nat.Defs.

Before pre_11924

After post_11924

47062a71

Diff

@@ -3,44 +3,24 @@ Copyright (c) 2014 Floris van Doorn (c) 2016 Microsoft Corporation. All rights r
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
+import Mathlib.Algebra.Order.Group.Nat
 import Mathlib.Algebra.Order.Monoid.WithZero
 import Mathlib.Algebra.Order.Ring.Canonical
-import Mathlib.Data.Nat.Basic
+import Mathlib.Algebra.Ring.Nat
 
 #align_import data.nat.order.basic from "leanprover-community/mathlib"@"3ed3f98a1e836241990d3d308f1577e434977130"
 
 /-!
-# Algebraic order instances for the natural numbers
+# The natural numbers form an ordered semiring
 
-This file contains algebraic order instances on the natural numbers and a few lemmas about them.
+This file contains the commutative linear orderded semiring instance on the natural numbers.
 
-## Implementation note
-
-Std has a home-baked development of the algebraic and order theoretic theory of `ℕ` which, in
-particular, is not typeclass-mediated. This is useful to set up the algebra and finiteness libraries
-in mathlib (naturals show up as indices in lists, cardinality in finsets, powers in groups, ...).
-This home-baked development is pursued in `Data.Nat.Defs`.
-
-Less basic uses of `ℕ` should however use the typeclass-mediated development. `Data.Nat.Basic` gives
-access to the algebraic instances. The current file is the one giving access to the algebraic
-order instances.
-
-## TODO
-
-The names of this file, `Data.Nat.Defs` and `Data.Nat.Basic` are archaic and don't match up with
-reality anymore. Rename them.
+See note [foundational algebra order theory].
 -/
 
-universe u v
-
 namespace Nat
 
-/-! ### instances -/
-
-instance orderBot : OrderBot ℕ where
-  bot := 0
-  bot_le := Nat.zero_le
-#align nat.order_bot Nat.orderBot
+/-! ### Instances -/
 
 instance linearOrderedCommSemiring : LinearOrderedCommSemiring ℕ :=
   { Nat.commSemiring, Nat.linearOrder with
@@ -55,10 +35,12 @@ instance linearOrderedCommMonoidWithZero : LinearOrderedCommMonoidWithZero ℕ :
   { Nat.linearOrderedCommSemiring, (inferInstance : CommMonoidWithZero ℕ) with
     mul_le_mul_left := fun _ _ h c => Nat.mul_le_mul_left c h }
 
-/-! Extra instances to short-circuit type class resolution and ensure computability -/
+/-!
+### Extra instances to short-circuit type class resolution
 
+These also prevent non-computable instances being used to construct these instances non-computably.
+-/
 
--- Not using `inferInstance` avoids `Classical.choice` in the following two
 instance linearOrderedSemiring : LinearOrderedSemiring ℕ :=
   inferInstance
 
@@ -74,9 +56,6 @@ instance orderedSemiring : OrderedSemiring ℕ :=
 instance orderedCommSemiring : OrderedCommSemiring ℕ :=
   StrictOrderedCommSemiring.toOrderedCommSemiring'
 
-instance linearOrderedCancelAddCommMonoid : LinearOrderedCancelAddCommMonoid ℕ :=
-  inferInstance
-
 instance canonicallyOrderedCommSemiring : CanonicallyOrderedCommSemiring ℕ :=
   { Nat.nontrivial, Nat.orderBot, (inferInstance : OrderedAddCommMonoid ℕ),
     (inferInstance : LinearOrderedSemiring ℕ), (inferInstance : CommSemiring ℕ) with
@@ -84,16 +63,4 @@ instance canonicallyOrderedCommSemiring : CanonicallyOrderedCommSemiring ℕ :=
     le_self_add := Nat.le_add_right,
     eq_zero_or_eq_zero_of_mul_eq_zero := Nat.eq_zero_of_mul_eq_zero }
 
-instance canonicallyLinearOrderedAddCommMonoid : CanonicallyLinearOrderedAddCommMonoid ℕ :=
-  { (inferInstance : CanonicallyOrderedAddCommMonoid ℕ), Nat.linearOrder with }
-
-instance : OrderedSub ℕ := by
-  constructor
-  intro m n k
-  induction' n with n ih generalizing k
-  · simp
-  · simp only [sub_succ, pred_le_iff, ih, succ_add, add_succ]
-
-theorem _root_.NeZero.one_le {n : ℕ} [NeZero n] : 1 ≤ n := one_le_iff_ne_zero.mpr (NeZero.ne n)
-
 end Nat

chore: Split Data.{Nat,Int}{.Order}.Basic in group vs ring instances (#11924)

Scatter the content of Data.Nat.Basic across:

Data.Nat.Defs for the lemmas having no dependencies
Algebra.Group.Nat for the monoid instances and the few miscellaneous lemmas needing them.
Algebra.Ring.Nat for the semiring instance and the few miscellaneous lemmas following it.

Similarly, scatter

Data.Int.Basic across Data.Int.Defs, Algebra.Group.Int, Algebra.Ring.Int
Data.Nat.Order.Basic across Data.Nat.Defs, Algebra.Order.Group.Nat, Algebra.Order.Ring.Nat
Data.Int.Order.Basic across Data.Int.Defs, Algebra.Order.Group.Int, Algebra.Order.Ring.Int

Also move a few lemmas from Data.Nat.Order.Lemmas to Data.Nat.Defs.

Before pre_11924

After post_11924

47062a71

chore: Reduce scope of LinearOrderedCommGroupWithZero (#11716)

Reconstitute the file Algebra.Order.Monoid.WithZero from three files:

Algebra.Order.Monoid.WithZero.Defs
Algebra.Order.Monoid.WithZero.Basic
Algebra.Order.WithZero

Avoid importing it in many files. Most uses were just to get le_zero_iff to work on Nat.

Before pre_11716

After post_11716

bb349f30

Diff

@@ -3,6 +3,7 @@ Copyright (c) 2014 Floris van Doorn (c) 2016 Microsoft Corporation. All rights r
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
+import Mathlib.Algebra.Order.Monoid.WithZero
 import Mathlib.Algebra.Order.Ring.Canonical
 import Mathlib.Data.Nat.Basic

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

@@ -5,22 +5,30 @@ Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
 import Mathlib.Algebra.Order.Ring.Canonical
 import Mathlib.Data.Nat.Basic
-import Mathlib.Init.Data.Nat.Bitwise
 
 #align_import data.nat.order.basic from "leanprover-community/mathlib"@"3ed3f98a1e836241990d3d308f1577e434977130"
 
-
 /-!
-# The natural numbers as a linearly ordered commutative semiring
+# Algebraic order instances for the natural numbers
 
-We also have a variety of lemmas which have been deferred from `Data.Nat.Basic` because it is
-easier to prove them with this ordered semiring instance available.
+This file contains algebraic order instances on the natural numbers and a few lemmas about them.
 
-### TODO
+## Implementation note
 
-Move most of the theorems to `Data.Nat.Defs` by modifying their proofs.
--/
+Std has a home-baked development of the algebraic and order theoretic theory of `ℕ` which, in
+particular, is not typeclass-mediated. This is useful to set up the algebra and finiteness libraries
+in mathlib (naturals show up as indices in lists, cardinality in finsets, powers in groups, ...).
+This home-baked development is pursued in `Data.Nat.Defs`.
+
+Less basic uses of `ℕ` should however use the typeclass-mediated development. `Data.Nat.Basic` gives
+access to the algebraic instances. The current file is the one giving access to the algebraic
+order instances.
 
+## TODO
+
+The names of this file, `Data.Nat.Defs` and `Data.Nat.Basic` are archaic and don't match up with
+reality anymore. Rename them.
+-/
 
 universe u v
 
@@ -78,137 +86,6 @@ instance canonicallyOrderedCommSemiring : CanonicallyOrderedCommSemiring ℕ :=
 instance canonicallyLinearOrderedAddCommMonoid : CanonicallyLinearOrderedAddCommMonoid ℕ :=
   { (inferInstance : CanonicallyOrderedAddCommMonoid ℕ), Nat.linearOrder with }
 
-variable {m n k l : ℕ}
-
-/-! ### Equalities and inequalities involving zero and one -/
-
-theorem _root_.NeZero.one_le [NeZero n] : 1 ≤ n := one_le_iff_ne_zero.mpr (NeZero.ne n)
-
-#align nat.mul_ne_zero Nat.mul_ne_zero
-
--- Porting note: already in Std
-#align nat.mul_eq_zero Nat.mul_eq_zero
-
--- Porting note: removing `simp` attribute
-protected theorem zero_eq_mul : 0 = m * n ↔ m = 0 ∨ n = 0 := by rw [eq_comm, Nat.mul_eq_zero]
-#align nat.zero_eq_mul Nat.zero_eq_mul
-
-theorem eq_zero_of_double_le (h : 2 * n ≤ n) : n = 0 :=
-  add_right_eq_self.mp <| le_antisymm ((two_mul n).symm.trans_le h) le_add_self
-#align nat.eq_zero_of_double_le Nat.eq_zero_of_double_le
-
-theorem eq_zero_of_mul_le (hb : 2 ≤ n) (h : n * m ≤ m) : m = 0 :=
-  eq_zero_of_double_le <| le_trans (Nat.mul_le_mul_right _ hb) h
-#align nat.eq_zero_of_mul_le Nat.eq_zero_of_mul_le
-
-#align nat.zero_max Nat.zero_max
-
-@[simp]
-theorem min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 := min_eq_bot
-#align nat.min_eq_zero_iff Nat.min_eq_zero_iff
-
-@[simp]
-theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 := max_eq_bot
-#align nat.max_eq_zero_iff Nat.max_eq_zero_iff
-
-theorem add_eq_max_iff : m + n = max m n ↔ m = 0 ∨ n = 0 := by
-  rw [← min_eq_zero_iff]
-  rcases le_total m n with H | H <;> simp [H]
-#align nat.add_eq_max_iff Nat.add_eq_max_iff
-
-theorem add_eq_min_iff : m + n = min m n ↔ m = 0 ∧ n = 0 := by
-  rw [← max_eq_zero_iff]
-  rcases le_total m n with H | H <;> simp [H]
-#align nat.add_eq_min_iff Nat.add_eq_min_iff
-
-theorem one_le_of_lt (h : n < m) : 1 ≤ m :=
-  lt_of_le_of_lt (Nat.zero_le _) h
-#align nat.one_le_of_lt Nat.one_le_of_lt
-
-theorem eq_one_of_mul_eq_one_right (H : m * n = 1) : m = 1 :=
-  eq_one_of_dvd_one ⟨n, H.symm⟩
-#align nat.eq_one_of_mul_eq_one_right Nat.eq_one_of_mul_eq_one_right
-
-theorem eq_one_of_mul_eq_one_left (H : m * n = 1) : n = 1 :=
-  eq_one_of_mul_eq_one_right (by rwa [mul_comm])
-#align nat.eq_one_of_mul_eq_one_left Nat.eq_one_of_mul_eq_one_left
-
-/-! ### `succ` -/
-
-
-theorem two_le_iff : ∀ n, 2 ≤ n ↔ n ≠ 0 ∧ n ≠ 1
-  | 0 => by simp
-  | 1 => by simp
-  | n + 2 => by simp
-#align nat.two_le_iff Nat.two_le_iff
-
-@[simp]
-theorem lt_one_iff {n : ℕ} : n < 1 ↔ n = 0 :=
-  Nat.lt_succ_iff.trans nonpos_iff_eq_zero
-#align nat.lt_one_iff Nat.lt_one_iff
-
-/-! ### `add` -/
-
-#align nat.add_pos_left Nat.add_pos_left
-#align nat.add_pos_right Nat.add_pos_right
-
-theorem add_pos_iff_pos_or_pos (m n : ℕ) : 0 < m + n ↔ 0 < m ∨ 0 < n :=
-  Iff.intro
-    (by
-      intro h
-      cases' m with m
-      · simp [zero_add] at h
-        exact Or.inr h
-      exact Or.inl (succ_pos _))
-    (by
-      intro h; cases' h with mpos npos
-      · apply Nat.add_pos_left mpos
-      apply Nat.add_pos_right _ npos)
-#align nat.add_pos_iff_pos_or_pos Nat.add_pos_iff_pos_or_pos
-
-theorem add_eq_one_iff : m + n = 1 ↔ m = 0 ∧ n = 1 ∨ m = 1 ∧ n = 0 := by
-  cases n <;> simp [succ_eq_add_one, ← add_assoc, succ_inj']
-#align nat.add_eq_one_iff Nat.add_eq_one_iff
-
-theorem add_eq_two_iff : m + n = 2 ↔ m = 0 ∧ n = 2 ∨ m = 1 ∧ n = 1 ∨ m = 2 ∧ n = 0 := by
-  omega
-#align nat.add_eq_two_iff Nat.add_eq_two_iff
-
-theorem add_eq_three_iff :
-    m + n = 3 ↔ m = 0 ∧ n = 3 ∨ m = 1 ∧ n = 2 ∨ m = 2 ∧ n = 1 ∨ m = 3 ∧ n = 0 := by
-  omega
-#align nat.add_eq_three_iff Nat.add_eq_three_iff
-
-theorem le_add_one_iff : m ≤ n + 1 ↔ m ≤ n ∨ m = n + 1 := by
-  rw [le_iff_lt_or_eq, lt_add_one_iff]
-#align nat.le_add_one_iff Nat.le_add_one_iff
-
-theorem le_and_le_add_one_iff : n ≤ m ∧ m ≤ n + 1 ↔ m = n ∨ m = n + 1 := by
-  rw [le_add_one_iff, and_or_left, ← le_antisymm_iff, eq_comm, and_iff_right_of_imp]
-  rintro rfl
-  exact n.le_succ
-#align nat.le_and_le_add_one_iff Nat.le_and_le_add_one_iff
-
-theorem add_succ_lt_add (hab : m < n) (hcd : k < l) : m + k + 1 < n + l := by
-  rw [add_assoc]
-  exact add_lt_add_of_lt_of_le hab (Nat.succ_le_iff.2 hcd)
-#align nat.add_succ_lt_add Nat.add_succ_lt_add
-
-/-! ### `pred` -/
-
-
-theorem pred_le_iff : pred m ≤ n ↔ m ≤ succ n :=
-  ⟨le_succ_of_pred_le, by
-    cases m
-    · exact fun _ => zero_le n
-    exact le_of_succ_le_succ⟩
-#align nat.pred_le_iff Nat.pred_le_iff
-
-/-! ### `sub`
-
-Most lemmas come from the `OrderedSub` instance on `ℕ`. -/
-
-
 instance : OrderedSub ℕ := by
   constructor
   intro m n k
@@ -216,514 +93,6 @@ instance : OrderedSub ℕ := by
   · simp
   · simp only [sub_succ, pred_le_iff, ih, succ_add, add_succ]
 
-theorem lt_pred_iff : n < pred m ↔ succ n < m :=
-  show n < m - 1 ↔ n + 1 < m from lt_tsub_iff_right
-#align nat.lt_pred_iff Nat.lt_pred_iff
-
-theorem lt_of_lt_pred (h : m < n - 1) : m < n :=
-  lt_of_succ_lt (lt_pred_iff.1 h)
-#align nat.lt_of_lt_pred Nat.lt_of_lt_pred
-
-theorem le_or_le_of_add_eq_add_pred (h : k + l = m + n - 1) : m ≤ k ∨ n ≤ l := by
-  rcases le_or_lt m k with h' | h' <;> [left; right]
-  · exact h'
-  · replace h' := add_lt_add_right h' l
-    rw [h] at h'
-    rcases n.eq_zero_or_pos with hn | hn
-    · rw [hn]
-      exact zero_le l
-    rw [n.add_sub_assoc (Nat.succ_le_of_lt hn), add_lt_add_iff_left] at h'
-    exact Nat.le_of_pred_lt h'
-#align nat.le_or_le_of_add_eq_add_pred Nat.le_or_le_of_add_eq_add_pred
-
-/-- A version of `Nat.sub_succ` in the form `_ - 1` instead of `Nat.pred _`. -/
-theorem sub_succ' (m n : ℕ) : m - n.succ = m - n - 1 :=
-  rfl
-#align nat.sub_succ' Nat.sub_succ'
-
-/-! ### `mul` -/
-
-theorem succ_mul_pos (m : ℕ) (hn : 0 < n) : 0 < succ m * n :=
-  mul_pos (succ_pos m) hn
-#align nat.succ_mul_pos Nat.succ_mul_pos
-
-theorem mul_self_le_mul_self (h : m ≤ n) : m * m ≤ n * n :=
-  mul_le_mul h h (zero_le _) (zero_le _)
-#align nat.mul_self_le_mul_self Nat.mul_self_le_mul_self
-
-theorem mul_self_lt_mul_self : ∀ {m n : ℕ}, m < n → m * m < n * n
-  | 0, _, h => mul_pos h h
-  | succ _, _, h => mul_lt_mul h (le_of_lt h) (succ_pos _) (zero_le _)
-#align nat.mul_self_lt_mul_self Nat.mul_self_lt_mul_self
-
-theorem mul_self_le_mul_self_iff : m ≤ n ↔ m * m ≤ n * n :=
-  ⟨mul_self_le_mul_self, le_imp_le_of_lt_imp_lt mul_self_lt_mul_self⟩
-#align nat.mul_self_le_mul_self_iff Nat.mul_self_le_mul_self_iff
-
-theorem mul_self_lt_mul_self_iff : m < n ↔ m * m < n * n :=
-  le_iff_le_iff_lt_iff_lt.1 mul_self_le_mul_self_iff
-#align nat.mul_self_lt_mul_self_iff Nat.mul_self_lt_mul_self_iff
-
-theorem le_mul_self : ∀ n : ℕ, n ≤ n * n
-  | 0 => le_rfl
-  | n + 1 => by simp
-#align nat.le_mul_self Nat.le_mul_self
-
--- Moved to Std
-#align nat.le_mul_of_pos_left Nat.le_mul_of_pos_left
-
--- Moved to Std
-#align nat.le_mul_of_pos_right Nat.le_mul_of_pos_right
-
-theorem mul_self_inj : m * m = n * n ↔ m = n :=
-  le_antisymm_iff.trans
-    (le_antisymm_iff.trans (and_congr mul_self_le_mul_self_iff mul_self_le_mul_self_iff)).symm
-#align nat.mul_self_inj Nat.mul_self_inj
-
-theorem le_add_pred_of_pos (n : ℕ) {i : ℕ} (hi : i ≠ 0) : n ≤ i + (n - 1) := by
-  refine le_trans ?_ add_tsub_le_assoc
-  simp [add_comm, Nat.add_sub_assoc, one_le_iff_ne_zero.2 hi]
-#align nat.le_add_pred_of_pos Nat.le_add_pred_of_pos
-
-@[simp]
-theorem lt_mul_self_iff : ∀ {n : ℕ}, n < n * n ↔ 1 < n
-  | 0 => iff_of_false (lt_irrefl _) zero_le_one.not_lt
-  | n + 1 => lt_mul_iff_one_lt_left n.succ_pos
-#align nat.lt_mul_self_iff Nat.lt_mul_self_iff
-
-theorem add_sub_one_le_mul (hm : m ≠ 0) (hn : n ≠ 0) : m + n - 1 ≤ m * n := by
-  cases m
-  · cases hm rfl
-  · rw [succ_add, Nat.add_one_sub_one, succ_mul]
-    exact add_le_add_right (le_mul_of_one_le_right' <| succ_le_iff.2 <| pos_iff_ne_zero.2 hn) _
-#align nat.add_sub_one_le_mul Nat.add_sub_one_le_mul
-
-/-!
-### Recursion and induction principles
-
-This section is here due to dependencies -- the lemmas here require some of the lemmas
-proved above, and some of the results in later sections depend on the definitions in this section.
--/
-
-
-/-- Given a predicate on two naturals `P : ℕ → ℕ → Prop`, `P a b` is true for all `a < b` if
-`P (a + 1) (a + 1)` is true for all `a`, `P 0 (b + 1)` is true for all `b` and for all
-`a < b`, `P (a + 1) b` is true and `P a (b + 1)` is true implies `P (a + 1) (b + 1)` is true. -/
-@[elab_as_elim]
-theorem diag_induction (P : ℕ → ℕ → Prop) (ha : ∀ a, P (a + 1) (a + 1)) (hb : ∀ b, P 0 (b + 1))
-    (hd : ∀ a b, a < b → P (a + 1) b → P a (b + 1) → P (a + 1) (b + 1)) : ∀ a b, a < b → P a b
-  | 0, b + 1, _ => hb _
-  | a + 1, b + 1, h => by
-    apply hd _ _ ((add_lt_add_iff_right _).1 h)
-    · have this : a + 1 = b ∨ a + 1 < b := by rwa [← le_iff_eq_or_lt, ← Nat.lt_succ_iff]
-      have wf : (a + 1) + b < (a + 1) + (b + 1) := by simp
-      rcases this with (rfl | h)
-      · exact ha _
-      apply diag_induction P ha hb hd (a + 1) b h
-    have _ : a + (b + 1) < (a + 1) + (b + 1) := by simp
-    apply diag_induction P ha hb hd a (b + 1)
-    apply lt_of_le_of_lt (Nat.le_succ _) h
-  termination_by a b _c => a + b
-  decreasing_by all_goals assumption
-#align nat.diag_induction Nat.diag_induction
-
-/-- A subset of `ℕ` containing `k : ℕ` and closed under `Nat.succ` contains every `n ≥ k`. -/
-theorem set_induction_bounded {S : Set ℕ} (hk : k ∈ S) (h_ind : ∀ k : ℕ, k ∈ S → k + 1 ∈ S)
-    (hnk : k ≤ n) : n ∈ S :=
-  @leRecOn (fun n => n ∈ S) k n hnk @h_ind hk
-#align nat.set_induction_bounded Nat.set_induction_bounded
-
-/-- A subset of `ℕ` containing zero and closed under `Nat.succ` contains all of `ℕ`. -/
-theorem set_induction {S : Set ℕ} (hb : 0 ∈ S) (h_ind : ∀ k : ℕ, k ∈ S → k + 1 ∈ S) (n : ℕ) :
-    n ∈ S :=
-  set_induction_bounded hb h_ind (zero_le n)
-#align nat.set_induction Nat.set_induction
-
-/-! ### `div` -/
-
-
-protected theorem div_le_of_le_mul' (h : m ≤ k * n) : m / k ≤ n :=
-  (Nat.eq_zero_or_pos k).elim (fun k0 => by rw [k0, Nat.div_zero]; apply zero_le) fun k0 =>
-    le_of_mul_le_mul_left
-      (calc
-        k * (m / k) ≤ m % k + k * (m / k) := Nat.le_add_left _ _
-        _ = m := mod_add_div _ _
-        _ ≤ k * n := h) k0
-#align nat.div_le_of_le_mul' Nat.div_le_of_le_mul'
-
-protected theorem div_le_self' (m n : ℕ) : m / n ≤ m :=
-  (Nat.eq_zero_or_pos n).elim (fun n0 => by rw [n0, Nat.div_zero]; apply zero_le) fun n0 =>
-    Nat.div_le_of_le_mul' <|
-      calc
-        m = 1 * m := (one_mul _).symm
-        _ ≤ n * m := Nat.mul_le_mul_right _ n0
-#align nat.div_le_self' Nat.div_le_self'
-
-#align nat.div_lt_of_lt_mul Nat.div_lt_of_lt_mul
-
-theorem eq_zero_of_le_div (hn : 2 ≤ n) (h : m ≤ m / n) : m = 0 :=
-  eq_zero_of_mul_le hn <| by
-    rw [mul_comm]; exact (Nat.le_div_iff_mul_le' (lt_of_lt_of_le (by decide) hn)).1 h
-#align nat.eq_zero_of_le_div Nat.eq_zero_of_le_div
-
-theorem div_mul_div_le_div (m n k : ℕ) : m / k * n / m ≤ n / k :=
-  if hm0 : m = 0 then by simp [hm0]
-  else
-    calc
-      m / k * n / m ≤ n * m / k / m :=
-        Nat.div_le_div_right (by rw [mul_comm]; exact mul_div_le_mul_div_assoc _ _ _)
-      _ = n / k := by
-        { rw [Nat.div_div_eq_div_mul, mul_comm n, mul_comm k,
-            Nat.mul_div_mul_left _ _ (Nat.pos_of_ne_zero hm0)] }
-#align nat.div_mul_div_le_div Nat.div_mul_div_le_div
-
-theorem eq_zero_of_le_half (h : n ≤ n / 2) : n = 0 :=
-  eq_zero_of_le_div le_rfl h
-#align nat.eq_zero_of_le_half Nat.eq_zero_of_le_half
-
-theorem mul_div_mul_comm_of_dvd_dvd (hmk : k ∣ m) (hnl : l ∣ n) :
-    m * n / (k * l) = m / k * (n / l) := by
-  rcases k.eq_zero_or_pos with (rfl | hk0); · simp
-  rcases l.eq_zero_or_pos with (rfl | hl0); · simp
-  obtain ⟨_, rfl⟩ := hmk
-  obtain ⟨_, rfl⟩ := hnl
-  rw [mul_mul_mul_comm, Nat.mul_div_cancel_left _ hk0, Nat.mul_div_cancel_left _ hl0,
-    Nat.mul_div_cancel_left _ (mul_pos hk0 hl0)]
-#align nat.mul_div_mul_comm_of_dvd_dvd Nat.mul_div_mul_comm_of_dvd_dvd
-
-theorem le_half_of_half_lt_sub {a b : ℕ} (h : a / 2 < a - b) : b ≤ a / 2 := by
-  rw [Nat.le_div_iff_mul_le two_pos]
-  rw [Nat.div_lt_iff_lt_mul two_pos, Nat.mul_sub_right_distrib, lt_tsub_iff_right, mul_two a] at h
-  exact le_of_lt (Nat.lt_of_add_lt_add_left h)
-#align nat.le_half_of_half_lt_sub Nat.le_half_of_half_lt_sub
-
-theorem half_le_of_sub_le_half {a b : ℕ} (h : a - b ≤ a / 2) : a / 2 ≤ b := by
-  rw [Nat.le_div_iff_mul_le two_pos, Nat.mul_sub_right_distrib, tsub_le_iff_right, mul_two,
-    add_le_add_iff_left] at h
-  rw [← Nat.mul_div_left b two_pos]
-  exact Nat.div_le_div_right h
-#align nat.half_le_of_sub_le_half Nat.half_le_of_sub_le_half
-
-/-! ### `mod`, `dvd` -/
-
-
-theorem two_mul_odd_div_two (hn : n % 2 = 1) : 2 * (n / 2) = n - 1 := by
-  conv =>
-    rhs
-    rw [← Nat.mod_add_div n 2, hn, @add_tsub_cancel_left]
-#align nat.two_mul_odd_div_two Nat.two_mul_odd_div_two
-
-theorem div_dvd_of_dvd (h : n ∣ m) : m / n ∣ m :=
-  ⟨n, (Nat.div_mul_cancel h).symm⟩
-#align nat.div_dvd_of_dvd Nat.div_dvd_of_dvd
-
-protected theorem div_div_self (h : n ∣ m) (hm : m ≠ 0) : m / (m / n) = n := by
-  rcases h with ⟨_, rfl⟩
-  rw [mul_ne_zero_iff] at hm
-  rw [mul_div_right _ (Nat.pos_of_ne_zero hm.1), mul_div_left _ (Nat.pos_of_ne_zero hm.2)]
-#align nat.div_div_self Nat.div_div_self
-
-#align nat.mod_mul_right_div_self Nat.mod_mul_right_div_self
-#align nat.mod_mul_left_div_self Nat.mod_mul_left_div_self
-
-theorem not_dvd_of_pos_of_lt (h1 : 0 < n) (h2 : n < m) : ¬m ∣ n := by
-  rintro ⟨k, rfl⟩
-  rcases Nat.eq_zero_or_pos k with (rfl | hk)
-  · exact lt_irrefl 0 h1
-  · exact not_lt.2 (Nat.le_mul_of_pos_right _ hk) h2
-#align nat.not_dvd_of_pos_of_lt Nat.not_dvd_of_pos_of_lt
-
-/-- If `m` and `n` are equal mod `k`, `m - n` is zero mod `k`. -/
-theorem sub_mod_eq_zero_of_mod_eq (h : m % k = n % k) : (m - n) % k = 0 := by
-  rw [← Nat.mod_add_div m k, ← Nat.mod_add_div n k, ← h, tsub_add_eq_tsub_tsub,
-    @add_tsub_cancel_left, ← mul_tsub k, Nat.mul_mod_right]
-#align nat.sub_mod_eq_zero_of_mod_eq Nat.sub_mod_eq_zero_of_mod_eq
-
-@[simp]
-theorem one_mod (n : ℕ) : 1 % (n + 2) = 1 :=
-  Nat.mod_eq_of_lt (add_lt_add_right n.succ_pos 1)
-#align nat.one_mod Nat.one_mod
-
-theorem one_mod_of_ne_one : ∀ {n : ℕ}, n ≠ 1 → 1 % n = 1
-  | 0, _ | (n + 2), _ => by simp
-
-theorem dvd_sub_mod (k : ℕ) : n ∣ k - k % n :=
-  ⟨k / n, tsub_eq_of_eq_add_rev (Nat.mod_add_div k n).symm⟩
-#align nat.dvd_sub_mod Nat.dvd_sub_mod
-
-theorem add_mod_eq_ite :
-    (m + n) % k = if k ≤ m % k + n % k then m % k + n % k - k else m % k + n % k := by
-  cases k; simp only [zero_eq, mod_zero, _root_.zero_le, ↓reduceIte, tsub_zero]
-  rw [Nat.add_mod]
-  split_ifs with h
-  · rw [Nat.mod_eq_sub_mod h, Nat.mod_eq_of_lt]
-    exact
-      (tsub_lt_iff_right h).mpr (Nat.add_lt_add (m.mod_lt (zero_lt_succ _))
-        (n.mod_lt (zero_lt_succ _)))
-  · exact Nat.mod_eq_of_lt (lt_of_not_ge h)
-#align nat.add_mod_eq_ite Nat.add_mod_eq_ite
-
-theorem div_eq_self : m / n = m ↔ m = 0 ∨ n = 1 := by
-  constructor
-  · intro
-    match n with
-    | 0 => simp_all
-    | 1 =>
-      right
-      rfl
-    | n+2 =>
-      left
-      have : m / (n + 2) ≤ m / 2 := div_le_div_left (by simp) (by decide)
-      refine eq_zero_of_le_half ?_
-      simp_all
-  · rintro (rfl | rfl) <;> simp
-#align nat.div_eq_self Nat.div_eq_self
-
-theorem div_eq_sub_mod_div : m / n = (m - m % n) / n := by
-  by_cases n0 : n = 0
-  · rw [n0, Nat.div_zero, Nat.div_zero]
-  · have : m - m % n = n * (m / n) := by
-      rw [tsub_eq_iff_eq_add_of_le (Nat.mod_le _ _), add_comm, mod_add_div]
-    rw [this, mul_div_right _ (Nat.pos_of_ne_zero n0)]
-#align nat.div_eq_sub_mod_div Nat.div_eq_sub_mod_div
-
-/-- `m` is not divisible by `n` if it is between `n * k` and `n * (k + 1)` for some `k`. -/
-theorem not_dvd_of_between_consec_multiples (h1 : n * k < m) (h2 : m < n * (k + 1)) : ¬n ∣ m := by
-  rintro ⟨d, rfl⟩
-  exact Monotone.ne_of_lt_of_lt_nat (Covariant.monotone_of_const n) k h1 h2 d rfl
-#align nat.not_dvd_of_between_consec_multiples Nat.not_dvd_of_between_consec_multiples
-
-/-! ### `find` -/
-
-
-section Find
-
-variable {p q : ℕ → Prop} [DecidablePred p] [DecidablePred q]
-
--- Porting note (#10618): removing `simp` attribute as `simp` can prove it
-theorem find_pos (h : ∃ n : ℕ, p n) : 0 < Nat.find h ↔ ¬p 0 := by
-  rw [pos_iff_ne_zero, Ne, Nat.find_eq_zero]
-#align nat.find_pos Nat.find_pos
-
-theorem find_add {hₘ : ∃ m, p (m + n)} {hₙ : ∃ n, p n} (hn : n ≤ Nat.find hₙ) :
-    Nat.find hₘ + n = Nat.find hₙ := by
-  refine ((le_find_iff _ _).2 fun m hm hpm => hm.not_le ?_).antisymm ?_
-  · have hnm : n ≤ m := hn.trans (find_le hpm)
-    refine add_le_of_le_tsub_right_of_le hnm (find_le ?_)
-    rwa [tsub_add_cancel_of_le hnm]
-  · rw [← tsub_le_iff_right]
-    refine (le_find_iff _ _).2 fun m hm hpm => hm.not_le ?_
-    rw [tsub_le_iff_right]
-    exact find_le hpm
-#align nat.find_add Nat.find_add
-
-end Find
-
-/-! ### `find_greatest` -/
-
-
-section FindGreatest
-
-variable {P Q : ℕ → Prop} [DecidablePred P]
-
-theorem findGreatest_eq_iff :
-    Nat.findGreatest P k = m ↔ m ≤ k ∧ (m ≠ 0 → P m) ∧ ∀ ⦃n⦄, m < n → n ≤ k → ¬P n := by
-  induction' k with k ihk generalizing m
-  · rw [eq_comm, Iff.comm]
-    simp only [zero_eq, nonpos_iff_eq_zero, ne_eq, findGreatest_zero, and_iff_left_iff_imp]
-    rintro rfl
-    exact ⟨fun h => (h rfl).elim, fun n hlt heq => (hlt.ne heq.symm).elim⟩
-  · by_cases hk : P (k + 1)
-    · rw [findGreatest_eq hk]
-      constructor
-      · rintro rfl
-        exact ⟨le_rfl, fun _ => hk, fun n hlt hle => (hlt.not_le hle).elim⟩
-      · rintro ⟨hle, h0, hm⟩
-        rcases Decidable.eq_or_lt_of_le hle with (rfl | hlt)
-        exacts [rfl, (hm hlt le_rfl hk).elim]
-    · rw [findGreatest_of_not hk, ihk]
-      constructor
-      · rintro ⟨hle, hP, hm⟩
-        refine ⟨hle.trans k.le_succ, hP, fun n hlt hle => ?_⟩
-        rcases Decidable.eq_or_lt_of_le hle with (rfl | hlt')
-        exacts [hk, hm hlt <| Nat.lt_succ_iff.1 hlt']
-      · rintro ⟨hle, hP, hm⟩
-        refine ⟨Nat.lt_succ_iff.1 (hle.lt_of_ne ?_), hP,
-          fun n hlt hle => hm hlt (hle.trans k.le_succ)⟩
-        rintro rfl
-        exact hk (hP k.succ_ne_zero)
-#align nat.find_greatest_eq_iff Nat.findGreatest_eq_iff
-
-theorem findGreatest_eq_zero_iff : Nat.findGreatest P k = 0 ↔ ∀ ⦃n⦄, 0 < n → n ≤ k → ¬P n := by
-  simp [findGreatest_eq_iff]
-#align nat.find_greatest_eq_zero_iff Nat.findGreatest_eq_zero_iff
-
-@[simp] lemma findGreatest_pos : 0 < Nat.findGreatest P k ↔ ∃ n, 0 < n ∧ n ≤ k ∧ P n := by
-  rw [pos_iff_ne_zero, Ne.def, findGreatest_eq_zero_iff]; push_neg; rfl
-
-theorem findGreatest_spec (hmb : m ≤ n) (hm : P m) : P (Nat.findGreatest P n) := by
-  by_cases h : Nat.findGreatest P n = 0
-  · cases m
-    · rwa [h]
-    exact ((findGreatest_eq_zero_iff.1 h) (zero_lt_succ _) hmb hm).elim
-  · exact (findGreatest_eq_iff.1 rfl).2.1 h
-#align nat.find_greatest_spec Nat.findGreatest_spec
-
-theorem findGreatest_le (n : ℕ) : Nat.findGreatest P n ≤ n :=
-  (findGreatest_eq_iff.1 rfl).1
-#align nat.find_greatest_le Nat.findGreatest_le
-
-theorem le_findGreatest (hmb : m ≤ n) (hm : P m) : m ≤ Nat.findGreatest P n :=
-  le_of_not_lt fun hlt => (findGreatest_eq_iff.1 rfl).2.2 hlt hmb hm
-#align nat.le_find_greatest Nat.le_findGreatest
-
-theorem findGreatest_mono_right (P : ℕ → Prop) [DecidablePred P] :
-    Monotone (Nat.findGreatest P) := by
-  refine monotone_nat_of_le_succ fun n => ?_
-  rw [findGreatest_succ]
-  split_ifs
-  · exact (findGreatest_le n).trans (le_succ _)
-  · rfl
-#align nat.find_greatest_mono_right Nat.findGreatest_mono_right
-
-theorem findGreatest_mono_left [DecidablePred Q] (hPQ : P ≤ Q) :
-    Nat.findGreatest P ≤ Nat.findGreatest Q := by
-  intro n
-  induction' n with n hn
-  · rfl
-  by_cases h : P (n + 1)
-  · rw [findGreatest_eq h, findGreatest_eq (hPQ _ h)]
-  · rw [findGreatest_of_not h]
-    exact hn.trans (Nat.findGreatest_mono_right _ <| le_succ _)
-#align nat.find_greatest_mono_left Nat.findGreatest_mono_left
-
-theorem findGreatest_mono [DecidablePred Q] (hPQ : P ≤ Q) (hmn : m ≤ n) :
-    Nat.findGreatest P m ≤ Nat.findGreatest Q n :=
-  (Nat.findGreatest_mono_right _ hmn).trans <| findGreatest_mono_left hPQ _
-#align nat.find_greatest_mono Nat.findGreatest_mono
-
-theorem findGreatest_is_greatest (hk : Nat.findGreatest P n < k) (hkb : k ≤ n) : ¬P k :=
-  (findGreatest_eq_iff.1 rfl).2.2 hk hkb
-#align nat.find_greatest_is_greatest Nat.findGreatest_is_greatest
-
-theorem findGreatest_of_ne_zero (h : Nat.findGreatest P n = m) (h0 : m ≠ 0) : P m :=
-  (findGreatest_eq_iff.1 h).2.1 h0
-#align nat.find_greatest_of_ne_zero Nat.findGreatest_of_ne_zero
-
-end FindGreatest
-
-/-! ### `bit0` and `bit1` -/
-section Bit
-
-set_option linter.deprecated false
-
-protected theorem bit0_le {n m : ℕ} (h : n ≤ m) : bit0 n ≤ bit0 m :=
-  add_le_add h h
-#align nat.bit0_le Nat.bit0_le
-
-protected theorem bit1_le {n m : ℕ} (h : n ≤ m) : bit1 n ≤ bit1 m :=
-  succ_le_succ (add_le_add h h)
-#align nat.bit1_le Nat.bit1_le
-
-theorem bit_le : ∀ (b : Bool) {m n : ℕ}, m ≤ n → bit b m ≤ bit b n
-  | true, _, _, h => Nat.bit1_le h
-  | false, _, _, h => Nat.bit0_le h
-#align nat.bit_le Nat.bit_le
-
-theorem bit0_le_bit : ∀ (b) {m n : ℕ}, m ≤ n → bit0 m ≤ bit b n
-  | true, _, _, h => le_of_lt <| Nat.bit0_lt_bit1 h
-  | false, _, _, h => Nat.bit0_le h
-#align nat.bit0_le_bit Nat.bit0_le_bit
-
-theorem bit_le_bit1 : ∀ (b) {m n : ℕ}, m ≤ n → bit b m ≤ bit1 n
-  | false, _, _, h => le_of_lt <| Nat.bit0_lt_bit1 h
-  | true, _, _, h => Nat.bit1_le h
-#align nat.bit_le_bit1 Nat.bit_le_bit1
-
-theorem bit_lt_bit0 : ∀ (b) {m n : ℕ}, m < n → bit b m < bit0 n
-  | true, _, _, h => Nat.bit1_lt_bit0 h
-  | false, _, _, h => Nat.bit0_lt h
-#align nat.bit_lt_bit0 Nat.bit_lt_bit0
-
-theorem bit_lt_bit (a b) (h : m < n) : bit a m < bit b n :=
-  lt_of_lt_of_le (bit_lt_bit0 _ h) (bit0_le_bit _ le_rfl)
-#align nat.bit_lt_bit Nat.bit_lt_bit
-
-@[simp]
-theorem bit0_le_bit1_iff : bit0 m ≤ bit1 n ↔ m ≤ n :=
-  ⟨fun h => by
-    rwa [← Nat.lt_succ_iff, n.bit1_eq_succ_bit0,
-    ← n.bit0_succ_eq, bit0_lt_bit0, Nat.lt_succ_iff] at h,
-    fun h => le_of_lt (Nat.bit0_lt_bit1 h)⟩
-#align nat.bit0_le_bit1_iff Nat.bit0_le_bit1_iff
-
-@[simp]
-theorem bit0_lt_bit1_iff : bit0 m < bit1 n ↔ m ≤ n :=
-  ⟨fun h => bit0_le_bit1_iff.1 (le_of_lt h), Nat.bit0_lt_bit1⟩
-#align nat.bit0_lt_bit1_iff Nat.bit0_lt_bit1_iff
-
-@[simp]
-theorem bit1_le_bit0_iff : bit1 m ≤ bit0 n ↔ m < n :=
-  ⟨fun h => by rwa [m.bit1_eq_succ_bit0, succ_le_iff, bit0_lt_bit0] at h, fun h =>
-    le_of_lt (Nat.bit1_lt_bit0 h)⟩
-#align nat.bit1_le_bit0_iff Nat.bit1_le_bit0_iff
-
-@[simp]
-theorem bit1_lt_bit0_iff : bit1 m < bit0 n ↔ m < n :=
-  ⟨fun h => bit1_le_bit0_iff.1 (le_of_lt h), Nat.bit1_lt_bit0⟩
-#align nat.bit1_lt_bit0_iff Nat.bit1_lt_bit0_iff
-
--- Porting note: temporarily porting only needed portions
-/-
-@[simp]
-theorem one_le_bit0_iff : 1 ≤ bit0 n ↔ 0 < n := by
-  convert bit1_le_bit0_iff
-  rfl
-#align nat.one_le_bit0_iff Nat.one_le_bit0_iff
-
-@[simp]
-theorem one_lt_bit0_iff : 1 < bit0 n ↔ 1 ≤ n := by
-  convert bit1_lt_bit0_iff
-  rfl
-#align nat.one_lt_bit0_iff Nat.one_lt_bit0_iff
-
-@[simp]
-theorem bit_le_bit_iff : ∀ {b : Bool}, bit b m ≤ bit b n ↔ m ≤ n
-  | false => bit0_le_bit0
-  | true => bit1_le_bit1
-#align nat.bit_le_bit_iff Nat.bit_le_bit_iff
-
-@[simp]
-theorem bit_lt_bit_iff : ∀ {b : Bool}, bit b m < bit b n ↔ m < n
-  | false => bit0_lt_bit0
-  | true => bit1_lt_bit1
-#align nat.bit_lt_bit_iff Nat.bit_lt_bit_iff
-
-@[simp]
-theorem bit_le_bit1_iff : ∀ {b : Bool}, bit b m ≤ bit1 n ↔ m ≤ n
-  | false => bit0_le_bit1_iff
-  | true => bit1_le_bit1
-#align nat.bit_le_bit1_iff Nat.bit_le_bit1_iff
--/
-
-end Bit
-
-/-! ### decidability of predicates -/
-
-
-instance decidableLoHi (lo hi : ℕ) (P : ℕ → Prop) [H : DecidablePred P] :
-    Decidable (∀ x, lo ≤ x → x < hi → P x) :=
-  decidable_of_iff (∀ x < hi - lo, P (lo + x))
-    ⟨fun al x hl hh => by
-      have := al (x - lo) ((tsub_lt_tsub_iff_right hl).mpr hh)
-      rwa [add_tsub_cancel_of_le hl] at this, fun al x h =>
-      al _ (Nat.le_add_right _ _) (lt_tsub_iff_left.mp h)⟩
-#align nat.decidable_lo_hi Nat.decidableLoHi
-
-instance decidableLoHiLe (lo hi : ℕ) (P : ℕ → Prop) [DecidablePred P] :
-    Decidable (∀ x, lo ≤ x → x ≤ hi → P x) :=
-  decidable_of_iff (∀ x, lo ≤ x → x < hi + 1 → P x) <|
-    ball_congr fun _ _ => imp_congr Nat.lt_succ_iff Iff.rfl
-#align nat.decidable_lo_hi_le Nat.decidableLoHiLe
+theorem _root_.NeZero.one_le {n : ℕ} [NeZero n] : 1 ≤ n := one_le_iff_ne_zero.mpr (NeZero.ne n)
 
 end Nat

chore: classify "simp can prove" porting notes (#11550)

Classifies by adding issue number #10618 to porting notes claiming "simp can prove it".

5befdcb9

Diff

@@ -500,7 +500,7 @@ section Find
 
 variable {p q : ℕ → Prop} [DecidablePred p] [DecidablePred q]
 
--- Porting note: removing `simp` attribute as `simp` can prove it
+-- Porting note (#10618): removing `simp` attribute as `simp` can prove it
 theorem find_pos (h : ∃ n : ℕ, p n) : 0 < Nat.find h ↔ ¬p 0 := by
   rw [pos_iff_ne_zero, Ne, Nat.find_eq_zero]
 #align nat.find_pos Nat.find_pos

chore: simplify some proofs for the 2024-03-16 nightly (#11547)

Some small changes to adapt to the 2024-03-16 nightly that can land in advance.

c5a921ec

Diff

@@ -323,7 +323,7 @@ theorem diag_induction (P : ℕ → ℕ → Prop) (ha : ∀ a, P (a + 1) (a + 1)
     have _ : a + (b + 1) < (a + 1) + (b + 1) := by simp
     apply diag_induction P ha hb hd a (b + 1)
     apply lt_of_le_of_lt (Nat.le_succ _) h
-  termination_by a b c => a + b
+  termination_by a b _c => a + b
   decreasing_by all_goals assumption
 #align nat.diag_induction Nat.diag_induction

chore: golf using omega (#11318)

Backported from #11314.

bbf22060

Diff

@@ -171,16 +171,12 @@ theorem add_eq_one_iff : m + n = 1 ↔ m = 0 ∧ n = 1 ∨ m = 1 ∧ n = 0 := by
 #align nat.add_eq_one_iff Nat.add_eq_one_iff
 
 theorem add_eq_two_iff : m + n = 2 ↔ m = 0 ∧ n = 2 ∨ m = 1 ∧ n = 1 ∨ m = 2 ∧ n = 0 := by
-  cases n <;>
-  simp [(succ_ne_zero 1).symm, (show 2 = Nat.succ 1 from rfl),
-    succ_eq_add_one, ← add_assoc, succ_inj', add_eq_one_iff]
+  omega
 #align nat.add_eq_two_iff Nat.add_eq_two_iff
 
 theorem add_eq_three_iff :
     m + n = 3 ↔ m = 0 ∧ n = 3 ∨ m = 1 ∧ n = 2 ∨ m = 2 ∧ n = 1 ∨ m = 3 ∧ n = 0 := by
-  cases n <;>
-  simp [(succ_ne_zero 1).symm, succ_eq_add_one, (show 3 = Nat.succ 2 from rfl),
-    ← add_assoc, succ_inj', add_eq_two_iff]
+  omega
 #align nat.add_eq_three_iff Nat.add_eq_three_iff
 
 theorem le_add_one_iff : m ≤ n + 1 ↔ m ≤ n ∨ m = n + 1 := by

chore: squeeze some non-terminal simps (#11247)

This PR accompanies #11246, squeezing some non-terminal simps highlighted by the linter until I decided to stop!

1ad8c3fe

Diff

@@ -457,7 +457,7 @@ theorem dvd_sub_mod (k : ℕ) : n ∣ k - k % n :=
 
 theorem add_mod_eq_ite :
     (m + n) % k = if k ≤ m % k + n % k then m % k + n % k - k else m % k + n % k := by
-  cases k; simp [mod_zero]
+  cases k; simp only [zero_eq, mod_zero, _root_.zero_le, ↓reduceIte, tsub_zero]
   rw [Nat.add_mod]
   split_ifs with h
   · rw [Nat.mod_eq_sub_mod h, Nat.mod_eq_of_lt]

chore: move Mathlib to v4.7.0-rc1 (#11162)

This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0 branch as we update to intermediate nightlies.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>

fa48894a

Diff

@@ -363,14 +363,6 @@ protected theorem div_le_self' (m n : ℕ) : m / n ≤ m :=
         _ ≤ n * m := Nat.mul_le_mul_right _ n0
 #align nat.div_le_self' Nat.div_le_self'
 
-protected theorem div_lt_of_lt_mul (h : m < n * k) : m / n < k :=
-  lt_of_mul_lt_mul_left
-    (calc
-      n * (m / n) ≤ m % n + n * (m / n) := Nat.le_add_left _ _
-      _ = m := mod_add_div _ _
-      _ < n * k := h
-      )
-    (Nat.zero_le n)
 #align nat.div_lt_of_lt_mul Nat.div_lt_of_lt_mul
 
 theorem eq_zero_of_le_div (hn : 2 ≤ n) (h : m ≤ m / n) : m = 0 :=
@@ -435,18 +427,7 @@ protected theorem div_div_self (h : n ∣ m) (hm : m ≠ 0) : m / (m / n) = n :=
   rw [mul_div_right _ (Nat.pos_of_ne_zero hm.1), mul_div_left _ (Nat.pos_of_ne_zero hm.2)]
 #align nat.div_div_self Nat.div_div_self
 
--- Porting note: later `simp [mod_zero]` can be changed to `simp` once `mod_zero` is given
---a `simp` attribute.
-theorem mod_mul_right_div_self (m n k : ℕ) : m % (n * k) / n = m / n % k := by
-  rcases Nat.eq_zero_or_pos n with (rfl | hn); simp [mod_zero]
-  rcases Nat.eq_zero_or_pos k with (rfl | hk); simp [mod_zero]
-  conv_rhs => rw [← mod_add_div m (n * k)]
-  rw [mul_assoc, add_mul_div_left _ _ hn, add_mul_mod_self_left,
-    mod_eq_of_lt (Nat.div_lt_of_lt_mul (mod_lt _ (mul_pos hn hk)))]
 #align nat.mod_mul_right_div_self Nat.mod_mul_right_div_self
-
-theorem mod_mul_left_div_self (m n k : ℕ) : m % (k * n) / n = m / n % k := by
-  rw [mul_comm k, mod_mul_right_div_self]
 #align nat.mod_mul_left_div_self Nat.mod_mul_left_div_self
 
 theorem not_dvd_of_pos_of_lt (h1 : 0 < n) (h2 : n < m) : ¬m ∣ n := by

style: homogenise porting notes (#11145)

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

converts "--porting note" into "-- Porting note";
converts "porting note" into "Porting note".

8be0b69c

Diff

@@ -89,7 +89,7 @@ theorem _root_.NeZero.one_le [NeZero n] : 1 ≤ n := one_le_iff_ne_zero.mpr (NeZ
 -- Porting note: already in Std
 #align nat.mul_eq_zero Nat.mul_eq_zero
 
---Porting note: removing `simp` attribute
+-- Porting note: removing `simp` attribute
 protected theorem zero_eq_mul : 0 = m * n ↔ m = 0 ∨ n = 0 := by rw [eq_comm, Nat.mul_eq_zero]
 #align nat.zero_eq_mul Nat.zero_eq_mul
 
@@ -435,7 +435,7 @@ protected theorem div_div_self (h : n ∣ m) (hm : m ≠ 0) : m / (m / n) = n :=
   rw [mul_div_right _ (Nat.pos_of_ne_zero hm.1), mul_div_left _ (Nat.pos_of_ne_zero hm.2)]
 #align nat.div_div_self Nat.div_div_self
 
---Porting note: later `simp [mod_zero]` can be changed to `simp` once `mod_zero` is given
+-- Porting note: later `simp [mod_zero]` can be changed to `simp` once `mod_zero` is given
 --a `simp` attribute.
 theorem mod_mul_right_div_self (m n k : ℕ) : m % (n * k) / n = m / n % k := by
   rcases Nat.eq_zero_or_pos n with (rfl | hn); simp [mod_zero]
@@ -523,7 +523,7 @@ section Find
 
 variable {p q : ℕ → Prop} [DecidablePred p] [DecidablePred q]
 
---Porting note: removing `simp` attribute as `simp` can prove it
+-- Porting note: removing `simp` attribute as `simp` can prove it
 theorem find_pos (h : ∃ n : ℕ, p n) : 0 < Nat.find h ↔ ¬p 0 := by
   rw [pos_iff_ne_zero, Ne, Nat.find_eq_zero]
 #align nat.find_pos Nat.find_pos

chore: add lemmas for nat literals corresponding to lemmas for nat casts (#8006)

I loogled for every occurrence of "cast", Nat and "natCast" and where the casted nat was n, and made sure there were corresponding @[simp] lemmas for 0, 1, and OfNat.ofNat n. This is necessary in general for simp confluence. Example:

import Mathlib

variable {α : Type*} [LinearOrderedRing α] (m n : ℕ) [m.AtLeastTwo] [n.AtLeastTwo]

example : ((OfNat.ofNat m : ℕ) : α) ≤ ((OfNat.ofNat n : ℕ) : α) ↔ (OfNat.ofNat m : ℕ) ≤ (OfNat.ofNat n : ℕ) := by
  simp only [Nat.cast_le] -- this `@[simp]` lemma can apply

example : ((OfNat.ofNat m : ℕ) : α) ≤ ((OfNat.ofNat n : ℕ) : α) ↔ (OfNat.ofNat m : α) ≤ (OfNat.ofNat n : α) := by
  simp only [Nat.cast_ofNat] -- and so can this one

example : (OfNat.ofNat m : α) ≤ (OfNat.ofNat n : α) ↔ (OfNat.ofNat m : ℕ) ≤ (OfNat.ofNat n : ℕ) := by
  simp -- fails! `simp` doesn't have a lemma to bridge their results. confluence issue.

As far as I know, the only file this PR leaves with ofNat gaps is PartENat.lean. #8002 is addressing that file in parallel.

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

bbe9baad

Diff

@@ -82,6 +82,8 @@ variable {m n k l : ℕ}
 
 /-! ### Equalities and inequalities involving zero and one -/
 
+theorem _root_.NeZero.one_le [NeZero n] : 1 ≤ n := one_le_iff_ne_zero.mpr (NeZero.ne n)
+
 #align nat.mul_ne_zero Nat.mul_ne_zero
 
 -- Porting note: already in Std

chore: bump dependencies (#10315)

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

ba9f2e5b

Diff

@@ -142,7 +142,7 @@ theorem two_le_iff : ∀ n, 2 ≤ n ↔ n ≠ 0 ∧ n ≠ 1
 
 @[simp]
 theorem lt_one_iff {n : ℕ} : n < 1 ↔ n = 0 :=
-  lt_succ_iff.trans nonpos_iff_eq_zero
+  Nat.lt_succ_iff.trans nonpos_iff_eq_zero
 #align nat.lt_one_iff Nat.lt_one_iff
 
 /-! ### `add` -/
@@ -567,9 +567,10 @@ theorem findGreatest_eq_iff :
       · rintro ⟨hle, hP, hm⟩
         refine ⟨hle.trans k.le_succ, hP, fun n hlt hle => ?_⟩
         rcases Decidable.eq_or_lt_of_le hle with (rfl | hlt')
-        exacts [hk, hm hlt <| lt_succ_iff.1 hlt']
+        exacts [hk, hm hlt <| Nat.lt_succ_iff.1 hlt']
       · rintro ⟨hle, hP, hm⟩
-        refine ⟨lt_succ_iff.1 (hle.lt_of_ne ?_), hP, fun n hlt hle => hm hlt (hle.trans k.le_succ)⟩
+        refine ⟨Nat.lt_succ_iff.1 (hle.lt_of_ne ?_), hP,
+          fun n hlt hle => hm hlt (hle.trans k.le_succ)⟩
         rintro rfl
         exact hk (hP k.succ_ne_zero)
 #align nat.find_greatest_eq_iff Nat.findGreatest_eq_iff
@@ -743,7 +744,7 @@ instance decidableLoHi (lo hi : ℕ) (P : ℕ → Prop) [H : DecidablePred P] :
 instance decidableLoHiLe (lo hi : ℕ) (P : ℕ → Prop) [DecidablePred P] :
     Decidable (∀ x, lo ≤ x → x ≤ hi → P x) :=
   decidable_of_iff (∀ x, lo ≤ x → x < hi + 1 → P x) <|
-    ball_congr fun _ _ => imp_congr lt_succ_iff Iff.rfl
+    ball_congr fun _ _ => imp_congr Nat.lt_succ_iff Iff.rfl
 #align nat.decidable_lo_hi_le Nat.decidableLoHiLe
 
 end Nat

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

@@ -325,8 +325,8 @@ theorem diag_induction (P : ℕ → ℕ → Prop) (ha : ∀ a, P (a + 1) (a + 1)
     have _ : a + (b + 1) < (a + 1) + (b + 1) := by simp
     apply diag_induction P ha hb hd a (b + 1)
     apply lt_of_le_of_lt (Nat.le_succ _) h
-  termination_by _ a b c => a + b
-  decreasing_by { assumption }
+  termination_by a b c => a + b
+  decreasing_by all_goals assumption
 #align nat.diag_induction Nat.diag_induction
 
 /-- A subset of `ℕ` containing `k : ℕ` and closed under `Nat.succ` contains every `n ≥ k`. -/

feat: add Int.le_add_one_iff (#9892)

Co-authored-by: Yury G. Kudryashov <urkud@urkud.name>

e1650985

Diff

@@ -181,12 +181,8 @@ theorem add_eq_three_iff :
     ← add_assoc, succ_inj', add_eq_two_iff]
 #align nat.add_eq_three_iff Nat.add_eq_three_iff
 
-theorem le_add_one_iff : m ≤ n + 1 ↔ m ≤ n ∨ m = n + 1 :=
-  ⟨fun h =>
-    match Nat.eq_or_lt_of_le h with
-    | Or.inl h => Or.inr h
-    | Or.inr h => Or.inl <| Nat.le_of_succ_le_succ h,
-    Or.rec (fun h => le_trans h <| Nat.le_add_right _ _) le_of_eq⟩
+theorem le_add_one_iff : m ≤ n + 1 ↔ m ≤ n ∨ m = n + 1 := by
+  rw [le_iff_lt_or_eq, lt_add_one_iff]
 #align nat.le_add_one_iff Nat.le_add_one_iff
 
 theorem le_and_le_add_one_iff : n ≤ m ∧ m ≤ n + 1 ↔ m = n ∨ m = n + 1 := by

fix: patch for std4#198 (more mul lemmas for Nat) (#6204)

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

2f63d25e

Diff

@@ -275,18 +275,10 @@ theorem le_mul_self : ∀ n : ℕ, n ≤ n * n
   | n + 1 => by simp
 #align nat.le_mul_self Nat.le_mul_self
 
-theorem le_mul_of_pos_left (h : 0 < n) : m ≤ n * m := by
-  conv =>
-    lhs
-    rw [← one_mul m]
-  exact mul_le_mul_of_nonneg_right h.nat_succ_le (zero_le _)
+-- Moved to Std
 #align nat.le_mul_of_pos_left Nat.le_mul_of_pos_left
 
-theorem le_mul_of_pos_right (h : 0 < n) : m ≤ m * n := by
-  conv =>
-    lhs
-    rw [← mul_one m]
-  exact mul_le_mul_of_nonneg_left h.nat_succ_le (zero_le _)
+-- Moved to Std
 #align nat.le_mul_of_pos_right Nat.le_mul_of_pos_right
 
 theorem mul_self_inj : m * m = n * n ↔ m = n :=
@@ -463,7 +455,7 @@ theorem not_dvd_of_pos_of_lt (h1 : 0 < n) (h2 : n < m) : ¬m ∣ n := by
   rintro ⟨k, rfl⟩
   rcases Nat.eq_zero_or_pos k with (rfl | hk)
   · exact lt_irrefl 0 h1
-  · exact not_lt.2 (le_mul_of_pos_right hk) h2
+  · exact not_lt.2 (Nat.le_mul_of_pos_right _ hk) h2
 #align nat.not_dvd_of_pos_of_lt Nat.not_dvd_of_pos_of_lt
 
 /-- If `m` and `n` are equal mod `k`, `m - n` is zero mod `k`. -/

refactor: Split off basic Nat file (#9551)

Data.Nat.Basic is currently made of two things:

Basic lemmas that continue the theory in Std (and could belong there, really)
Basic algebraic order instances

I need the first ones earlier in the algebraic order hierarchy, hence the split.

Part of #9411. Similar to #9443

497ed074

Diff

@@ -5,7 +5,7 @@ Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
 import Mathlib.Algebra.Order.Ring.Canonical
 import Mathlib.Data.Nat.Basic
-import Mathlib.Data.Nat.Bits
+import Mathlib.Init.Data.Nat.Bitwise
 
 #align_import data.nat.order.basic from "leanprover-community/mathlib"@"3ed3f98a1e836241990d3d308f1577e434977130"
 
@@ -16,7 +16,9 @@ import Mathlib.Data.Nat.Bits
 We also have a variety of lemmas which have been deferred from `Data.Nat.Basic` because it is
 easier to prove them with this ordered semiring instance available.
 
-You may find that some theorems can be moved back to `Data.Nat.Basic` by modifying their proofs.
+### TODO
+
+Move most of the theorems to `Data.Nat.Defs` by modifying their proofs.
 -/
 
 
@@ -80,21 +82,6 @@ variable {m n k l : ℕ}
 
 /-! ### Equalities and inequalities involving zero and one -/
 
-theorem one_le_iff_ne_zero : 1 ≤ n ↔ n ≠ 0 :=
-  Nat.add_one_le_iff.trans pos_iff_ne_zero
-#align nat.one_le_iff_ne_zero Nat.one_le_iff_ne_zero
-
-theorem one_lt_iff_ne_zero_and_ne_one : ∀ {n : ℕ}, 1 < n ↔ n ≠ 0 ∧ n ≠ 1
-  | 0 => by decide
-  | 1 => by decide
-  | n + 2 => by simp
-#align nat.one_lt_iff_ne_zero_and_ne_one Nat.one_lt_iff_ne_zero_and_ne_one
-
-theorem le_one_iff_eq_zero_or_eq_one : ∀ {n : ℕ}, n ≤ 1 ↔ n = 0 ∨ n = 1
-  | 0 => by decide
-  | 1 => by decide
-  | n + 2 => by simp
-
 #align nat.mul_ne_zero Nat.mul_ne_zero
 
 -- Porting note: already in Std

chore(*): replace $ with <| (#9319)

See Zulip thread for the discussion.

9f6d3388

Diff

@@ -322,7 +322,7 @@ theorem add_sub_one_le_mul (hm : m ≠ 0) (hn : n ≠ 0) : m + n - 1 ≤ m * n :
   cases m
   · cases hm rfl
   · rw [succ_add, Nat.add_one_sub_one, succ_mul]
-    exact add_le_add_right (le_mul_of_one_le_right' $ succ_le_iff.2 $ pos_iff_ne_zero.2 hn) _
+    exact add_le_add_right (le_mul_of_one_le_right' <| succ_le_iff.2 <| pos_iff_ne_zero.2 hn) _
 #align nat.add_sub_one_le_mul Nat.add_sub_one_le_mul
 
 /-!

chore: remove uses of cases' (#9171)

I literally went through and regex'd some uses of cases', replacing them with rcases; this is meant to be a low effort PR as I hope that tools can do this in the future.

rcases is an easier replacement than cases, though with better tools we could in future do a second pass converting simple rcases added here (and existing ones) to cases.

3fca282c

Diff

@@ -124,12 +124,12 @@ theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 := max_eq_bot
 
 theorem add_eq_max_iff : m + n = max m n ↔ m = 0 ∨ n = 0 := by
   rw [← min_eq_zero_iff]
-  cases' le_total m n with H H <;> simp [H]
+  rcases le_total m n with H | H <;> simp [H]
 #align nat.add_eq_max_iff Nat.add_eq_max_iff
 
 theorem add_eq_min_iff : m + n = min m n ↔ m = 0 ∧ n = 0 := by
   rw [← max_eq_zero_iff]
-  cases' le_total m n with H H <;> simp [H]
+  rcases le_total m n with H | H <;> simp [H]
 #align nat.add_eq_min_iff Nat.add_eq_min_iff
 
 theorem one_le_of_lt (h : n < m) : 1 ≤ m :=
@@ -244,11 +244,11 @@ theorem lt_of_lt_pred (h : m < n - 1) : m < n :=
 #align nat.lt_of_lt_pred Nat.lt_of_lt_pred
 
 theorem le_or_le_of_add_eq_add_pred (h : k + l = m + n - 1) : m ≤ k ∨ n ≤ l := by
-  cases' le_or_lt m k with h' h' <;> [left; right]
+  rcases le_or_lt m k with h' | h' <;> [left; right]
   · exact h'
   · replace h' := add_lt_add_right h' l
     rw [h] at h'
-    cases' n.eq_zero_or_pos with hn hn
+    rcases n.eq_zero_or_pos with hn | hn
     · rw [hn]
       exact zero_le l
     rw [n.add_sub_assoc (Nat.succ_le_of_lt hn), add_lt_add_iff_left] at h'

feat(Combinatorics): definition and basic properties of Schnirelmann density (#7342)

Provide the definition of the Schnirelmann density, basic properties of it, and some simple useful calculations.

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com> Co-authored-by: Doga Can Sertbas <dogacan.sertbas@gmail.com>

Co-authored-by: Bhavik Mehta <bm489@cam.ac.uk> Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

441b6cef

Diff

@@ -490,6 +490,9 @@ theorem one_mod (n : ℕ) : 1 % (n + 2) = 1 :=
   Nat.mod_eq_of_lt (add_lt_add_right n.succ_pos 1)
 #align nat.one_mod Nat.one_mod
 
+theorem one_mod_of_ne_one : ∀ {n : ℕ}, n ≠ 1 → 1 % n = 1
+  | 0, _ | (n + 2), _ => by simp
+
 theorem dvd_sub_mod (k : ℕ) : n ∣ k - k % n :=
   ⟨k / n, tsub_eq_of_eq_add_rev (Nat.mod_add_div k n).symm⟩
 #align nat.dvd_sub_mod Nat.dvd_sub_mod

fix: patch for std4#197 (More add lemmas for Nat) (#6202)

d76f1524

Diff

@@ -173,8 +173,8 @@ theorem add_pos_iff_pos_or_pos (m n : ℕ) : 0 < m + n ↔ 0 < m ∨ 0 < n :=
       exact Or.inl (succ_pos _))
     (by
       intro h; cases' h with mpos npos
-      · apply add_pos_left mpos
-      apply add_pos_right _ npos)
+      · apply Nat.add_pos_left mpos
+      apply Nat.add_pos_right _ npos)
 #align nat.add_pos_iff_pos_or_pos Nat.add_pos_iff_pos_or_pos
 
 theorem add_eq_one_iff : m + n = 1 ↔ m = 0 ∧ n = 1 ∨ m = 1 ∧ n = 0 := by

fix: patch for std4#203 (more sub lemmas for Nat) (#6216)

c159834a

Diff

@@ -321,7 +321,7 @@ theorem lt_mul_self_iff : ∀ {n : ℕ}, n < n * n ↔ 1 < n
 theorem add_sub_one_le_mul (hm : m ≠ 0) (hn : n ≠ 0) : m + n - 1 ≤ m * n := by
   cases m
   · cases hm rfl
-  · rw [succ_add, succ_sub_one, succ_mul]
+  · rw [succ_add, Nat.add_one_sub_one, succ_mul]
     exact add_le_add_right (le_mul_of_one_le_right' $ succ_le_iff.2 $ pos_iff_ne_zero.2 hn) _
 #align nat.add_sub_one_le_mul Nat.add_sub_one_le_mul

feat(Data/Nat): add Nat.div_pow (#8327)

Adds the missing lemma Nat.div_pow, which seemed to be missing (at least, exact?% couldn't find it with all of Mathlib imported). Also moves div_mul_div_comm higher in the hierarchy (and golf) because it doesn't need the ordered semiring instance, cf the docstring of Data/Nat/Order/Basic.

Co-authored-by: Bhavik Mehta <bm489@cam.ac.uk>

c8d9ed0f

Diff

@@ -506,26 +506,6 @@ theorem add_mod_eq_ite :
   · exact Nat.mod_eq_of_lt (lt_of_not_ge h)
 #align nat.add_mod_eq_ite Nat.add_mod_eq_ite
 
-theorem div_mul_div_comm (hmn : n ∣ m) (hkl : l ∣ k) : m / n * (k / l) = m * k / (n * l) :=
-  have exi1 : ∃ x, m = n * x := hmn
-  have exi2 : ∃ y, k = l * y := hkl
-  if hn : n = 0 then by simp [hn]
-  else
-    have : 0 < n := Nat.pos_of_ne_zero hn
-    if hl : l = 0 then by simp [hl]
-    else by
-      have : 0 < l := Nat.pos_of_ne_zero hl
-      cases' exi1 with x hx
-      cases' exi2 with y hy
-      rw [hx, hy, Nat.mul_div_cancel_left, Nat.mul_div_cancel_left]
-      apply Eq.symm
-      apply Nat.div_eq_of_eq_mul_left
-      apply mul_pos
-      repeat' assumption
-      -- Porting note: this line was `cc` in Lean3
-      simp only [mul_comm, mul_left_comm, mul_assoc]
-#align nat.div_mul_div_comm Nat.div_mul_div_comm
-
 theorem div_eq_self : m / n = m ↔ m = 0 ∨ n = 1 := by
   constructor
   · intro

feat: patch for std4#196 (more min/max lemmas for Nat) (#8074)

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

6f355e37

Diff

@@ -112,8 +112,6 @@ theorem eq_zero_of_mul_le (hb : 2 ≤ n) (h : n * m ≤ m) : m = 0 :=
   eq_zero_of_double_le <| le_trans (Nat.mul_le_mul_right _ hb) h
 #align nat.eq_zero_of_mul_le Nat.eq_zero_of_mul_le
 
-theorem zero_max : max 0 n = n :=
-  max_eq_right (zero_le _)
 #align nat.zero_max Nat.zero_max
 
 @[simp]

chore: rename CanonicallyOrderedAddMonoid to ..AddCommMonoid (#7503)

Renames:

CanonicallyOrderedMonoid -> CanonicallyOrderedCommMonoid

CanonicallyOrderedAddMonoid -> CanonicallyOrderedAddCommMonoid

CanonicallyLinearOrderedMonoid -> CanonicallyLinearOrderedCommMonoid

CanonicallyLinearOrderedAddMonoid -> CanonicallyLinearOrderedAddCommMonoid

f3bc24c3

Diff

@@ -73,8 +73,8 @@ instance canonicallyOrderedCommSemiring : CanonicallyOrderedCommSemiring ℕ :=
     le_self_add := Nat.le_add_right,
     eq_zero_or_eq_zero_of_mul_eq_zero := Nat.eq_zero_of_mul_eq_zero }
 
-instance canonicallyLinearOrderedAddMonoid : CanonicallyLinearOrderedAddMonoid ℕ :=
-  { (inferInstance : CanonicallyOrderedAddMonoid ℕ), Nat.linearOrder with }
+instance canonicallyLinearOrderedAddCommMonoid : CanonicallyLinearOrderedAddCommMonoid ℕ :=
+  { (inferInstance : CanonicallyOrderedAddCommMonoid ℕ), Nat.linearOrder with }
 
 variable {m n k l : ℕ}

feat: Zeckendorf's theorem (#6880)

Prove Zeckendorf's theorem: Every natural number can be written uniquely as a sum of distinct non-consecutive Fibonacci numbers.

Instead of proving an ExistsUnique statement, I define an equivalence between natural numbers and Zeckendorf representations.

Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com>

1d02ef70

Diff

@@ -622,6 +622,9 @@ theorem findGreatest_eq_zero_iff : Nat.findGreatest P k = 0 ↔ ∀ ⦃n⦄, 0 <
   simp [findGreatest_eq_iff]
 #align nat.find_greatest_eq_zero_iff Nat.findGreatest_eq_zero_iff
 
+@[simp] lemma findGreatest_pos : 0 < Nat.findGreatest P k ↔ ∃ n, 0 < n ∧ n ≤ k ∧ P n := by
+  rw [pos_iff_ne_zero, Ne.def, findGreatest_eq_zero_iff]; push_neg; rfl
+
 theorem findGreatest_spec (hmb : m ≤ n) (hm : P m) : P (Nat.findGreatest P n) := by
   by_cases h : Nat.findGreatest P n = 0
   · cases m

feat(Data/Nat/Order/Basic): le_one_iff_eq_zero_or_eq_one (#6949)

Co-authored-by: Moritz Firsching <firsching@google.com>

a085bc37

Diff

@@ -90,6 +90,11 @@ theorem one_lt_iff_ne_zero_and_ne_one : ∀ {n : ℕ}, 1 < n ↔ n ≠ 0 ∧ n 
   | n + 2 => by simp
 #align nat.one_lt_iff_ne_zero_and_ne_one Nat.one_lt_iff_ne_zero_and_ne_one
 
+theorem le_one_iff_eq_zero_or_eq_one : ∀ {n : ℕ}, n ≤ 1 ↔ n = 0 ∨ n = 1
+  | 0 => by decide
+  | 1 => by decide
+  | n + 2 => by simp
+
 #align nat.mul_ne_zero Nat.mul_ne_zero
 
 -- Porting note: already in Std

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,16 +2,13 @@
 Copyright (c) 2014 Floris van Doorn (c) 2016 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.order.basic
-! leanprover-community/mathlib commit 3ed3f98a1e836241990d3d308f1577e434977130
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Algebra.Order.Ring.Canonical
 import Mathlib.Data.Nat.Basic
 import Mathlib.Data.Nat.Bits
 
+#align_import data.nat.order.basic from "leanprover-community/mathlib"@"3ed3f98a1e836241990d3d308f1577e434977130"
+
 
 /-!
 # The natural numbers as a linearly ordered commutative semiring

chore: cleanup whitespace (#5988)

Grepping for [^ .:{-] [^ :] and reviewing the results. Once I started I couldn't stop. :-)

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

12343aa5

Diff

@@ -685,7 +685,7 @@ protected theorem bit1_le {n m : ℕ} (h : n ≤ m) : bit1 n ≤ bit1 m :=
 #align nat.bit1_le Nat.bit1_le
 
 theorem bit_le : ∀ (b : Bool) {m n : ℕ}, m ≤ n → bit b m ≤ bit b n
-  | true, _, _, h => Nat.bit1_le  h
+  | true, _, _, h => Nat.bit1_le h
   | false, _, _, h => Nat.bit0_le h
 #align nat.bit_le Nat.bit_le

Match https://github.com/leanprover-community/mathlib/pull/18737

feat: a + b - 1 ≤ a * b (#5828)

56e73de0

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.nat.order.basic
-! leanprover-community/mathlib commit e8638a0fcaf73e4500469f368ef9494e495099b3
+! leanprover-community/mathlib commit 3ed3f98a1e836241990d3d308f1577e434977130
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -115,26 +115,11 @@ theorem zero_max : max 0 n = n :=
 #align nat.zero_max Nat.zero_max
 
 @[simp]
-theorem min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 := by
-  constructor
-  · intro h
-    cases' le_total m n with H H
-    · simpa [H] using Or.inl h
-    · simpa [H] using Or.inr h
-  · rintro (rfl | rfl) <;> simp
+theorem min_eq_zero_iff : min m n = 0 ↔ m = 0 ∨ n = 0 := min_eq_bot
 #align nat.min_eq_zero_iff Nat.min_eq_zero_iff
 
 @[simp]
-theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 := by
-  constructor
-  · intro h
-    cases' le_total m n with H H
-    · simp only [H, max_eq_right] at h
-      exact ⟨le_antisymm (H.trans h.le) (zero_le _), h⟩
-    · simp only [H, max_eq_left] at h
-      exact ⟨h, le_antisymm (H.trans h.le) (zero_le _)⟩
-  · rintro ⟨rfl, rfl⟩
-    simp
+theorem max_eq_zero_iff : max m n = 0 ↔ m = 0 ∧ n = 0 := max_eq_bot
 #align nat.max_eq_zero_iff Nat.max_eq_zero_iff
 
 theorem add_eq_max_iff : m + n = max m n ↔ m = 0 ∨ n = 0 := by
@@ -333,6 +318,13 @@ theorem lt_mul_self_iff : ∀ {n : ℕ}, n < n * n ↔ 1 < n
   | n + 1 => lt_mul_iff_one_lt_left n.succ_pos
 #align nat.lt_mul_self_iff Nat.lt_mul_self_iff
 
+theorem add_sub_one_le_mul (hm : m ≠ 0) (hn : n ≠ 0) : m + n - 1 ≤ m * n := by
+  cases m
+  · cases hm rfl
+  · rw [succ_add, succ_sub_one, succ_mul]
+    exact add_le_add_right (le_mul_of_one_le_right' $ succ_le_iff.2 $ pos_iff_ne_zero.2 hn) _
+#align nat.add_sub_one_le_mul Nat.add_sub_one_le_mul
+
 /-!
 ### Recursion and induction principles

chore: remove occurrences of semicolon after space (#5713)

This is the second half of the changes originally in #5699, removing all occurrences of ; after a space and implementing a linter rule to enforce it.

In most cases this 2-character substring has a space after it, so the following command was run first:

find . -type f -name "*.lean" -exec sed -i -E 's/ ; /; /g' {} \;

The remaining cases were few enough in number that they were done manually.

c795bd35

Diff

@@ -378,7 +378,7 @@ theorem set_induction {S : Set ℕ} (hb : 0 ∈ S) (h_ind : ∀ k : ℕ, k ∈ S
 
 
 protected theorem div_le_of_le_mul' (h : m ≤ k * n) : m / k ≤ n :=
-  (Nat.eq_zero_or_pos k).elim (fun k0 => by rw [k0, Nat.div_zero] ; apply zero_le) fun k0 =>
+  (Nat.eq_zero_or_pos k).elim (fun k0 => by rw [k0, Nat.div_zero]; apply zero_le) fun k0 =>
     le_of_mul_le_mul_left
       (calc
         k * (m / k) ≤ m % k + k * (m / k) := Nat.le_add_left _ _
@@ -414,7 +414,7 @@ theorem div_mul_div_le_div (m n k : ℕ) : m / k * n / m ≤ n / k :=
   else
     calc
       m / k * n / m ≤ n * m / k / m :=
-        Nat.div_le_div_right (by rw [mul_comm] ; exact mul_div_le_mul_div_assoc _ _ _)
+        Nat.div_le_div_right (by rw [mul_comm]; exact mul_div_le_mul_div_assoc _ _ _)
       _ = n / k := by
         { rw [Nat.div_div_eq_div_mul, mul_comm n, mul_comm k,
             Nat.mul_div_mul_left _ _ (Nat.pos_of_ne_zero hm0)] }

chore: add space after exacts (#4945)

Too often tempted to change these during other PRs, so doing a mass edit here.

Co-authored-by: Scott Morrison <scott.morrison@anu.edu.au>

bf799bb9

Diff

@@ -611,13 +611,13 @@ theorem findGreatest_eq_iff :
         exact ⟨le_rfl, fun _ => hk, fun n hlt hle => (hlt.not_le hle).elim⟩
       · rintro ⟨hle, h0, hm⟩
         rcases Decidable.eq_or_lt_of_le hle with (rfl | hlt)
-        exacts[rfl, (hm hlt le_rfl hk).elim]
+        exacts [rfl, (hm hlt le_rfl hk).elim]
     · rw [findGreatest_of_not hk, ihk]
       constructor
       · rintro ⟨hle, hP, hm⟩
         refine ⟨hle.trans k.le_succ, hP, fun n hlt hle => ?_⟩
         rcases Decidable.eq_or_lt_of_le hle with (rfl | hlt')
-        exacts[hk, hm hlt <| lt_succ_iff.1 hlt']
+        exacts [hk, hm hlt <| lt_succ_iff.1 hlt']
       · rintro ⟨hle, hP, hm⟩
         refine ⟨lt_succ_iff.1 (hle.lt_of_ne ?_), hP, fun n hlt hle => hm hlt (hle.trans k.le_succ)⟩
         rintro rfl

chore: fix upper/lowercase in comments (#4360)

Run a non-interactive version of fix-comments.py on all files.
Go through the diff and manually add/discard/edit chunks.

27d257fc

Diff

@@ -50,7 +50,7 @@ instance linearOrderedCommMonoidWithZero : LinearOrderedCommMonoidWithZero ℕ :
 /-! Extra instances to short-circuit type class resolution and ensure computability -/
 
 
--- Not using `infer_instance` avoids `classical.choice` in the following two
+-- Not using `inferInstance` avoids `Classical.choice` in the following two
 instance linearOrderedSemiring : LinearOrderedSemiring ℕ :=
   inferInstance

chore: update std 05-22 (#4248)

The main breaking change is that tac <;> [t1, t2] is now written tac <;> [t1; t2], to avoid clashing with tactics like cases and use that take comma-separated lists.

ac36b28e

Diff

@@ -259,7 +259,7 @@ theorem lt_of_lt_pred (h : m < n - 1) : m < n :=
 #align nat.lt_of_lt_pred Nat.lt_of_lt_pred
 
 theorem le_or_le_of_add_eq_add_pred (h : k + l = m + n - 1) : m ≤ k ∨ n ≤ l := by
-  cases' le_or_lt m k with h' h' <;> [left, right]
+  cases' le_or_lt m k with h' h' <;> [left; right]
   · exact h'
   · replace h' := add_lt_add_right h' l
     rw [h] at h'

chore: bump dependencies (#4012)

This just bumps the Std dependency, to get access to Mario's new "Try this:" implementation.

Co-authored-by: Bulhwi Cha <chabulhwi@semmalgil.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@anu.edu.au> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>

f513eb6d

Diff

@@ -175,17 +175,7 @@ theorem lt_one_iff {n : ℕ} : n < 1 ↔ n = 0 :=
 
 /-! ### `add` -/
 
-
-theorem add_pos_left {m : ℕ} (h : 0 < m) (n : ℕ) : 0 < m + n :=
-  calc
-    m + n > 0 + n := Nat.add_lt_add_right h n
-    _ = n := Nat.zero_add n
-    _ ≥ 0 := zero_le n
 #align nat.add_pos_left Nat.add_pos_left
-
-theorem add_pos_right (m : ℕ) {n : ℕ} (h : 0 < n) : 0 < m + n := by
-  rw [add_comm]
-  exact add_pos_left h m
 #align nat.add_pos_right Nat.add_pos_right
 
 theorem add_pos_iff_pos_or_pos (m n : ℕ) : 0 < m + n ↔ 0 < m ∨ 0 < n :=

chore: fix #align lines (#3640)

This PR fixes two things:

Most align statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align). This is often seen in the mathport output after ending calc blocks.
All remaining more-than-one-line #align statements. (This was needed for a script I wrote for #3630.)

2b42dc7c

Diff

@@ -181,7 +181,6 @@ theorem add_pos_left {m : ℕ} (h : 0 < m) (n : ℕ) : 0 < m + n :=
     m + n > 0 + n := Nat.add_lt_add_right h n
     _ = n := Nat.zero_add n
     _ ≥ 0 := zero_le n
-
 #align nat.add_pos_left Nat.add_pos_left
 
 theorem add_pos_right (m : ℕ) {n : ℕ} (h : 0 < n) : 0 < m + n := by
@@ -211,7 +210,6 @@ theorem add_eq_two_iff : m + n = 2 ↔ m = 0 ∧ n = 2 ∨ m = 1 ∧ n = 1 ∨ m
   cases n <;>
   simp [(succ_ne_zero 1).symm, (show 2 = Nat.succ 1 from rfl),
     succ_eq_add_one, ← add_assoc, succ_inj', add_eq_one_iff]
-
 #align nat.add_eq_two_iff Nat.add_eq_two_iff
 
 theorem add_eq_three_iff :
@@ -396,7 +394,6 @@ protected theorem div_le_of_le_mul' (h : m ≤ k * n) : m / k ≤ n :=
         k * (m / k) ≤ m % k + k * (m / k) := Nat.le_add_left _ _
         _ = m := mod_add_div _ _
         _ ≤ k * n := h) k0
-
 #align nat.div_le_of_le_mul' Nat.div_le_of_le_mul'
 
 protected theorem div_le_self' (m n : ℕ) : m / n ≤ m :=
@@ -405,7 +402,6 @@ protected theorem div_le_self' (m n : ℕ) : m / n ≤ m :=
       calc
         m = 1 * m := (one_mul _).symm
         _ ≤ n * m := Nat.mul_le_mul_right _ n0
-
 #align nat.div_le_self' Nat.div_le_self'
 
 protected theorem div_lt_of_lt_mul (h : m < n * k) : m / n < k :=
@@ -432,8 +428,6 @@ theorem div_mul_div_le_div (m n k : ℕ) : m / k * n / m ≤ n / k :=
       _ = n / k := by
         { rw [Nat.div_div_eq_div_mul, mul_comm n, mul_comm k,
             Nat.mul_div_mul_left _ _ (Nat.pos_of_ne_zero hm0)] }
-
-
 #align nat.div_mul_div_le_div Nat.div_mul_div_le_div
 
 theorem eq_zero_of_le_half (h : n ≤ n / 2) : n = 0 :=
@@ -548,7 +542,6 @@ theorem div_mul_div_comm (hmn : n ∣ m) (hkl : l ∣ k) : m / n * (k / l) = m *
       repeat' assumption
       -- Porting note: this line was `cc` in Lean3
       simp only [mul_comm, mul_left_comm, mul_assoc]
-
 #align nat.div_mul_div_comm Nat.div_mul_div_comm
 
 theorem div_eq_self : m / n = m ↔ m = 0 ∨ n = 1 := by

feat: Dot notation aliases (#3303)

Match https://github.com/leanprover-community/mathlib/pull/18698 and a bit of https://github.com/leanprover-community/mathlib/pull/18785.

Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com>

4fa401fa

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.nat.order.basic
-! leanprover-community/mathlib commit 26f081a2fb920140ed5bc5cc5344e84bcc7cb2b2
+! leanprover-community/mathlib commit e8638a0fcaf73e4500469f368ef9494e495099b3
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -289,21 +289,6 @@ theorem sub_succ' (m n : ℕ) : m - n.succ = m - n - 1 :=
 
 /-! ### `mul` -/
 
-
-theorem mul_eq_one_iff : ∀ {m n : ℕ}, m * n = 1 ↔ m = 1 ∧ n = 1
-  | 0, 0 => by decide
-  | 0, 1 => by decide
-  | 1, 0 => by decide
-  | m + 2, 0 => by simp
-  | 0, n + 2 => by simp
-  | m + 1, n + 1 =>
-    ⟨fun h => by
-      simp only [succ_mul, mul_succ, add_succ, one_mul, mul_one, (add_assoc _ _ _).symm,
-          ← succ_eq_add_one, add_eq_zero_iff, (show 1 = succ 0 from rfl), succ_inj'] at h
-      simp [h],
-      fun h => by simp only [h, mul_one]⟩
-#align nat.mul_eq_one_iff Nat.mul_eq_one_iff
-
 theorem succ_mul_pos (m : ℕ) (hn : 0 < n) : 0 < succ m * n :=
   mul_pos (succ_pos m) hn
 #align nat.succ_mul_pos Nat.succ_mul_pos

chore: bump to leanprover/lean4:nightly-2023-02-10 (#2188)

5bbbc25c

Diff

@@ -484,7 +484,7 @@ theorem half_le_of_sub_le_half {a b : ℕ} (h : a - b ≤ a / 2) : a / 2 ≤ b :
 theorem two_mul_odd_div_two (hn : n % 2 = 1) : 2 * (n / 2) = n - 1 := by
   conv =>
     rhs
-    rw [← Nat.mod_add_div n 2, hn, add_tsub_cancel_left]
+    rw [← Nat.mod_add_div n 2, hn, @add_tsub_cancel_left]
 #align nat.two_mul_odd_div_two Nat.two_mul_odd_div_two
 
 theorem div_dvd_of_dvd (h : n ∣ m) : m / n ∣ m :=
@@ -521,7 +521,7 @@ theorem not_dvd_of_pos_of_lt (h1 : 0 < n) (h2 : n < m) : ¬m ∣ n := by
 /-- If `m` and `n` are equal mod `k`, `m - n` is zero mod `k`. -/
 theorem sub_mod_eq_zero_of_mod_eq (h : m % k = n % k) : (m - n) % k = 0 := by
   rw [← Nat.mod_add_div m k, ← Nat.mod_add_div n k, ← h, tsub_add_eq_tsub_tsub,
-    add_tsub_cancel_left, ← mul_tsub k, Nat.mul_mod_right]
+    @add_tsub_cancel_left, ← mul_tsub k, Nat.mul_mod_right]
 #align nat.sub_mod_eq_zero_of_mod_eq Nat.sub_mod_eq_zero_of_mod_eq
 
 @[simp]

chore: bump to nightly-2023-02-03 (#1999)

78fc778d

Diff

@@ -177,7 +177,6 @@ theorem lt_one_iff {n : ℕ} : n < 1 ↔ n = 0 :=
 
 
 theorem add_pos_left {m : ℕ} (h : 0 < m) (n : ℕ) : 0 < m + n :=
-  show _ > _ from -- lean4#2073
   calc
     m + n > 0 + n := Nat.add_lt_add_right h n
     _ = n := Nat.zero_add n

chore: bump lean 01-29 (#1927)

1abd74a8

Diff

@@ -177,6 +177,7 @@ theorem lt_one_iff {n : ℕ} : n < 1 ↔ n = 0 :=
 
 
 theorem add_pos_left {m : ℕ} (h : 0 < m) (n : ℕ) : 0 < m + n :=
+  show _ > _ from -- lean4#2073
   calc
     m + n > 0 + n := Nat.add_lt_add_right h n
     _ = n := Nat.zero_add n

chore: make variables implicit (#1545)

Corresponds to [#18167](https://github.com/leanprover-community/mathlib/pull/18167).

d89c3c10

Diff

@@ -74,7 +74,7 @@ instance canonicallyOrderedCommSemiring : CanonicallyOrderedCommSemiring ℕ :=
     (inferInstance : LinearOrderedSemiring ℕ), (inferInstance : CommSemiring ℕ) with
     exists_add_of_le := fun {_ _} h => (Nat.le.dest h).imp fun _ => Eq.symm,
     le_self_add := Nat.le_add_right,
-    eq_zero_or_eq_zero_of_mul_eq_zero := fun _ _ => Nat.eq_zero_of_mul_eq_zero }
+    eq_zero_or_eq_zero_of_mul_eq_zero := Nat.eq_zero_of_mul_eq_zero }
 
 instance canonicallyLinearOrderedAddMonoid : CanonicallyLinearOrderedAddMonoid ℕ :=
   { (inferInstance : CanonicallyOrderedAddMonoid ℕ), Nat.linearOrder with }

chore: format by line breaks with long lines (#1529)

This was done semi-automatically with some regular expressions in vim in contrast to the fully automatic https://github.com/leanprover-community/mathlib4/pull/1523.

Co-authored-by: Moritz Firsching <firsching@google.com>

1050066f

Diff

@@ -676,8 +676,8 @@ theorem le_findGreatest (hmb : m ≤ n) (hm : P m) : m ≤ Nat.findGreatest P n
   le_of_not_lt fun hlt => (findGreatest_eq_iff.1 rfl).2.2 hlt hmb hm
 #align nat.le_find_greatest Nat.le_findGreatest
 
-theorem findGreatest_mono_right (P : ℕ → Prop) [DecidablePred P] : Monotone (Nat.findGreatest P) :=
-  by
+theorem findGreatest_mono_right (P : ℕ → Prop) [DecidablePred P] :
+    Monotone (Nat.findGreatest P) := by
   refine monotone_nat_of_le_succ fun n => ?_
   rw [findGreatest_succ]
   split_ifs

chore: format by line breaks (#1523)

During porting, I usually fix the desired format we seem to want for the line breaks around by with

awk '{do {{if (match($0, "^  by$") && length(p) < 98) {p=p " by";} else {if (NR!=1) {print p}; p=$0}}} while (getline == 1) if (getline==0) print p}' Mathlib/File/Im/Working/On.lean

I noticed there are some more files that slipped through.

This pull request is the result of running this command:

grep -lr "^  by\$" Mathlib | xargs -n 1 awk -i inplace '{do {{if (match($0, "^  by$") && length(p) < 98 && not (match(p, "^[ \t]*--"))) {p=p " by";} else {if (NR!=1) {print p}; p=$0}}} while (getline == 1) if (getline==0) print p}'

Co-authored-by: Moritz Firsching <firsching@google.com>

d6d859a7

Diff

@@ -465,15 +465,13 @@ theorem mul_div_mul_comm_of_dvd_dvd (hmk : k ∣ m) (hnl : l ∣ n) :
     Nat.mul_div_cancel_left _ (mul_pos hk0 hl0)]
 #align nat.mul_div_mul_comm_of_dvd_dvd Nat.mul_div_mul_comm_of_dvd_dvd
 
-theorem le_half_of_half_lt_sub {a b : ℕ} (h : a / 2 < a - b) : b ≤ a / 2 :=
-  by
+theorem le_half_of_half_lt_sub {a b : ℕ} (h : a / 2 < a - b) : b ≤ a / 2 := by
   rw [Nat.le_div_iff_mul_le two_pos]
   rw [Nat.div_lt_iff_lt_mul two_pos, Nat.mul_sub_right_distrib, lt_tsub_iff_right, mul_two a] at h
   exact le_of_lt (Nat.lt_of_add_lt_add_left h)
 #align nat.le_half_of_half_lt_sub Nat.le_half_of_half_lt_sub
 
-theorem half_le_of_sub_le_half {a b : ℕ} (h : a - b ≤ a / 2) : a / 2 ≤ b :=
-  by
+theorem half_le_of_sub_le_half {a b : ℕ} (h : a - b ≤ a / 2) : a / 2 ≤ b := by
   rw [Nat.le_div_iff_mul_le two_pos, Nat.mul_sub_right_distrib, tsub_le_iff_right, mul_two,
     add_le_add_iff_left] at h
   rw [← Nat.mul_div_left b two_pos]

chore: remove iff_self from simp only after lean4#1933 (#1406)

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

72b23bd4

Diff

@@ -260,7 +260,7 @@ instance : OrderedSub ℕ := by
   intro m n k
   induction' n with n ih generalizing k
   · simp
-  · simp only [sub_succ, pred_le_iff, ih, succ_add, add_succ, iff_self]
+  · simp only [sub_succ, pred_le_iff, ih, succ_add, add_succ]
 
 theorem lt_pred_iff : n < pred m ↔ succ n < m :=
   show n < m - 1 ↔ n + 1 < m from lt_tsub_iff_right

chore: update Data.Nat.Order.Basic to account for my mathlib PR (#1378)

bf1283e9

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.nat.order.basic
-! leanprover-community/mathlib commit 655994e298904d7e5bbd1e18c95defd7b543eb94
+! leanprover-community/mathlib commit 26f081a2fb920140ed5bc5cc5344e84bcc7cb2b2
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -465,6 +465,21 @@ theorem mul_div_mul_comm_of_dvd_dvd (hmk : k ∣ m) (hnl : l ∣ n) :
     Nat.mul_div_cancel_left _ (mul_pos hk0 hl0)]
 #align nat.mul_div_mul_comm_of_dvd_dvd Nat.mul_div_mul_comm_of_dvd_dvd
 
+theorem le_half_of_half_lt_sub {a b : ℕ} (h : a / 2 < a - b) : b ≤ a / 2 :=
+  by
+  rw [Nat.le_div_iff_mul_le two_pos]
+  rw [Nat.div_lt_iff_lt_mul two_pos, Nat.mul_sub_right_distrib, lt_tsub_iff_right, mul_two a] at h
+  exact le_of_lt (Nat.lt_of_add_lt_add_left h)
+#align nat.le_half_of_half_lt_sub Nat.le_half_of_half_lt_sub
+
+theorem half_le_of_sub_le_half {a b : ℕ} (h : a - b ≤ a / 2) : a / 2 ≤ b :=
+  by
+  rw [Nat.le_div_iff_mul_le two_pos, Nat.mul_sub_right_distrib, tsub_le_iff_right, mul_two,
+    add_le_add_iff_left] at h
+  rw [← Nat.mul_div_left b two_pos]
+  exact Nat.div_le_div_right h
+#align nat.half_le_of_sub_le_half Nat.half_le_of_sub_le_half
+
 /-! ### `mod`, `dvd` -/

chore: fix more casing errors per naming scheme (#1232)

I've avoided anything under Tactic or test.

In correcting the names, I found Option.isNone_iff_eq_none duplicated between Std and Mathlib, so the Mathlib one has been removed.

Co-authored-by: Reid Barton <rwbarton@gmail.com>

31a56f75

Diff

@@ -282,7 +282,7 @@ theorem le_or_le_of_add_eq_add_pred (h : k + l = m + n - 1) : m ≤ k ∨ n ≤
     exact Nat.le_of_pred_lt h'
 #align nat.le_or_le_of_add_eq_add_pred Nat.le_or_le_of_add_eq_add_pred
 
-/-- A version of `nat.sub_succ` in the form `_ - 1` instead of `nat.pred _`. -/
+/-- A version of `Nat.sub_succ` in the form `_ - 1` instead of `Nat.pred _`. -/
 theorem sub_succ' (m n : ℕ) : m - n.succ = m - n - 1 :=
   rfl
 #align nat.sub_succ' Nat.sub_succ'
@@ -389,13 +389,13 @@ theorem diag_induction (P : ℕ → ℕ → Prop) (ha : ∀ a, P (a + 1) (a + 1)
   decreasing_by { assumption }
 #align nat.diag_induction Nat.diag_induction
 
-/-- A subset of `ℕ` containing `k : ℕ` and closed under `nat.succ` contains every `n ≥ k`. -/
+/-- A subset of `ℕ` containing `k : ℕ` and closed under `Nat.succ` contains every `n ≥ k`. -/
 theorem set_induction_bounded {S : Set ℕ} (hk : k ∈ S) (h_ind : ∀ k : ℕ, k ∈ S → k + 1 ∈ S)
     (hnk : k ≤ n) : n ∈ S :=
   @leRecOn (fun n => n ∈ S) k n hnk @h_ind hk
 #align nat.set_induction_bounded Nat.set_induction_bounded
 
-/-- A subset of `ℕ` containing zero and closed under `nat.succ` contains all of `ℕ`. -/
+/-- A subset of `ℕ` containing zero and closed under `Nat.succ` contains all of `ℕ`. -/
 theorem set_induction {S : Set ℕ} (hb : 0 ∈ S) (h_ind : ∀ k : ℕ, k ∈ S → k + 1 ∈ S) (n : ℕ) :
     n ∈ S :=
   set_induction_bounded hb h_ind (zero_le n)

chore: fix casing per naming scheme (#1183)

Fix a lot of wrong casing mostly in the docstrings but also sometimes in def/theorem names. E.g. fin 2 --> Fin 2, add_monoid_hom --> AddMonoidHom

Remove \n from to_additive docstrings that were inserted by mathport.

Move files and directories with Gcd and Smul to GCD and SMul

71723d8b

Diff

@@ -252,7 +252,7 @@ theorem pred_le_iff : pred m ≤ n ↔ m ≤ succ n :=
 
 /-! ### `sub`
 
-Most lemmas come from the `has_ordered_sub` instance on `ℕ`. -/
+Most lemmas come from the `OrderedSub` instance on `ℕ`. -/
 
 
 instance : OrderedSub ℕ := by

feat: Port Data.Nat.Size (#1140)

550b5853

Co-authored-by: ART0 <18333981+0Art0@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

dddfba93

Diff

@@ -10,6 +10,8 @@ Authors: Floris van Doorn, Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
 import Mathlib.Algebra.Order.Ring.Canonical
 import Mathlib.Data.Nat.Basic
+import Mathlib.Data.Nat.Bits
+
 
 /-!
 # The natural numbers as a linearly ordered commutative semiring
@@ -696,6 +698,102 @@ theorem findGreatest_of_ne_zero (h : Nat.findGreatest P n = m) (h0 : m ≠ 0) :
 
 end FindGreatest
 
+/-! ### `bit0` and `bit1` -/
+section Bit
+
+set_option linter.deprecated false
+
+protected theorem bit0_le {n m : ℕ} (h : n ≤ m) : bit0 n ≤ bit0 m :=
+  add_le_add h h
+#align nat.bit0_le Nat.bit0_le
+
+protected theorem bit1_le {n m : ℕ} (h : n ≤ m) : bit1 n ≤ bit1 m :=
+  succ_le_succ (add_le_add h h)
+#align nat.bit1_le Nat.bit1_le
+
+theorem bit_le : ∀ (b : Bool) {m n : ℕ}, m ≤ n → bit b m ≤ bit b n
+  | true, _, _, h => Nat.bit1_le  h
+  | false, _, _, h => Nat.bit0_le h
+#align nat.bit_le Nat.bit_le
+
+theorem bit0_le_bit : ∀ (b) {m n : ℕ}, m ≤ n → bit0 m ≤ bit b n
+  | true, _, _, h => le_of_lt <| Nat.bit0_lt_bit1 h
+  | false, _, _, h => Nat.bit0_le h
+#align nat.bit0_le_bit Nat.bit0_le_bit
+
+theorem bit_le_bit1 : ∀ (b) {m n : ℕ}, m ≤ n → bit b m ≤ bit1 n
+  | false, _, _, h => le_of_lt <| Nat.bit0_lt_bit1 h
+  | true, _, _, h => Nat.bit1_le h
+#align nat.bit_le_bit1 Nat.bit_le_bit1
+
+theorem bit_lt_bit0 : ∀ (b) {m n : ℕ}, m < n → bit b m < bit0 n
+  | true, _, _, h => Nat.bit1_lt_bit0 h
+  | false, _, _, h => Nat.bit0_lt h
+#align nat.bit_lt_bit0 Nat.bit_lt_bit0
+
+theorem bit_lt_bit (a b) (h : m < n) : bit a m < bit b n :=
+  lt_of_lt_of_le (bit_lt_bit0 _ h) (bit0_le_bit _ le_rfl)
+#align nat.bit_lt_bit Nat.bit_lt_bit
+
+@[simp]
+theorem bit0_le_bit1_iff : bit0 m ≤ bit1 n ↔ m ≤ n :=
+  ⟨fun h => by
+    rwa [← Nat.lt_succ_iff, n.bit1_eq_succ_bit0,
+    ← n.bit0_succ_eq, bit0_lt_bit0, Nat.lt_succ_iff] at h,
+    fun h => le_of_lt (Nat.bit0_lt_bit1 h)⟩
+#align nat.bit0_le_bit1_iff Nat.bit0_le_bit1_iff
+
+@[simp]
+theorem bit0_lt_bit1_iff : bit0 m < bit1 n ↔ m ≤ n :=
+  ⟨fun h => bit0_le_bit1_iff.1 (le_of_lt h), Nat.bit0_lt_bit1⟩
+#align nat.bit0_lt_bit1_iff Nat.bit0_lt_bit1_iff
+
+@[simp]
+theorem bit1_le_bit0_iff : bit1 m ≤ bit0 n ↔ m < n :=
+  ⟨fun h => by rwa [m.bit1_eq_succ_bit0, succ_le_iff, bit0_lt_bit0] at h, fun h =>
+    le_of_lt (Nat.bit1_lt_bit0 h)⟩
+#align nat.bit1_le_bit0_iff Nat.bit1_le_bit0_iff
+
+@[simp]
+theorem bit1_lt_bit0_iff : bit1 m < bit0 n ↔ m < n :=
+  ⟨fun h => bit1_le_bit0_iff.1 (le_of_lt h), Nat.bit1_lt_bit0⟩
+#align nat.bit1_lt_bit0_iff Nat.bit1_lt_bit0_iff
+
+-- Porting note: temporarily porting only needed portions
+/-
+@[simp]
+theorem one_le_bit0_iff : 1 ≤ bit0 n ↔ 0 < n := by
+  convert bit1_le_bit0_iff
+  rfl
+#align nat.one_le_bit0_iff Nat.one_le_bit0_iff
+
+@[simp]
+theorem one_lt_bit0_iff : 1 < bit0 n ↔ 1 ≤ n := by
+  convert bit1_lt_bit0_iff
+  rfl
+#align nat.one_lt_bit0_iff Nat.one_lt_bit0_iff
+
+@[simp]
+theorem bit_le_bit_iff : ∀ {b : Bool}, bit b m ≤ bit b n ↔ m ≤ n
+  | false => bit0_le_bit0
+  | true => bit1_le_bit1
+#align nat.bit_le_bit_iff Nat.bit_le_bit_iff
+
+@[simp]
+theorem bit_lt_bit_iff : ∀ {b : Bool}, bit b m < bit b n ↔ m < n
+  | false => bit0_lt_bit0
+  | true => bit1_lt_bit1
+#align nat.bit_lt_bit_iff Nat.bit_lt_bit_iff
+
+@[simp]
+theorem bit_le_bit1_iff : ∀ {b : Bool}, bit b m ≤ bit1 n ↔ m ≤ n
+  | false => bit0_le_bit1_iff
+  | true => bit1_le_bit1
+#align nat.bit_le_bit1_iff Nat.bit_le_bit1_iff
+-/
+
+end Bit
+
 /-! ### decidability of predicates -/

chore: update lean4/std4 (#1096)

a9a1f7d7

Diff

@@ -91,8 +91,6 @@ theorem one_lt_iff_ne_zero_and_ne_one : ∀ {n : ℕ}, 1 < n ↔ n ≠ 0 ∧ n 
   | n + 2 => by simp
 #align nat.one_lt_iff_ne_zero_and_ne_one Nat.one_lt_iff_ne_zero_and_ne_one
 
-protected theorem mul_ne_zero (n0 : n ≠ 0) (m0 : m ≠ 0) : n * m ≠ 0
-  | nm => (eq_zero_of_mul_eq_zero nm).elim n0 m0
 #align nat.mul_ne_zero Nat.mul_ne_zero
 
 -- Porting note: already in Std
@@ -446,7 +444,7 @@ theorem div_mul_div_le_div (m n k : ℕ) : m / k * n / m ≤ n / k :=
         Nat.div_le_div_right (by rw [mul_comm] ; exact mul_div_le_mul_div_assoc _ _ _)
       _ = n / k := by
         { rw [Nat.div_div_eq_div_mul, mul_comm n, mul_comm k,
-            Nat.mul_div_mul _ _ (Nat.pos_of_ne_zero hm0)] }
+            Nat.mul_div_mul_left _ _ (Nat.pos_of_ne_zero hm0)] }
 
 
 #align nat.div_mul_div_le_div Nat.div_mul_div_le_div