mathlib documentation

data.finset.basic

Finite sets

mathlib has several different models for finite sets, and it can be confusing when you're first getting used to them!

This file builds the basic theory of finset α, modelled as a multiset α without duplicates.

It's "constructive" in the since that there is an underlying list of elements, although this is wrapped in a quotient by permutations, so anytime you actually use this list you're obligated to show you didn't depend on the ordering.

There's also the typeclass fintype α (which asserts that there is some finset α containing every term of type α) as well as the predicate finite on s : set α (which asserts nonempty (fintype s)).

source
structure finset (α : Type u_4) :
Type u_4

finset α is the type of finite sets of elements of α. It is implemented as a multiset (a list up to permutation) which has no duplicate elements.

source
theorem finset.eq_of_veq {α : Type u_1} {s t : finset α} :
s.val = t.val → s = t

source
@[simp]
theorem finset.val_inj {α : Type u_1} {s t : finset α} :
s.val = t.val ↔ s = t

source
@[simp]
theorem finset.erase_dup_eq_self {α : Type u_1} [decidable_eq α] (s : finset α) :
s.val.erase_dup = s.val

source
@[instance]
def finset.has_decidable_eq {α : Type u_1} [decidable_eq α] :
decidable_eq (finset α)

Equations

membership

source
@[instance]
def finset.has_mem {α : Type u_1} :
has_mem α (finset α)

Equations
source
theorem finset.mem_def {α : Type u_1} {a : α} {s : finset α} :
a ∈ s ↔ a ∈ s.val

source
@[simp]
theorem finset.mem_mk {α : Type u_1} {a : α} {s : multiset α} {nd : s.nodup} :
a ∈ {val := s, nodup := nd} ↔ a ∈ s

source
@[instance]
def finset.decidable_mem {α : Type u_1} [h : decidable_eq α] (a : α) (s : finset α) :
decidable (a ∈ s)

Equations

set coercion

source
@[instance]
def finset.set.has_coe_t {α : Type u_1} :
has_coe_t (finset α) (set α)

Convert a finset to a set in the natural way.

Equations
source
@[simp]
theorem finset.mem_coe {α : Type u_1} {a : α} {s : finset α} :
a ∈ ↑s ↔ a ∈ s

source
@[simp]
theorem finset.set_of_mem {α : Type u_1} {s : finset α} :
{a : α | a ∈ s} = ↑s

source
@[simp]
theorem finset.coe_mem {α : Type u_1} {s : finset α} (x : ↥↑s) :
↑x ∈ s

source
@[simp]
theorem finset.mk_coe {α : Type u_1} {s : finset α} (x : ↥↑s) {h : ↑x ∈ ↑s} :
⟨↑x, h⟩ = x

source
@[instance]
def finset.decidable_mem' {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
decidable (a ∈ ↑s)

Equations

extensionality

source
theorem finset.ext_iff {α : Type u_1} {s₁ s₂ : finset α} :
s₁ = s₂ ↔ ∀ (a : α), a ∈ s₁ ↔ a ∈ s₂

source
@[ext]
theorem finset.ext {α : Type u_1} {s₁ s₂ : finset α} :
(∀ (a : α), a ∈ s₁ ↔ a ∈ s₂) → s₁ = s₂

source
@[simp]
theorem finset.coe_inj {α : Type u_1} {s₁ s₂ : finset α} :
↑s₁ = ↑s₂ ↔ s₁ = s₂

source
theorem finset.coe_injective {α : Type u_1} :
function.injective coe

subset

source
@[instance]
def finset.has_subset {α : Type u_1} :
has_subset (finset α)

Equations
source
theorem finset.subset_def {α : Type u_1} {s₁ s₂ : finset α} :
s₁ ⊆ s₂ ↔ s₁.val ⊆ s₂.val

source
@[simp]
theorem finset.subset.refl {α : Type u_1} (s : finset α) :
s ⊆ s

source
theorem finset.subset_of_eq {α : Type u_1} {s t : finset α} (h : s = t) :
s ⊆ t

source
theorem finset.subset.trans {α : Type u_1} {s₁ s₂ s₃ : finset α} :
s₁ ⊆ s₂ → s₂ ⊆ s₃ → s₁ ⊆ s₃

source
theorem finset.superset.trans {α : Type u_1} {s₁ s₂ s₃ : finset α} :
s₁ ⊇ s₂ → s₂ ⊇ s₃ → s₁ ⊇ s₃

source
theorem finset.mem_of_subset {α : Type u_1} {s₁ s₂ : finset α} {a : α} :
s₁ ⊆ s₂ → a ∈ s₁ → a ∈ s₂

source
theorem finset.subset.antisymm {α : Type u_1} {s₁ s₂ : finset α} (H₁ : s₁ ⊆ s₂) (H₂ : s₂ ⊆ s₁) :
s₁ = s₂

source
theorem finset.subset_iff {α : Type u_1} {s₁ s₂ : finset α} :
s₁ ⊆ s₂ ↔ ∀ ⦃x : α⦄, x ∈ s₁ → x ∈ s₂

source
@[simp]
theorem finset.coe_subset {α : Type u_1} {s₁ s₂ : finset α} :
↑s₁ ⊆ ↑s₂ ↔ s₁ ⊆ s₂

source
@[simp]
theorem finset.val_le_iff {α : Type u_1} {s₁ s₂ : finset α} :
s₁.val ≤ s₂.val ↔ s₁ ⊆ s₂

source
@[instance]
def finset.has_ssubset {α : Type u_1} :
has_ssubset (finset α)

Equations
source
@[instance]
def finset.partial_order {α : Type u_1} :
partial_order (finset α)

Equations
source
theorem finset.subset.antisymm_iff {α : Type u_1} {s₁ s₂ : finset α} :
s₁ = s₂ ↔ s₁ ⊆ s₂ ∧ s₂ ⊆ s₁

source
@[simp]
theorem finset.le_iff_subset {α : Type u_1} {s₁ s₂ : finset α} :
s₁ ≤ s₂ ↔ s₁ ⊆ s₂

source
@[simp]
theorem finset.lt_iff_ssubset {α : Type u_1} {s₁ s₂ : finset α} :
s₁ < s₂ ↔ s₁ ⊂ s₂

source
@[simp]
theorem finset.coe_ssubset {α : Type u_1} {s₁ s₂ : finset α} :
↑s₁ ⊂ ↑s₂ ↔ s₁ ⊂ s₂

source
@[simp]
theorem finset.val_lt_iff {α : Type u_1} {s₁ s₂ : finset α} :
s₁.val < s₂.val ↔ s₁ ⊂ s₂

source
theorem finset.ssubset_iff_of_subset {α : Type u_1} {s₁ s₂ : finset α} (h : s₁ ⊆ s₂) :
s₁ ⊂ s₂ ↔ ∃ (x : α) (H : x ∈ s₂), x ∉ s₁

Nonempty

source
def finset.nonempty {α : Type u_1} (s : finset α) :
Prop

The property s.nonempty expresses the fact that the finset s is not empty. It should be used in theorem assumptions instead of ∃ x, x ∈ s or s ≠ ∅ as it gives access to a nice API thanks to the dot notation.

Equations
source
@[simp]
theorem finset.coe_nonempty {α : Type u_1} {s : finset α} :
↑s.nonempty ↔ s.nonempty

source
theorem finset.nonempty.bex {α : Type u_1} {s : finset α} (h : s.nonempty) :
∃ (x : α), x ∈ s

source
theorem finset.nonempty.mono {α : Type u_1} {s t : finset α} (hst : s ⊆ t) (hs : s.nonempty) :
t.nonempty

empty

source
def finset.empty {α : Type u_1} :
finset α

The empty finset

Equations
source
@[instance]
def finset.has_emptyc {α : Type u_1} :
has_emptyc (finset α)

Equations
source
@[instance]
def finset.inhabited {α : Type u_1} :
inhabited (finset α)

Equations
source
@[simp]
theorem finset.empty_val {α : Type u_1} :
∅.val = 0

source
@[simp]
theorem finset.not_mem_empty {α : Type u_1} (a : α) :
a ∉ ∅

source
@[simp]
theorem finset.not_nonempty_empty {α : Type u_1} :
¬∅.nonempty

source
@[simp]
theorem finset.mk_zero {α : Type u_1} :
{val := 0, nodup := _} = ∅

source
theorem finset.ne_empty_of_mem {α : Type u_1} {a : α} {s : finset α} (h : a ∈ s) :
s ≠ ∅

source
theorem finset.nonempty.ne_empty {α : Type u_1} {s : finset α} (h : s.nonempty) :
s ≠ ∅

source
@[simp]
theorem finset.empty_subset {α : Type u_1} (s : finset α) :
∅ ⊆ s

source
theorem finset.eq_empty_of_forall_not_mem {α : Type u_1} {s : finset α} (H : ∀ (x : α), x ∉ s) :
s = ∅

source
theorem finset.eq_empty_iff_forall_not_mem {α : Type u_1} {s : finset α} :
s = ∅ ↔ ∀ (x : α), x ∉ s

source
@[simp]
theorem finset.val_eq_zero {α : Type u_1} {s : finset α} :
s.val = 0 ↔ s = ∅

source
theorem finset.subset_empty {α : Type u_1} {s : finset α} :
s ⊆ ∅ ↔ s = ∅

source
theorem finset.nonempty_of_ne_empty {α : Type u_1} {s : finset α} (h : s ≠ ∅) :
s.nonempty

source
theorem finset.nonempty_iff_ne_empty {α : Type u_1} {s : finset α} :
s.nonempty ↔ s ≠ ∅

source
@[simp]
theorem finset.not_nonempty_iff_eq_empty {α : Type u_1} {s : finset α} :
¬s.nonempty ↔ s = ∅

source
theorem finset.eq_empty_or_nonempty {α : Type u_1} (s : finset α) :
s = ∅ ∨ s.nonempty

source
@[simp]
theorem finset.coe_empty {α : Type u_1} :
↑∅ = ∅

source
theorem finset.eq_empty_of_not_nonempty {α : Type u_1} (h : ¬nonempty α) (s : finset α) :
s = ∅

A finset for an empty type is empty.

singleton

source
@[instance]
def finset.has_singleton {α : Type u_1} :
has_singleton α (finset α)

{a} : finset a is the set {a} containing a and nothing else.

This differs from insert a ∅ in that it does not require a decidable_eq instance for α.

Equations
source
@[simp]
theorem finset.singleton_val {α : Type u_1} (a : α) :
{a}.val = a ::ₘ 0

source
@[simp]
theorem finset.mem_singleton {α : Type u_1} {a b : α} :
b ∈ {a} ↔ b = a

source
theorem finset.not_mem_singleton {α : Type u_1} {a b : α} :
a ∉ {b} ↔ a ≠ b

source
theorem finset.mem_singleton_self {α : Type u_1} (a : α) :
a ∈ {a}

source
theorem finset.singleton_inj {α : Type u_1} {a b : α} :
{a} = {b} ↔ a = b

