data.multiset.fold | Mathlib porting status

Changes since the initial port

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

Changes in mathlib3

9003f287

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

f2f413b9

bump to nightly-2024-04-07-08

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

b03b8656

Diff

@@ -167,11 +167,9 @@ theorem max_le_of_forall_le {α : Type _} [CanonicallyLinearOrderedAddCommMonoid
 #align multiset.max_le_of_forall_le Multiset.max_le_of_forall_le
 -/
 
-#print Multiset.max_nat_le_of_forall_le /-
 theorem max_nat_le_of_forall_le (l : Multiset ℕ) (n : ℕ) (h : ∀ x ∈ l, x ≤ n) : l.fold max 0 ≤ n :=
   max_le_of_forall_le l n h
 #align multiset.max_nat_le_of_forall_le Multiset.max_nat_le_of_forall_le
--/
 
 end Order

f2f413b9

bump to nightly-2024-02-23-08

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

ac9421d6

Diff

@@ -25,7 +25,7 @@ variable {α β : Type _}
 
 section Fold
 
-variable (op : α → α → α) [hc : IsCommutative α op] [ha : IsAssociative α op]
+variable (op : α → α → α) [hc : Std.Commutative α op] [ha : Std.Associative α op]
 
 local notation a " * " b => op a b
 
@@ -128,7 +128,7 @@ theorem fold_distrib {f g : β → α} (u₁ u₂ : α) (s : Multiset β) :
 -/
 
 #print Multiset.fold_hom /-
-theorem fold_hom {op' : β → β → β} [IsCommutative β op'] [IsAssociative β op'] {m : α → β}
+theorem fold_hom {op' : β → β → β} [Std.Commutative β op'] [Std.Associative β op'] {m : α → β}
     (hm : ∀ x y, m (op x y) = op' (m x) (m y)) (b : α) (s : Multiset α) :
     (s.map m).fold op' (m b) = m (s.fold op b) :=
   Multiset.induction_on s (by simp) (by simp (config := { contextual := true }) [hm])

f2f413b9

bump to nightly-2024-02-05-08

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

516c6ec2

Diff

@@ -144,7 +144,7 @@ theorem fold_union_inter [DecidableEq α] (s₁ s₂ : Multiset α) (b₁ b₂ :
 
 #print Multiset.fold_dedup_idem /-
 @[simp]
-theorem fold_dedup_idem [DecidableEq α] [hi : IsIdempotent α op] (s : Multiset α) (b : α) :
+theorem fold_dedup_idem [DecidableEq α] [hi : Std.IdempotentOp α op] (s : Multiset α) (b : α) :
     (dedup s).fold op b = s.fold op b :=
   Multiset.induction_on s (by simp) fun a s IH =>
     by

f2f413b9

bump to nightly-2023-10-07-06

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

d191b687

Diff

@@ -159,7 +159,7 @@ end Fold
 section Order
 
 #print Multiset.max_le_of_forall_le /-
-theorem max_le_of_forall_le {α : Type _} [CanonicallyLinearOrderedAddMonoid α] (l : Multiset α)
+theorem max_le_of_forall_le {α : Type _} [CanonicallyLinearOrderedAddCommMonoid α] (l : Multiset α)
     (n : α) (h : ∀ x ∈ l, x ≤ n) : l.fold max ⊥ ≤ n :=
   by
   induction l using Quotient.inductionOn

f2f413b9

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) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
-import Mathbin.Data.Multiset.Dedup
-import Mathbin.Data.List.MinMax
+import Data.Multiset.Dedup
+import Data.List.MinMax
 
 #align_import data.multiset.fold from "leanprover-community/mathlib"@"f2f413b9d4be3a02840d0663dace76e8fe3da053"

f2f413b9

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) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module data.multiset.fold
-! leanprover-community/mathlib commit f2f413b9d4be3a02840d0663dace76e8fe3da053
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Multiset.Dedup
 import Mathbin.Data.List.MinMax
 
+#align_import data.multiset.fold from "leanprover-community/mathlib"@"f2f413b9d4be3a02840d0663dace76e8fe3da053"
+
 /-!
 # The fold operation for a commutative associative operation over a multiset.

f2f413b9

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -30,11 +30,8 @@ section Fold
 
 variable (op : α → α → α) [hc : IsCommutative α op] [ha : IsAssociative α op]
 
--- mathport name: op
 local notation a " * " b => op a b
 
-include hc ha
-
 #print Multiset.fold /-
 /-- `fold op b s` folds a commutative associative operation `op` over
   the multiset `s`. -/
@@ -164,21 +161,26 @@ end Fold
 
 section Order
 
+#print Multiset.max_le_of_forall_le /-
 theorem max_le_of_forall_le {α : Type _} [CanonicallyLinearOrderedAddMonoid α] (l : Multiset α)
     (n : α) (h : ∀ x ∈ l, x ≤ n) : l.fold max ⊥ ≤ n :=
   by
   induction l using Quotient.inductionOn
   simpa using List.max_le_of_forall_le _ _ h
 #align multiset.max_le_of_forall_le Multiset.max_le_of_forall_le
+-/
 
+#print Multiset.max_nat_le_of_forall_le /-
 theorem max_nat_le_of_forall_le (l : Multiset ℕ) (n : ℕ) (h : ∀ x ∈ l, x ≤ n) : l.fold max 0 ≤ n :=
   max_le_of_forall_le l n h
 #align multiset.max_nat_le_of_forall_le Multiset.max_nat_le_of_forall_le
+-/
 
 end Order
 
 open Nat
 
+#print Multiset.le_smul_dedup /-
 theorem le_smul_dedup [DecidableEq α] (s : Multiset α) : ∃ n : ℕ, s ≤ n • dedup s :=
   ⟨(s.map fun a => count a s).fold max 0,
     le_iff_count.2 fun a => by
@@ -188,6 +190,7 @@ theorem le_smul_dedup [DecidableEq α] (s : Multiset α) : ∃ n : ℕ, s ≤ n
           [simp [le_max_left]; simpa [cons_erase h]]
       · simp [count_eq_zero.2 h, Nat.zero_le]⟩
 #align multiset.le_smul_dedup Multiset.le_smul_dedup
+-/
 
 end Multiset

f2f413b9

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -185,7 +185,7 @@ theorem le_smul_dedup [DecidableEq α] (s : Multiset α) : ∃ n : ℕ, s ≤ n
       rw [count_nsmul]; by_cases a ∈ s
       · refine' le_trans _ (Nat.mul_le_mul_left _ <| count_pos.2 <| mem_dedup.2 h)
         have : count a s ≤ fold max 0 (map (fun a => count a s) (a ::ₘ erase s a)) <;>
-          [simp [le_max_left];simpa [cons_erase h] ]
+          [simp [le_max_left]; simpa [cons_erase h]]
       · simp [count_eq_zero.2 h, Nat.zero_le]⟩
 #align multiset.le_smul_dedup Multiset.le_smul_dedup

f2f413b9

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -164,12 +164,6 @@ end Fold
 
 section Order
 
-/- warning: multiset.max_le_of_forall_le -> Multiset.max_le_of_forall_le is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : CanonicallyLinearOrderedAddMonoid.{u1} α] (l : Multiset.{u1} α) (n : α), (forall (x : α), (Membership.Mem.{u1, u1} α (Multiset.{u1} α) (Multiset.hasMem.{u1} α) x l) -> (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) x n)) -> (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) (Multiset.fold.{u1} α (LinearOrder.max.{u1} α (CanonicallyLinearOrderedAddMonoid.toLinearOrder.{u1} α _inst_1)) (sup_isCommutative.{u1} α (CanonicallyLinearOrderedAddMonoid.semilatticeSup.{u1} α _inst_1)) (sup_isAssociative.{u1} α (CanonicallyLinearOrderedAddMonoid.semilatticeSup.{u1} α _inst_1)) (Bot.bot.{u1} α (CanonicallyOrderedAddMonoid.toHasBot.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))) l) n)
-but is expected to have type
-  forall {α : Type.{u1}} [_inst_1 : CanonicallyLinearOrderedAddMonoid.{u1} α] (l : Multiset.{u1} α) (n : α), (forall (x : α), (Membership.mem.{u1, u1} α (Multiset.{u1} α) (Multiset.instMembershipMultiset.{u1} α) x l) -> (LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) x n)) -> (LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) (Multiset.fold.{u1} α (Max.max.{u1} α (LinearOrder.toMax.{u1} α (CanonicallyLinearOrderedAddMonoid.toLinearOrder.{u1} α _inst_1))) (instIsCommutativeMaxToMax.{u1} α (CanonicallyLinearOrderedAddMonoid.toLinearOrder.{u1} α _inst_1)) (instIsAssociativeMaxToMax.{u1} α (CanonicallyLinearOrderedAddMonoid.toLinearOrder.{u1} α _inst_1)) (Bot.bot.{u1} α (CanonicallyOrderedAddMonoid.toBot.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))) l) n)
-Case conversion may be inaccurate. Consider using '#align multiset.max_le_of_forall_le Multiset.max_le_of_forall_leₓ'. -/
 theorem max_le_of_forall_le {α : Type _} [CanonicallyLinearOrderedAddMonoid α] (l : Multiset α)
     (n : α) (h : ∀ x ∈ l, x ≤ n) : l.fold max ⊥ ≤ n :=
   by
