mathlib documentation

data.finset.prod

Finsets in product types #

This file defines finset constructions on the product type α × β. Beware not to confuse with the finset.prod operation which computes the multiplicative product.

Main declarations #

prod #

@[protected]
def finset.product {α : Type u_1} {β : Type u_2} (s : finset α) (t : finset β) :
finset × β)

product s t is the set of pairs (a, b) such that a ∈ s and b ∈ t.

Equations
@[simp]
theorem finset.product_val {α : Type u_1} {β : Type u_2} {s : finset α} {t : finset β} :
@[simp]
theorem finset.mem_product {α : Type u_1} {β : Type u_2} {s : finset α} {t : finset β} {p : α × β} :
p s.product t p.fst s p.snd t
@[simp, norm_cast]
theorem finset.coe_product {α : Type u_1} {β : Type u_2} (s : finset α) (t : finset β) :
theorem finset.subset_product {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] {s : finset × β)} :
theorem finset.product_subset_product {α : Type u_1} {β : Type u_2} {s s' : finset α} {t t' : finset β} (hs : s s') (ht : t t') :
s.product t s'.product t'
theorem finset.product_subset_product_left {α : Type u_1} {β : Type u_2} {s s' : finset α} {t : finset β} (hs : s s') :
theorem finset.product_subset_product_right {α : Type u_1} {β : Type u_2} {s : finset α} {t t' : finset β} (ht : t t') :
theorem finset.product_eq_bUnion {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] (s : finset α) (t : finset β) :
s.product t = s.bUnion (λ (a : α), finset.image (λ (b : β), (a, b)) t)
theorem finset.product_eq_bUnion_right {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] (s : finset α) (t : finset β) :
s.product t = t.bUnion (λ (b : β), finset.image (λ (a : α), (a, b)) s)
@[simp]
theorem finset.product_bUnion {α : Type u_1} {β : Type u_2} {γ : Type u_3} [decidable_eq γ] (s : finset α) (t : finset β) (f : α × βfinset γ) :
(s.product t).bUnion f = s.bUnion (λ (a : α), t.bUnion (λ (b : β), f (a, b)))

See also finset.sup_product_left.

@[simp]
theorem finset.card_product {α : Type u_1} {β : Type u_2} (s : finset α) (t : finset β) :
(s.product t).card = (s.card) * t.card
theorem finset.filter_product {α : Type u_1} {β : Type u_2} {s : finset α} {t : finset β} (p : α → Prop) (q : β → Prop) [decidable_pred p] [decidable_pred q] :
finset.filter (λ (x : α × β), p x.fst q x.snd) (s.product t) = (finset.filter p s).product (finset.filter q t)
theorem finset.filter_product_card {α : Type u_1} {β : Type u_2} (s : finset α) (t : finset β) (p : α → Prop) (q : β → Prop) [decidable_pred p] [decidable_pred q] :
(finset.filter (λ (x : α × β), p x.fst q x.snd) (s.product t)).card = ((finset.filter p s).card) * (finset.filter q t).card + ((finset.filter (not p) s).card) * (finset.filter (not q) t).card
theorem finset.empty_product {α : Type u_1} {β : Type u_2} (t : finset β) :
theorem finset.product_empty {α : Type u_1} {β : Type u_2} (s : finset α) :
theorem finset.nonempty.product {α : Type u_1} {β : Type u_2} {s : finset α} {t : finset β} (hs : s.nonempty) (ht : t.nonempty) :
theorem finset.nonempty.fst {α : Type u_1} {β : Type u_2} {s : finset α} {t : finset β} (h : (s.product t).nonempty) :
theorem finset.nonempty.snd {α : Type u_1} {β : Type u_2} {s : finset α} {t : finset β} (h : (s.product t).nonempty) :
@[simp]
theorem finset.nonempty_product {α : Type u_1} {β : Type u_2} {s : finset α} {t : finset β} :
@[simp]
theorem finset.singleton_product {α : Type u_1} {β : Type u_2} {t : finset β} {a : α} :
{a}.product t = finset.map {to_fun := prod.mk a, inj' := _} t
@[simp]
theorem finset.product_singleton {α : Type u_1} {β : Type u_2} {s : finset α} {b : β} :
s.product {b} = finset.map {to_fun := λ (i : α), (i, b), inj' := _} s
theorem finset.singleton_product_singleton {α : Type u_1} {β : Type u_2} {a : α} {b : β} :
{a}.product {b} = {(a, b)}
@[simp]
theorem finset.union_product {α : Type u_1} {β : Type u_2} {s s' : finset α} {t : finset β} [decidable_eq α] [decidable_eq β] :
(s s').product t = s.product t s'.product t
@[simp]
theorem finset.product_union {α : Type u_1} {β : Type u_2} {s : finset α} {t t' : finset β} [decidable_eq α] [decidable_eq β] :
s.product (t t') = s.product t s.product t'
def finset.diag {α : Type u_1} (s : finset α) [decidable_eq α] :
finset × α)

Given a finite set s, the diagonal, s.diag is the set of pairs of the form (a, a) for a ∈ s.

Equations
def finset.off_diag {α : Type u_1} (s : finset α) [decidable_eq α] :
finset × α)

Given a finite set s, the off-diagonal, s.off_diag is the set of pairs (a, b) with a ≠ b for a, b ∈ s.

Equations
@[simp]
theorem finset.mem_diag {α : Type u_1} (s : finset α) [decidable_eq α] (x : α × α) :
x s.diag x.fst s x.fst = x.snd
@[simp]
theorem finset.mem_off_diag {α : Type u_1} (s : finset α) [decidable_eq α] (x : α × α) :
@[simp]
theorem finset.diag_card {α : Type u_1} (s : finset α) [decidable_eq α] :
@[simp]
theorem finset.off_diag_card {α : Type u_1} (s : finset α) [decidable_eq α] :
@[simp]
theorem finset.diag_empty {α : Type u_1} [decidable_eq α] :
@[simp]
theorem finset.off_diag_empty {α : Type u_1} [decidable_eq α] :