source
@[simp]
theorem finset.singleton_nonempty {α : Type u_1} (a : α) :
{a}.nonempty

source
@[simp]
theorem finset.singleton_ne_empty {α : Type u_1} (a : α) :
{a} ≠ ∅

source
@[simp]
theorem finset.coe_singleton {α : Type u_1} (a : α) :
↑{a} = {a}

source
theorem finset.eq_singleton_iff_unique_mem {α : Type u_1} {s : finset α} {a : α} :
s = {a} ↔ a ∈ s ∧ ∀ (x : α), x ∈ s → x = a

source
theorem finset.eq_singleton_iff_nonempty_unique_mem {α : Type u_1} {s : finset α} {a : α} :
s = {a} ↔ s.nonempty ∧ ∀ (x : α), x ∈ s → x = a

source
theorem finset.singleton_iff_unique_mem {α : Type u_1} (s : finset α) :
(∃ (a : α), s = {a}) ↔ ∃! (a : α), a ∈ s

source
theorem finset.singleton_subset_set_iff {α : Type u_1} {s : set α} {a : α} :
↑{a} ⊆ s ↔ a ∈ s

source
@[simp]
theorem finset.singleton_subset_iff {α : Type u_1} {s : finset α} {a : α} :
{a} ⊆ s ↔ a ∈ s

cons

source
def finset.cons {α : Type u_1} (a : α) (s : finset α) (h : a ∉ s) :
finset α

cons a s h is the set {a} ∪ s containing a and the elements of s. It is the same as insert a s when it is defined, but unlike insert a s it does not require decidable_eq α, and the union is guaranteed to be disjoint.

Equations
source
@[simp]
theorem finset.mem_cons {α : Type u_1} {a : α} {s : finset α} {h : a ∉ s} {b : α} :
b ∈ finset.cons a s h ↔ b = a ∨ b ∈ s

source
@[simp]
theorem finset.cons_val {α : Type u_1} {a : α} {s : finset α} (h : a ∉ s) :
(finset.cons a s h).val = a ::ₘ s.val

source
@[simp]
theorem finset.mk_cons {α : Type u_1} {a : α} {s : multiset α} (h : (a ::ₘ s).nodup) :
{val := a ::ₘ s, nodup := h} = finset.cons a {val := s, nodup := _} _

source
@[simp]
theorem finset.nonempty_cons {α : Type u_1} {a : α} {s : finset α} (h : a ∉ s) :
(finset.cons a s h).nonempty

source
@[simp]
theorem finset.nonempty_mk_coe {α : Type u_1} {l : list α} {hl : ↑l.nodup} :
{val := ↑l, nodup := hl}.nonempty ↔ l ≠ list.nil

disjoint union

source
def finset.disj_union {α : Type u_1} (s t : finset α) (h : ∀ (a : α), a ∈ s → a ∉ t) :
finset α

disj_union s t h is the set such that a ∈ disj_union s t h iff a ∈ s or a ∈ t. It is the same as s ∪ t, but it does not require decidable equality on the type. The hypothesis ensures that the sets are disjoint.

Equations
source
@[simp]
theorem finset.mem_disj_union {α : Type u_1} {s t : finset α} {h : ∀ (a : α), a ∈ s → a ∉ t} {a : α} :
a ∈ s.disj_union t h ↔ a ∈ s ∨ a ∈ t

insert

source
@[instance]
def finset.has_insert {α : Type u_1} [decidable_eq α] :
has_insert α (finset α)

insert a s is the set {a} ∪ s containing a and the elements of s.