@@ -177,12 +171,6 @@ theorem max_le_of_forall_le {α : Type _} [CanonicallyLinearOrderedAddMonoid α]
   simpa using List.max_le_of_forall_le _ _ h
 #align multiset.max_le_of_forall_le Multiset.max_le_of_forall_le
 
-/- warning: multiset.max_nat_le_of_forall_le -> Multiset.max_nat_le_of_forall_le is a dubious translation:
-lean 3 declaration is
-  forall (l : Multiset.{0} Nat) (n : Nat), (forall (x : Nat), (Membership.Mem.{0, 0} Nat (Multiset.{0} Nat) (Multiset.hasMem.{0} Nat) x l) -> (LE.le.{0} Nat Nat.hasLe x n)) -> (LE.le.{0} Nat Nat.hasLe (Multiset.fold.{0} Nat (LinearOrder.max.{0} Nat Nat.linearOrder) (sup_isCommutative.{0} Nat (CanonicallyLinearOrderedAddMonoid.semilatticeSup.{0} Nat Nat.canonicallyLinearOrderedAddMonoid)) (sup_isAssociative.{0} Nat (CanonicallyLinearOrderedAddMonoid.semilatticeSup.{0} Nat Nat.canonicallyLinearOrderedAddMonoid)) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) l) n)
-but is expected to have type
-  forall (l : Multiset.{0} Nat) (n : Nat), (forall (x : Nat), (Membership.mem.{0, 0} Nat (Multiset.{0} Nat) (Multiset.instMembershipMultiset.{0} Nat) x l) -> (LE.le.{0} Nat instLENat x n)) -> (LE.le.{0} Nat instLENat (Multiset.fold.{0} Nat (Max.max.{0} Nat (LinearOrder.toMax.{0} Nat Nat.linearOrder)) (instIsCommutativeMaxToMax.{0} Nat Nat.linearOrder) (instIsAssociativeMaxToMax.{0} Nat Nat.linearOrder) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) l) n)
-Case conversion may be inaccurate. Consider using '#align multiset.max_nat_le_of_forall_le Multiset.max_nat_le_of_forall_leₓ'. -/
 theorem max_nat_le_of_forall_le (l : Multiset ℕ) (n : ℕ) (h : ∀ x ∈ l, x ≤ n) : l.fold max 0 ≤ n :=
   max_le_of_forall_le l n h
 #align multiset.max_nat_le_of_forall_le Multiset.max_nat_le_of_forall_le
