[GOAL]
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝ : CommMonoid β
x : β
f : α → ℕ
⊢ ∀ {s : Finset α}, ∏ i in s, x ^ f i = x ^ ∑ x in s, f x
[PROOFSTEP]
apply Finset.induction
[GOAL]
case empty
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝ : CommMonoid β
x : β
f : α → ℕ
⊢ ∏ i in ∅, x ^ f i = x ^ ∑ x in ∅, f x
[PROOFSTEP]
simp
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝ : CommMonoid β
x : β
f : α → ℕ
⊢ ∀ ⦃a : α⦄ {s : Finset α},
    ¬a ∈ s → ∏ i in s, x ^ f i = x ^ ∑ x in s, f x → ∏ i in insert a s, x ^ f i = x ^ ∑ x in insert a s, f x
[PROOFSTEP]
intro a s has H
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g : α → β
inst✝ : CommMonoid β
x : β
f : α → ℕ
a : α
s : Finset α
has : ¬a ∈ s
H : ∏ i in s, x ^ f i = x ^ ∑ x in s, f x
⊢ ∏ i in insert a s, x ^ f i = x ^ ∑ x in insert a s, f x
[PROOFSTEP]
rw [Finset.prod_insert has, Finset.sum_insert has, pow_add, H]
[GOAL]
α : Type u
β : Type v
γ : Type w
s s₁✝ s₂✝ : Finset α
a : α
b : β
f g : α → β
inst✝ : NonUnitalNonAssocSemiring β
ι₁ : Type u_1
ι₂ : Type u_2
s₁ : Finset ι₁
s₂ : Finset ι₂
f₁ : ι₁ → β
f₂ : ι₂ → β
⊢ (∑ x₁ in s₁, f₁ x₁) * ∑ x₂ in s₂, f₂ x₂ = ∑ p in s₁ ×ˢ s₂, f₁ p.fst * f₂ p.snd
[PROOFSTEP]
rw [sum_product, sum_mul, sum_congr rfl]
[GOAL]
α : Type u
β : Type v
γ : Type w
s s₁✝ s₂✝ : Finset α
a : α
b : β
f g : α → β
inst✝ : NonUnitalNonAssocSemiring β
ι₁ : Type u_1
ι₂ : Type u_2
s₁ : Finset ι₁
s₂ : Finset ι₂
f₁ : ι₁ → β
f₂ : ι₂ → β
⊢ ∀ (x : ι₁), x ∈ s₁ → f₁ x * ∑ x₂ in s₂, f₂ x₂ = ∑ y in s₂, f₁ (x, y).fst * f₂ (x, y).snd
[PROOFSTEP]
intros
[GOAL]
α : Type u
β : Type v
γ : Type w
s s₁✝ s₂✝ : Finset α
a : α
b : β
f g : α → β
inst✝ : NonUnitalNonAssocSemiring β
ι₁ : Type u_1
ι₂ : Type u_2
s₁ : Finset ι₁
s₂ : Finset ι₂
f₁ : ι₁ → β
f₂ : ι₂ → β
x✝ : ι₁
a✝ : x✝ ∈ s₁
⊢ f₁ x✝ * ∑ x₂ in s₂, f₂ x₂ = ∑ y in s₂, f₁ (x✝, y).fst * f₂ (x✝, y).snd
[PROOFSTEP]
rw [mul_sum]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g : α → β
inst✝¹ : NonAssocSemiring β
inst✝ : DecidableEq α
s : Finset α
f : α → β
a : α
⊢ (∑ x in s, f x * if a = x then 1 else 0) = if a ∈ s then f a else 0
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g : α → β
inst✝¹ : NonAssocSemiring β
inst✝ : DecidableEq α
s : Finset α
f : α → β
a : α
⊢ ∑ x in s, (if a = x then 1 else 0) * f x = if a ∈ s then f a else 0
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b✝ : β
f✝ g : α → β
inst✝ : DivisionSemiring β
s : Finset α
f : α → β
b : β
⊢ (∑ x in s, f x) / b = ∑ x in s, f x / b
[PROOFSTEP]
simp only [div_eq_mul_inv, sum_mul]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
s : Finset α
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
⊢ ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
[PROOFSTEP]
induction' s using Finset.induction with a s ha ih
[GOAL]
case empty
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
⊢ ∏ a in ∅, ∑ b in t a, f a b = ∑ p in pi ∅ t, ∏ x in attach ∅, f (↑x) (p ↑x (_ : ↑x ∈ ∅))
[PROOFSTEP]
rw [pi_empty, sum_singleton]
[GOAL]
case empty
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
⊢ ∏ a in ∅, ∑ b in t a, f a b = ∏ x in attach ∅, f (↑x) (Pi.empty (fun a => δ a) ↑x (_ : ↑x ∈ ∅))
[PROOFSTEP]
rfl
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
⊢ ∏ a in insert a s, ∑ b in t a, f a b =
    ∑ p in pi (insert a s) t, ∏ x in attach (insert a s), f (↑x) (p ↑x (_ : ↑x ∈ insert a s))