Equations
source
theorem finset.insert_def {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
insert a s = {val := multiset.ndinsert a s.val, nodup := _}

source
@[simp]
theorem finset.insert_val {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
(insert a s).val = multiset.ndinsert a s.val

source
theorem finset.insert_val' {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
(insert a s).val = (a ::ₘ s.val).erase_dup

source
theorem finset.insert_val_of_not_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∉ s) :
(insert a s).val = a ::ₘ s.val

source
@[simp]
theorem finset.mem_insert {α : Type u_1} [decidable_eq α] {a b : α} {s : finset α} :
a ∈ insert b s ↔ a = b ∨ a ∈ s

source
theorem finset.mem_insert_self {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
a ∈ insert a s

source
theorem finset.mem_insert_of_mem {α : Type u_1} [decidable_eq α] {a b : α} {s : finset α} (h : a ∈ s) :
a ∈ insert b s

source
theorem finset.mem_of_mem_insert_of_ne {α : Type u_1} [decidable_eq α] {a b : α} {s : finset α} (h : b ∈ insert a s) :
b ≠ a → b ∈ s

source
@[simp]
theorem finset.cons_eq_insert {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) (h : a ∉ s) :
finset.cons a s h = insert a s

source
@[simp]
theorem finset.coe_insert {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
↑(insert a s) = insert a ↑s

source
theorem finset.mem_insert_coe {α : Type u_1} [decidable_eq α] {s : finset α} {x y : α} :
x ∈ insert y s ↔ x ∈ insert y ↑s

source
@[instance]
def finset.is_lawful_singleton {α : Type u_1} [decidable_eq α] :
is_lawful_singleton α (finset α)

source
@[simp]
theorem finset.insert_eq_of_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∈ s) :
insert a s = s

source
@[simp]
theorem finset.insert_singleton_self_eq {α : Type u_1} [decidable_eq α] (a : α) :
{a, a} = {a}

source
theorem finset.insert.comm {α : Type u_1} [decidable_eq α] (a b : α) (s : finset α) :
insert a (insert b s) = insert b (insert a s)

source
theorem finset.insert_singleton_comm {α : Type u_1} [decidable_eq α] (a b : α) :
{a, b} = {b, a}

source
@[simp]
theorem finset.insert_idem {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
insert a (insert a s) = insert a s

source
@[simp]
theorem finset.insert_nonempty {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
(insert a s).nonempty

source
@[simp]
theorem finset.insert_ne_empty {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
insert a s ≠ ∅

The universe annotation is required for the following instance, possibly this is a bug in Lean. See leanprover.zulipchat.com/#narrow/stream/113488-general/topic/strange.20error.20(universe.20issue.3F)

source
@[instance]
def finset.has_insert.insert.nonempty {α : Type u} [decidable_eq α] (i : α) (s : finset α) :
nonempty ↥↑(insert i s)

source
theorem finset.ne_insert_of_not_mem {α : Type u_1} [decidable_eq α] (s t : finset α) {a : α} (h : a ∉ s) :
s ≠ insert a t

source
theorem finset.insert_subset {α : Type u_1} [decidable_eq α] {a : α} {s t : finset α} :
insert a s ⊆ t ↔ a ∈ t ∧ s ⊆ t

source
theorem finset.subset_insert {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
s ⊆ insert a s

source
theorem finset.insert_subset_insert {α : Type u_1} [decidable_eq α] (a : α) {s t : finset α} (h : s ⊆ t) :
insert a s ⊆ insert a t

source
theorem finset.ssubset_iff {α : Type u_1} [decidable_eq α] {s t : finset α} :
s ⊂ t ↔ ∃ (a : α) (H : a ∉ s), insert a s ⊆ t

source
theorem finset.ssubset_insert {α : Type u_1} [decidable_eq α] {s : finset α} {a : α} (h : a ∉ s) :
s ⊂ insert a s

source
theorem finset.induction {α : Type u_1} {p : finset α → Prop} [decidable_eq α] (h₁ : p ∅) (h₂ : ∀ ⦃a : α⦄ {s : finset α}, a ∉ s → p s → p (insert a s)) (s : finset α) :
p s

source
theorem finset.induction_on {α : Type u_1} {p : finset α → Prop} [decidable_eq α] (s : finset α) (h₁ : p ∅) (h₂ : ∀ ⦃a : α⦄ {s : finset α}, a ∉ s → p s → p (insert a s)) :
p s

To prove a proposition about an arbitrary finset α, it suffices to prove it for the empty finset, and to show that if it holds for some finset α, then it holds for the finset obtained by inserting a new element.

source
theorem finset.induction_on' {α : Type u_1} {p : finset α → Prop} [decidable_eq α] (S : finset α) (h₁ : p ∅) (h₂ : ∀ {a : α} {s : finset α}, a ∈ S → s ⊆ S → a ∉ s → p s → p (insert a s)) :
p S

To prove a proposition about S : finset α, it suffices to prove it for the empty finset, and to show that if it holds for some finset α ⊆ S, then it holds for the finset obtained by inserting a new element of S.

source
def finset.subtype_insert_equiv_option {α : Type u_1} [decidable_eq α] {t : finset α} {x : α} (h : x ∉ t) :
{i // i ∈ insert x t} ≃ option {i // i ∈ t}

Inserting an element to a finite set is equivalent to the option type.

Equations

union

source
@[instance]
def finset.has_union {α : Type u_1} [decidable_eq α] :
has_union (finset α)

s ∪ t is the set such that a ∈ s ∪ t iff a ∈ s or a ∈ t.

Equations
source
theorem finset.union_val_nd {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
(s₁ ∪ s₂).val = s₁.val.ndunion s₂.val

source
@[simp]
theorem finset.union_val {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
(s₁ ∪ s₂).val = s₁.val ∪ s₂.val

source
@[simp]
theorem finset.mem_union {α : Type u_1} [decidable_eq α] {a : α} {s₁ s₂ : finset α} :
a ∈ s₁ ∪ s₂ ↔ a ∈ s₁ ∨ a ∈ s₂

source
@[simp]
theorem finset.disj_union_eq_union {α : Type u_1} [decidable_eq α] (s t : finset α) (h : ∀ (a : α), a ∈ s → a ∉ t) :
s.disj_union t h = s ∪ t

source
theorem finset.mem_union_left {α : Type u_1} [decidable_eq α] {a : α} {s₁ : finset α} (s₂ : finset α) (h : a ∈ s₁) :
a ∈ s₁ ∪ s₂

source
theorem finset.mem_union_right {α : Type u_1} [decidable_eq α] {a : α} {s₂ : finset α} (s₁ : finset α) (h : a ∈ s₂) :
a ∈ s₁ ∪ s₂

source
theorem finset.forall_mem_union {α : Type u_1} [decidable_eq α] {s₁ s₂ : finset α} {p : α → Prop} :
(∀ (ab : α), ab ∈ s₁ ∪ s₂ → p ab) ↔ (∀ (a : α), a ∈ s₁ → p a) ∧ ∀ (b : α), b ∈ s₂ → p b

source
theorem finset.not_mem_union {α : Type u_1} [decidable_eq α] {a : α} {s₁ s₂ : finset α} :
a ∉ s₁ ∪ s₂ ↔ a ∉ s₁ ∧ a ∉ s₂

source
@[simp]
theorem finset.coe_union {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
↑(s₁ ∪ s₂) = ↑s₁ ∪ ↑s₂

source
theorem finset.union_subset {α : Type u_1} [decidable_eq α] {s₁ s₂ s₃ : finset α} (h₁ : s₁ ⊆ s₃) (h₂ : s₂ ⊆ s₃) :
s₁ ∪ s₂ ⊆ s₃

source
theorem finset.subset_union_left {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ ⊆ s₁ ∪ s₂

source
theorem finset.subset_union_right {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₂ ⊆ s₁ ∪ s₂

source
theorem finset.union_subset_union {α : Type u_1} [decidable_eq α] {s1 t1 s2 t2 : finset α} (h1 : s1 ⊆ t1) (h2 : s2 ⊆ t2) :
s1 ∪ s2 ⊆ t1 ∪ t2

source
theorem finset.union_comm {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ ∪ s₂ = s₂ ∪ s₁

source
@[instance]
def finset.has_union.union.is_commutative {α : Type u_1} [decidable_eq α] :
is_commutative (finset α) has_union.union

source
@[simp]
theorem finset.union_assoc {α : Type u_1} [decidable_eq α] (s₁ s₂ s₃ : finset α) :
s₁ ∪ s₂ ∪ s₃ = s₁ ∪ (s₂ ∪ s₃)

source
@[instance]
def finset.has_union.union.is_associative {α : Type u_1} [decidable_eq α] :
is_associative (finset α) has_union.union

source
@[simp]
theorem finset.union_idempotent {α : Type u_1} [decidable_eq α] (s : finset α) :
s ∪ s = s

source
@[instance]
def finset.has_union.union.is_idempotent {α : Type u_1} [decidable_eq α] :
is_idempotent (finset α) has_union.union

source
theorem finset.union_left_comm {α : Type u_1} [decidable_eq α] (s₁ s₂ s₃ : finset α) :
s₁ ∪ (s₂ ∪ s₃) = s₂ ∪ (s₁ ∪ s₃)

source
theorem finset.union_right_comm {α : Type u_1} [decidable_eq α] (s₁ s₂ s₃ : finset α) :
s₁ ∪ s₂ ∪ s₃ = s₁ ∪ s₃ ∪ s₂

source
theorem finset.union_self {α : Type u_1} [decidable_eq α] (s : finset α) :
s ∪ s = s

source
@[simp]
theorem finset.union_empty {α : Type u_1} [decidable_eq α] (s : finset α) :
s ∪ ∅ = s

source
@[simp]
theorem finset.empty_union {α : Type u_1} [decidable_eq α] (s : finset α) :
∅ ∪ s = s

source
theorem finset.insert_eq {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
insert a s = {a} ∪ s

source
@[simp]
theorem finset.insert_union {α : Type u_1} [decidable_eq α] (a : α) (s t : finset α) :
insert a s ∪ t = insert a (s ∪ t)

source
@[simp]
theorem finset.union_insert {α : Type u_1} [decidable_eq α] (a : α) (s t : finset α) :
s ∪ insert a t = insert a (s ∪ t)

source
theorem finset.insert_union_distrib {α : Type u_1} [decidable_eq α] (a : α) (s t : finset α) :
insert a (s ∪ t) = insert a s ∪ insert a t

source
@[simp]
theorem finset.union_eq_left_iff_subset {α : Type u_1} [decidable_eq α] {s t : finset α} :
s ∪ t = s ↔ t ⊆ s

source
@[simp]
theorem finset.left_eq_union_iff_subset {α : Type u_1} [decidable_eq α] {s t : finset α} :
s = s ∪ t ↔ t ⊆ s

source
@[simp]
theorem finset.union_eq_right_iff_subset {α : Type u_1} [decidable_eq α] {s t : finset α} :
t ∪ s = s ↔ t ⊆ s

source
@[simp]
theorem finset.right_eq_union_iff_subset {α : Type u_1} [decidable_eq α] {s t : finset α} :
s = t ∪ s ↔ t ⊆ s

source
theorem finset.induction_on_union {α : Type u_1} [decidable_eq α] (P : finset α → finset α → Prop) (symm : ∀ {a b : finset α}, P a b → P b a) (empty_right : ∀ {a : finset α}, P a ∅) (singletons : ∀ {a b : α}, P {a} {b}) (union_of : ∀ {a b c : finset α}, P a c → P b c → P (a ∪ b) c) (a b : finset α) :
P a b

To prove a relation on pairs of finset X, it suffices to show that it is

  • symmetric,
  • it holds when one of the finsets is empty,
  • it holds for pairs of singletons,
  • if it holds for [a, c] and for [b, c], then it holds for [a ∪ b, c].

inter

source
@[instance]
def finset.has_inter {α : Type u_1} [decidable_eq α] :
has_inter (finset α)

s ∩ t is the set such that a ∈ s ∩ t iff a ∈ s and a ∈ t.

Equations
source
theorem finset.inter_val_nd {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
(s₁ ∩ s₂).val = s₁.val.ndinter s₂.val

source
@[simp]
theorem finset.inter_val {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
(s₁ ∩ s₂).val = s₁.val ∩ s₂.val

source
@[simp]
theorem finset.mem_inter {α : Type u_1} [decidable_eq α] {a : α} {s₁ s₂ : finset α} :
a ∈ s₁ ∩ s₂ ↔ a ∈ s₁ ∧ a ∈ s₂

source
theorem finset.mem_of_mem_inter_left {α : Type u_1} [decidable_eq α] {a : α} {s₁ s₂ : finset α} (h : a ∈ s₁ ∩ s₂) :
a ∈ s₁

source
theorem finset.mem_of_mem_inter_right {α : Type u_1} [decidable_eq α] {a : α} {s₁ s₂ : finset α} (h : a ∈ s₁ ∩ s₂) :
a ∈ s₂

source
theorem finset.mem_inter_of_mem {α : Type u_1} [decidable_eq α] {a : α} {s₁ s₂ : finset α} :
a ∈ s₁ → a ∈ s₂ → a ∈ s₁ ∩ s₂

source
theorem finset.inter_subset_left {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ ∩ s₂ ⊆ s₁

source
theorem finset.inter_subset_right {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ ∩ s₂ ⊆ s₂

source
theorem finset.subset_inter {α : Type u_1} [decidable_eq α] {s₁ s₂ s₃ : finset α} :
s₁ ⊆ s₂ → s₁ ⊆ s₃ → s₁ ⊆ s₂ ∩ s₃

source
@[simp]
theorem finset.coe_inter {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
↑(s₁ ∩ s₂) = ↑s₁ ∩ ↑s₂

source
@[simp]
theorem finset.union_inter_cancel_left {α : Type u_1} [decidable_eq α] {s t : finset α} :
(s ∪ t) ∩ s = s

source
@[simp]
theorem finset.union_inter_cancel_right {α : Type u_1} [decidable_eq α] {s t : finset α} :
(s ∪ t) ∩ t = t

source
theorem finset.inter_comm {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ ∩ s₂ = s₂ ∩ s₁

source
@[simp]
theorem finset.inter_assoc {α : Type u_1} [decidable_eq α] (s₁ s₂ s₃ : finset α) :
s₁ ∩ s₂ ∩ s₃ = s₁ ∩ (s₂ ∩ s₃)

source
theorem finset.inter_left_comm {α : Type u_1} [decidable_eq α] (s₁ s₂ s₃ : finset α) :
s₁ ∩ (s₂ ∩ s₃) = s₂ ∩ (s₁ ∩ s₃)

source
theorem finset.inter_right_comm {α : Type u_1} [decidable_eq α] (s₁ s₂ s₃ : finset α) :
s₁ ∩ s₂ ∩ s₃ = s₁ ∩ s₃ ∩ s₂

source
@[simp]
theorem finset.inter_self {α : Type u_1} [decidable_eq α] (s : finset α) :
s ∩ s = s

source
@[simp]
theorem finset.inter_empty {α : Type u_1} [decidable_eq α] (s : finset α) :
s ∩ ∅ = ∅

source
@[simp]
theorem finset.empty_inter {α : Type u_1} [decidable_eq α] (s : finset α) :
∅ ∩ s = ∅

source
@[simp]
theorem finset.inter_union_self {α : Type u_1} [decidable_eq α] (s t : finset α) :
s ∩ (t ∪ s) = s

source
@[simp]
theorem finset.insert_inter_of_mem {α : Type u_1} [decidable_eq α] {s₁ s₂ : finset α} {a : α} (h : a ∈ s₂) :
insert a s₁ ∩ s₂ = insert a (s₁ ∩ s₂)

source
@[simp]
theorem finset.inter_insert_of_mem {α : Type u_1} [decidable_eq α] {s₁ s₂ : finset α} {a : α} (h : a ∈ s₁) :
s₁ ∩ insert a s₂ = insert a (s₁ ∩ s₂)

source
@[simp]
theorem finset.insert_inter_of_not_mem {α : Type u_1} [decidable_eq α] {s₁ s₂ : finset α} {a : α} (h : a ∉ s₂) :
insert a s₁ ∩ s₂ = s₁ ∩ s₂

source
@[simp]
theorem finset.inter_insert_of_not_mem {α : Type u_1} [decidable_eq α] {s₁ s₂ : finset α} {a : α} (h : a ∉ s₁) :
s₁ ∩ insert a s₂ = s₁ ∩ s₂

source
@[simp]
theorem finset.singleton_inter_of_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (H : a ∈ s) :
{a} ∩ s = {a}

source
@[simp]
theorem finset.singleton_inter_of_not_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (H : a ∉ s) :
{a} ∩ s = ∅

source
@[simp]
theorem finset.inter_singleton_of_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∈ s) :
s ∩ {a} = {a}

source
@[simp]
theorem finset.inter_singleton_of_not_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∉ s) :
s ∩ {a} = ∅

source
theorem finset.inter_subset_inter {α : Type u_1} [decidable_eq α] {x y s t : finset α} (h : x ⊆ y) (h' : s ⊆ t) :
x ∩ s ⊆ y ∩ t

source
theorem finset.inter_subset_inter_right {α : Type u_1} [decidable_eq α] {x y s : finset α} (h : x ⊆ y) :
x ∩ s ⊆ y ∩ s

source
theorem finset.inter_subset_inter_left {α : Type u_1} [decidable_eq α] {x y s : finset α} (h : x ⊆ y) :
s ∩ x ⊆ s ∩ y

lattice laws

source
@[instance]
def finset.lattice {α : Type u_1} [decidable_eq α] :
lattice (finset α)

Equations
source
@[simp]
theorem finset.sup_eq_union {α : Type u_1} [decidable_eq α] (s t : finset α) :
s ⊔ t = s ∪ t

source
@[simp]
theorem finset.inf_eq_inter {α : Type u_1} [decidable_eq α] (s t : finset α) :
s ⊓ t = s ∩ t

source
@[instance]
def finset.semilattice_inf_bot {α : Type u_1} [decidable_eq α] :
semilattice_inf_bot (finset α)

Equations
source
@[instance]
def finset.semilattice_sup_bot {α : Type u_1} [decidable_eq α] :
semilattice_sup_bot (finset α)

Equations
source
@[instance]
def finset.distrib_lattice {α : Type u_1} [decidable_eq α] :
distrib_lattice (finset α)

Equations
source
theorem finset.inter_distrib_left {α : Type u_1} [decidable_eq α] (s t u : finset α) :
s ∩ (t ∪ u) = s ∩ t ∪ s ∩ u

source
theorem finset.inter_distrib_right {α : Type u_1} [decidable_eq α] (s t u : finset α) :
(s ∪ t) ∩ u = s ∩ u ∪ t ∩ u

source
theorem finset.union_distrib_left {α : Type u_1} [decidable_eq α] (s t u : finset α) :
s ∪ t ∩ u = (s ∪ t) ∩ (s ∪ u)

source
theorem finset.union_distrib_right {α : Type u_1} [decidable_eq α] (s t u : finset α) :
s ∩ t ∪ u = (s ∪ u) ∩ (t ∪ u)

source
theorem finset.union_eq_empty_iff {α : Type u_1} [decidable_eq α] (A B : finset α) :
A ∪ B = ∅ ↔ A = ∅ ∧ B = ∅

erase

source
def finset.erase {α : Type u_1} [decidable_eq α] (s : finset α) (a : α) :
finset α

erase s a is the set s - {a}, that is, the elements of s which are not equal to a.

Equations
source
@[simp]
theorem finset.erase_val {α : Type u_1} [decidable_eq α] (s : finset α) (a : α) :
(s.erase a).val = s.val.erase a

source
@[simp]
theorem finset.mem_erase {α : Type u_1} [decidable_eq α] {a b : α} {s : finset α} :
a ∈ s.erase b ↔ a ≠ b ∧ a ∈ s

source
theorem finset.not_mem_erase {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
a ∉ s.erase a

source
@[simp]
theorem finset.erase_empty {α : Type u_1} [decidable_eq α] (a : α) :
∅.erase a = ∅

source
theorem finset.ne_of_mem_erase {α : Type u_1} [decidable_eq α] {a b : α} {s : finset α} :
b ∈ s.erase a → b ≠ a

source
theorem finset.mem_of_mem_erase {α : Type u_1} [decidable_eq α] {a b : α} {s : finset α} :
b ∈ s.erase a → b ∈ s

source
theorem finset.mem_erase_of_ne_of_mem {α : Type u_1} [decidable_eq α] {a b : α} {s : finset α} :
a ≠ b → a ∈ s → a ∈ s.erase b

source
theorem finset.eq_of_mem_of_not_mem_erase {α : Type u_1} [decidable_eq α] {a b : α} {s : finset α} (hs : b ∈ s) (hsa : b ∉ s.erase a) :
b = a

An element of s that is not an element of erase s a must be a.

source
theorem finset.erase_insert {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∉ s) :
(insert a s).erase a = s

source
theorem finset.insert_erase {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∈ s) :
insert a (s.erase a) = s

source
theorem finset.erase_subset_erase {α : Type u_1} [decidable_eq α] (a : α) {s t : finset α} (h : s ⊆ t) :
s.erase a ⊆ t.erase a

source
theorem finset.erase_subset {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
s.erase a ⊆ s

source
@[simp]
theorem finset.coe_erase {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
↑(s.erase a) = ↑s \ {a}

source
theorem finset.erase_ssubset {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∈ s) :
s.erase a ⊂ s

source
theorem finset.erase_eq_of_not_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∉ s) :
s.erase a = s

source
theorem finset.subset_insert_iff {α : Type u_1} [decidable_eq α] {a : α} {s t : finset α} :
s ⊆ insert a t ↔ s.erase a ⊆ t

source
theorem finset.erase_insert_subset {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
(insert a s).erase a ⊆ s

source
theorem finset.insert_erase_subset {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
s ⊆ insert a (s.erase a)

sdiff

source
@[instance]
def finset.has_sdiff {α : Type u_1} [decidable_eq α] :
has_sdiff (finset α)

s \ t is the set consisting of the elements of s that are not in t.

Equations
source
@[simp]
theorem finset.mem_sdiff {α : Type u_1} [decidable_eq α] {a : α} {s₁ s₂ : finset α} :
a ∈ s₁ \ s₂ ↔ a ∈ s₁ ∧ a ∉ s₂

source
theorem finset.not_mem_sdiff_of_mem_right {α : Type u_1} [decidable_eq α] {a : α} {s t : finset α} (h : a ∈ t) :
a ∉ s \ t

source
theorem finset.sdiff_union_of_subset {α : Type u_1} [decidable_eq α] {s₁ s₂ : finset α} (h : s₁ ⊆ s₂) :
s₂ \ s₁ ∪ s₁ = s₂

source
theorem finset.union_sdiff_of_subset {α : Type u_1} [decidable_eq α] {s₁ s₂ : finset α} (h : s₁ ⊆ s₂) :
s₁ ∪ s₂ \ s₁ = s₂

source
theorem finset.inter_sdiff {α : Type u_1} [decidable_eq α] (s t u : finset α) :
s ∩ (t \ u) = s ∩ t \ u

source
@[simp]
theorem finset.inter_sdiff_self {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ ∩ (s₂ \ s₁) = ∅

source
@[simp]
theorem finset.sdiff_inter_self {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₂ \ s₁ ∩ s₁ = ∅

source
@[simp]
theorem finset.sdiff_self {α : Type u_1} [decidable_eq α] (s₁ : finset α) :
s₁ \ s₁ = ∅

source
theorem finset.sdiff_inter_distrib_right {α : Type u_1} [decidable_eq α] (s₁ s₂ s₃ : finset α) :
s₁ \ (s₂ ∩ s₃) = s₁ \ s₂ ∪ s₁ \ s₃

source
@[simp]
theorem finset.sdiff_inter_self_left {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ \ (s₁ ∩ s₂) = s₁ \ s₂

source
@[simp]
theorem finset.sdiff_inter_self_right {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ \ (s₂ ∩ s₁) = s₁ \ s₂

source
@[simp]
theorem finset.sdiff_empty {α : Type u_1} [decidable_eq α] {s₁ : finset α} :
s₁ \ ∅ = s₁

source
theorem finset.sdiff_subset_sdiff {α : Type u_1} [decidable_eq α] {s₁ s₂ t₁ t₂ : finset α} (h₁ : t₁ ⊆ t₂) (h₂ : s₂ ⊆ s₁) :
t₁ \ s₁ ⊆ t₂ \ s₂

source
theorem finset.sdiff_subset_self {α : Type u_1} [decidable_eq α] {s₁ s₂ : finset α} :
s₁ \ s₂ ⊆ s₁

source
@[simp]
theorem finset.coe_sdiff {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
↑(s₁ \ s₂) = ↑s₁ \ ↑s₂

source
@[simp]
theorem finset.union_sdiff_self_eq_union {α : Type u_1} [decidable_eq α] {s t : finset α} :
s ∪ t \ s = s ∪ t

source
@[simp]
theorem finset.sdiff_union_self_eq_union {α : Type u_1} [decidable_eq α] {s t : finset α} :
s \ t ∪ t = s ∪ t

source
theorem finset.union_sdiff_symm {α : Type u_1} [decidable_eq α] {s t : finset α} :
s ∪ t \ s = t ∪ s \ t

source
theorem finset.sdiff_union_inter {α : Type u_1} [decidable_eq α] (s t : finset α) :
s \ t ∪ s ∩ t = s

source
@[simp]
theorem finset.sdiff_idem {α : Type u_1} [decidable_eq α] (s t : finset α) :
s \ t \ t = s \ t

source
theorem finset.sdiff_eq_empty_iff_subset {α : Type u_1} [decidable_eq α] {s t : finset α} :
s \ t = ∅ ↔ s ⊆ t

source
@[simp]
theorem finset.empty_sdiff {α : Type u_1} [decidable_eq α] (s : finset α) :
∅ \ s = ∅

source
theorem finset.insert_sdiff_of_not_mem {α : Type u_1} [decidable_eq α] (s : finset α) {t : finset α} {x : α} (h : x ∉ t) :
insert x s \ t = insert x (s \ t)

source
theorem finset.insert_sdiff_of_mem {α : Type u_1} [decidable_eq α] (s : finset α) {t : finset α} {x : α} (h : x ∈ t) :
insert x s \ t = s \ t

source
@[simp]
theorem finset.insert_sdiff_insert {α : Type u_1} [decidable_eq α] (s t : finset α) (x : α) :
insert x s \ insert x t = s \ insert x t

source
theorem finset.sdiff_insert_of_not_mem {α : Type u_1} [decidable_eq α] {s : finset α} {x : α} (h : x ∉ s) (t : finset α) :
s \ insert x t = s \ t

source
@[simp]
theorem finset.sdiff_subset {α : Type u_1} [decidable_eq α] (s t : finset α) :
s \ t ⊆ s

source
theorem finset.union_sdiff_distrib {α : Type u_1} [decidable_eq α] (s₁ s₂ t : finset α) :
(s₁ ∪ s₂) \ t = s₁ \ t ∪ s₂ \ t

source
theorem finset.sdiff_union_distrib {α : Type u_1} [decidable_eq α] (s t₁ t₂ : finset α) :
s \ (t₁ ∪ t₂) = s \ t₁ ∩ (s \ t₂)

source
theorem finset.union_sdiff_self {α : Type u_1} [decidable_eq α] (s t : finset α) :
(s ∪ t) \ t = s \ t

source
theorem finset.sdiff_singleton_eq_erase {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
s \ {a} = s.erase a

source
theorem finset.sdiff_sdiff_self_left {α : Type u_1} [decidable_eq α] (s t : finset α) :
s \ (s \ t) = s ∩ t

source
theorem finset.inter_eq_inter_of_sdiff_eq_sdiff {α : Type u_1} [decidable_eq α] {s t₁ t₂ : finset α} :
s \ t₁ = s \ t₂ → s ∩ t₁ = s ∩ t₂

attach

source
def finset.attach {α : Type u_1} (s : finset α) :
finset {x // x ∈ s}

attach s takes the elements of s and forms a new set of elements of the subtype {x // x ∈ s}.

Equations
source
theorem finset.sizeof_lt_sizeof_of_mem {α : Type u_1} [has_sizeof α] {x : α} {s : finset α} (hx : x ∈ s) :
sizeof x < sizeof s

source
@[simp]
theorem finset.attach_val {α : Type u_1} (s : finset α) :
s.attach.val = s.val.attach

source
@[simp]
theorem finset.mem_attach {α : Type u_1} (s : finset α) (x : {x // x ∈ s}) :
x ∈ s.attach

source
@[simp]
theorem finset.attach_empty {α : Type u_1} :
∅.attach = ∅

piecewise

source
def finset.piecewise {α : Type u_1} {δ : α → Sort u_2} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] (i : α) :
δ i

s.piecewise f g is the function equal to f on the finset s, and to g on its complement.

Equations
source
@[simp]
theorem finset.piecewise_insert_self {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [decidable_eq α] {j : α} [Π (i : α), decidable (i ∈ insert j s)] :
(insert j s).piecewise f g j = f j

source
@[simp]
theorem finset.piecewise_empty {α : Type u_1} {δ : α → Sort u_4} (f g : Π (i : α), δ i) [Π (i : α), decidable (i ∈ ∅)] :
∅.piecewise f g = g

source
theorem finset.piecewise_coe {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] [Π (j : α), decidable (j ∈ ↑s)] :
↑s.piecewise f g = s.piecewise f g

source
@[simp]
theorem finset.piecewise_eq_of_mem {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] {i : α} (hi : i ∈ s) :
s.piecewise f g i = f i

source
@[simp]
theorem finset.piecewise_eq_of_not_mem {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] {i : α} (hi : i ∉ s) :
s.piecewise f g i = g i

source
theorem finset.piecewise_congr {α : Type u_1} {δ : α → Sort u_4} (s : finset α) [Π (j : α), decidable (j ∈ s)] {f f' g g' : Π (i : α), δ i} (hf : ∀ (i : α), i ∈ s → f i = f' i) (hg : ∀ (i : α), i ∉ s → g i = g' i) :
s.piecewise f g = s.piecewise f' g'

source
@[simp]
theorem finset.piecewise_insert_of_ne {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] [decidable_eq α] {i j : α} [Π (i : α), decidable (i ∈ insert j s)] (h : i ≠ j) :
(insert j s).piecewise f g i = s.piecewise f g i

source
theorem finset.piecewise_insert {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] [decidable_eq α] (j : α) [Π (i : α), decidable (i ∈ insert j s)] :
(insert j s).piecewise f g = function.update (s.piecewise f g) j (f j)

source
theorem finset.piecewise_cases {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] {i : α} (p : δ i → Prop) (hf : p (f i)) (hg : p (g i)) :
p (s.piecewise f g i)

source
theorem finset.piecewise_mem_set_pi {α : Type u_1} (s : finset α) [Π (j : α), decidable (j ∈ s)] {δ : α → Type u_2} {t : set α} {t' : Π (i : α), set (δ i)} {f g : Π (i : α), δ i} (hf : f ∈ t.pi t') (hg : g ∈ t.pi t') :
s.piecewise f g ∈ t.pi t'

source
theorem finset.piecewise_singleton {α : Type u_1} {δ : α → Sort u_4} (f g : Π (i : α), δ i) [decidable_eq α] (i : α) :
{i}.piecewise f g = function.update g i (f i)

source
theorem finset.piecewise_piecewise_of_subset_left {α : Type u_1} {δ : α → Sort u_4} {s t : finset α} [Π (i : α), decidable (i ∈ s)] [Π (i : α), decidable (i ∈ t)] (h : s ⊆ t) (f₁ f₂ g : Π (a : α), δ a) :
s.piecewise (t.piecewise f₁ f₂) g = s.piecewise f₁ g

source
@[simp]
theorem finset.piecewise_idem_left {α : Type u_1} {δ : α → Sort u_4} (s : finset α) [Π (j : α), decidable (j ∈ s)] (f₁ f₂ g : Π (a : α), δ a) :
s.piecewise (s.piecewise f₁ f₂) g = s.piecewise f₁ g

source
theorem finset.piecewise_piecewise_of_subset_right {α : Type u_1} {δ : α → Sort u_4} {s t : finset α} [Π (i : α), decidable (i ∈ s)] [Π (i : α), decidable (i ∈ t)] (h : t ⊆ s) (f g₁ g₂ : Π (a : α), δ a) :
s.piecewise f (t.piecewise g₁ g₂) = s.piecewise f g₂

source
@[simp]
theorem finset.piecewise_idem_right {α : Type u_1} {δ : α → Sort u_4} (s : finset α) [Π (j : α), decidable (j ∈ s)] (f g₁ g₂ : Π (a : α), δ a) :
s.piecewise f (s.piecewise g₁ g₂) = s.piecewise f g₂

source
theorem finset.update_eq_piecewise {α : Type u_1} {β : Type u_2} [decidable_eq α] (f : α → β) (i : α) (v : β) :
function.update f i v = {i}.piecewise (λ (j : α), v) f

source
theorem finset.update_piecewise {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] [decidable_eq α] (i : α) (v : δ i) :
function.update (s.piecewise f g) i v = s.piecewise (function.update f i v) (function.update g i v)

source
theorem finset.update_piecewise_of_mem {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] [decidable_eq α] {i : α} (hi : i ∈ s) (v : δ i) :
function.update (s.piecewise f g) i v = s.piecewise (function.update f i v) g

source
theorem finset.update_piecewise_of_not_mem {α : Type u_1} {δ : α → Sort u_4} (s : finset α) (f g : Π (i : α), δ i) [Π (j : α), decidable (j ∈ s)] [decidable_eq α] {i : α} (hi : i ∉ s) (v : δ i) :
function.update (s.piecewise f g) i v = s.piecewise f (function.update g i v)

source
theorem finset.piecewise_le_of_le_of_le {α : Type u_1} (s : finset α) [Π (j : α), decidable (j ∈ s)] {δ : α → Type u_2} [Π (i : α), preorder (δ i)] {f g h : Π (i : α), δ i} (Hf : f ≤ h) (Hg : g ≤ h) :
s.piecewise f g ≤ h

source
theorem finset.le_piecewise_of_le_of_le {α : Type u_1} (s : finset α) [Π (j : α), decidable (j ∈ s)] {δ : α → Type u_2} [Π (i : α), preorder (δ i)] {f g h : Π (i : α), δ i} (Hf : h ≤ f) (Hg : h ≤ g) :
h ≤ s.piecewise f g

source
theorem finset.piecewise_le_piecewise' {α : Type u_1} (s : finset α) [Π (j : α), decidable (j ∈ s)] {δ : α → Type u_2} [Π (i : α), preorder (δ i)] {f g f' g' : Π (i : α), δ i} (Hf : ∀ (x : α), x ∈ s → f x ≤ f' x) (Hg : ∀ (x : α), x ∉ s → g x ≤ g' x) :
s.piecewise f g ≤ s.piecewise f' g'

source
theorem finset.piecewise_le_piecewise {α : Type u_1} (s : finset α) [Π (j : α), decidable (j ∈ s)] {δ : α → Type u_2} [Π (i : α), preorder (δ i)] {f g f' g' : Π (i : α), δ i} (Hf : f ≤ f') (Hg : g ≤ g') :
s.piecewise f g ≤ s.piecewise f' g'

source
theorem finset.piecewise_mem_Icc_of_mem_of_mem {α : Type u_1} (s : finset α) [Π (j : α), decidable (j ∈ s)] {δ : α → Type u_2} [Π (i : α), preorder (δ i)] {f f₁ g g₁ : Π (i : α), δ i} (hf : f ∈ set.Icc f₁ g₁) (hg : g ∈ set.Icc f₁ g₁) :
s.piecewise f g ∈ set.Icc f₁ g₁

source
theorem finset.piecewise_mem_Icc {α : Type u_1} (s : finset α) [Π (j : α), decidable (j ∈ s)] {δ : α → Type u_2} [Π (i : α), preorder (δ i)] {f g : Π (i : α), δ i} (h : f ≤ g) :
s.piecewise f g ∈ set.Icc f g

source
theorem finset.piecewise_mem_Icc' {α : Type u_1} (s : finset α) [Π (j : α), decidable (j ∈ s)] {δ : α → Type u_2} [Π (i : α), preorder (δ i)] {f g : Π (i : α), δ i} (h : g ≤ f) :
s.piecewise f g ∈ set.Icc g f

source
@[instance]
def finset.decidable_dforall_finset {α : Type u_1} {s : finset α} {p : Π (a : α), a ∈ s → Prop} [hp : Π (a : α) (h : a ∈ s), decidable (p a h)] :
decidable (∀ (a : α) (h : a ∈ s), p a h)

Equations
source
@[instance]
def finset.decidable_eq_pi_finset {α : Type u_1} {s : finset α} {β : α → Type u_2} [h : Π (a : α), decidable_eq (β a)] :
decidable_eq (Π (a : α), a ∈ s → β a)

decidable equality for functions whose domain is bounded by finsets

Equations
source
@[instance]
def finset.decidable_dexists_finset {α : Type u_1} {s : finset α} {p : Π (a : α), a ∈ s → Prop} [hp : Π (a : α) (h : a ∈ s), decidable (p a h)] :
decidable (∃ (a : α) (h : a ∈ s), p a h)

Equations

filter

source
def finset.filter {α : Type u_1} (p : α → Prop) [decidable_pred p] (s : finset α) :
finset α

filter p s is the set of elements of s that satisfy p.

Equations
source
@[simp]
theorem finset.filter_val {α : Type u_1} (p : α → Prop) [decidable_pred p] (s : finset α) :
(finset.filter p s).val = multiset.filter p s.val

source
@[simp]
theorem finset.filter_subset {α : Type u_1} (p : α → Prop) [decidable_pred p] (s : finset α) :
finset.filter p s ⊆ s

source
@[simp]
theorem finset.mem_filter {α : Type u_1} {p : α → Prop} [decidable_pred p] {s : finset α} {a : α} :
a ∈ finset.filter p s ↔ a ∈ s ∧ p a

source
theorem finset.filter_ssubset {α : Type u_1} {p : α → Prop} [decidable_pred p] {s : finset α} :
finset.filter p s ⊂ s ↔ ∃ (x : α) (H : x ∈ s), ¬p x

source
theorem finset.filter_filter {α : Type u_1} (p q : α → Prop) [decidable_pred p] [decidable_pred q] (s : finset α) :
finset.filter q (finset.filter p s) = finset.filter (λ (a : α), p a ∧ q a) s

source
theorem finset.filter_true {α : Type u_1} {s : finset α} [h : decidable_pred (λ (_x : α), true)] :
finset.filter (λ (_x : α), true) s = s

source
@[simp]
theorem finset.filter_false {α : Type u_1} {h : decidable_pred (λ (a : α), false)} (s : finset α) :
finset.filter (λ (a : α), false) s = ∅

source
@[simp]
theorem finset.filter_true_of_mem {α : Type u_1} {p : α → Prop} [decidable_pred p] {s : finset α} (h : ∀ (x : α), x ∈ s → p x) :
finset.filter p s = s

If all elements of a finset satisfy the predicate p, s.filter p is s.

source
theorem finset.filter_false_of_mem {α : Type u_1} {p : α → Prop} [decidable_pred p] {s : finset α} (h : ∀ (x : α), x ∈ s → ¬p x) :
finset.filter p s = ∅

If all elements of a finset fail to satisfy the predicate p, s.filter p is ∅.

source
theorem finset.filter_congr {α : Type u_1} {p q : α → Prop} [decidable_pred p] [decidable_pred q] {s : finset α} (H : ∀ (x : α), x ∈ s → (p x ↔ q x)) :
finset.filter p s = finset.filter q s

source
theorem finset.filter_empty {α : Type u_1} (p : α → Prop) [decidable_pred p] :
finset.filter p ∅ = ∅

source
theorem finset.filter_subset_filter {α : Type u_1} (p : α → Prop) [decidable_pred p] {s t : finset α} (h : s ⊆ t) :
finset.filter p s ⊆ finset.filter p t

source
@[simp]
theorem finset.coe_filter {α : Type u_1} (p : α → Prop) [decidable_pred p] (s : finset α) :
↑(finset.filter p s) = {x ∈ ↑s | p x}

source
theorem finset.filter_singleton {α : Type u_1} (p : α → Prop) [decidable_pred p] (a : α) :
finset.filter p {a} = ite (p a) {a} ∅

source
theorem finset.filter_union {α : Type u_1} (p : α → Prop) [decidable_pred p] [decidable_eq α] (s₁ s₂ : finset α) :
finset.filter p (s₁ ∪ s₂) = finset.filter p s₁ ∪ finset.filter p s₂

source
theorem finset.filter_union_right {α : Type u_1} (p q : α → Prop) [decidable_pred p] [decidable_pred q] [decidable_eq α] (s : finset α) :
finset.filter p s ∪ finset.filter q s = finset.filter (λ (x : α), p x ∨ q x) s

source
theorem finset.filter_mem_eq_inter {α : Type u_1} [decidable_eq α] {s t : finset α} [Π (i : α), decidable (i ∈ t)] :
finset.filter (λ (i : α), i ∈ t) s = s ∩ t

source
theorem finset.filter_inter {α : Type u_1} (p : α → Prop) [decidable_pred p] [decidable_eq α] (s t : finset α) :
finset.filter p s ∩ t = finset.filter p (s ∩ t)

source
theorem finset.inter_filter {α : Type u_1} (p : α → Prop) [decidable_pred p] [decidable_eq α] (s t : finset α) :
s ∩ finset.filter p t = finset.filter p (s ∩ t)

source
theorem finset.filter_insert {α : Type u_1} (p : α → Prop) [decidable_pred p] [decidable_eq α] (a : α) (s : finset α) :
finset.filter p (insert a s) = ite (p a) (insert a (finset.filter p s)) (finset.filter p s)

source
theorem finset.filter_or {α : Type u_1} (p q : α → Prop) [decidable_pred p] [decidable_pred q] [decidable_eq α] [decidable_pred (λ (a : α), p a ∨ q a)] (s : finset α) :
finset.filter (λ (a : α), p a ∨ q a) s = finset.filter p s ∪ finset.filter q s

source
theorem finset.filter_and {α : Type u_1} (p q : α → Prop) [decidable_pred p] [decidable_pred q] [decidable_eq α] [decidable_pred (λ (a : α), p a ∧ q a)] (s : finset α) :
finset.filter (λ (a : α), p a ∧ q a) s = finset.filter p s ∩ finset.filter q s

source
theorem finset.filter_not {α : Type u_1} (p : α → Prop) [decidable_pred p] [decidable_eq α] [decidable_pred (λ (a : α), ¬p a)] (s : finset α) :
finset.filter (λ (a : α), ¬p a) s = s \ finset.filter p s

source
theorem finset.sdiff_eq_filter {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ \ s₂ = finset.filter (λ (_x : α), _x ∉ s₂) s₁

source
theorem finset.sdiff_eq_self {α : Type u_1} [decidable_eq α] (s₁ s₂ : finset α) :
s₁ \ s₂ = s₁ ↔ s₁ ∩ s₂ ⊆ ∅

source
theorem finset.filter_union_filter_neg_eq {α : Type u_1} (p : α → Prop) [decidable_pred p] [decidable_eq α] [decidable_pred (λ (a : α), ¬p a)] (s : finset α) :
finset.filter p s ∪ finset.filter (λ (a : α), ¬p a) s = s

source
theorem finset.filter_inter_filter_neg_eq {α : Type u_1} (p : α → Prop) [decidable_pred p] [decidable_eq α] (s : finset α) :
finset.filter p s ∩ finset.filter (λ (a : α), ¬p a) s = ∅

source
theorem finset.subset_union_elim {α : Type u_1} [decidable_eq α] {s : finset α} {t₁ t₂ : set α} (h : ↑s ⊆ t₁ ∪ t₂) :
∃ (s₁ s₂ : finset α), s₁ ∪ s₂ = s ∧ ↑s₁ ⊆ t₁ ∧ ↑s₂ ⊆ t₂ \ t₁

source
@[simp]
theorem finset.filter_congr_decidable {α : Type u_1} (s : finset α) (p : α → Prop) (h : decidable_pred p) [decidable_pred p] :
finset.filter p s = finset.filter p s

source
@[instance]
def finset.has_sep {α : Type u_1} :
has_sep α (finset α)

The following instance allows us to write { x ∈ s | p x } for finset.filter s p. Since the former notation requires us to define this for all propositions p, and finset.filter only works for decidable propositions, the notation { x ∈ s | p x } is only compatible with classical logic because it uses classical.prop_decidable. We don't want to redo all lemmas of finset.filter for has_sep.sep, so we make sure that simp unfolds the notation { x ∈ s | p x } to finset.filter s p. If p happens to be decidable, the simp-lemma filter_congr_decidable will make sure that finset.filter uses the right instance for decidability.

Equations
source
@[simp]
theorem finset.sep_def {α : Type u_1} (s : finset α) (p : α → Prop) :
{x ∈ s | p x} = finset.filter p s

source
theorem finset.filter_eq {β : Type u_2} [decidable_eq β] (s : finset β) (b : β) :
finset.filter (eq b) s = ite (b ∈ s) {b} ∅

After filtering out everything that does not equal a given value, at most that value remains.

This is equivalent to filter_eq' with the equality the other way.

source
theorem finset.filter_eq' {β : Type u_2} [decidable_eq β] (s : finset β) (b : β) :
finset.filter (λ (a : β), a = b) s = ite (b ∈ s) {b} ∅

After filtering out everything that does not equal a given value, at most that value remains.

This is equivalent to filter_eq with the equality the other way.

source
theorem finset.filter_ne {β : Type u_2} [decidable_eq β] (s : finset β) (b : β) :
finset.filter (λ (a : β), b ≠ a) s = s.erase b

source
theorem finset.filter_ne' {β : Type u_2} [decidable_eq β] (s : finset β) (b : β) :
finset.filter (λ (a : β), a ≠ b) s = s.erase b

range

source
def finset.range (n : ℕ) :
finset ℕ

range n is the set of natural numbers less than n.

Equations
source
@[simp]
theorem finset.range_coe (n : ℕ) :
(finset.range n).val = multiset.range n

source
@[simp]
theorem finset.mem_range {n m : ℕ} :
m ∈ finset.range n ↔ m < n

source
@[simp]
theorem finset.range_zero  :
finset.range 0 = ∅

source
@[simp]
theorem finset.range_one  :
finset.range 1 = {0}

source
theorem finset.range_succ {n : ℕ} :
finset.range n.succ = insert n (finset.range n)

source
theorem finset.range_add_one {n : ℕ} :
finset.range (n + 1) = insert n (finset.range n)

source
@[simp]
theorem finset.not_mem_range_self {n : ℕ} :
n ∉ finset.range n

source
@[simp]
theorem finset.self_mem_range_succ (n : ℕ) :
n ∈ finset.range (n + 1)

source
@[simp]
theorem finset.range_subset {n m : ℕ} :
finset.range n ⊆ finset.range m ↔ n ≤ m

source
theorem finset.range_mono  :
monotone finset.range

source
theorem finset.mem_range_succ_iff {a b : ℕ} :
a ∈ finset.range b.succ ↔ a ≤ b

source
theorem finset.exists_mem_empty_iff {α : Type u_1} (p : α → Prop) :
(∃ (x : α), x ∈ ∅ ∧ p x) ↔ false

source
theorem finset.exists_mem_insert {α : Type u_1} [d : decidable_eq α] (a : α) (s : finset α) (p : α → Prop) :
(∃ (x : α), x ∈ insert a s ∧ p x) ↔ p a ∨ ∃ (x : α), x ∈ s ∧ p x

source
theorem finset.forall_mem_empty_iff {α : Type u_1} (p : α → Prop) :
(∀ (x : α), x ∈ ∅ → p x) ↔ true

source
theorem finset.forall_mem_insert {α : Type u_1} [d : decidable_eq α] (a : α) (s : finset α) (p : α → Prop) :
(∀ (x : α), x ∈ insert a s → p x) ↔ p a ∧ ∀ (x : α), x ∈ s → p x

source
def not_mem_range_equiv (k : ℕ) :
{n // n ∉ multiset.range k} ≃ ℕ

Equivalence between the set of natural numbers which are ≥ k and ℕ, given by n → n - k.

Equations
source
@[simp]
theorem coe_not_mem_range_equiv (k : ℕ) :
⇑(not_mem_range_equiv k) = λ (i : {n // n ∉ multiset.range k}), ↑i - k

source
@[simp]
theorem coe_not_mem_range_equiv_symm (k : ℕ) :
⇑((not_mem_range_equiv k).symm) = λ (j : ℕ), ⟨j + k, _⟩

source
def option.to_finset {α : Type u_1} (o : option α) :
finset α

Construct an empty or singleton finset from an option

Equations
  • o.to_finset = option.to_finset._match_1 o
  • option.to_finset._match_1 (some a) = {a}
  • option.to_finset._match_1 none = ∅
source
@[simp]
theorem option.to_finset_none {α : Type u_1} :
none.to_finset = ∅

source
@[simp]
theorem option.to_finset_some {α : Type u_1} {a : α} :
(some a).to_finset = {a}

source
@[simp]
theorem option.mem_to_finset {α : Type u_1} {a : α} {o : option α} :
a ∈ o.to_finset ↔ a ∈ o

erase_dup on list and multiset

source
def multiset.to_finset {α : Type u_1} [decidable_eq α] (s : multiset α) :
finset α

to_finset s removes duplicates from the multiset s to produce a finset.

Equations
source
@[simp]
theorem multiset.to_finset_val {α : Type u_1} [decidable_eq α] (s : multiset α) :
s.to_finset.val = s.erase_dup

source
theorem multiset.to_finset_eq {α : Type u_1} [decidable_eq α] {s : multiset α} (n : s.nodup) :
{val := s, nodup := n} = s.to_finset

source
@[simp]
theorem multiset.mem_to_finset {α : Type u_1} [decidable_eq α] {a : α} {s : multiset α} :
a ∈ s.to_finset ↔ a ∈ s

source
@[simp]
theorem multiset.to_finset_zero {α : Type u_1} [decidable_eq α] :
0.to_finset = ∅

source
@[simp]
theorem multiset.to_finset_cons {α : Type u_1} [decidable_eq α] (a : α) (s : multiset α) :
(a ::ₘ s).to_finset = insert a s.to_finset

source
@[simp]
theorem multiset.to_finset_add {α : Type u_1} [decidable_eq α] (s t : multiset α) :
(s + t).to_finset = s.to_finset ∪ t.to_finset

source
@[simp]
theorem multiset.to_finset_nsmul {α : Type u_1} [decidable_eq α] (s : multiset α) (n : ℕ) (hn : n ≠ 0) :
(n •ℕ s).to_finset = s.to_finset

source
@[simp]
theorem multiset.to_finset_inter {α : Type u_1} [decidable_eq α] (s t : multiset α) :
(s ∩ t).to_finset = s.to_finset ∩ t.to_finset

source
@[simp]
theorem multiset.to_finset_union {α : Type u_1} [decidable_eq α] (s t : multiset α) :
(s ∪ t).to_finset = s.to_finset ∪ t.to_finset

source
theorem multiset.to_finset_eq_empty {α : Type u_1} [decidable_eq α] {m : multiset α} :
m.to_finset = ∅ ↔ m = 0

source
@[simp]
theorem multiset.to_finset_subset {α : Type u_1} [decidable_eq α] (m1 m2 : multiset α) :
m1.to_finset ⊆ m2.to_finset ↔ m1 ⊆ m2

source
@[simp]
theorem finset.val_to_finset {α : Type u_1} [decidable_eq α] (s : finset α) :
s.val.to_finset = s

source
def list.to_finset {α : Type u_1} [decidable_eq α] (l : list α) :
finset α

to_finset l removes duplicates from the list l to produce a finset.

Equations
source
@[simp]
theorem list.to_finset_val {α : Type u_1} [decidable_eq α] (l : list α) :
l.to_finset.val = ↑(l.erase_dup)

source
theorem list.to_finset_eq {α : Type u_1} [decidable_eq α] {l : list α} (n : l.nodup) :
{val := ↑l, nodup := n} = l.to_finset

source
@[simp]
theorem list.mem_to_finset {α : Type u_1} [decidable_eq α] {a : α} {l : list α} :
a ∈ l.to_finset ↔ a ∈ l

source
@[simp]
theorem list.to_finset_nil {α : Type u_1} [decidable_eq α] :
list.nil.to_finset = ∅

source
@[simp]
theorem list.to_finset_cons {α : Type u_1} [decidable_eq α] {a : α} {l : list α} :
(a :: l).to_finset = insert a l.to_finset

source
theorem list.to_finset_surj_on {α : Type u_1} [decidable_eq α] :
set.surj_on list.to_finset {l : list α | l.nodup} set.univ

source
theorem list.to_finset_surjective {α : Type u_1} [decidable_eq α] :
function.surjective list.to_finset

map

source
def finset.map {α : Type u_1} {β : Type u_2} (f : α ↪ β) (s : finset α) :
finset β

When f is an embedding of α in β and s is a finset in α, then s.map f is the image finset in β. The embedding condition guarantees that there are no duplicates in the image.

Equations
source
@[simp]
theorem finset.map_val {α : Type u_1} {β : Type u_2} (f : α ↪ β) (s : finset α) :
(finset.map f s).val = multiset.map ⇑f s.val

source
@[simp]
theorem finset.map_empty {α : Type u_1} {β : Type u_2} (f : α ↪ β) :
finset.map f ∅ = ∅

source
@[simp]
theorem finset.mem_map {α : Type u_1} {β : Type u_2} {f : α ↪ β} {s : finset α} {b : β} :
b ∈ finset.map f s ↔ ∃ (a : α) (H : a ∈ s), ⇑f a = b

source
theorem finset.mem_map' {α : Type u_1} {β : Type u_2} (f : α ↪ β) {a : α} {s : finset α} :
⇑f a ∈ finset.map f s ↔ a ∈ s

source
theorem finset.mem_map_of_mem {α : Type u_1} {β : Type u_2} (f : α ↪ β) {a : α} {s : finset α} :
a ∈ s → ⇑f a ∈ finset.map f s

source
@[simp]
theorem finset.coe_map {α : Type u_1} {β : Type u_2} (f : α ↪ β) (s : finset α) :
↑(finset.map f s) = ⇑f '' ↑s

source
theorem finset.coe_map_subset_range {α : Type u_1} {β : Type u_2} (f : α ↪ β) (s : finset α) :
↑(finset.map f s) ⊆ set.range ⇑f

source
theorem finset.map_to_finset {α : Type u_1} {β : Type u_2} {f : α ↪ β} [decidable_eq α] [decidable_eq β] {s : multiset α} :
finset.map f s.to_finset = (multiset.map ⇑f s).to_finset

source
@[simp]
theorem finset.map_refl {α : Type u_1} {s : finset α} :
finset.map (function.embedding.refl α) s = s

source
theorem finset.map_map {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : α ↪ β} {s : finset α} {g : β ↪ γ} :
finset.map g (finset.map f s) = finset.map (f.trans g) s

source
theorem finset.map_subset_map {α : Type u_1} {β : Type u_2} {f : α ↪ β} {s₁ s₂ : finset α} :
finset.map f s₁ ⊆ finset.map f s₂ ↔ s₁ ⊆ s₂

source
theorem finset.map_inj {α : Type u_1} {β : Type u_2} {f : α ↪ β} {s₁ s₂ : finset α} :
finset.map f s₁ = finset.map f s₂ ↔ s₁ = s₂

source
def finset.map_embedding {α : Type u_1} {β : Type u_2} (f : α ↪ β) :
finset α ↪ finset β

Associate to an embedding f from α to β the embedding that maps a finset to its image under f.

Equations
source
@[simp]
theorem finset.map_embedding_apply {α : Type u_1} {β : Type u_2} {f : α ↪ β} {s : finset α} :
⇑(finset.map_embedding f) s = finset.map f s

source
theorem finset.map_filter {α : Type u_1} {β : Type u_2} {f : α ↪ β} {s : finset α} {p : β → Prop} [decidable_pred p] :
finset.filter p (finset.map f s) = finset.map f (finset.filter (p ∘ ⇑f) s)

source
theorem finset.map_union {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] {f : α ↪ β} (s₁ s₂ : finset α) :
finset.map f (s₁ ∪ s₂) = finset.map f s₁ ∪ finset.map f s₂

source
theorem finset.map_inter {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] {f : α ↪ β} (s₁ s₂ : finset α) :
finset.map f (s₁ ∩ s₂) = finset.map f s₁ ∩ finset.map f s₂

source
@[simp]
theorem finset.map_singleton {α : Type u_1} {β : Type u_2} (f : α ↪ β) (a : α) :
finset.map f {a} = {⇑f a}

source
@[simp]
theorem finset.map_insert {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] (f : α ↪ β) (a : α) (s : finset α) :
finset.map f (insert a s) = insert (⇑f a) (finset.map f s)

source
@[simp]
theorem finset.map_eq_empty {α : Type u_1} {β : Type u_2} {f : α ↪ β} {s : finset α} :
finset.map f s = ∅ ↔ s = ∅

source
theorem finset.attach_map_val {α : Type u_1} {s : finset α} :
finset.map (function.embedding.subtype (λ (x : α), x ∈ s)) s.attach = s

source
theorem finset.nonempty.map {α : Type u_1} {β : Type u_2} {s : finset α} (h : s.nonempty) (f : α ↪ β) :
(finset.map f s).nonempty

source
theorem finset.range_add_one' (n : ℕ) :
finset.range (n + 1) = insert 0 (finset.map {to_fun := λ (i : ℕ), i + 1, inj' := _} (finset.range n))

image

source
def finset.image {α : Type u_1} {β : Type u_2} [decidable_eq β] (f : α → β) (s : finset α) :
finset β

image f s is the forward image of s under f.

Equations
source
@[simp]
theorem finset.image_val {α : Type u_1} {β : Type u_2} [decidable_eq β] (f : α → β) (s : finset α) :
(finset.image f s).val = (multiset.map f s.val).erase_dup

source
@[simp]
theorem finset.image_empty {α : Type u_1} {β : Type u_2} [decidable_eq β] (f : α → β) :
finset.image f ∅ = ∅

source
@[simp]
theorem finset.mem_image {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} {s : finset α} {b : β} :
b ∈ finset.image f s ↔ ∃ (a : α) (H : a ∈ s), f a = b

source
theorem finset.mem_image_of_mem {α : Type u_1} {β : Type u_2} [decidable_eq β] (f : α → β) {a : α} {s : finset α} (h : a ∈ s) :
f a ∈ finset.image f s

source
theorem finset.filter_mem_image_eq_image {α : Type u_1} {β : Type u_2} [decidable_eq β] (f : α → β) (s : finset α) (t : finset β) (h : ∀ (x : α), x ∈ s → f x ∈ t) :
finset.filter (λ (y : β), y ∈ finset.image f s) t = finset.image f s

source
theorem finset.fiber_nonempty_iff_mem_image {α : Type u_1} {β : Type u_2} [decidable_eq β] (f : α → β) (s : finset α) (y : β) :
(finset.filter (λ (x : α), f x = y) s).nonempty ↔ y ∈ finset.image f s

source
@[simp]
theorem finset.coe_image {α : Type u_1} {β : Type u_2} [decidable_eq β] {s : finset α} {f : α → β} :
↑(finset.image f s) = f '' ↑s

source
theorem finset.nonempty.image {α : Type u_1} {β : Type u_2} [decidable_eq β] {s : finset α} (h : s.nonempty) (f : α → β) :
(finset.image f s).nonempty

source
theorem finset.image_to_finset {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} [decidable_eq α] {s : multiset α} :
finset.image f s.to_finset = (multiset.map f s).to_finset

source
theorem finset.image_val_of_inj_on {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} {s : finset α} (H : ∀ (x : α), x ∈ s → ∀ (y : α), y ∈ s → f x = f y → x = y) :
(finset.image f s).val = multiset.map f s.val

source
@[simp]
theorem finset.image_id {α : Type u_1} {s : finset α} [decidable_eq α] :
finset.image id s = s

source
theorem finset.image_image {α : Type u_1} {β : Type u_2} {γ : Type u_3} [decidable_eq β] {f : α → β} {s : finset α} [decidable_eq γ] {g : β → γ} :
finset.image g (finset.image f s) = finset.image (g ∘ f) s

source
theorem finset.image_subset_image {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} {s₁ s₂ : finset α} (h : s₁ ⊆ s₂) :
finset.image f s₁ ⊆ finset.image f s₂

source
theorem finset.image_subset_iff {α : Type u_1} {β : Type u_2} [decidable_eq β] {s : finset α} {t : finset β} {f : α → β} :
finset.image f s ⊆ t ↔ ∀ (x : α), x ∈ s → f x ∈ t

source
theorem finset.image_mono {α : Type u_1} {β : Type u_2} [decidable_eq β] (f : α → β) :
monotone (finset.image f)

source
theorem finset.coe_image_subset_range {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} {s : finset α} :
↑(finset.image f s) ⊆ set.range f

source
theorem finset.image_filter {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} {s : finset α} {p : β → Prop} [decidable_pred p] :
finset.filter p (finset.image f s) = finset.image f (finset.filter (p ∘ f) s)

source
theorem finset.image_union {α : Type u_1} {β : Type u_2} [decidable_eq β] [decidable_eq α] {f : α → β} (s₁ s₂ : finset α) :
finset.image f (s₁ ∪ s₂) = finset.image f s₁ ∪ finset.image f s₂

source
theorem finset.image_inter {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} [decidable_eq α] (s₁ s₂ : finset α) (hf : ∀ (x y : α), f x = f y → x = y) :
finset.image f (s₁ ∩ s₂) = finset.image f s₁ ∩ finset.image f s₂

source
@[simp]
theorem finset.image_singleton {α : Type u_1} {β : Type u_2} [decidable_eq β] (f : α → β) (a : α) :
finset.image f {a} = {f a}

source
@[simp]
theorem finset.image_insert {α : Type u_1} {β : Type u_2} [decidable_eq β] [decidable_eq α] (f : α → β) (a : α) (s : finset α) :
finset.image f (insert a s) = insert (f a) (finset.image f s)

source
@[simp]
theorem finset.image_eq_empty {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} {s : finset α} :
finset.image f s = ∅ ↔ s = ∅

source
theorem finset.attach_image_val {α : Type u_1} [decidable_eq α] {s : finset α} :
finset.image subtype.val s.attach = s

source
@[simp]
theorem finset.attach_insert {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} :
(insert a s).attach = insert ⟨a, _⟩ (finset.image (λ (x : {x // x ∈ s}), ⟨x.val, _⟩) s.attach)

source
theorem finset.map_eq_image {α : Type u_1} {β : Type u_2} [decidable_eq β] (f : α ↪ β) (s : finset α) :
finset.map f s = finset.image ⇑f s

source
theorem finset.image_const {α : Type u_1} {β : Type u_2} [decidable_eq β] {s : finset α} (h : s.nonempty) (b : β) :
finset.image (λ (a : α), b) s = {b}

source
@[instance]
def finset.functor [Π (P : Prop), decidable P] :
functor finset

Because finset.image requires a decidable_eq instances for the target type, we can only construct a functor finset when working classically.

Equations
source
@[instance]
def finset.is_lawful_functor [Π (P : Prop), decidable P] :
is_lawful_functor finset

source
def finset.subtype {α : Type u_1} (p : α → Prop) [decidable_pred p] (s : finset α) :
finset (subtype p)

Given a finset s and a predicate p, s.subtype p is the finset of subtype p whose elements belong to s.

Equations
source
@[simp]
theorem finset.mem_subtype {α : Type u_1} {p : α → Prop} [decidable_pred p] {s : finset α} {a : subtype p} :
a ∈ finset.subtype p s ↔ ↑a ∈ s

source
theorem finset.subtype_eq_empty {α : Type u_1} {p : α → Prop} [decidable_pred p] {s : finset α} :
finset.subtype p s = ∅ ↔ ∀ (x : α), p x → x ∉ s

source
@[simp]
theorem finset.subtype_map {α : Type u_1} {s : finset α} (p : α → Prop) [decidable_pred p] :
finset.map (function.embedding.subtype p) (finset.subtype p s) = finset.filter p s

s.subtype p converts back to s.filter p with embedding.subtype.

source
theorem finset.subtype_map_of_mem {α : Type u_1} {s : finset α} {p : α → Prop} [decidable_pred p] (h : ∀ (x : α), x ∈ s → p x) :
finset.map (function.embedding.subtype p) (finset.subtype p s) = s

If all elements of a finset satisfy the predicate p, s.subtype p converts back to s with embedding.subtype.

source
theorem finset.property_of_mem_map_subtype {α : Type u_1} {p : α → Prop} (s : finset {x // p x}) {a : α} (h : a ∈ finset.map (function.embedding.subtype (λ (x : α), p x)) s) :
p a

If a finset of a subtype is converted to the main type with embedding.subtype, all elements of the result have the property of the subtype.

source
theorem finset.not_mem_map_subtype_of_not_property {α : Type u_1} {p : α → Prop} (s : finset {x // p x}) {a : α} (h : ¬p a) :
a ∉ finset.map (function.embedding.subtype (λ (x : α), p x)) s

If a finset of a subtype is converted to the main type with embedding.subtype, the result does not contain any value that does not satisfy the property of the subtype.

source
theorem finset.map_subtype_subset {α : Type u_1} {t : set α} (s : finset ↥t) :
↑(finset.map (function.embedding.subtype (λ (x : α), x ∈ t)) s) ⊆ t

If a finset of a subtype is converted to the main type with embedding.subtype, the result is a subset of the set giving the subtype.

source
theorem finset.subset_image_iff {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} {s : finset β} {t : set α} :
↑s ⊆ f '' t ↔ ∃ (s' : finset α), ↑s' ⊆ t ∧ finset.image f s' = s

source
theorem multiset.to_finset_map {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] (f : α → β) (m : multiset α) :
(multiset.map f m).to_finset = finset.image f m.to_finset

card

source
def finset.card {α : Type u_1} (s : finset α) :
ℕ

card s is the cardinality (number of elements) of s.

Equations
source
theorem finset.card_def {α : Type u_1} (s : finset α) :
s.card = ⇑multiset.card s.val

source
@[simp]
theorem finset.card_mk {α : Type u_1} {m : multiset α} {nodup : m.nodup} :
{val := m, nodup := nodup}.card = ⇑multiset.card m

source
@[simp]
theorem finset.card_empty {α : Type u_1} :
∅.card = 0

source
@[simp]
theorem finset.card_eq_zero {α : Type u_1} {s : finset α} :
s.card = 0 ↔ s = ∅

source
theorem finset.card_pos {α : Type u_1} {s : finset α} :
0 < s.card ↔ s.nonempty

source
theorem finset.card_ne_zero_of_mem {α : Type u_1} {s : finset α} {a : α} (h : a ∈ s) :
s.card ≠ 0

source
theorem finset.card_eq_one {α : Type u_1} {s : finset α} :
s.card = 1 ↔ ∃ (a : α), s = {a}

source
@[simp]
theorem finset.card_insert_of_not_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∉ s) :
(insert a s).card = s.card + 1

source
theorem finset.card_insert_of_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} (h : a ∈ s) :
(insert a s).card = s.card

source
theorem finset.card_insert_le {α : Type u_1} [decidable_eq α] (a : α) (s : finset α) :
(insert a s).card ≤ s.card + 1

source
@[simp]
theorem finset.card_singleton {α : Type u_1} (a : α) :
{a}.card = 1

source
theorem finset.card_singleton_inter {α : Type u_1} [decidable_eq α] {x : α} {s : finset α} :
({x} ∩ s).card ≤ 1

source
theorem finset.card_erase_of_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} :
a ∈ s → (s.erase a).card = s.card.pred

source
theorem finset.card_erase_lt_of_mem {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} :
a ∈ s → (s.erase a).card < s.card

source
theorem finset.card_erase_le {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} :
(s.erase a).card ≤ s.card

source
theorem finset.pred_card_le_card_erase {α : Type u_1} [decidable_eq α] {a : α} {s : finset α} :
s.card - 1 ≤ (s.erase a).card

source
@[simp]
theorem finset.card_range (n : ℕ) :
(finset.range n).card = n

source
@[simp]
theorem finset.card_attach {α : Type u_1} {s : finset α} :
s.attach.card = s.card

source
theorem multiset.to_finset_card_le {α : Type u_1} [decidable_eq α] (m : multiset α) :
m.to_finset.card ≤ ⇑multiset.card m

source
theorem list.to_finset_card_le {α : Type u_1} [decidable_eq α] (l : list α) :
l.to_finset.card ≤ l.length

source
theorem finset.card_image_le {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} {s : finset α} :
(finset.image f s).card ≤ s.card

source
theorem finset.card_image_of_inj_on {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} {s : finset α} (H : ∀ (x : α), x ∈ s → ∀ (y : α), y ∈ s → f x = f y → x = y) :
(finset.image f s).card = s.card

source
theorem finset.card_image_of_injective {α : Type u_1} {β : Type u_2} [decidable_eq β] {f : α → β} (s : finset α) (H : function.injective f) :
(finset.image f s).card = s.card

source
theorem finset.fiber_card_ne_zero_iff_mem_image {α : Type u_1} {β : Type u_2} (s : finset α) (f : α → β) [decidable_eq β] (y : β) :
(finset.filter (λ (x : α), f x = y) s).card ≠ 0 ↔ y ∈ finset.image f s

source
@[simp]
theorem finset.card_map {α : Type u_1} {β : Type u_2} (f : α ↪ β) {s : finset α} :
(finset.map f s).card = s.card

source
theorem finset.card_eq_of_bijective {α : Type u_1} {s : finset α} {n : ℕ} (f : Π (i : ℕ), i < n → α) (hf : ∀ (a : α), a ∈ s → (∃ (i : ℕ) (h : i < n), f i h = a)) (hf' : ∀ (i : ℕ) (h : i < n), f i h ∈ s) (f_inj : ∀ (i j : ℕ) (hi : i < n) (hj : j < n), f i hi = f j hj → i = j) :
s.card = n

source
theorem finset.card_eq_succ {α : Type u_1} [decidable_eq α] {s : finset α} {n : ℕ} :
s.card = n + 1 ↔ ∃ (a : α) (t : finset α), a ∉ t ∧ insert a t = s ∧ t.card = n

source
theorem finset.card_le_of_subset {α : Type u_1} {s t : finset α} :
s ⊆ t → s.card ≤ t.card

source
theorem finset.eq_of_subset_of_card_le {α : Type u_1} {s t : finset α} (h : s ⊆ t) (h₂ : t.card ≤ s.card) :
s = t

source
theorem finset.card_lt_card {α : Type u_1} {s t : finset α} (h : s ⊂ t) :
s.card < t.card

source
theorem finset.card_le_card_of_inj_on {α : Type u_1} {β : Type u_2} {s : finset α} {t : finset β} (f : α → β) (hf : ∀ (a : α), a ∈ s → f a ∈ t) (f_inj : ∀ (a₁ : α), a₁ ∈ s → ∀ (a₂ : α), a₂ ∈ s → f a₁ = f a₂ → a₁ = a₂) :
s.card ≤ t.card

source
theorem finset.exists_ne_map_eq_of_card_lt_of_maps_to {α : Type u_1} {β : Type u_2} {s : finset α} {t : finset β} (hc : t.card < s.card) {f : α → β} (hf : ∀ (a : α), a ∈ s → f a ∈ t) :
∃ (x : α) (H : x ∈ s) (y : α) (H : y ∈ s), x ≠ y ∧ f x = f y

If there are more pigeons than pigeonholes, then there are two pigeons in the same pigeonhole.

source
theorem finset.card_le_of_inj_on {α : Type u_1} {n : ℕ} {s : finset α} (f : ℕ → α) (hf : ∀ (i : ℕ), i < n → f i ∈ s) (f_inj : ∀ (i j : ℕ), i < n → j < n → f i = f j → i = j) :
n ≤ s.card

source
def finset.strong_induction_on {α : Type u_1} {p : finset α → Sort u_2} (s : finset α) :
(Π (s : finset α), (Π (t : finset α), t ⊂ s → p t) → p s) → p s

Suppose that, given objects defined on all strict subsets of any finset s, one knows how to define an object on s. Then one can inductively define an object on all finsets, starting from the empty set and iterating. This can be used either to define data, or to prove properties.

Equations