@@ -191,12 +179,6 @@ end Order
 
 open Nat
 
-/- warning: multiset.le_smul_dedup -> Multiset.le_smul_dedup is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Multiset.{u1} α), Exists.{1} Nat (fun (n : Nat) => LE.le.{u1} (Multiset.{u1} α) (Preorder.toHasLe.{u1} (Multiset.{u1} α) (PartialOrder.toPreorder.{u1} (Multiset.{u1} α) (Multiset.partialOrder.{u1} α))) s (SMul.smul.{0, u1} Nat (Multiset.{u1} α) (AddMonoid.SMul.{u1} (Multiset.{u1} α) (AddRightCancelMonoid.toAddMonoid.{u1} (Multiset.{u1} α) (AddCancelMonoid.toAddRightCancelMonoid.{u1} (Multiset.{u1} α) (AddCancelCommMonoid.toAddCancelMonoid.{u1} (Multiset.{u1} α) (OrderedCancelAddCommMonoid.toCancelAddCommMonoid.{u1} (Multiset.{u1} α) (Multiset.orderedCancelAddCommMonoid.{u1} α)))))) n (Multiset.dedup.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s)))
-but is expected to have type
-  forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Multiset.{u1} α), Exists.{1} Nat (fun (n : Nat) => LE.le.{u1} (Multiset.{u1} α) (Preorder.toLE.{u1} (Multiset.{u1} α) (PartialOrder.toPreorder.{u1} (Multiset.{u1} α) (Multiset.instPartialOrderMultiset.{u1} α))) s (HSMul.hSMul.{0, u1, u1} Nat (Multiset.{u1} α) (Multiset.{u1} α) (instHSMul.{0, u1} Nat (Multiset.{u1} α) (AddMonoid.SMul.{u1} (Multiset.{u1} α) (AddRightCancelMonoid.toAddMonoid.{u1} (Multiset.{u1} α) (AddCancelMonoid.toAddRightCancelMonoid.{u1} (Multiset.{u1} α) (AddCancelCommMonoid.toAddCancelMonoid.{u1} (Multiset.{u1} α) (OrderedCancelAddCommMonoid.toCancelAddCommMonoid.{u1} (Multiset.{u1} α) (Multiset.instOrderedCancelAddCommMonoidMultiset.{u1} α))))))) n (Multiset.dedup.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s)))
-Case conversion may be inaccurate. Consider using '#align multiset.le_smul_dedup Multiset.le_smul_dedupₓ'. -/
 theorem le_smul_dedup [DecidableEq α] (s : Multiset α) : ∃ n : ℕ, s ≤ n • dedup s :=
   ⟨(s.map fun a => count a s).fold max 0,
     le_iff_count.2 fun a => by

