[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a : α
m : Multiset ι
f g : ι → α
x y z : α
⊢ (fun x x_1 => x * x_1) x ((fun x x_1 => x * x_1) y z) = (fun x x_1 => x * x_1) y ((fun x x_1 => x * x_1) x z)
[PROOFSTEP]
simp [mul_left_comm]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
s : Multiset α
x y z : α
⊢ (fun x x_1 => x * x_1) x ((fun x x_1 => x * x_1) y z) = (fun x x_1 => x * x_1) y ((fun x x_1 => x * x_1) x z)
[PROOFSTEP]
simp [mul_left_comm]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
s : Multiset α
x y z : α
⊢ (fun x x_1 => x * x_1) ((fun x x_1 => x * x_1) x y) z = (fun x x_1 => x * x_1) ((fun x x_1 => x * x_1) x z) y
[PROOFSTEP]
simp [mul_right_comm]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
s : Multiset α
⊢ foldl (fun x y => y * x) (_ : ∀ (_x _y _z : α), _z * (_y * _x) = _y * (_z * _x)) 1 s =
    foldl (fun x x_1 => x * x_1) (_ : ∀ (x y z : α), x * y * z = x * z * y) 1 s
[PROOFSTEP]
simp [mul_comm]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
s : Multiset α
⊢ List.prod (toList s) = prod s
[PROOFSTEP]
conv_rhs => rw [← coe_toList s]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
s : Multiset α
| prod s
[PROOFSTEP]
rw [← coe_toList s]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
s : Multiset α
| prod s
[PROOFSTEP]
rw [← coe_toList s]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
s : Multiset α
| prod s
[PROOFSTEP]
rw [← coe_toList s]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
s : Multiset α
⊢ List.prod (toList s) = prod ↑(toList s)
[PROOFSTEP]
rw [coe_prod]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
s t : Multiset α
a : α
m : Multiset ι
f g : ι → α
inst✝ : DecidableEq α
h : a ∈ s
⊢ a * prod (erase s a) = prod s
[PROOFSTEP]
rw [← s.coe_toList, coe_erase, coe_prod, coe_prod, List.prod_erase (mem_toList.2 h)]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
s t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
inst✝ : DecidableEq ι
a : ι
h : a ∈ m
⊢ f a * prod (map f (erase m a)) = prod (map f m)
[PROOFSTEP]
rw [← m.coe_toList, coe_erase, coe_map, coe_map, coe_prod, coe_prod, List.prod_map_erase f (mem_toList.2 h)]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
a : α
⊢ prod {a} = a
[PROOFSTEP]
simp only [mul_one, prod_cons, ← cons_zero, eq_self_iff_true, prod_zero]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
a b : α
⊢ prod {a, b} = a * b
[PROOFSTEP]
rw [insert_eq_cons, prod_cons, prod_singleton]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t✝ : Multiset α
a : α
m : Multiset ι
f g : ι → α
s t : Multiset α
l₁ l₂ : List α
⊢ prod (Quotient.mk (List.isSetoid α) l₁ + Quotient.mk (List.isSetoid α) l₂) =
    prod (Quotient.mk (List.isSetoid α) l₁) * prod (Quotient.mk (List.isSetoid α) l₂)
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a : α
m✝ : Multiset ι
f g : ι → α
m : Multiset α
⊢ prod (0 • m) = prod m ^ 0
[PROOFSTEP]
rw [zero_nsmul, pow_zero]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a : α
m✝ : Multiset ι
f g : ι → α
m : Multiset α
⊢ prod 0 = 1
[PROOFSTEP]
rfl
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a : α
m✝ : Multiset ι
f g : ι → α
m : Multiset α
n : ℕ
⊢ prod ((n + 1) • m) = prod m ^ (n + 1)
[PROOFSTEP]
rw [add_nsmul, one_nsmul, pow_add, pow_one, prod_add, prod_nsmul m n]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
n : ℕ
a : α
⊢ prod (replicate n a) = a ^ n
[PROOFSTEP]
simp [replicate, List.prod_replicate]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
s t : Multiset α
a : α
m : Multiset ι
f g : ι → α
inst✝ : DecidableEq ι
i : ι
hf : ∀ (i' : ι), i' ≠ i → i' ∈ m → f i' = 1
⊢ prod (map f m) = f i ^ count i m
[PROOFSTEP]
induction' m using Quotient.inductionOn with l
[GOAL]
case h
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
s t : Multiset α
a : α
m : Multiset ι
f g : ι → α
inst✝ : DecidableEq ι
i : ι
hf✝ : ∀ (i' : ι), i' ≠ i → i' ∈ m → f i' = 1
l : List ι
hf : ∀ (i' : ι), i' ≠ i → i' ∈ Quotient.mk (List.isSetoid ι) l → f i' = 1
⊢ prod (map f (Quotient.mk (List.isSetoid ι) l)) = f i ^ count i (Quotient.mk (List.isSetoid ι) l)
[PROOFSTEP]
simp [List.prod_map_eq_pow_single i f hf]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
s t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
inst✝ : DecidableEq α
a : α
h : ∀ (a' : α), a' ≠ a → a' ∈ s → a' = 1
⊢ prod s = a ^ count a s
[PROOFSTEP]
induction' s using Quotient.inductionOn with l
[GOAL]
case h
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
s t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
inst✝ : DecidableEq α
a : α
h✝ : ∀ (a' : α), a' ≠ a → a' ∈ s → a' = 1
l : List α
h : ∀ (a' : α), a' ≠ a → a' ∈ Quotient.mk (List.isSetoid α) l → a' = 1
⊢ prod (Quotient.mk (List.isSetoid α) l) = a ^ count a (Quotient.mk (List.isSetoid α) l)
[PROOFSTEP]
simp [List.prod_eq_pow_single a h]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
s t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
inst✝ : DecidableEq α
a : α
⊢ a ^ count a s = prod (filter (Eq a) s)
[PROOFSTEP]
rw [filter_eq, prod_replicate]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝² : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f✝ g : ι → α
inst✝¹ : CommMonoid β
s : Multiset α
F : Type u_5
inst✝ : MonoidHomClass F α β
f : F
l : List α
⊢ prod (map (↑f) (Quotient.mk (List.isSetoid α) l)) = ↑f (prod (Quotient.mk (List.isSetoid α) l))
[PROOFSTEP]
simp only [l.prod_hom f, quot_mk_to_coe, coe_map, coe_prod]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝² : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f✝ g✝ : ι → α
inst✝¹ : CommMonoid β
s : Multiset ι
F : Type u_5
inst✝ : MonoidHomClass F α β
f : F
g : ι → α
⊢ prod (map (fun i => ↑f (g i)) s) = ↑f (prod (map g s))
[PROOFSTEP]
convert (s.map g).prod_hom f
[GOAL]
case h.e'_2.h.e'_3
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝² : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f✝ g✝ : ι → α
inst✝¹ : CommMonoid β
s : Multiset ι
F : Type u_5
inst✝ : MonoidHomClass F α β
f : F
g : ι → α
⊢ map (fun i => ↑f (g i)) s = map (↑f) (map g s)
[PROOFSTEP]
exact (map_map _ _ _).symm
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝² : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f✝ g : ι → α
inst✝¹ : CommMonoid β
inst✝ : CommMonoid γ
s : Multiset ι
f : α → β → γ
hf : ∀ (a b : α) (c d : β), f (a * b) (c * d) = f a c * f b d
hf' : f 1 1 = 1
f₁ : ι → α
f₂ : ι → β
l : List ι
⊢ prod (map (fun i => f (f₁ i) (f₂ i)) (Quotient.mk (List.isSetoid ι) l)) =
    f (prod (map f₁ (Quotient.mk (List.isSetoid ι) l))) (prod (map f₂ (Quotient.mk (List.isSetoid ι) l)))
[PROOFSTEP]
simp only [l.prod_hom₂ f hf hf', quot_mk_to_coe, coe_map, coe_prod]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f✝ g✝ : ι → α
inst✝ : CommMonoid β
s : Multiset ι
r : α → β → Prop
f : ι → α
g : ι → β
h₁ : r 1 1
h₂ : ∀ ⦃a : ι⦄ ⦃b : α⦄ ⦃c : β⦄, r b c → r (f a * b) (g a * c)
l : List ι
⊢ r (prod (map f (Quotient.mk (List.isSetoid ι) l))) (prod (map g (Quotient.mk (List.isSetoid ι) l)))
[PROOFSTEP]
simp only [l.prod_hom_rel h₁ h₂, quot_mk_to_coe, coe_map, coe_prod]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a : α
m : Multiset ι
f g : ι → α
⊢ prod (map (fun x => 1) m) = 1
[PROOFSTEP]
rw [map_const', prod_replicate, one_pow]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
inst✝ : HasDistribNeg α
s : Multiset α
⊢ ∀ (a : List α),
    prod (map Neg.neg (Quotient.mk (List.isSetoid α) a)) =
      (-1) ^ ↑card (Quotient.mk (List.isSetoid α) a) * prod (Quotient.mk (List.isSetoid α) a)
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a : α
m✝ : Multiset ι
f✝ g : ι → α
m : Multiset β
n : Multiset γ
f : β → γ → α
⊢ prod (map (fun a => prod (map (fun b => f a b) n)) 0) = prod (map (fun b => prod (map (fun a => f a b) 0)) n)
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a✝ : α
m✝¹ : Multiset ι
f✝ g : ι → α
m✝ : Multiset β
n : Multiset γ
f : β → γ → α
a : β
m : Multiset β
ih : prod (map (fun a => prod (map (fun b => f a b) n)) m) = prod (map (fun b => prod (map (fun a => f a b) m)) n)
⊢ prod (map (fun a => prod (map (fun b => f a b) n)) (a ::ₘ m)) =
    prod (map (fun b => prod (map (fun a => f a b) (a ::ₘ m))) n)
[PROOFSTEP]
simp [ih]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
p : α → Prop
s : Multiset α
p_mul : ∀ (a b : α), p a → p b → p (a * b)
p_one : p 1
p_s : ∀ (a : α), a ∈ s → p a
⊢ p (prod s)
[PROOFSTEP]
rw [prod_eq_foldr]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
p : α → Prop
s : Multiset α
p_mul : ∀ (a b : α), p a → p b → p (a * b)
p_one : p 1
p_s : ∀ (a : α), a ∈ s → p a
⊢ p (foldr (fun x x_1 => x * x_1) (_ : ∀ (x y z : α), x * (y * z) = y * (x * z)) 1 s)
[PROOFSTEP]
exact foldr_induction (· * ·) (fun x y z => by simp [mul_left_comm]) 1 p s p_mul p_one p_s
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a : α
m : Multiset ι
f g : ι → α
p : α → Prop
s : Multiset α
p_mul : ∀ (a b : α), p a → p b → p (a * b)
p_one : p 1
p_s : ∀ (a : α), a ∈ s → p a
x y z : α
⊢ (fun x x_1 => x * x_1) x ((fun x x_1 => x * x_1) y z) = (fun x x_1 => x * x_1) y ((fun x x_1 => x * x_1) x z)
[PROOFSTEP]
simp [mul_left_comm]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a : α
m : Multiset ι
f g : ι → α
p : α → Prop
p_mul : ∀ (a b : α), p a → p b → p (a * b)
hs : s ≠ ∅
p_s : ∀ (a : α), a ∈ s → p a
⊢ p (prod s)
[PROOFSTEP]
induction' s using Multiset.induction_on with a s hsa
[GOAL]
case empty
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a : α
m : Multiset ι
f g : ι → α
p : α → Prop
p_mul : ∀ (a b : α), p a → p b → p (a * b)
hs✝ : s ≠ ∅
p_s✝ : ∀ (a : α), a ∈ s → p a
hs : 0 ≠ ∅
p_s : ∀ (a : α), a ∈ 0 → p a
⊢ p (prod 0)
[PROOFSTEP]
simp at hs 
[GOAL]
case cons
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
p : α → Prop
p_mul : ∀ (a b : α), p a → p b → p (a * b)
hs✝ : s✝ ≠ ∅
p_s✝ : ∀ (a : α), a ∈ s✝ → p a
a : α
s : Multiset α
hsa : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → p (prod s)
hs : a ::ₘ s ≠ ∅
p_s : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
⊢ p (prod (a ::ₘ s))
[PROOFSTEP]
rw [prod_cons]
[GOAL]
case cons
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
p : α → Prop
p_mul : ∀ (a b : α), p a → p b → p (a * b)
hs✝ : s✝ ≠ ∅
p_s✝ : ∀ (a : α), a ∈ s✝ → p a
a : α
s : Multiset α
hsa : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → p (prod s)
hs : a ::ₘ s ≠ ∅
p_s : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
⊢ p (a * prod s)
[PROOFSTEP]
by_cases hs_empty : s = ∅
[GOAL]
case pos
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
p : α → Prop
p_mul : ∀ (a b : α), p a → p b → p (a * b)
hs✝ : s✝ ≠ ∅
p_s✝ : ∀ (a : α), a ∈ s✝ → p a
a : α
s : Multiset α
hsa : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → p (prod s)
hs : a ::ₘ s ≠ ∅
p_s : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hs_empty : s = ∅
⊢ p (a * prod s)
[PROOFSTEP]
simp [hs_empty, p_s a]
[GOAL]
case neg
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
p : α → Prop
p_mul : ∀ (a b : α), p a → p b → p (a * b)
hs✝ : s✝ ≠ ∅
p_s✝ : ∀ (a : α), a ∈ s✝ → p a
a : α
s : Multiset α
hsa : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → p (prod s)
hs : a ::ₘ s ≠ ∅
p_s : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hs_empty : ¬s = ∅
⊢ p (a * prod s)
[PROOFSTEP]
have hps : ∀ x, x ∈ s → p x := fun x hxs => p_s x (mem_cons_of_mem hxs)
[GOAL]
case neg
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s✝ t : Multiset α
a✝ : α
m : Multiset ι
f g : ι → α
p : α → Prop
p_mul : ∀ (a b : α), p a → p b → p (a * b)
hs✝ : s✝ ≠ ∅
p_s✝ : ∀ (a : α), a ∈ s✝ → p a
a : α
s : Multiset α
hsa : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → p (prod s)
hs : a ::ₘ s ≠ ∅
p_s : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hs_empty : ¬s = ∅
hps : ∀ (x : α), x ∈ s → p x
⊢ p (a * prod s)
[PROOFSTEP]
exact p_mul a s.prod (p_s a (mem_cons_self a s)) (hsa hs_empty hps)
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s t : Multiset α
a : α
m : Multiset ι
f g : ι → α
h : s ≤ t
⊢ prod s ∣ prod t
[PROOFSTEP]
obtain ⟨z, rfl⟩ := exists_add_of_le h
[GOAL]
case intro
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
s : Multiset α
a : α
m : Multiset ι
f g : ι → α
z : Multiset α
h : s ≤ s + z
⊢ prod s ∣ prod (s + z)
[PROOFSTEP]
simp only [prod_add, dvd_mul_right]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid β
S : Multiset α
g1 g2 : α → β
h : ∀ (a : α), a ∈ S → g1 a ∣ g2 a
⊢ prod (map g1 S) ∣ prod (map g2 S)
[PROOFSTEP]
apply Multiset.induction_on' S
[GOAL]
case h₁
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid β
S : Multiset α
g1 g2 : α → β
h : ∀ (a : α), a ∈ S → g1 a ∣ g2 a
⊢ prod (map g1 0) ∣ prod (map g2 0)
[PROOFSTEP]
simp
[GOAL]
case h₂
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid β
S : Multiset α
g1 g2 : α → β
h : ∀ (a : α), a ∈ S → g1 a ∣ g2 a
⊢ ∀ {a : α} {s : Multiset α},
    a ∈ S → s ⊆ S → prod (map g1 s) ∣ prod (map g2 s) → prod (map g1 (insert a s)) ∣ prod (map g2 (insert a s))
[PROOFSTEP]
intro a T haS _ IH
[GOAL]
case h₂
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid β
S : Multiset α
g1 g2 : α → β
h : ∀ (a : α), a ∈ S → g1 a ∣ g2 a
a : α
T : Multiset α
haS : a ∈ S
a✝ : T ⊆ S
IH : prod (map g1 T) ∣ prod (map g2 T)
⊢ prod (map g1 (insert a T)) ∣ prod (map g2 (insert a T))
[PROOFSTEP]
simp [mul_dvd_mul (h a haS) IH]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoidWithZero α
s : Multiset α
h : 0 ∈ s
⊢ prod s = 0
[PROOFSTEP]
rcases Multiset.exists_cons_of_mem h with ⟨s', hs'⟩
[GOAL]
case intro
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoidWithZero α
s : Multiset α
h : 0 ∈ s
s' : Multiset α
hs' : s = 0 ::ₘ s'
⊢ prod s = 0
[PROOFSTEP]
simp [hs', Multiset.prod_cons]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝² : CommMonoidWithZero α
inst✝¹ : NoZeroDivisors α
inst✝ : Nontrivial α
s : Multiset α
l : List α
⊢ prod (Quotient.mk (List.isSetoid α) l) = 0 ↔ 0 ∈ Quotient.mk (List.isSetoid α) l
[PROOFSTEP]
rw [quot_mk_to_coe, coe_prod]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝² : CommMonoidWithZero α
inst✝¹ : NoZeroDivisors α
inst✝ : Nontrivial α
s : Multiset α
l : List α
⊢ List.prod l = 0 ↔ 0 ∈ ↑l
[PROOFSTEP]
exact List.prod_eq_zero_iff
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : DivisionCommMonoid α
m : Multiset ι
f g : ι → α
⊢ prod (map (fun i => (f i)⁻¹) m) = (prod (map f m))⁻¹
[PROOFSTEP]
simp_rw [← (m.map f).prod_map_inv', map_map, Function.comp_apply]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : DivisionCommMonoid α
m : Multiset ι
f g : ι → α
n : ℤ
⊢ prod (map (fun i => f i ^ n) m) = prod (map f m) ^ n
[PROOFSTEP]
convert (m.map f).prod_hom (zpowGroupHom n : α →* α)
[GOAL]
case h.e'_2.h.e'_3
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : DivisionCommMonoid α
m : Multiset ι
f g : ι → α
n : ℤ
⊢ map (fun i => f i ^ n) m = map (↑(zpowGroupHom n)) (map f m)
[PROOFSTEP]
simp only [map_map, Function.comp_apply, zpowGroupHom_apply]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : NonUnitalNonAssocSemiring α
a : α
s : Multiset ι
f : ι → α
⊢ sum (map (fun i => a * f i) 0) = a * sum (map f 0)
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : NonUnitalNonAssocSemiring α
a : α
s✝ : Multiset ι
f : ι → α
i : ι
s : Multiset ι
ih : sum (map (fun i => a * f i) s) = a * sum (map f s)
⊢ sum (map (fun i => a * f i) (i ::ₘ s)) = a * sum (map f (i ::ₘ s))
[PROOFSTEP]
simp [ih, mul_add]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : NonUnitalNonAssocSemiring α
a : α
s : Multiset ι
f : ι → α
⊢ sum (map (fun i => f i * a) 0) = sum (map f 0) * a
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : NonUnitalNonAssocSemiring α
a✝ : α
s✝ : Multiset ι
f : ι → α
a : ι
s : Multiset ι
ih : sum (map (fun i => f i * a✝) s) = sum (map f s) * a✝
⊢ sum (map (fun i => f i * a✝) (a ::ₘ s)) = sum (map f (a ::ₘ s)) * a✝
[PROOFSTEP]
simp [ih, add_mul]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : Semiring α
a : α
s✝ : Multiset α
x : α
s : Multiset α
ih : (∀ (x : α), x ∈ s → a ∣ x) → a ∣ sum s
h : ∀ (x_1 : α), x_1 ∈ x ::ₘ s → a ∣ x_1
⊢ a ∣ sum (x ::ₘ s)
[PROOFSTEP]
rw [sum_cons]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : Semiring α
a : α
s✝ : Multiset α
x : α
s : Multiset α
ih : (∀ (x : α), x ∈ s → a ∣ x) → a ∣ sum s
h : ∀ (x_1 : α), x_1 ∈ x ::ₘ s → a ∣ x_1
⊢ a ∣ x + sum s
[PROOFSTEP]
exact dvd_add (h _ (mem_cons_self _ _)) (ih fun y hy => h _ <| mem_cons.2 <| Or.inr hy)
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a : α
l : List α
hl : ∀ (x : α), x ∈ Quotient.mk (List.isSetoid α) l → 1 ≤ x
⊢ 1 ≤ prod (Quotient.mk (List.isSetoid α) l)
[PROOFSTEP]
simpa using List.one_le_prod_of_one_le hl
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a : α
l : List α
hl : ∀ (x : α), x ∈ Quotient.mk (List.isSetoid α) l → 1 ≤ x
x : α
hx : x ∈ Quotient.mk (List.isSetoid α) l
⊢ x ≤ prod (Quotient.mk (List.isSetoid α) l)
[PROOFSTEP]
simpa using List.single_le_prod hl x hx
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s✝ t : Multiset α
a : α
s : Multiset α
n : α
h : ∀ (x : α), x ∈ s → x ≤ n
⊢ prod s ≤ n ^ ↑card s
[PROOFSTEP]
induction s using Quotient.inductionOn
[GOAL]
case h
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a n : α
a✝ : List α
h : ∀ (x : α), x ∈ Quotient.mk (List.isSetoid α) a✝ → x ≤ n
⊢ prod (Quotient.mk (List.isSetoid α) a✝) ≤ n ^ ↑card (Quotient.mk (List.isSetoid α) a✝)
[PROOFSTEP]
simpa using List.prod_le_pow_card _ _ h
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a : α
⊢ ∀ (a : List α),
    (∀ (x : α), x ∈ Quotient.mk (List.isSetoid α) a → 1 ≤ x) →
      prod (Quotient.mk (List.isSetoid α) a) = 1 → ∀ (x : α), x ∈ Quotient.mk (List.isSetoid α) a → x = 1
[PROOFSTEP]
simp only [quot_mk_to_coe, coe_prod, mem_coe]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a : α
⊢ ∀ (a : List α), (∀ (x : α), x ∈ a → 1 ≤ x) → List.prod a = 1 → ∀ (x : α), x ∈ a → x = 1
[PROOFSTEP]
exact fun l => List.all_one_of_le_one_le_of_prod_eq_one
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a : α
h : Rel (fun x x_1 => x ≤ x_1) s t
⊢ prod s ≤ prod t
[PROOFSTEP]
induction' h with _ _ _ _ rh _ rt
[GOAL]
case zero
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a : α
⊢ prod 0 ≤ prod 0
[PROOFSTEP]
rfl
[GOAL]
case cons
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a a✝¹ b✝ : α
as✝ bs✝ : Multiset α
rh : a✝¹ ≤ b✝
a✝ : Rel (fun x x_1 => x ≤ x_1) as✝ bs✝
rt : prod as✝ ≤ prod bs✝
⊢ prod (a✝¹ ::ₘ as✝) ≤ prod (b✝ ::ₘ bs✝)
[PROOFSTEP]
rw [prod_cons, prod_cons]
[GOAL]
case cons
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a a✝¹ b✝ : α
as✝ bs✝ : Multiset α
rh : a✝¹ ≤ b✝
a✝ : Rel (fun x x_1 => x ≤ x_1) as✝ bs✝
rt : prod as✝ ≤ prod bs✝
⊢ a✝¹ * prod as✝ ≤ b✝ * prod bs✝
[PROOFSTEP]
exact mul_le_mul' rh rt
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a : α
h : ∀ (x : α), x ∈ s → a ≤ x
⊢ a ^ ↑card s ≤ prod s
[PROOFSTEP]
rw [← Multiset.prod_replicate, ← Multiset.map_const]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommMonoid α
s t : Multiset α
a : α
h : ∀ (x : α), x ∈ s → a ≤ x
⊢ prod (map (Function.const α a) s) ≤ prod s
[PROOFSTEP]
exact prod_map_le_prod _ h
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommSemiring α
m : Multiset α
h : ∀ (a : α), a ∈ m → 0 ≤ a
⊢ 0 ≤ prod m
[PROOFSTEP]
revert h
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommSemiring α
m : Multiset α
⊢ (∀ (a : α), a ∈ m → 0 ≤ a) → 0 ≤ prod m
[PROOFSTEP]
refine' m.induction_on _ _
[GOAL]
case refine'_1
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommSemiring α
m : Multiset α
⊢ (∀ (a : α), a ∈ 0 → 0 ≤ a) → 0 ≤ prod 0
[PROOFSTEP]
rintro -
[GOAL]
case refine'_1
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommSemiring α
m : Multiset α
⊢ 0 ≤ prod 0
[PROOFSTEP]
rw [prod_zero]
[GOAL]
case refine'_1
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommSemiring α
m : Multiset α
⊢ 0 ≤ 1
[PROOFSTEP]
exact zero_le_one
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommSemiring α
m : Multiset α
⊢ ∀ ⦃a : α⦄ {s : Multiset α},
    ((∀ (a : α), a ∈ s → 0 ≤ a) → 0 ≤ prod s) → (∀ (a_2 : α), a_2 ∈ a ::ₘ s → 0 ≤ a_2) → 0 ≤ prod (a ::ₘ s)
[PROOFSTEP]
intro a s hs ih
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommSemiring α
m : Multiset α
a : α
s : Multiset α
hs : (∀ (a : α), a ∈ s → 0 ≤ a) → 0 ≤ prod s
ih : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → 0 ≤ a_1
⊢ 0 ≤ prod (a ::ₘ s)
[PROOFSTEP]
rw [prod_cons]
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : OrderedCommSemiring α
m : Multiset α
a : α
s : Multiset α
hs : (∀ (a : α), a ∈ s → 0 ≤ a) → 0 ≤ prod s
ih : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → 0 ≤ a_1
⊢ 0 ≤ a * prod s
[PROOFSTEP]
exact mul_nonneg (ih _ <| mem_cons_self _ _) (hs fun a ha => ih _ <| mem_cons_of_mem ha)
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
m : Multiset α
h : ∀ (x : α), x ∈ m → x = 1
⊢ prod m = 1
[PROOFSTEP]
induction' m using Quotient.inductionOn with l
[GOAL]
case h
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CommMonoid α
m : Multiset α
h✝ : ∀ (x : α), x ∈ m → x = 1
l : List α
h : ∀ (x : α), x ∈ Quotient.mk (List.isSetoid α) l → x = 1
⊢ prod (Quotient.mk (List.isSetoid α) l) = 1
[PROOFSTEP]
simp [List.prod_eq_one h]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CanonicallyOrderedMonoid α
m : Multiset α
a : α
h : a ∈ m
⊢ a ≤ prod m
[PROOFSTEP]
obtain ⟨m', rfl⟩ := exists_cons_of_mem h
[GOAL]
case intro
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CanonicallyOrderedMonoid α
a : α
m' : Multiset α
h : a ∈ a ::ₘ m'
⊢ a ≤ prod (a ::ₘ m')
[PROOFSTEP]
rw [prod_cons]
[GOAL]
case intro
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝ : CanonicallyOrderedMonoid α
a : α
m' : Multiset α
h : a ∈ a ::ₘ m'
⊢ a ≤ a * prod m'
[PROOFSTEP]
exact _root_.le_mul_right (le_refl a)
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_one : f 1 = 1
hp_one : p 1
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
s : Multiset α
hps : ∀ (a : α), a ∈ s → p a
⊢ f (prod s) ≤ prod (map f s)
[PROOFSTEP]
revert s
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_one : f 1 = 1
hp_one : p 1
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
⊢ ∀ (s : Multiset α), (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
[PROOFSTEP]
refine' Multiset.induction _ _
[GOAL]
case refine'_1
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_one : f 1 = 1
hp_one : p 1
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
⊢ (∀ (a : α), a ∈ 0 → p a) → f (prod 0) ≤ prod (map f 0)
[PROOFSTEP]
simp [le_of_eq h_one]
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_one : f 1 = 1
hp_one : p 1
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
⊢ ∀ ⦃a : α⦄ {s : Multiset α},
    ((∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)) →
      (∀ (a_2 : α), a_2 ∈ a ::ₘ s → p a_2) → f (prod (a ::ₘ s)) ≤ prod (map f (a ::ₘ s))
[PROOFSTEP]
intro a s hs hpsa
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_one : f 1 = 1
hp_one : p 1
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hpsa : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
⊢ f (prod (a ::ₘ s)) ≤ prod (map f (a ::ₘ s))
[PROOFSTEP]
have hps : ∀ x, x ∈ s → p x := fun x hx => hpsa x (mem_cons_of_mem hx)
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_one : f 1 = 1
hp_one : p 1
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hpsa : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hps : ∀ (x : α), x ∈ s → p x
⊢ f (prod (a ::ₘ s)) ≤ prod (map f (a ::ₘ s))
[PROOFSTEP]
have hp_prod : p s.prod := prod_induction p s hp_mul hp_one hps
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_one : f 1 = 1
hp_one : p 1
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hpsa : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hps : ∀ (x : α), x ∈ s → p x
hp_prod : p (prod s)
⊢ f (prod (a ::ₘ s)) ≤ prod (map f (a ::ₘ s))
[PROOFSTEP]
rw [prod_cons, map_cons, prod_cons]
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_one : f 1 = 1
hp_one : p 1
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hpsa : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hps : ∀ (x : α), x ∈ s → p x
hp_prod : p (prod s)
⊢ f (a * prod s) ≤ f a * prod (map f s)
[PROOFSTEP]
exact (h_mul a s.prod (hpsa a (mem_cons_self a s)) hp_prod).trans (mul_le_mul_left' (hs hps) _)
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
h_one : f 1 = 1
h_mul : ∀ (a b : α), f (a * b) ≤ f a * f b
s : Multiset α
⊢ ∀ (a b : α), (fun x => True) a → (fun x => True) b → (fun x => True) (a * b)
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
h_one : f 1 = 1
h_mul : ∀ (a b : α), f (a * b) ≤ f a * f b
s : Multiset α
⊢ ∀ (a : α), a ∈ s → (fun x => True) a
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
s : Multiset α
hs_nonempty : s ≠ ∅
hs : ∀ (a : α), a ∈ s → p a
⊢ f (prod s) ≤ prod (map f s)
[PROOFSTEP]
revert s
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
⊢ ∀ (s : Multiset α), s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
[PROOFSTEP]
refine' Multiset.induction _ _
[GOAL]
case refine'_1
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
⊢ 0 ≠ ∅ → (∀ (a : α), a ∈ 0 → p a) → f (prod 0) ≤ prod (map f 0)
[PROOFSTEP]
intro h
[GOAL]
case refine'_1
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
h : 0 ≠ ∅
⊢ (∀ (a : α), a ∈ 0 → p a) → f (prod 0) ≤ prod (map f 0)
[PROOFSTEP]
exfalso
[GOAL]
case refine'_1.h
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
h : 0 ≠ ∅
⊢ False
[PROOFSTEP]
exact h rfl
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
⊢ ∀ ⦃a : α⦄ {s : Multiset α},
    (s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)) →
      a ::ₘ s ≠ ∅ → (∀ (a_2 : α), a_2 ∈ a ::ₘ s → p a_2) → f (prod (a ::ₘ s)) ≤ prod (map f (a ::ₘ s))
[PROOFSTEP]
rintro a s hs - hsa_prop
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hsa_prop : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
⊢ f (prod (a ::ₘ s)) ≤ prod (map f (a ::ₘ s))
[PROOFSTEP]
rw [prod_cons, map_cons, prod_cons]
[GOAL]
case refine'_2
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hsa_prop : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
⊢ f (a * prod s) ≤ f a * prod (map f s)
[PROOFSTEP]
by_cases hs_empty : s = ∅
[GOAL]
case pos
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hsa_prop : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hs_empty : s = ∅
⊢ f (a * prod s) ≤ f a * prod (map f s)
[PROOFSTEP]
simp [hs_empty]
[GOAL]
case neg
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hsa_prop : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hs_empty : ¬s = ∅
⊢ f (a * prod s) ≤ f a * prod (map f s)
[PROOFSTEP]
have hsa_restrict : ∀ x, x ∈ s → p x := fun x hx => hsa_prop x (mem_cons_of_mem hx)
[GOAL]
case neg
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hsa_prop : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hs_empty : ¬s = ∅
hsa_restrict : ∀ (x : α), x ∈ s → p x
⊢ f (a * prod s) ≤ f a * prod (map f s)
[PROOFSTEP]
have hp_sup : p s.prod := prod_induction_nonempty p hp_mul hs_empty hsa_restrict
[GOAL]
case neg
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hsa_prop : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hs_empty : ¬s = ∅
hsa_restrict : ∀ (x : α), x ∈ s → p x
hp_sup : p (prod s)
⊢ f (a * prod s) ≤ f a * prod (map f s)
[PROOFSTEP]
have hp_a : p a := hsa_prop a (mem_cons_self a s)
[GOAL]
case neg
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
p : α → Prop
h_mul : ∀ (a b : α), p a → p b → f (a * b) ≤ f a * f b
hp_mul : ∀ (a b : α), p a → p b → p (a * b)
a : α
s : Multiset α
hs : s ≠ ∅ → (∀ (a : α), a ∈ s → p a) → f (prod s) ≤ prod (map f s)
hsa_prop : ∀ (a_1 : α), a_1 ∈ a ::ₘ s → p a_1
hs_empty : ¬s = ∅
hsa_restrict : ∀ (x : α), x ∈ s → p x
hp_sup : p (prod s)
hp_a : p a
⊢ f (a * prod s) ≤ f a * prod (map f s)
[PROOFSTEP]
exact (h_mul a _ hp_a hp_sup).trans (mul_le_mul_left' (hs hs_empty hsa_restrict) _)
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
h_mul : ∀ (a b : α), f (a * b) ≤ f a * f b
s : Multiset α
hs_nonempty : s ≠ ∅
⊢ ∀ (a b : α), (fun x => True) a → (fun x => True) b → f (a * b) ≤ f a * f b
[PROOFSTEP]
simp [h_mul]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
h_mul : ∀ (a b : α), f (a * b) ≤ f a * f b
s : Multiset α
hs_nonempty : s ≠ ∅
⊢ ∀ (a b : α), (fun x => True) a → (fun x => True) b → (fun x => True) (a * b)
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
inst✝¹ : CommMonoid α
inst✝ : OrderedCommMonoid β
f : α → β
h_mul : ∀ (a b : α), f (a * b) ≤ f a * f b
s : Multiset α
hs_nonempty : s ≠ ∅
⊢ ∀ (a : α), a ∈ s → (fun x => True) a
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
s : Multiset α
⊢ sum (map (fun a => {a}) 0) = 0
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
s : Multiset α
⊢ ∀ ⦃a : α⦄ {s : Multiset α}, sum (map (fun a => {a}) s) = s → sum (map (fun a => {a}) (a ::ₘ s)) = a ::ₘ s
[PROOFSTEP]
simp
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
s : Multiset ℕ
n : ℕ
⊢ sum s % n = sum (map (fun x => x % n) s) % n
[PROOFSTEP]
induction s using Multiset.induction
[GOAL]
case empty
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
n : ℕ
⊢ sum 0 % n = sum (map (fun x => x % n) 0) % n
[PROOFSTEP]
simp [Nat.add_mod, *]
[GOAL]
case cons
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
n a✝¹ : ℕ
s✝ : Multiset ℕ
a✝ : sum s✝ % n = sum (map (fun x => x % n) s✝) % n
⊢ sum (a✝¹ ::ₘ s✝) % n = sum (map (fun x => x % n) (a✝¹ ::ₘ s✝)) % n
[PROOFSTEP]
simp [Nat.add_mod, *]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
s : Multiset ℕ
n : ℕ
⊢ prod s % n = prod (map (fun x => x % n) s) % n
[PROOFSTEP]
induction s using Multiset.induction
[GOAL]
case empty
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
n : ℕ
⊢ prod 0 % n = prod (map (fun x => x % n) 0) % n
[PROOFSTEP]
simp [Nat.mul_mod, *]
[GOAL]
case cons
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
n a✝¹ : ℕ
s✝ : Multiset ℕ
a✝ : prod s✝ % n = prod (map (fun x => x % n) s✝) % n
⊢ prod (a✝¹ ::ₘ s✝) % n = prod (map (fun x => x % n) (a✝¹ ::ₘ s✝)) % n
[PROOFSTEP]
simp [Nat.mul_mod, *]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
s : Multiset ℤ
n : ℤ
⊢ sum s % n = sum (map (fun x => x % n) s) % n
[PROOFSTEP]
induction s using Multiset.induction
[GOAL]
case empty
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
n : ℤ
⊢ sum 0 % n = sum (map (fun x => x % n) 0) % n
[PROOFSTEP]
simp [Int.add_emod, *]
[GOAL]
case cons
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
n a✝¹ : ℤ
s✝ : Multiset ℤ
a✝ : sum s✝ % n = sum (map (fun x => x % n) s✝) % n
⊢ sum (a✝¹ ::ₘ s✝) % n = sum (map (fun x => x % n) (a✝¹ ::ₘ s✝)) % n
[PROOFSTEP]
simp [Int.add_emod, *]
[GOAL]
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
s : Multiset ℤ
n : ℤ
⊢ prod s % n = prod (map (fun x => x % n) s) % n
[PROOFSTEP]
induction s using Multiset.induction
[GOAL]
case empty
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
n : ℤ
⊢ prod 0 % n = prod (map (fun x => x % n) 0) % n
[PROOFSTEP]
simp [Int.mul_emod, *]
[GOAL]
case cons
ι : Type u_1
α : Type u_2
β : Type u_3
γ : Type u_4
n a✝¹ : ℤ
s✝ : Multiset ℤ
a✝ : prod s✝ % n = prod (map (fun x => x % n) s✝) % n
⊢ prod (a✝¹ ::ₘ s✝) % n = prod (map (fun x => x % n) (a✝¹ ::ₘ s✝)) % n
[PROOFSTEP]
simp [Int.mul_emod, *]
