case empty
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha : IsAssociative β op
f : α → β
b : β
s : Finset α
a : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
⊢ r c (fold op b f ∅) ↔ r c b ∧ ∀ (x : α), x ∈ ∅ → r c (f x)

case insert
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ r c (fold op b f (insert a s)) ↔ r c b ∧ ∀ (x : α), x ∈ insert a s → r c (f x)
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha : IsAssociative β op
f : α → β
b : β
s : Finset α
a : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
⊢ r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
induction' s using Finset.induction_on with a s ha IH
case insert
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ (r c b ∧ r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)) ↔ r c b ∧ ∀ (x : α), x ∈ insert a s → r c (f x)
case insert
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ r c (fold op b f (insert a s)) ↔ r c b ∧ ∀ (x : α), x ∈ insert a s → r c (f x)
rw [Finset.fold_insert ha, hr, IH, ← and_assoc, @and_comm (r c (f a)), and_assoc]
case insert
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ (r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)) ↔ ∀ (x : α), x ∈ insert a s → r c (f x)
case insert
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ (r c b ∧ r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)) ↔ r c b ∧ ∀ (x : α), x ∈ insert a s → r c (f x)
apply and_congr Iff.rfl
case insert.mp
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ (r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)) → ∀ (x : α), x ∈ insert a s → r c (f x)

case insert.mpr
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ (∀ (x : α), x ∈ insert a s → r c (f x)) → r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)
case insert
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ (r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)) ↔ ∀ (x : α), x ∈ insert a s → r c (f x)
constructor
no goals
case empty
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha : IsAssociative β op
f : α → β
b : β
s : Finset α
a : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
⊢ r c (fold op b f ∅) ↔ r c b ∧ ∀ (x : α), x ∈ ∅ → r c (f x)
simp
case insert.mp.intro
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
h₁ : r c (f a)
h₂ : ∀ (x : α), x ∈ s → r c (f x)
⊢ ∀ (x : α), x ∈ insert a s → r c (f x)
case insert.mp
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ (r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)) → ∀ (x : α), x ∈ insert a s → r c (f x)
rintro ⟨h₁, h₂⟩
case insert.mp.intro
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b✝ : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b✝ f s) ↔ r c b✝ ∧ ∀ (x : α), x ∈ s → r c (f x)
h₁ : r c (f a)
h₂ : ∀ (x : α), x ∈ s → r c (f x)
b : α
hb : b ∈ insert a s
⊢ r c (f b)
case insert.mp.intro
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
h₁ : r c (f a)
h₂ : ∀ (x : α), x ∈ s → r c (f x)
⊢ ∀ (x : α), x ∈ insert a s → r c (f x)
intro b hb
case insert.mp.intro
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b✝ : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b✝ f s) ↔ r c b✝ ∧ ∀ (x : α), x ∈ s → r c (f x)
h₁ : r c (f a)
h₂ : ∀ (x : α), x ∈ s → r c (f x)
b : α
hb : b = a ∨ b ∈ s
⊢ r c (f b)
case insert.mp.intro
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b✝ : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b✝ f s) ↔ r c b✝ ∧ ∀ (x : α), x ∈ s → r c (f x)
h₁ : r c (f a)
h₂ : ∀ (x : α), x ∈ s → r c (f x)
b : α
hb : b ∈ insert a s
⊢ r c (f b)
rw [Finset.mem_insert] at hb
no goals
case insert.mp.intro
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b✝ : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b✝ f s) ↔ r c b✝ ∧ ∀ (x : α), x ∈ s → r c (f x)
h₁ : r c (f a)
h₂ : ∀ (x : α), x ∈ s → r c (f x)
b : α
hb : b = a ∨ b ∈ s
⊢ r c (f b)
rcases hb with (rfl | hb) <;> solve_by_elim
case insert.mpr
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
h : ∀ (x : α), x ∈ insert a s → r c (f x)
⊢ r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)
case insert.mpr
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
⊢ (∀ (x : α), x ∈ insert a s → r c (f x)) → r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)
intro h
case insert.mpr.left
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
h : ∀ (x : α), x ∈ insert a s → r c (f x)
⊢ r c (f a)

case insert.mpr.right
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
h : ∀ (x : α), x ∈ insert a s → r c (f x)
⊢ ∀ (x : α), x ∈ s → r c (f x)
case insert.mpr
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
h : ∀ (x : α), x ∈ insert a s → r c (f x)
⊢ r c (f a) ∧ ∀ (x : α), x ∈ s → r c (f x)
constructor
no goals
case insert.mpr.left
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
h : ∀ (x : α), x ∈ insert a s → r c (f x)
⊢ r c (f a)
exact h a (Finset.mem_insert_self _ _)
no goals
case insert.mpr.right
α : Type u_1
β : Type u_2
γ : Type ?u.57392
op : β → β → β
hc : IsCommutative β op
ha✝ : IsAssociative β op
f : α → β
b : β
s✝ : Finset α
a✝ : α
r : β → β → Prop
hr : ∀ {x y z : β}, r x (op y z) ↔ r x y ∧ r x z
c : β
a : α
s : Finset α
ha : ¬a ∈ s
IH : r c (fold op b f s) ↔ r c b ∧ ∀ (x : α), x ∈ s → r c (f x)
h : ∀ (x : α), x ∈ insert a s → r c (f x)
⊢ ∀ (x : α), x ∈ s → r c (f x)
exact fun b hb => h b <| Finset.mem_insert_of_mem hb