f2f413b9

bump to nightly-2023-05-24-06

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

fbc7b476

Diff

@@ -203,7 +203,7 @@ theorem le_smul_dedup [DecidableEq α] (s : Multiset α) : ∃ n : ℕ, s ≤ n
       rw [count_nsmul]; by_cases a ∈ s
       · refine' le_trans _ (Nat.mul_le_mul_left _ <| count_pos.2 <| mem_dedup.2 h)
         have : count a s ≤ fold max 0 (map (fun a => count a s) (a ::ₘ erase s a)) <;>
-          [simp [le_max_left], simpa [cons_erase h] ]
+          [simp [le_max_left];simpa [cons_erase h] ]
       · simp [count_eq_zero.2 h, Nat.zero_le]⟩
 #align multiset.le_smul_dedup Multiset.le_smul_dedup

f2f413b9

bump to nightly-2023-05-16-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8

9cb92e8c

Diff

@@ -166,7 +166,7 @@ section Order
 
 /- warning: multiset.max_le_of_forall_le -> Multiset.max_le_of_forall_le is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : CanonicallyLinearOrderedAddMonoid.{u1} α] (l : Multiset.{u1} α) (n : α), (forall (x : α), (Membership.Mem.{u1, u1} α (Multiset.{u1} α) (Multiset.hasMem.{u1} α) x l) -> (LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) x n)) -> (LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) (Multiset.fold.{u1} α (LinearOrder.max.{u1} α (CanonicallyLinearOrderedAddMonoid.toLinearOrder.{u1} α _inst_1)) (sup_isCommutative.{u1} α (CanonicallyLinearOrderedAddMonoid.semilatticeSup.{u1} α _inst_1)) (sup_isAssociative.{u1} α (CanonicallyLinearOrderedAddMonoid.semilatticeSup.{u1} α _inst_1)) (Bot.bot.{u1} α (CanonicallyOrderedAddMonoid.toHasBot.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))) l) n)