[PROOFSTEP]
have h₁ : ∀ x ∈ t a, ∀ y ∈ t a, x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t)) :=
  by
  intro x _ y _ h
  simp only [disjoint_iff_ne, mem_image]
  rintro _ ⟨p₂, _, eq₂⟩ _ ⟨p₃, _, eq₃⟩ eq
  have : Pi.cons s a x p₂ a (mem_insert_self _ _) = Pi.cons s a y p₃ a (mem_insert_self _ _) := by rw [eq₂, eq₃, eq]
  rw [Pi.cons_same, Pi.cons_same] at this 
  exact h this
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
⊢ ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
[PROOFSTEP]
intro x _ y _ h
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝² : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
x : δ a
a✝¹ : x ∈ t a
y : δ a
a✝ : y ∈ t a
h : x ≠ y
⊢ Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
[PROOFSTEP]
simp only [disjoint_iff_ne, mem_image]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝² : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
x : δ a
a✝¹ : x ∈ t a
y : δ a
a✝ : y ∈ t a
h : x ≠ y
⊢ ∀ (a_1 : (a' : α) → a' ∈ insert a s → δ a'),
    (∃ a_2, a_2 ∈ pi s t ∧ Pi.cons s a x a_2 = a_1) →
      ∀ (b : (a' : α) → a' ∈ insert a s → δ a'), (∃ a_3, a_3 ∈ pi s t ∧ Pi.cons s a y a_3 = b) → a_1 ≠ b
[PROOFSTEP]
rintro _ ⟨p₂, _, eq₂⟩ _ ⟨p₃, _, eq₃⟩ eq
[GOAL]
case intro.intro.intro.intro
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝³ : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
x : δ a
a✝² : x ∈ t a
y : δ a
a✝¹ : y ∈ t a
h : x ≠ y
a✝ : (a' : α) → a' ∈ insert a s → δ a'
p₂ : (a : α) → a ∈ s → δ a
left✝¹ : p₂ ∈ pi s t
eq₂ : Pi.cons s a x p₂ = a✝
b✝ : (a' : α) → a' ∈ insert a s → δ a'
p₃ : (a : α) → a ∈ s → δ a
left✝ : p₃ ∈ pi s t
eq₃ : Pi.cons s a y p₃ = b✝
eq : a✝ = b✝
⊢ False
[PROOFSTEP]
have : Pi.cons s a x p₂ a (mem_insert_self _ _) = Pi.cons s a y p₃ a (mem_insert_self _ _) := by rw [eq₂, eq₃, eq]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝³ : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
x : δ a
a✝² : x ∈ t a
y : δ a
a✝¹ : y ∈ t a
h : x ≠ y
a✝ : (a' : α) → a' ∈ insert a s → δ a'
p₂ : (a : α) → a ∈ s → δ a
left✝¹ : p₂ ∈ pi s t
eq₂ : Pi.cons s a x p₂ = a✝
b✝ : (a' : α) → a' ∈ insert a s → δ a'
p₃ : (a : α) → a ∈ s → δ a
left✝ : p₃ ∈ pi s t
eq₃ : Pi.cons s a y p₃ = b✝
eq : a✝ = b✝
⊢ Pi.cons s a x p₂ a (_ : a ∈ insert a s) = Pi.cons s a y p₃ a (_ : a ∈ insert a s)
[PROOFSTEP]
rw [eq₂, eq₃, eq]
[GOAL]
case intro.intro.intro.intro
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝³ : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
x : δ a
a✝² : x ∈ t a
y : δ a
a✝¹ : y ∈ t a
h : x ≠ y
a✝ : (a' : α) → a' ∈ insert a s → δ a'
p₂ : (a : α) → a ∈ s → δ a
left✝¹ : p₂ ∈ pi s t
eq₂ : Pi.cons s a x p₂ = a✝
b✝ : (a' : α) → a' ∈ insert a s → δ a'
p₃ : (a : α) → a ∈ s → δ a
left✝ : p₃ ∈ pi s t
eq₃ : Pi.cons s a y p₃ = b✝
eq : a✝ = b✝
this : Pi.cons s a x p₂ a (_ : a ∈ insert a s) = Pi.cons s a y p₃ a (_ : a ∈ insert a s)
⊢ False
[PROOFSTEP]
rw [Pi.cons_same, Pi.cons_same] at this 
[GOAL]
case intro.intro.intro.intro
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝³ : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
x : δ a
a✝² : x ∈ t a
y : δ a
a✝¹ : y ∈ t a
h : x ≠ y
a✝ : (a' : α) → a' ∈ insert a s → δ a'
p₂ : (a : α) → a ∈ s → δ a
left✝¹ : p₂ ∈ pi s t
eq₂ : Pi.cons s a x p₂ = a✝
b✝ : (a' : α) → a' ∈ insert a s → δ a'
p₃ : (a : α) → a ∈ s → δ a
left✝ : p₃ ∈ pi s t
eq₃ : Pi.cons s a y p₃ = b✝
eq : a✝ = b✝
this : x = y
⊢ False
[PROOFSTEP]
exact h this
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
⊢ ∏ a in insert a s, ∑ b in t a, f a b =
    ∑ p in pi (insert a s) t, ∏ x in attach (insert a s), f (↑x) (p ↑x (_ : ↑x ∈ insert a s))
[PROOFSTEP]
rw [prod_insert ha, pi_insert ha, ih, sum_mul, sum_biUnion h₁]
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
⊢ ∑ x in t a, f a x * ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s)) =
    ∑ x in t a, ∑ i in image (Pi.cons s a x) (pi s t), ∏ x in attach (insert a s), f (↑x) (i ↑x (_ : ↑x ∈ insert a s))
[PROOFSTEP]
refine' sum_congr rfl fun b _ => _
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝ : b ∈ t a
⊢ f a b * ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s)) =
    ∑ i in image (Pi.cons s a b) (pi s t), ∏ x in attach (insert a s), f (↑x) (i ↑x (_ : ↑x ∈ insert a s))
[PROOFSTEP]
have h₂ : ∀ p₁ ∈ pi s t, ∀ p₂ ∈ pi s t, Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂ := fun p₁ _ p₂ _ eq =>
  Pi.cons_injective ha eq
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
⊢ f a b * ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s)) =
    ∑ i in image (Pi.cons s a b) (pi s t), ∏ x in attach (insert a s), f (↑x) (i ↑x (_ : ↑x ∈ insert a s))
[PROOFSTEP]
rw [sum_image h₂, mul_sum]
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
⊢ ∑ x in pi s t, f a b * ∏ x_1 in attach s, f (↑x_1) (x ↑x_1 (_ : ↑x_1 ∈ s)) =
    ∑ x in pi s t, ∏ x_1 in attach (insert a s), f (↑x_1) (Pi.cons s a b x ↑x_1 (_ : ↑x_1 ∈ insert a s))
[PROOFSTEP]
refine' sum_congr rfl fun g _ => _
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝¹ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
g : (a : α) → a ∈ s → δ a
x✝ : g ∈ pi s t
⊢ f a b * ∏ x in attach s, f (↑x) (g ↑x (_ : ↑x ∈ s)) =
    ∏ x in attach (insert a s), f (↑x) (Pi.cons s a b g ↑x (_ : ↑x ∈ insert a s))
[PROOFSTEP]
rw [attach_insert, prod_insert, prod_image]
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝¹ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
g : (a : α) → a ∈ s → δ a
x✝ : g ∈ pi s t
⊢ f a b * ∏ x in attach s, f (↑x) (g ↑x (_ : ↑x ∈ s)) =
    f (↑{ val := a, property := (_ : a ∈ insert a s) })
        (Pi.cons s a b g ↑{ val := a, property := (_ : a ∈ insert a s) }
          (_ : ↑{ val := a, property := (_ : a ∈ insert a s) } ∈ insert a s)) *
      ∏ x in attach s,
        f (↑{ val := ↑x, property := (_ : ↑x ∈ insert a s) })
          (Pi.cons s a b g ↑{ val := ↑x, property := (_ : ↑x ∈ insert a s) }
            (_ : ↑{ val := ↑x, property := (_ : ↑x ∈ insert a s) } ∈ insert a s))
[PROOFSTEP]
simp only [Pi.cons_same]
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝¹ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
g : (a : α) → a ∈ s → δ a
x✝ : g ∈ pi s t
⊢ f a b * ∏ x in attach s, f (↑x) (g ↑x (_ : ↑x ∈ s)) =
    f a b *
      ∏ x in attach s,
        f (↑x)
          (Pi.cons s a b g ↑{ val := ↑x, property := (_ : ↑x ∈ insert a s) }
            (_ : ↑{ val := ↑x, property := (_ : ↑x ∈ insert a s) } ∈ insert a s))
[PROOFSTEP]
congr with ⟨v, hv⟩
[GOAL]
case insert.e_a.e_f.h.mk
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝¹ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
g : (a : α) → a ∈ s → δ a
x✝ : g ∈ pi s t
v : α
hv : v ∈ s
⊢ f (↑{ val := v, property := hv }) (g ↑{ val := v, property := hv } (_ : ↑{ val := v, property := hv } ∈ s)) =
    f (↑{ val := v, property := hv })
      (Pi.cons s a b g
        ↑{ val := ↑{ val := v, property := hv }, property := (_ : ↑{ val := v, property := hv } ∈ insert a s) }
        (_ :
          ↑{ val := ↑{ val := v, property := hv }, property := (_ : ↑{ val := v, property := hv } ∈ insert a s) } ∈
            insert a s))
[PROOFSTEP]
congr
[GOAL]
case insert.e_a.e_f.h.mk.e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝¹ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
g : (a : α) → a ∈ s → δ a
x✝ : g ∈ pi s t
v : α
hv : v ∈ s
⊢ g ↑{ val := v, property := hv } (_ : ↑{ val := v, property := hv } ∈ s) =
    Pi.cons s a b g
      ↑{ val := ↑{ val := v, property := hv }, property := (_ : ↑{ val := v, property := hv } ∈ insert a s) }
      (_ :
        ↑{ val := ↑{ val := v, property := hv }, property := (_ : ↑{ val := v, property := hv } ∈ insert a s) } ∈
          insert a s)
[PROOFSTEP]
exact (Pi.cons_ne (by rintro rfl; exact ha hv)).symm
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝¹ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
g : (a : α) → a ∈ s → δ a
x✝ : g ∈ pi s t
v : α
hv : v ∈ s
⊢ a ≠ ↑{ val := v, property := hv }
[PROOFSTEP]
rintro rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝¹ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
g : (a : α) → a ∈ s → δ a
x✝ : g ∈ pi s t
hv : a ∈ s
⊢ False
[PROOFSTEP]
exact ha hv
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝¹ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
g : (a : α) → a ∈ s → δ a
x✝ : g ∈ pi s t
⊢ ∀ (x : { x // x ∈ s }),
    x ∈ attach s →
      ∀ (y : { x // x ∈ s }),
        y ∈ attach s →
          { val := ↑x, property := (_ : ↑x ∈ insert a s) } = { val := ↑y, property := (_ : ↑y ∈ insert a s) } → x = y
[PROOFSTEP]
exact fun _ _ _ _ => Subtype.eq ∘ Subtype.mk.inj
[GOAL]
case insert
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b✝ : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
δ : α → Type u_1
inst✝¹ : DecidableEq α
inst✝ : (a : α) → DecidableEq (δ a)
t : (a : α) → Finset (δ a)
f : (a : α) → δ a → β
a : α
s : Finset α
ha : ¬a ∈ s
ih : ∏ a in s, ∑ b in t a, f a b = ∑ p in pi s t, ∏ x in attach s, f (↑x) (p ↑x (_ : ↑x ∈ s))
h₁ :
  ∀ (x : δ a),
    x ∈ t a → ∀ (y : δ a), y ∈ t a → x ≠ y → Disjoint (image (Pi.cons s a x) (pi s t)) (image (Pi.cons s a y) (pi s t))
b : δ a
x✝¹ : b ∈ t a
h₂ :
  ∀ (p₁ : (a : α) → a ∈ s → δ a),
    p₁ ∈ pi s t → ∀ (p₂ : (a : α) → a ∈ s → δ a), p₂ ∈ pi s t → Pi.cons s a b p₁ = Pi.cons s a b p₂ → p₁ = p₂
g : (a : α) → a ∈ s → δ a
x✝ : g ∈ pi s t
⊢ ¬{ val := a, property := (_ : a ∈ insert a s) } ∈
      image (fun x => { val := ↑x, property := (_ : ↑x ∈ insert a s) }) (attach s)
[PROOFSTEP]
simpa only [mem_image, mem_attach, Subtype.mk.injEq, true_and, Subtype.exists, exists_prop, exists_eq_right] using ha
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
⊢ ∏ a in s, (f a + g a) = ∑ t in powerset s, (∏ a in t, f a) * ∏ a in s \ t, g a
[PROOFSTEP]
classical calc
  ∏ a in s, (f a + g a) = ∏ a in s, ∑ p in ({ True, False } : Finset Prop), if p then f a else g a := by simp
  _ =
      ∑ p in (s.pi fun _ => { True, False } : Finset (∀ a ∈ s, Prop)),
        ∏ a in s.attach, if p a.1 a.2 then f a.1 else g a.1 :=
    prod_sum
  _ = ∑ t in s.powerset, (∏ a in t, f a) * ∏ a in s \ t, g a :=
    sum_bij' (fun f _ => s.filter (fun a => ∀ h : a ∈ s, f a h)) (by simp)
      (fun a _ => by
        rw [prod_ite]
        congr 1
        exact
          prod_bij' (fun a _ => a.1) (by simp; tauto) (by simp) (fun a ha => ⟨a, (mem_filter.1 ha).1⟩)
            (fun a ha => by simp at ha ; simp; tauto) (by simp) (by simp)
        exact
          prod_bij' (fun a _ => a.1) (by simp) (by simp) (fun a ha => ⟨a, (mem_sdiff.1 ha).1⟩)
            (fun a ha => by simp at ha ; simp; tauto) (by simp) (by simp))
      (fun t _ a _ => a ∈ t) (by simp [Classical.em])
      (by simp_rw [mem_filter, Function.funext_iff, eq_iff_iff, mem_pi, mem_insert]; tauto)
      (by simp_rw [ext_iff, @mem_filter _ _ (id _), mem_powerset]; tauto)
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
⊢ ∏ a in s, (f a + g a) = ∑ t in powerset s, (∏ a in t, f a) * ∏ a in s \ t, g a
[PROOFSTEP]
calc
  ∏ a in s, (f a + g a) = ∏ a in s, ∑ p in ({ True, False } : Finset Prop), if p then f a else g a := by simp
  _ =
      ∑ p in (s.pi fun _ => { True, False } : Finset (∀ a ∈ s, Prop)),
        ∏ a in s.attach, if p a.1 a.2 then f a.1 else g a.1 :=
    prod_sum
  _ = ∑ t in s.powerset, (∏ a in t, f a) * ∏ a in s \ t, g a :=
    sum_bij' (fun f _ => s.filter (fun a => ∀ h : a ∈ s, f a h)) (by simp)
      (fun a _ => by
        rw [prod_ite]
        congr 1
        exact
          prod_bij' (fun a _ => a.1) (by simp; tauto) (by simp) (fun a ha => ⟨a, (mem_filter.1 ha).1⟩)
            (fun a ha => by simp at ha ; simp; tauto) (by simp) (by simp)
        exact
          prod_bij' (fun a _ => a.1) (by simp) (by simp) (fun a ha => ⟨a, (mem_sdiff.1 ha).1⟩)
            (fun a ha => by simp at ha ; simp; tauto) (by simp) (by simp))
      (fun t _ a _ => a ∈ t) (by simp [Classical.em])
      (by simp_rw [mem_filter, Function.funext_iff, eq_iff_iff, mem_pi, mem_insert]; tauto)
      (by simp_rw [ext_iff, @mem_filter _ _ (id _), mem_powerset]; tauto)
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
⊢ ∏ a in s, (f a + g a) = ∏ a in s, ∑ p in {True, False}, if p then f a else g a
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
⊢ ∀ (a : (a : α) → a ∈ s → Prop) (ha : a ∈ pi s fun x => {True, False}),
    (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a ha ∈ powerset s
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ (∏ a_1 in attach s, if a ↑a_1 (_ : ↑a_1 ∈ s) then f ↑a_1 else g ↑a_1) =
    (∏ a in (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝, f a) *
      ∏ a in s \ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝, g a
[PROOFSTEP]
rw [prod_ite]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ (∏ x in filter (fun a_1 => a ↑a_1 (_ : ↑a_1 ∈ s)) (attach s), f ↑x) *
      ∏ x in filter (fun x => ¬a ↑x (_ : ↑x ∈ s)) (attach s), g ↑x =
    (∏ a in (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝, f a) *
      ∏ a in s \ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝, g a
[PROOFSTEP]
congr 1
[GOAL]
case e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∏ x in filter (fun a_1 => a ↑a_1 (_ : ↑a_1 ∈ s)) (attach s), f ↑x =
    ∏ a in (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝, f a
case e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∏ x in filter (fun x => ¬a ↑x (_ : ↑x ∈ s)) (attach s), g ↑x =
    ∏ a in s \ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝, g a
[PROOFSTEP]
exact
  prod_bij' (fun a _ => a.1) (by simp; tauto) (by simp) (fun a ha => ⟨a, (mem_filter.1 ha).1⟩)
    (fun a ha => by simp at ha ; simp; tauto) (by simp) (by simp)
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∀ (a_1 : { x // x ∈ s }) (ha : a_1 ∈ filter (fun a_2 => a ↑a_2 (_ : ↑a_2 ∈ s)) (attach s)),
    (fun a_2 x => ↑a_2) a_1 ha ∈ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∀ (a_1 : α) (b : a_1 ∈ s),
    a a_1 (_ : ↑{ val := a_1, property := b } ∈ s) → ∀ (h : ↑{ val := a_1, property := b } ∈ s), a a_1 h
[PROOFSTEP]
tauto
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∀ (a_1 : { x // x ∈ s }) (ha : a_1 ∈ filter (fun a_2 => a ↑a_2 (_ : ↑a_2 ∈ s)) (attach s)),
    f ↑a_1 = f ((fun a_2 x => ↑a_2) a_1 ha)
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝¹ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a✝ : (a : α) → a ∈ s → Prop
x✝ : a✝ ∈ pi s fun x => {True, False}
a : α
ha : a ∈ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a✝ x✝
⊢ (fun a ha => { val := a, property := (_ : a ∈ s) }) a ha ∈ filter (fun a => a✝ ↑a (_ : ↑a ∈ s)) (attach s)
[PROOFSTEP]
simp at ha 
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝¹ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a✝ : (a : α) → a ∈ s → Prop
x✝ : a✝ ∈ pi s fun x => {True, False}
a : α
ha✝ : a ∈ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a✝ x✝
ha : a ∈ s ∧ ∀ (h : a ∈ s), a✝ a h
⊢ (fun a ha => { val := a, property := (_ : a ∈ s) }) a ha✝ ∈ filter (fun a => a✝ ↑a (_ : ↑a ∈ s)) (attach s)
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝¹ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a✝ : (a : α) → a ∈ s → Prop
x✝ : a✝ ∈ pi s fun x => {True, False}
a : α
ha✝ : a ∈ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a✝ x✝
ha : a ∈ s ∧ ∀ (h : a ∈ s), a✝ a h
⊢ a✝ a (_ : ↑{ val := a, property := (_ : a ∈ s) } ∈ s)
[PROOFSTEP]
tauto
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∀ (a_1 : { x // x ∈ s }) (ha : a_1 ∈ filter (fun a_2 => a ↑a_2 (_ : ↑a_2 ∈ s)) (attach s)),
    (fun a_2 ha => { val := a_2, property := (_ : a_2 ∈ s) }) ((fun a_2 x => ↑a_2) a_1 ha)
        (_ : (fun a_2 x => ↑a_2) a_1 ha ∈ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝) =
      a_1
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∀ (a_1 : α) (ha : a_1 ∈ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝),
    (fun a_2 x => ↑a_2) ((fun a_2 ha => { val := a_2, property := (_ : a_2 ∈ s) }) a_1 ha)
        (_ :
          (fun a_2 ha => { val := a_2, property := (_ : a_2 ∈ s) }) a_1 ha ∈
            filter (fun a_2 => a ↑a_2 (_ : ↑a_2 ∈ s)) (attach s)) =
      a_1
[PROOFSTEP]
simp
[GOAL]
case e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∏ x in filter (fun x => ¬a ↑x (_ : ↑x ∈ s)) (attach s), g ↑x =
    ∏ a in s \ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝, g a
[PROOFSTEP]
exact
  prod_bij' (fun a _ => a.1) (by simp) (by simp) (fun a ha => ⟨a, (mem_sdiff.1 ha).1⟩)
    (fun a ha => by simp at ha ; simp; tauto) (by simp) (by simp)
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∀ (a_1 : { x // x ∈ s }) (ha : a_1 ∈ filter (fun x => ¬a ↑x (_ : ↑x ∈ s)) (attach s)),
    (fun a_2 x => ↑a_2) a_1 ha ∈ s \ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∀ (a_1 : { x // x ∈ s }) (ha : a_1 ∈ filter (fun x => ¬a ↑x (_ : ↑x ∈ s)) (attach s)),
    g ↑a_1 = g ((fun a_2 x => ↑a_2) a_1 ha)
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝¹ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a✝ : (a : α) → a ∈ s → Prop
x✝ : a✝ ∈ pi s fun x => {True, False}
a : α
ha : a ∈ s \ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a✝ x✝
⊢ (fun a ha => { val := a, property := (_ : a ∈ s) }) a ha ∈ filter (fun x => ¬a✝ ↑x (_ : ↑x ∈ s)) (attach s)
[PROOFSTEP]
simp at ha 
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝¹ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a✝ : (a : α) → a ∈ s → Prop
x✝ : a✝ ∈ pi s fun x => {True, False}
a : α
ha✝ : a ∈ s \ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a✝ x✝
ha : a ∈ s ∧ (a ∈ s → ∃ x, ¬a✝ a x)
⊢ (fun a ha => { val := a, property := (_ : a ∈ s) }) a ha✝ ∈ filter (fun x => ¬a✝ ↑x (_ : ↑x ∈ s)) (attach s)
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝¹ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a✝ : (a : α) → a ∈ s → Prop
x✝ : a✝ ∈ pi s fun x => {True, False}
a : α
ha✝ : a ∈ s \ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a✝ x✝
ha : a ∈ s ∧ (a ∈ s → ∃ x, ¬a✝ a x)
⊢ ¬a✝ a (_ : ↑{ val := a, property := (_ : a ∈ s) } ∈ s)
[PROOFSTEP]
tauto
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∀ (a_1 : { x // x ∈ s }) (ha : a_1 ∈ filter (fun x => ¬a ↑x (_ : ↑x ∈ s)) (attach s)),
    (fun a_2 ha => { val := a_2, property := (_ : a_2 ∈ s) }) ((fun a_2 x => ↑a_2) a_1 ha)
        (_ : ↑a_1 ∈ s \ filter (fun a_2 => ∀ (h : a_2 ∈ s), a a_2 h) s) =
      a_1
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
a : (a : α) → a ∈ s → Prop
x✝ : a ∈ pi s fun x => {True, False}
⊢ ∀ (a_1 : α) (ha : a_1 ∈ s \ (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a x✝),
    (fun a_2 x => ↑a_2) ((fun a_2 ha => { val := a_2, property := (_ : a_2 ∈ s) }) a_1 ha)
        (_ :
          (fun a_2 ha => { val := a_2, property := (_ : a_2 ∈ s) }) a_1 ha ∈
            filter (fun x => ¬a ↑x (_ : ↑x ∈ s)) (attach s)) =
      a_1
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
⊢ ∀ (a : Finset α) (ha : a ∈ powerset s), (fun t x a x => a ∈ t) a ha ∈ pi s fun x => {True, False}
[PROOFSTEP]
simp [Classical.em]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
⊢ ∀ (a : (a : α) → a ∈ s → Prop) (ha : a ∈ pi s fun x => {True, False}),
    (fun t x a x => a ∈ t) ((fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) a ha)
        (_ : filter (fun a_1 => ∀ (h : a_1 ∈ s), a a_1 h) s ∈ powerset s) =
      a
[PROOFSTEP]
simp_rw [mem_filter, Function.funext_iff, eq_iff_iff, mem_pi, mem_insert]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
⊢ ∀ (a : (a : α) → a ∈ s → Prop),
    (∀ (a_1 : α) (h : a_1 ∈ s), a a_1 h = True ∨ a a_1 h ∈ {False}) →
      ∀ (a_1 : α) (a_2 : a_1 ∈ s), (a_1 ∈ s ∧ ∀ (h : a_1 ∈ s), a a_1 h) ↔ a a_1 a_2
[PROOFSTEP]
tauto
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
⊢ ∀ (a : Finset α) (ha : a ∈ powerset s),
    (fun f x => filter (fun a => ∀ (h : a ∈ s), f a h) s) ((fun t x a x => a ∈ t) a ha)
        (_ : (fun a_1 x => a_1 ∈ a) ∈ pi s fun x => {True, False}) =
      a
[PROOFSTEP]
simp_rw [ext_iff, @mem_filter _ _ (id _), mem_powerset]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝¹ : CommSemiring β
inst✝ : DecidableEq α
f g : α → β
s : Finset α
⊢ ∀ (a : Finset α), a ⊆ s → ∀ (a_1 : α), a_1 ∈ s ∧ (a_1 ∈ s → a_1 ∈ a) ↔ a_1 ∈ a
[PROOFSTEP]
tauto
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
s : Finset ι
f g : ι → R
⊢ ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
[PROOFSTEP]
refine' Finset.induction_on_max s (by simp) _
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
s : Finset ι
f g : ι → R
⊢ ∏ i in ∅, (f i + g i) =
    ∏ i in ∅, f i +
      ∑ i in ∅, (g i * ∏ j in filter (fun x => x < i) ∅, (f j + g j)) * ∏ j in filter (fun j => i < j) ∅, f j
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
s : Finset ι
f g : ι → R
⊢ ∀ (a : ι) (s : Finset ι),
    (∀ (x : ι), x ∈ s → x < a) →
      ∏ i in s, (f i + g i) =
          ∏ i in s, f i +
            ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j →
        ∏ i in insert a s, (f i + g i) =
          ∏ i in insert a s, f i +
            ∑ i in insert a s,
              (g i * ∏ j in filter (fun x => x < i) (insert a s), (f j + g j)) *
                ∏ j in filter (fun j => i < j) (insert a s), f j
[PROOFSTEP]
clear s
[GOAL]
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
⊢ ∀ (a : ι) (s : Finset ι),
    (∀ (x : ι), x ∈ s → x < a) →
      ∏ i in s, (f i + g i) =
          ∏ i in s, f i +
            ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j →
        ∏ i in insert a s, (f i + g i) =
          ∏ i in insert a s, f i +
            ∑ i in insert a s,
              (g i * ∏ j in filter (fun x => x < i) (insert a s), (f j + g j)) *
                ∏ j in filter (fun j => i < j) (insert a s), f j
[PROOFSTEP]
intro a s ha ihs
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
⊢ ∏ i in insert a s, (f i + g i) =
    ∏ i in insert a s, f i +
      ∑ i in insert a s,
        (g i * ∏ j in filter (fun x => x < i) (insert a s), (f j + g j)) *
          ∏ j in filter (fun j => i < j) (insert a s), f j
[PROOFSTEP]
have ha' : a ∉ s := fun ha' => lt_irrefl a (ha a ha')
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
⊢ ∏ i in insert a s, (f i + g i) =
    ∏ i in insert a s, f i +
      ∑ i in insert a s,
        (g i * ∏ j in filter (fun x => x < i) (insert a s), (f j + g j)) *
          ∏ j in filter (fun j => i < j) (insert a s), f j
[PROOFSTEP]
rw [prod_insert ha', prod_insert ha', sum_insert ha', filter_insert, if_neg (lt_irrefl a), filter_true_of_mem ha, ihs,
  add_mul, mul_add, mul_add, add_assoc]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
⊢ f a * ∏ i in s, f i +
      (f a * ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j +
        (g a * ∏ i in s, f i +
          g a *
            ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j)) =
    f a * ∏ x in s, f x +
      ((g a * ∏ i in s, f i +
            g a *
              ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j) *
          ∏ j in filter (fun j => a < j) (insert a s), f j +
        ∑ x in s,
          (g x * ∏ j in filter (fun x_1 => x_1 < x) (insert a s), (f j + g j)) *
            ∏ j in filter (fun j => x < j) (insert a s), f j)
[PROOFSTEP]
congr 1
[GOAL]
case e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
⊢ f a * ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j +
      (g a * ∏ i in s, f i +
        g a * ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j) =
    (g a * ∏ i in s, f i +
          g a *
            ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j) *
        ∏ j in filter (fun j => a < j) (insert a s), f j +
      ∑ x in s,
        (g x * ∏ j in filter (fun x_1 => x_1 < x) (insert a s), (f j + g j)) *
          ∏ j in filter (fun j => x < j) (insert a s), f j
[PROOFSTEP]
rw [add_comm]
[GOAL]
case e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
⊢ g a * ∏ i in s, f i +
        g a * ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j +
      f a * ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j =
    (g a * ∏ i in s, f i +
          g a *
            ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j) *
        ∏ j in filter (fun j => a < j) (insert a s), f j +
      ∑ x in s,
        (g x * ∏ j in filter (fun x_1 => x_1 < x) (insert a s), (f j + g j)) *
          ∏ j in filter (fun j => x < j) (insert a s), f j
[PROOFSTEP]
congr 1
[GOAL]
case e_a.e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
⊢ g a * ∏ i in s, f i +
      g a * ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j =
    (g a * ∏ i in s, f i +
        g a * ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j) *
      ∏ j in filter (fun j => a < j) (insert a s), f j
[PROOFSTEP]
rw [filter_false_of_mem, prod_empty, mul_one]
[GOAL]
case e_a.e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
⊢ ∀ (x : ι), x ∈ insert a s → ¬a < x
[PROOFSTEP]
exact (forall_mem_insert _ _ _).2 ⟨lt_irrefl a, fun i hi => (ha i hi).not_lt⟩
[GOAL]
case e_a.e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
⊢ f a * ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j =
    ∑ x in s,
      (g x * ∏ j in filter (fun x_1 => x_1 < x) (insert a s), (f j + g j)) *
        ∏ j in filter (fun j => x < j) (insert a s), f j
[PROOFSTEP]
rw [mul_sum]
[GOAL]
case e_a.e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
⊢ ∑ x in s, f a * ((g x * ∏ j in filter (fun x_1 => x_1 < x) s, (f j + g j)) * ∏ j in filter (fun j => x < j) s, f j) =
    ∑ x in s,
      (g x * ∏ j in filter (fun x_1 => x_1 < x) (insert a s), (f j + g j)) *
        ∏ j in filter (fun j => x < j) (insert a s), f j
[PROOFSTEP]
refine' sum_congr rfl fun i hi => _
[GOAL]
case e_a.e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
i : ι
hi : i ∈ s
⊢ f a * ((g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j) =
    (g i * ∏ j in filter (fun x => x < i) (insert a s), (f j + g j)) * ∏ j in filter (fun j => i < j) (insert a s), f j
[PROOFSTEP]
rw [filter_insert, if_neg (ha i hi).not_lt, filter_insert, if_pos (ha i hi), prod_insert, mul_left_comm]
[GOAL]
case e_a.e_a
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a✝ : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommSemiring R
inst✝ : LinearOrder ι
f g : ι → R
a : ι
s : Finset ι
ha : ∀ (x : ι), x ∈ s → x < a
ihs :
  ∏ i in s, (f i + g i) =
    ∏ i in s, f i +
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j + g j)) * ∏ j in filter (fun j => i < j) s, f j
ha' : ¬a ∈ s
i : ι
hi : i ∈ s
⊢ ¬a ∈ filter (fun j => i < j) s
[PROOFSTEP]
exact mt (fun ha => (mem_filter.1 ha).1) ha'
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommRing R
inst✝ : LinearOrder ι
s : Finset ι
f g : ι → R
⊢ ∏ i in s, (f i - g i) =
    ∏ i in s, f i -
      ∑ i in s, (g i * ∏ j in filter (fun x => x < i) s, (f j - g j)) * ∏ j in filter (fun j => i < j) s, f j
[PROOFSTEP]
simp only [sub_eq_add_neg]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommRing R
inst✝ : LinearOrder ι
s : Finset ι
f g : ι → R
⊢ ∏ x in s, (f x + -g x) =
    ∏ i in s, f i +
      -∑ x in s, (g x * ∏ x in filter (fun x_1 => x_1 < x) s, (f x + -g x)) * ∏ i in filter (fun j => x < j) s, f i
[PROOFSTEP]
convert prod_add_ordered s f fun i => -g i
[GOAL]
case h.e'_3.h.e'_6
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommRing R
inst✝ : LinearOrder ι
s : Finset ι
f g : ι → R
⊢ -∑ x in s, (g x * ∏ x in filter (fun x_1 => x_1 < x) s, (f x + -g x)) * ∏ i in filter (fun j => x < j) s, f i =
    ∑ i in s, (-g i * ∏ j in filter (fun x => x < i) s, (f j + -g j)) * ∏ j in filter (fun j => i < j) s, f j
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommRing R
inst✝ : LinearOrder ι
s : Finset ι
f : ι → R
⊢ ∏ i in s, (1 - f i) = 1 - ∑ i in s, f i * ∏ j in filter (fun x => x < i) s, (1 - f j)
[PROOFSTEP]
rw [prod_sub_ordered]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝² : CommSemiring β
ι : Type u_1
R : Type u_2
inst✝¹ : CommRing R
inst✝ : LinearOrder ι
s : Finset ι
f : ι → R
⊢ ∏ i in s, 1 - ∑ i in s, (f i * ∏ j in filter (fun x => x < i) s, (1 - f j)) * ∏ j in filter (fun j => i < j) s, 1 =
    1 - ∑ i in s, f i * ∏ j in filter (fun x => x < i) s, (1 - f j)
[PROOFSTEP]
simp
[GOAL]
α✝ : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α✝
a✝ : α✝
b✝ : β
f g : α✝ → β
inst✝¹ : CommSemiring β
α : Type u_1
R : Type u_2
inst✝ : CommSemiring R
a b : R
s : Finset α
⊢ ∑ t in powerset s, a ^ card t * b ^ (card s - card t) = (a + b) ^ card s
[PROOFSTEP]
classical
rw [← prod_const, prod_add]
refine' Finset.sum_congr rfl fun t ht => _
rw [prod_const, prod_const, ← card_sdiff (mem_powerset.1 ht)]
[GOAL]
α✝ : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α✝
a✝ : α✝
b✝ : β
f g : α✝ → β
inst✝¹ : CommSemiring β
α : Type u_1
R : Type u_2
inst✝ : CommSemiring R
a b : R
s : Finset α
⊢ ∑ t in powerset s, a ^ card t * b ^ (card s - card t) = (a + b) ^ card s
[PROOFSTEP]
rw [← prod_const, prod_add]
[GOAL]
α✝ : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α✝
a✝ : α✝
b✝ : β
f g : α✝ → β
inst✝¹ : CommSemiring β
α : Type u_1
R : Type u_2
inst✝ : CommSemiring R
a b : R
s : Finset α
⊢ ∑ t in powerset s, a ^ card t * b ^ (card s - card t) = ∑ t in powerset s, (∏ a_1 in t, a) * ∏ a in s \ t, b
[PROOFSTEP]
refine' Finset.sum_congr rfl fun t ht => _
[GOAL]
α✝ : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α✝
a✝ : α✝
b✝ : β
f g : α✝ → β
inst✝¹ : CommSemiring β
α : Type u_1
R : Type u_2
inst✝ : CommSemiring R
a b : R
s t : Finset α
ht : t ∈ powerset s
⊢ a ^ card t * b ^ (card s - card t) = (∏ a_1 in t, a) * ∏ a in s \ t, b
[PROOFSTEP]
rw [prod_const, prod_const, ← card_sdiff (mem_powerset.1 ht)]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b✝ : β
f✝ g : α → β
inst✝ : CommSemiring β
b : β
s : Finset α
f : α → β
h : ∀ (x : α), x ∈ s → b ∣ f x
y : β
hy : y ∈ Multiset.map (fun x => f x) s.val
⊢ b ∣ y
[PROOFSTEP]
rcases Multiset.mem_map.1 hy with ⟨x, hx, rfl⟩
[GOAL]
case intro.intro
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b✝ : β
f✝ g : α → β
inst✝ : CommSemiring β
b : β
s : Finset α
f : α → β
h : ∀ (x : α), x ∈ s → b ∣ f x
x : α
hx : x ∈ s.val
hy : f x ∈ Multiset.map (fun x => f x) s.val
⊢ b ∣ f x
[PROOFSTEP]
exact h x hx
[GOAL]
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f g : α → β
R : Type u_1
inst✝ : CommRing R
n k : ℕ
⊢ ∏ i in range k, (↑n - ↑i) = ↑(∏ i in range k, (n - i))
[PROOFSTEP]
rw [prod_natCast]
[GOAL]
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f g : α → β
R : Type u_1
inst✝ : CommRing R
n k : ℕ
⊢ ∏ i in range k, (↑n - ↑i) = ∏ x in range k, ↑(n - x)
[PROOFSTEP]
cases' le_or_lt k n with hkn hnk
[GOAL]
case inl
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f g : α → β
R : Type u_1
inst✝ : CommRing R
n k : ℕ
hkn : k ≤ n
⊢ ∏ i in range k, (↑n - ↑i) = ∏ x in range k, ↑(n - x)
[PROOFSTEP]
exact prod_congr rfl fun i hi => (Nat.cast_sub <| (mem_range.1 hi).le.trans hkn).symm
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f g : α → β
R : Type u_1
inst✝ : CommRing R
n k : ℕ
hnk : n < k
⊢ ∏ i in range k, (↑n - ↑i) = ∏ x in range k, ↑(n - x)
[PROOFSTEP]
rw [← mem_range] at hnk 
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f g : α → β
R : Type u_1
inst✝ : CommRing R
n k : ℕ
hnk : n ∈ range k
⊢ ∏ i in range k, (↑n - ↑i) = ∏ x in range k, ↑(n - x)
[PROOFSTEP]
rw [prod_eq_zero hnk, prod_eq_zero hnk]
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f g : α → β
R : Type u_1
inst✝ : CommRing R
n k : ℕ
hnk : n ∈ range k
⊢ ↑(n - n) = 0
[PROOFSTEP]
simp
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f g : α → β
R : Type u_1
inst✝ : CommRing R
n k : ℕ
hnk : n ∈ range k
⊢ ↑n - ↑n = 0
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝¹ : DecidableEq α
inst✝ : CommMonoid β
s : Finset α
x : α
h : ¬x ∈ s
f : Finset α → β
⊢ ∏ a in powerset (insert x s), f a = (∏ a in powerset s, f a) * ∏ t in powerset s, f (insert x t)
[PROOFSTEP]
rw [powerset_insert, Finset.prod_union, Finset.prod_image]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝¹ : DecidableEq α
inst✝ : CommMonoid β
s : Finset α
x : α
h : ¬x ∈ s
f : Finset α → β
⊢ ∀ (x_1 : Finset α), x_1 ∈ powerset s → ∀ (y : Finset α), y ∈ powerset s → insert x x_1 = insert x y → x_1 = y
[PROOFSTEP]
intro t₁ h₁ t₂ h₂ heq
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝¹ : DecidableEq α
inst✝ : CommMonoid β
s : Finset α
x : α
h : ¬x ∈ s
f : Finset α → β
t₁ : Finset α
h₁ : t₁ ∈ powerset s
t₂ : Finset α
h₂ : t₂ ∈ powerset s
heq : insert x t₁ = insert x t₂
⊢ t₁ = t₂
[PROOFSTEP]
rw [← Finset.erase_insert (not_mem_of_mem_powerset_of_not_mem h₁ h), ←
  Finset.erase_insert (not_mem_of_mem_powerset_of_not_mem h₂ h), heq]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝¹ : DecidableEq α
inst✝ : CommMonoid β
s : Finset α
x : α
h : ¬x ∈ s
f : Finset α → β
⊢ Disjoint (powerset s) (image (insert x) (powerset s))
[PROOFSTEP]
rw [Finset.disjoint_iff_ne]
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝¹ : DecidableEq α
inst✝ : CommMonoid β
s : Finset α
x : α
h : ¬x ∈ s
f : Finset α → β
⊢ ∀ (a : Finset α), a ∈ powerset s → ∀ (b : Finset α), b ∈ image (insert x) (powerset s) → a ≠ b
[PROOFSTEP]
intro t₁ h₁ t₂ h₂
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝¹ : DecidableEq α
inst✝ : CommMonoid β
s : Finset α
x : α
h : ¬x ∈ s
f : Finset α → β
t₁ : Finset α
h₁ : t₁ ∈ powerset s
t₂ : Finset α
h₂ : t₂ ∈ image (insert x) (powerset s)
⊢ t₁ ≠ t₂
[PROOFSTEP]
rcases Finset.mem_image.1 h₂ with ⟨t₃, _h₃, H₃₂⟩
[GOAL]
case intro.intro
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝¹ : DecidableEq α
inst✝ : CommMonoid β
s : Finset α
x : α
h : ¬x ∈ s
f : Finset α → β
t₁ : Finset α
h₁ : t₁ ∈ powerset s
t₂ : Finset α
h₂ : t₂ ∈ image (insert x) (powerset s)
t₃ : Finset α
_h₃ : t₃ ∈ powerset s
H₃₂ : insert x t₃ = t₂
⊢ t₁ ≠ t₂
[PROOFSTEP]
rw [← H₃₂]
[GOAL]
case intro.intro
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝¹ : DecidableEq α
inst✝ : CommMonoid β
s : Finset α
x : α
h : ¬x ∈ s
f : Finset α → β
t₁ : Finset α
h₁ : t₁ ∈ powerset s
t₂ : Finset α
h₂ : t₂ ∈ image (insert x) (powerset s)
t₃ : Finset α
_h₃ : t₃ ∈ powerset s
H₃₂ : insert x t₃ = t₂
⊢ t₁ ≠ insert x t₃
[PROOFSTEP]
exact ne_insert_of_not_mem _ _ (not_mem_of_mem_powerset_of_not_mem h₁ h)
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ s₁ s₂ : Finset α
a : α
b : β
f✝ g : α → β
inst✝ : CommMonoid β
s : Finset α
f : Finset α → β
⊢ ∏ t in powerset s, f t = ∏ j in range (card s + 1), ∏ t in powersetLen j s, f t
[PROOFSTEP]
rw [powerset_card_disjiUnion, prod_disjiUnion]
[GOAL]
α : Type u
β : Type v
γ : Type w
s s₁ s₂ : Finset α
a : α
b : β
f✝ g✝ : α → β
inst✝ : NonUnitalNonAssocSemiring β
n k : ℕ
f g : ℕ → β
⊢ (∑ i in range (n + 1), f i) * ∑ i in range (k + 1), g i =
    (∑ i in range n, f i) * ∑ i in range k, g i + f n * ∑ i in range k, g i + (∑ i in range n, f i) * g k + f n * g k
[PROOFSTEP]
simp only [add_mul, mul_add, add_assoc, sum_range_succ]
