Documentation

Mathlib.Algebra.BigOperators.Group.Finset.Piecewise

Interaction of big operators with piecewise functions #

This file proves lemmas on the sum and product of piecewise functions, including ite and dite.

theorem Finset.prod_apply_dite {ι : Type u_1} {M : Type u_3} {γ : Type u_5} {s : Finset ι} [CommMonoid M] {p : ιProp} [DecidablePred p] [DecidablePred fun (x : ι) => ¬p x] (f : (x : ι) → p xγ) (g : (x : ι) → ¬p xγ) (h : γM) :
xs, h (if hx : p x then f x hx else g x hx) = (∏ x : { x : ι // x {xs | p x} }, h (f x )) * x : { x : ι // x {xs | ¬p x} }, h (g x )
theorem Finset.sum_apply_dite {ι : Type u_1} {M : Type u_3} {γ : Type u_5} {s : Finset ι} [AddCommMonoid M] {p : ιProp} [DecidablePred p] [DecidablePred fun (x : ι) => ¬p x] (f : (x : ι) → p xγ) (g : (x : ι) → ¬p xγ) (h : γM) :
xs, h (if hx : p x then f x hx else g x hx) = x : { x : ι // x {xs | p x} }, h (f x ) + x : { x : ι // x {xs | ¬p x} }, h (g x )
theorem Finset.prod_apply_ite {ι : Type u_1} {M : Type u_3} {γ : Type u_5} [CommMonoid M] {s : Finset ι} {p : ιProp} [DecidablePred p] (f g : ιγ) (h : γM) :
xs, h (if p x then f x else g x) = (∏ xs with p x, h (f x)) * xs with ¬p x, h (g x)
theorem Finset.sum_apply_ite {ι : Type u_1} {M : Type u_3} {γ : Type u_5} [AddCommMonoid M] {s : Finset ι} {p : ιProp} [DecidablePred p] (f g : ιγ) (h : γM) :
xs, h (if p x then f x else g x) = xs with p x, h (f x) + xs with ¬p x, h (g x)
theorem Finset.prod_dite {ι : Type u_1} {M : Type u_3} [CommMonoid M] {s : Finset ι} {p : ιProp} [DecidablePred p] (f : (x : ι) → p xM) (g : (x : ι) → ¬p xM) :
(∏ xs, if hx : p x then f x hx else g x hx) = (∏ x : { x : ι // x {xs | p x} }, f x ) * x : { x : ι // x {xs | ¬p x} }, g x
theorem Finset.sum_dite {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] {s : Finset ι} {p : ιProp} [DecidablePred p] (f : (x : ι) → p xM) (g : (x : ι) → ¬p xM) :
(∑ xs, if hx : p x then f x hx else g x hx) = x : { x : ι // x {xs | p x} }, f x + x : { x : ι // x {xs | ¬p x} }, g x
theorem Finset.prod_ite {ι : Type u_1} {M : Type u_3} [CommMonoid M] {s : Finset ι} {p : ιProp} [DecidablePred p] (f g : ιM) :
(∏ xs, if p x then f x else g x) = (∏ xs with p x, f x) * xs with ¬p x, g x
theorem Finset.sum_ite {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] {s : Finset ι} {p : ιProp} [DecidablePred p] (f g : ιM) :
(∑ xs, if p x then f x else g x) = xs with p x, f x + xs with ¬p x, g x
theorem Finset.prod_dite_of_false {ι : Type u_1} {M : Type u_3} {s : Finset ι} [CommMonoid M] {p : ιProp} [DecidablePred p] (h : is, ¬p i) (f : (i : ι) → p iM) (g : (i : ι) → ¬p iM) :
(∏ is, if hi : p i then f i hi else g i hi) = i : { x : ι // x s }, g i
theorem Finset.sum_dite_of_false {ι : Type u_1} {M : Type u_3} {s : Finset ι} [AddCommMonoid M] {p : ιProp} [DecidablePred p] (h : is, ¬p i) (f : (i : ι) → p iM) (g : (i : ι) → ¬p iM) :
(∑ is, if hi : p i then f i hi else g i hi) = i : { x : ι // x s }, g i
theorem Finset.prod_ite_of_false {ι : Type u_1} {M : Type u_3} {s : Finset ι} [CommMonoid M] {p : ιProp} [DecidablePred p] (h : xs, ¬p x) (f g : ιM) :
(∏ xs, if p x then f x else g x) = xs, g x
theorem Finset.sum_ite_of_false {ι : Type u_1} {M : Type u_3} {s : Finset ι} [AddCommMonoid M] {p : ιProp} [DecidablePred p] (h : xs, ¬p x) (f g : ιM) :
(∑ xs, if p x then f x else g x) = xs, g x
theorem Finset.prod_dite_of_true {ι : Type u_1} {M : Type u_3} {s : Finset ι} [CommMonoid M] {p : ιProp} [DecidablePred p] (h : is, p i) (f : (i : ι) → p iM) (g : (i : ι) → ¬p iM) :
(∏ is, if hi : p i then f i hi else g i hi) = i : { x : ι // x s }, f i
theorem Finset.sum_dite_of_true {ι : Type u_1} {M : Type u_3} {s : Finset ι} [AddCommMonoid M] {p : ιProp} [DecidablePred p] (h : is, p i) (f : (i : ι) → p iM) (g : (i : ι) → ¬p iM) :
(∑ is, if hi : p i then f i hi else g i hi) = i : { x : ι // x s }, f i
theorem Finset.prod_ite_of_true {ι : Type u_1} {M : Type u_3} {s : Finset ι} [CommMonoid M] {p : ιProp} [DecidablePred p] (h : xs, p x) (f g : ιM) :
(∏ xs, if p x then f x else g x) = xs, f x
theorem Finset.sum_ite_of_true {ι : Type u_1} {M : Type u_3} {s : Finset ι} [AddCommMonoid M] {p : ιProp} [DecidablePred p] (h : xs, p x) (f g : ιM) :
(∑ xs, if p x then f x else g x) = xs, f x
theorem Finset.prod_apply_ite_of_false {ι : Type u_1} {M : Type u_3} {γ : Type u_5} {s : Finset ι} [CommMonoid M] {p : ιProp} [DecidablePred p] (f g : ιγ) (k : γM) (h : xs, ¬p x) :
xs, k (if p x then f x else g x) = xs, k (g x)
theorem Finset.sum_apply_ite_of_false {ι : Type u_1} {M : Type u_3} {γ : Type u_5} {s : Finset ι} [AddCommMonoid M] {p : ιProp} [DecidablePred p] (f g : ιγ) (k : γM) (h : xs, ¬p x) :
xs, k (if p x then f x else g x) = xs, k (g x)
theorem Finset.prod_apply_ite_of_true {ι : Type u_1} {M : Type u_3} {γ : Type u_5} {s : Finset ι} [CommMonoid M] {p : ιProp} [DecidablePred p] (f g : ιγ) (k : γM) (h : xs, p x) :
xs, k (if p x then f x else g x) = xs, k (f x)
theorem Finset.sum_apply_ite_of_true {ι : Type u_1} {M : Type u_3} {γ : Type u_5} {s : Finset ι} [AddCommMonoid M] {p : ιProp} [DecidablePred p] (f g : ιγ) (k : γM) (h : xs, p x) :
xs, k (if p x then f x else g x) = xs, k (f x)
@[simp]
theorem Finset.prod_ite_mem {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s t : Finset ι) (f : ιM) :
(∏ is, if i t then f i else 1) = is t, f i
@[simp]
theorem Finset.sum_ite_mem {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s t : Finset ι) (f : ιM) :
(∑ is, if i t then f i else 0) = is t, f i
theorem Finset.prod_attach_eq_prod_dite {ι : Type u_1} {M : Type u_3} [CommMonoid M] [Fintype ι] (s : Finset ι) (f : { x : ι // x s }M) [DecidablePred fun (x : ι) => x s] :
is.attach, f i = i : ι, if h : i s then f i, h else 1
theorem Finset.sum_attach_eq_sum_dite {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [Fintype ι] (s : Finset ι) (f : { x : ι // x s }M) [DecidablePred fun (x : ι) => x s] :
is.attach, f i = i : ι, if h : i s then f i, h else 0
@[simp]
theorem Finset.prod_dite_eq {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : (x : ι) → a = xM) :
(∏ xs, if h : a = x then b x h else 1) = if a s then b a else 1
@[simp]
theorem Finset.sum_dite_eq {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : (x : ι) → a = xM) :
(∑ xs, if h : a = x then b x h else 0) = if a s then b a else 0
@[simp]
theorem Finset.prod_dite_eq' {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : (x : ι) → x = aM) :
(∏ xs, if h : x = a then b x h else 1) = if a s then b a else 1
@[simp]
theorem Finset.sum_dite_eq' {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : (x : ι) → x = aM) :
(∑ xs, if h : x = a then b x h else 0) = if a s then b a else 0
@[simp]
theorem Finset.prod_ite_eq {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : ιM) :
(∏ xs, if a = x then b x else 1) = if a s then b a else 1
@[simp]
theorem Finset.sum_ite_eq {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : ιM) :
(∑ xs, if a = x then b x else 0) = if a s then b a else 0
@[simp]
theorem Finset.prod_ite_eq' {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : ιM) :
(∏ xs, if x = a then b x else 1) = if a s then b a else 1

A product taken over a conditional whose condition is an equality test on the index and whose alternative is 1 has value either the term at that index or 1.

The difference with Finset.prod_ite_eq is that the arguments to Eq are swapped.

@[simp]
theorem Finset.sum_ite_eq' {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : ιM) :
(∑ xs, if x = a then b x else 0) = if a s then b a else 0

A sum taken over a conditional whose condition is an equality test on the index and whose alternative is 0 has value either the term at that index or 0.

The difference with Finset.sum_ite_eq is that the arguments to Eq are swapped.

theorem Finset.prod_ite_eq_of_mem {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : ιM) (h : a s) :
(∏ xs, if a = x then b x else 1) = b a
theorem Finset.sum_ite_eq_of_mem {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : ιM) (h : a s) :
(∑ xs, if a = x then b x else 0) = b a
theorem Finset.prod_ite_eq_of_mem' {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : ιM) (h : a s) :
(∏ xs, if x = a then b x else 1) = b a

The difference with Finset.prod_ite_eq_of_mem is that the arguments to Eq are swapped.

theorem Finset.sum_ite_eq_of_mem' {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s : Finset ι) (a : ι) (b : ιM) (h : a s) :
(∑ xs, if x = a then b x else 0) = b a
@[simp]
theorem Finset.prod_pi_mulSingle' {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (a : ι) (x : M) (s : Finset ι) :
a's, Pi.mulSingle a x a' = if a s then x else 1
@[simp]
theorem Finset.sum_pi_single' {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (a : ι) (x : M) (s : Finset ι) :
a's, Pi.single a x a' = if a s then x else 0
@[simp]
theorem Finset.prod_pi_mulSingle {ι : Type u_1} {M : ιType u_6} [DecidableEq ι] [(a : ι) → CommMonoid (M a)] (a : ι) (f : (a : ι) → M a) (s : Finset ι) :
a's, Pi.mulSingle a' (f a') a = if a s then f a else 1
@[simp]
theorem Finset.sum_pi_single {ι : Type u_1} {M : ιType u_6} [DecidableEq ι] [(a : ι) → AddCommMonoid (M a)] (a : ι) (f : (a : ι) → M a) (s : Finset ι) :
a's, Pi.single a' (f a') a = if a s then f a else 0
theorem Finset.prod_piecewise {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s t : Finset ι) (f g : ιM) :
xs, t.piecewise f g x = (∏ xs t, f x) * xs \ t, g x
theorem Finset.sum_piecewise {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s t : Finset ι) (f g : ιM) :
xs, t.piecewise f g x = xs t, f x + xs \ t, g x
theorem Finset.prod_inter_mul_prod_diff {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s t : Finset ι) (f : ιM) :
(∏ xs t, f x) * xs \ t, f x = xs, f x
theorem Finset.sum_inter_add_sum_diff {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s t : Finset ι) (f : ιM) :
xs t, f x + xs \ t, f x = xs, f x
theorem Finset.prod_eq_mul_prod_diff_singleton {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : i s) (f : ιM) :
xs, f x = f i * xs \ {i}, f x
theorem Finset.sum_eq_add_sum_diff_singleton {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : i s) (f : ιM) :
xs, f x = f i + xs \ {i}, f x
theorem Finset.prod_eq_prod_diff_singleton_mul {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : i s) (f : ιM) :
xs, f x = (∏ xs \ {i}, f x) * f i
theorem Finset.sum_eq_sum_diff_singleton_add {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : i s) (f : ιM) :
xs, f x = xs \ {i}, f x + f i
theorem Fintype.prod_eq_mul_prod_compl {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] [Fintype ι] (a : ι) (f : ιM) :
i : ι, f i = f a * i{a}, f i
theorem Fintype.sum_eq_add_sum_compl {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] [Fintype ι] (a : ι) (f : ιM) :
i : ι, f i = f a + i{a}, f i
theorem Fintype.prod_eq_prod_compl_mul {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] [Fintype ι] (a : ι) (f : ιM) :
i : ι, f i = (∏ i{a}, f i) * f a
theorem Fintype.sum_eq_sum_compl_add {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] [Fintype ι] (a : ι) (f : ιM) :
i : ι, f i = i{a}, f i + f a
theorem Finset.dvd_prod_of_mem {ι : Type u_1} {M : Type u_3} [CommMonoid M] (f : ιM) {a : ι} {s : Finset ι} (ha : a s) :
f a is, f i
theorem Finset.prod_update_of_notMem {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : is) (f : ιM) (b : M) :
xs, Function.update f i b x = xs, f x
theorem Finset.sum_update_of_notMem {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : is) (f : ιM) (b : M) :
xs, Function.update f i b x = xs, f x
@[deprecated Finset.sum_update_of_notMem (since := "2025-05-23")]
theorem Finset.sum_update_of_not_mem {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : is) (f : ιM) (b : M) :
xs, Function.update f i b x = xs, f x

Alias of Finset.sum_update_of_notMem.

@[deprecated Finset.prod_update_of_notMem (since := "2025-05-23")]
theorem Finset.prod_update_of_not_mem {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : is) (f : ιM) (b : M) :
xs, Function.update f i b x = xs, f x

Alias of Finset.prod_update_of_notMem.

theorem Finset.prod_update_of_mem {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : i s) (f : ιM) (b : M) :
xs, Function.update f i b x = b * xs \ {i}, f x
theorem Finset.sum_update_of_mem {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] {s : Finset ι} {i : ι} (h : i s) (f : ιM) (b : M) :
xs, Function.update f i b x = b + xs \ {i}, f x
theorem Finset.prod_ite_one {ι : Type u_1} {M : Type u_3} [CommMonoid M] (s : Finset ι) (p : ιProp) [DecidablePred p] (h : is, js, p ip ji = j) (a : M) :
(∏ is, if p i then a else 1) = if is, p i then a else 1

See also Finset.prod_ite_zero.

theorem Finset.sum_ite_zero {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] (s : Finset ι) (p : ιProp) [DecidablePred p] (h : is, js, p ip ji = j) (a : M) :
(∑ is, if p i then a else 0) = if is, p i then a else 0

See also Finset.sum_boole.

theorem Finset.prod_pow_boole {ι : Type u_1} {M : Type u_3} [CommMonoid M] [DecidableEq ι] (s : Finset ι) (f : ιM) (a : ι) :
(∏ xs, f x ^ if a = x then 1 else 0) = if a s then f a else 1
theorem Finset.sum_boole_nsmul {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [DecidableEq ι] (s : Finset ι) (f : ιM) (a : ι) :
xs, (if a = x then 1 else 0) f x = if a s then f a else 0
theorem Finset.card_filter {ι : Type u_1} (p : ιProp) [DecidablePred p] (s : Finset ι) :
{is | p i}.card = is, if p i then 1 else 0
theorem Fintype.prod_ite_eq_ite_exists {ι : Type u_1} {M : Type u_3} [CommMonoid M] [Fintype ι] (p : ιProp) [DecidablePred p] (h : ∀ (i j : ι), p ip ji = j) (a : M) :
(∏ i : ι, if p i then a else 1) = if ∃ (i : ι), p i then a else 1
theorem Fintype.sum_ite_eq_ite_exists {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [Fintype ι] (p : ιProp) [DecidablePred p] (h : ∀ (i j : ι), p ip ji = j) (a : M) :
(∑ i : ι, if p i then a else 0) = if ∃ (i : ι), p i then a else 0
theorem Fintype.prod_ite_mem {ι : Type u_1} {M : Type u_3} [CommMonoid M] [Fintype ι] [DecidableEq ι] (s : Finset ι) (f : ιM) :
(∏ i : ι, if i s then f i else 1) = is, f i
theorem Fintype.sum_ite_mem {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [Fintype ι] [DecidableEq ι] (s : Finset ι) (f : ιM) :
(∑ i : ι, if i s then f i else 0) = is, f i
theorem Fintype.prod_dite_eq {ι : Type u_1} {M : Type u_3} [CommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (f : (j : ι) → i = jM) :
(∏ j : ι, if h : i = j then f j h else 1) = f i

See also Finset.prod_dite_eq.

theorem Fintype.sum_dite_eq {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (f : (j : ι) → i = jM) :
(∑ j : ι, if h : i = j then f j h else 0) = f i

See also Finset.sum_dite_eq.

theorem Fintype.prod_dite_eq' {ι : Type u_1} {M : Type u_3} [CommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (f : (j : ι) → j = iM) :
(∏ j : ι, if h : j = i then f j h else 1) = f i

See also Finset.prod_dite_eq'.

theorem Fintype.sum_dite_eq' {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (f : (j : ι) → j = iM) :
(∑ j : ι, if h : j = i then f j h else 0) = f i

See also Finset.sum_dite_eq'.

theorem Fintype.prod_ite_eq {ι : Type u_1} {M : Type u_3} [CommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (f : ιM) :
(∏ j : ι, if i = j then f j else 1) = f i

See also Finset.prod_ite_eq.

theorem Fintype.sum_ite_eq {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (f : ιM) :
(∑ j : ι, if i = j then f j else 0) = f i

See also Finset.sum_ite_eq.

theorem Fintype.prod_ite_eq' {ι : Type u_1} {M : Type u_3} [CommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (f : ιM) :
(∏ j : ι, if j = i then f j else 1) = f i

See also Finset.prod_ite_eq'.

theorem Fintype.sum_ite_eq' {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (f : ιM) :
(∑ j : ι, if j = i then f j else 0) = f i

See also Finset.sum_ite_eq'.

theorem Fintype.prod_pi_mulSingle {ι : Type u_1} [Fintype ι] [DecidableEq ι] {M : ιType u_6} [(i : ι) → CommMonoid (M i)] (i : ι) (f : (i : ι) → M i) :
j : ι, Pi.mulSingle j (f j) i = f i

See also Finset.prod_pi_mulSingle.

theorem Fintype.sum_pi_single {ι : Type u_1} [Fintype ι] [DecidableEq ι] {M : ιType u_6} [(i : ι) → AddCommMonoid (M i)] (i : ι) (f : (i : ι) → M i) :
j : ι, Pi.single j (f j) i = f i

See also Finset.sum_pi_single.

theorem Fintype.prod_pi_mulSingle' {ι : Type u_1} {M : Type u_3} [CommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (a : M) :
j : ι, Pi.mulSingle i a j = a

See also Finset.prod_pi_mulSingle'.

theorem Fintype.sum_pi_single' {ι : Type u_1} {M : Type u_3} [AddCommMonoid M] [Fintype ι] [DecidableEq ι] (i : ι) (a : M) :
j : ι, Pi.single i a j = a

See also Finset.sum_pi_single'.