+  forall {α : Type.{u1}} [_inst_1 : CanonicallyLinearOrderedAddMonoid.{u1} α] (l : Multiset.{u1} α) (n : α), (forall (x : α), (Membership.Mem.{u1, u1} α (Multiset.{u1} α) (Multiset.hasMem.{u1} α) x l) -> (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) x n)) -> (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) (Multiset.fold.{u1} α (LinearOrder.max.{u1} α (CanonicallyLinearOrderedAddMonoid.toLinearOrder.{u1} α _inst_1)) (sup_isCommutative.{u1} α (CanonicallyLinearOrderedAddMonoid.semilatticeSup.{u1} α _inst_1)) (sup_isAssociative.{u1} α (CanonicallyLinearOrderedAddMonoid.semilatticeSup.{u1} α _inst_1)) (Bot.bot.{u1} α (CanonicallyOrderedAddMonoid.toHasBot.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))) l) n)
 but is expected to have type
   forall {α : Type.{u1}} [_inst_1 : CanonicallyLinearOrderedAddMonoid.{u1} α] (l : Multiset.{u1} α) (n : α), (forall (x : α), (Membership.mem.{u1, u1} α (Multiset.{u1} α) (Multiset.instMembershipMultiset.{u1} α) x l) -> (LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) x n)) -> (LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α (OrderedAddCommMonoid.toPartialOrder.{u1} α (CanonicallyOrderedAddMonoid.toOrderedAddCommMonoid.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))))) (Multiset.fold.{u1} α (Max.max.{u1} α (LinearOrder.toMax.{u1} α (CanonicallyLinearOrderedAddMonoid.toLinearOrder.{u1} α _inst_1))) (instIsCommutativeMaxToMax.{u1} α (CanonicallyLinearOrderedAddMonoid.toLinearOrder.{u1} α _inst_1)) (instIsAssociativeMaxToMax.{u1} α (CanonicallyLinearOrderedAddMonoid.toLinearOrder.{u1} α _inst_1)) (Bot.bot.{u1} α (CanonicallyOrderedAddMonoid.toBot.{u1} α (CanonicallyLinearOrderedAddMonoid.toCanonicallyOrderedAddMonoid.{u1} α _inst_1))) l) n)
 Case conversion may be inaccurate. Consider using '#align multiset.max_le_of_forall_le Multiset.max_le_of_forall_leₓ'. -/
@@ -193,7 +193,7 @@ open Nat
 
 /- warning: multiset.le_smul_dedup -> Multiset.le_smul_dedup is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Multiset.{u1} α), Exists.{1} Nat (fun (n : Nat) => LE.le.{u1} (Multiset.{u1} α) (Preorder.toLE.{u1} (Multiset.{u1} α) (PartialOrder.toPreorder.{u1} (Multiset.{u1} α) (Multiset.partialOrder.{u1} α))) s (SMul.smul.{0, u1} Nat (Multiset.{u1} α) (AddMonoid.SMul.{u1} (Multiset.{u1} α) (AddRightCancelMonoid.toAddMonoid.{u1} (Multiset.{u1} α) (AddCancelMonoid.toAddRightCancelMonoid.{u1} (Multiset.{u1} α) (AddCancelCommMonoid.toAddCancelMonoid.{u1} (Multiset.{u1} α) (OrderedCancelAddCommMonoid.toCancelAddCommMonoid.{u1} (Multiset.{u1} α) (Multiset.orderedCancelAddCommMonoid.{u1} α)))))) n (Multiset.dedup.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s)))
+  forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Multiset.{u1} α), Exists.{1} Nat (fun (n : Nat) => LE.le.{u1} (Multiset.{u1} α) (Preorder.toHasLe.{u1} (Multiset.{u1} α) (PartialOrder.toPreorder.{u1} (Multiset.{u1} α) (Multiset.partialOrder.{u1} α))) s (SMul.smul.{0, u1} Nat (Multiset.{u1} α) (AddMonoid.SMul.{u1} (Multiset.{u1} α) (AddRightCancelMonoid.toAddMonoid.{u1} (Multiset.{u1} α) (AddCancelMonoid.toAddRightCancelMonoid.{u1} (Multiset.{u1} α) (AddCancelCommMonoid.toAddCancelMonoid.{u1} (Multiset.{u1} α) (OrderedCancelAddCommMonoid.toCancelAddCommMonoid.{u1} (Multiset.{u1} α) (Multiset.orderedCancelAddCommMonoid.{u1} α)))))) n (Multiset.dedup.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s)))
 but is expected to have type
   forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Multiset.{u1} α), Exists.{1} Nat (fun (n : Nat) => LE.le.{u1} (Multiset.{u1} α) (Preorder.toLE.{u1} (Multiset.{u1} α) (PartialOrder.toPreorder.{u1} (Multiset.{u1} α) (Multiset.instPartialOrderMultiset.{u1} α))) s (HSMul.hSMul.{0, u1, u1} Nat (Multiset.{u1} α) (Multiset.{u1} α) (instHSMul.{0, u1} Nat (Multiset.{u1} α) (AddMonoid.SMul.{u1} (Multiset.{u1} α) (AddRightCancelMonoid.toAddMonoid.{u1} (Multiset.{u1} α) (AddCancelMonoid.toAddRightCancelMonoid.{u1} (Multiset.{u1} α) (AddCancelCommMonoid.toAddCancelMonoid.{u1} (Multiset.{u1} α) (OrderedCancelAddCommMonoid.toCancelAddCommMonoid.{u1} (Multiset.{u1} α) (Multiset.instOrderedCancelAddCommMonoidMultiset.{u1} α))))))) n (Multiset.dedup.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s)))
 Case conversion may be inaccurate. Consider using '#align multiset.le_smul_dedup Multiset.le_smul_dedupₓ'. -/

f2f413b9

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

9003f287

chore(Algebra/BigOperators/List): Use Std lemmas (#11725)

Make Algebra.BigOperators.List.Basic, Data.List.Chain not depend on Data.Nat.Order.Basic by using Nat-specific Std lemmas rather than general mathlib ones. I leave the Data.Nat.Basic import since Algebra.BigOperators.List.Basic is algebra territory.
Make Algebra.BigOperators.List.Basic not depend on Algebra.Divisibility.Basic. I'm not too sure about that one since they already are algebra. My motivation is that they involve ring-like objects while big operators are about group-like objects, but this is in some sense a second order refactor.
As a consequence, move the divisibility and MonoidWithZero lemmas from Algebra.BigOperators.List.Basic to Algebra.BigOperators.List.Lemmas.
Move the content of Algebra.BigOperators.List.Defs to Algebra.BigOperators.List.Basic since no file imported the former without the latter and their imports are becoming very close after this PR.
Make Data.List.Count, Data.List.Dedup, Data.List.ProdSigma, Data.List.Zip not depend on Algebra.BigOperators.List.Basic.
As a consequence, move the big operators lemmas that were in there to Algebra.BigOperators.List.Basic. For the lemmas that were Nat -specific, keep a version of them stated using Nat.sum.
To help with this, add Nat.sum_eq_listSum (l : List Nat) : Nat.sum l = l.sum.

f7519d5e

Diff

@@ -4,7 +4,6 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
 import Mathlib.Data.Multiset.Bind
-import Mathlib.Data.List.MinMax
 
 #align_import data.multiset.fold from "leanprover-community/mathlib"@"9003f28797c0664a49e4179487267c494477d853"
 
@@ -122,20 +121,6 @@ theorem fold_dedup_idem [DecidableEq α] [hi : Std.IdempotentOp op] (s : Multise
 
 end Fold
 
-section Order
-
-theorem max_le_of_forall_le {α : Type*} [CanonicallyLinearOrderedAddCommMonoid α] (l : Multiset α)
-    (n : α) (h : ∀ x ∈ l, x ≤ n) : l.fold max ⊥ ≤ n := by
-  induction l using Quotient.inductionOn
-  simpa using List.max_le_of_forall_le _ _ h
-#align multiset.max_le_of_forall_le Multiset.max_le_of_forall_le
-
-theorem max_nat_le_of_forall_le (l : Multiset ℕ) (n : ℕ) (h : ∀ x ∈ l, x ≤ n) : l.fold max 0 ≤ n :=
-  max_le_of_forall_le l n h
-#align multiset.max_nat_le_of_forall_le Multiset.max_nat_le_of_forall_le
-
-end Order
-
 open Nat
 
 theorem le_smul_dedup [DecidableEq α] (s : Multiset α) : ∃ n : ℕ, s ≤ n • dedup s :=

9003f287

chore(Data/List): Use Std lemmas (#11711)

Make use of Nat-specific lemmas from Std rather than the general ones provided by mathlib. Also reverse the dependency between Multiset.Nodup/Multiset.dedup and Multiset.sum since only the latter needs algebra. Also rename Algebra.BigOperators.Multiset.Abs to Algebra.BigOperators.Multiset.Order and move some lemmas from Algebra.BigOperators.Multiset.Basic to it.

The ultimate goal here is to carve out Data, Algebra and Order sublibraries.

3713a3fe

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
-import Mathlib.Data.Multiset.Dedup
+import Mathlib.Data.Multiset.Bind
 import Mathlib.Data.List.MinMax
 
 #align_import data.multiset.fold from "leanprover-community/mathlib"@"9003f28797c0664a49e4179487267c494477d853"

9003f287

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

@@ -22,7 +22,7 @@ variable {α β : Type*}
 
 section Fold
 
-variable (op : α → α → α) [hc : IsCommutative α op] [ha : IsAssociative α op]
+variable (op : α → α → α) [hc : Std.Commutative op] [ha : Std.Associative op]
 
 local notation a " * " b => op a b
 
@@ -100,7 +100,7 @@ theorem fold_distrib {f g : β → α} (u₁ u₂ : α) (s : Multiset β) :
       ha.assoc, hc.comm (g a), ha.assoc])
 #align multiset.fold_distrib Multiset.fold_distrib
 
-theorem fold_hom {op' : β → β → β} [IsCommutative β op'] [IsAssociative β op'] {m : α → β}
+theorem fold_hom {op' : β → β → β} [Std.Commutative op'] [Std.Associative op'] {m : α → β}
     (hm : ∀ x y, m (op x y) = op' (m x) (m y)) (b : α) (s : Multiset α) :
     (s.map m).fold op' (m b) = m (s.fold op b) :=
   Multiset.induction_on s (by simp) (by simp (config := { contextual := true }) [hm])
@@ -112,7 +112,7 @@ theorem fold_union_inter [DecidableEq α] (s₁ s₂ : Multiset α) (b₁ b₂ :
 #align multiset.fold_union_inter Multiset.fold_union_inter
 
 @[simp]
-theorem fold_dedup_idem [DecidableEq α] [hi : IsIdempotent α op] (s : Multiset α) (b : α) :
+theorem fold_dedup_idem [DecidableEq α] [hi : Std.IdempotentOp op] (s : Multiset α) (b : α) :
     (dedup s).fold op b = s.fold op b :=
   Multiset.induction_on s (by simp) fun a s IH => by
     by_cases h : a ∈ s <;> simp [IH, h]

9003f287

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

Renames:

CanonicallyOrderedMonoid -> CanonicallyOrderedCommMonoid

CanonicallyOrderedAddMonoid -> CanonicallyOrderedAddCommMonoid

CanonicallyLinearOrderedMonoid -> CanonicallyLinearOrderedCommMonoid

CanonicallyLinearOrderedAddMonoid -> CanonicallyLinearOrderedAddCommMonoid

f3bc24c3

Diff

@@ -124,7 +124,7 @@ end Fold
 
 section Order
 
-theorem max_le_of_forall_le {α : Type*} [CanonicallyLinearOrderedAddMonoid α] (l : Multiset α)
+theorem max_le_of_forall_le {α : Type*} [CanonicallyLinearOrderedAddCommMonoid α] (l : Multiset α)
     (n : α) (h : ∀ x ∈ l, x ≤ n) : l.fold max ⊥ ≤ n := by
   induction l using Quotient.inductionOn
   simpa using List.max_le_of_forall_le _ _ h

9003f287

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -15,7 +15,7 @@ import Mathlib.Data.List.MinMax
 
 namespace Multiset
 
-variable {α β : Type _}
+variable {α β : Type*}
 
 /-! ### fold -/
 
@@ -80,7 +80,7 @@ theorem fold_add (b₁ b₂ : α) (s₁ s₂ : Multiset α) :
       ha.assoc])
 #align multiset.fold_add Multiset.fold_add
 
-theorem fold_bind {ι : Type _} (s : Multiset ι) (t : ι → Multiset α) (b : ι → α) (b₀ : α) :
+theorem fold_bind {ι : Type*} (s : Multiset ι) (t : ι → Multiset α) (b : ι → α) (b₀ : α) :
     (s.bind t).fold op ((s.map b).fold op b₀) =
     (s.map fun i => (t i).fold op (b i)).fold op b₀ := by
   induction' s using Multiset.induction_on with a ha ih
@@ -124,7 +124,7 @@ end Fold
 
 section Order
 
-theorem max_le_of_forall_le {α : Type _} [CanonicallyLinearOrderedAddMonoid α] (l : Multiset α)
+theorem max_le_of_forall_le {α : Type*} [CanonicallyLinearOrderedAddMonoid α] (l : Multiset α)
     (n : α) (h : ∀ x ∈ l, x ≤ n) : l.fold max ⊥ ≤ n := by
   induction l using Quotient.inductionOn
   simpa using List.max_le_of_forall_le _ _ h

9003f287

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

depends on: #5966

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

89aa3a3b

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module data.multiset.fold
-! leanprover-community/mathlib commit 9003f28797c0664a49e4179487267c494477d853
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Multiset.Dedup
 import Mathlib.Data.List.MinMax
 
+#align_import data.multiset.fold from "leanprover-community/mathlib"@"9003f28797c0664a49e4179487267c494477d853"
+
 /-!
 # The fold operation for a commutative associative operation over a multiset.
 -/

9003f287

chore: bye-bye, solo bys! (#3825)

This PR puts, with one exception, every single remaining by that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh. The exception is when the by begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.

Essentially this is s/\n *by$/ by/g, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated bys".

14167e48

Diff

@@ -84,8 +84,8 @@ theorem fold_add (b₁ b₂ : α) (s₁ s₂ : Multiset α) :
 #align multiset.fold_add Multiset.fold_add
 
 theorem fold_bind {ι : Type _} (s : Multiset ι) (t : ι → Multiset α) (b : ι → α) (b₀ : α) :
-    (s.bind t).fold op ((s.map b).fold op b₀) = (s.map fun i => (t i).fold op (b i)).fold op b₀ :=
-  by
+    (s.bind t).fold op ((s.map b).fold op b₀) =
+    (s.map fun i => (t i).fold op (b i)).fold op b₀ := by
   induction' s using Multiset.induction_on with a ha ih
   · rw [zero_bind, map_zero, map_zero, fold_zero]
   · rw [cons_bind, map_cons, map_cons, fold_cons_left, fold_cons_left, fold_add, ih]
@@ -128,8 +128,7 @@ end Fold
 section Order
 
 theorem max_le_of_forall_le {α : Type _} [CanonicallyLinearOrderedAddMonoid α] (l : Multiset α)
-    (n : α) (h : ∀ x ∈ l, x ≤ n) : l.fold max ⊥ ≤ n :=
-  by
+    (n : α) (h : ∀ x ∈ l, x ≤ n) : l.fold max ⊥ ≤ n := by
   induction l using Quotient.inductionOn
   simpa using List.max_le_of_forall_le _ _ h
 #align multiset.max_le_of_forall_le Multiset.max_le_of_forall_le

9003f287

chore: add missing hypothesis names to by_cases (#2679)

5d07683a

Diff

@@ -118,7 +118,7 @@ theorem fold_union_inter [DecidableEq α] (s₁ s₂ : Multiset α) (b₁ b₂ :
 theorem fold_dedup_idem [DecidableEq α] [hi : IsIdempotent α op] (s : Multiset α) (b : α) :
     (dedup s).fold op b = s.fold op b :=
   Multiset.induction_on s (by simp) fun a s IH => by
-    by_cases a ∈ s <;> simp [IH, h]
+    by_cases h : a ∈ s <;> simp [IH, h]
     show fold op b s = op a (fold op b s)
     rw [← cons_erase h, fold_cons_left, ← ha.assoc, hi.idempotent]
 #align multiset.fold_dedup_idem Multiset.fold_dedup_idem

9003f287

feat: port Data.Multiset.Fold (#1548)

5456ba11

`data.multiset.fold` ⟷ `Mathlib.Data.Multiset.Fold`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 150

data.multiset.fold ⟷ Mathlib.Data.Multiset.Fold

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 150

`data.multiset.fold` ⟷ `Mathlib.Data.Multiset.Fold`