mathlib documentation

data.fintype.basic

Finite types #

This file defines a typeclass to state that a type is finite.

Main declarations #

fintype α: Typeclass saying that a type is finite. It takes as fields a finset and a proof that all terms of type α are in it.
finset.univ: The finset of all elements of a fintype.
fintype.card α: Cardinality of a fintype. Equal to finset.univ.card.
perms_of_finset s: The finset of permutations of the finset s.
fintype.trunc_equiv_fin: A fintype α is computably equivalent to fin (card α). The trunc-free, noncomputable version is fintype.equiv_fin.
fintype.trunc_equiv_of_card_eq fintype.equiv_of_card_eq: Two fintypes of same cardinality are equivalent. See above.
fin.equiv_iff_eq: fin m ≃ fin n iff m = n.
infinite α: Typeclass saying that a type is infinite. Defined as fintype α → false.
not_fintype: No fintype has an infinite instance.
infinite.nat_embedding: An embedding of ℕ into an infinite type.

We also provide the following versions of the pigeonholes principle.

fintype.exists_ne_map_eq_of_card_lt and is_empty_of_card_lt: Finitely many pigeons and pigeonholes. Weak formulation.
fintype.exists_ne_map_eq_of_infinite: Infinitely many pigeons in finitely many pigeonholes. Weak formulation.
fintype.exists_infinite_fiber: Infinitely many pigeons in finitely many pigeonholes. Strong formulation.

Some more pigeonhole-like statements can be found in data.fintype.card_embedding.

Instances #

Among others, we provide fintype instances for

A subtype of a fintype. See fintype.subtype.
The option of a fintype.
The product of two fintypes.
The sum of two fintypes.
Prop.

and infinite instances for

specific types: ℕ, ℤ
type constructors: set α, finset α, multiset α, list α, α ⊕ β, α × β

along with some machinery

Types which have a surjection from/an injection to a fintype are themselves fintypes. See fintype.of_injective and fintype.of_surjective.
Types which have an injection from/a surjection to an infinite type are themselves infinite. See infinite.of_injective and infinite.of_surjective.

@[class]

structure fintype (α : Type u_4) :

Type u_4

elems : finset α
complete : ∀ (x : α), x ∈ fintype.elems α

fintype α means that α is finite, i.e. there are only finitely many distinct elements of type α. The evidence of this is a finset elems (a list up to permutation without duplicates), together with a proof that everything of type α is in the list.

Instances of this typeclass

Instances of other typeclasses for fintype

def finset.univ {α : Type u_1} [fintype α] :

univ is the universal finite set of type finset α implied from the assumption fintype α.

Equations

finset.univ = fintype.elems α

@[simp]

theorem finset.mem_univ {α : Type u_1} [fintype α] (x : α) :

x ∈ finset.univ

@[simp]

theorem finset.mem_univ_val {α : Type u_1} [fintype α] (x : α) :

x ∈ finset.univ.val

theorem finset.eq_univ_iff_forall {α : Type u_1} [fintype α] {s : finset α} :

s = finset.univ ↔ ∀ (x : α), x ∈ s

theorem finset.eq_univ_of_forall {α : Type u_1} [fintype α] {s : finset α} :

(∀ (x : α), x ∈ s) → s = finset.univ

@[simp, norm_cast]

theorem finset.coe_univ {α : Type u_1} [fintype α] :

↑finset.univ = set.univ

@[simp, norm_cast]

theorem finset.coe_eq_univ {α : Type u_1} [fintype α] {s : finset α} :

↑s = set.univ ↔ s = finset.univ

theorem finset.univ_nonempty_iff {α : Type u_1} [fintype α] :

finset.univ.nonempty ↔ nonempty α

theorem finset.univ_nonempty {α : Type u_1} [fintype α] [nonempty α] :

finset.univ.nonempty

theorem finset.univ_eq_empty_iff {α : Type u_1} [fintype α] :

finset.univ = ∅ ↔ is_empty α

@[simp]

theorem finset.univ_eq_empty {α : Type u_1} [fintype α] [is_empty α] :

finset.univ = ∅

@[simp]

theorem finset.univ_unique {α : Type u_1} [fintype α] [unique α] :

finset.univ = {inhabited.default}

@[simp]

theorem finset.subset_univ {α : Type u_1} [fintype α] (s : finset α) :

s ⊆ finset.univ

@[protected, instance]

def finset.order_top {α : Type u_1} [fintype α] :

order_top (finset α)

Equations

finset.order_top = {top := finset.univ _inst_1, le_top := _}

@[protected, instance]

def finset.boolean_algebra {α : Type u_1} [fintype α] [decidable_eq α] :

boolean_algebra (finset α)

Equations

finset.boolean_algebra = {sup := generalized_boolean_algebra.sup finset.generalized_boolean_algebra, le := generalized_boolean_algebra.le finset.generalized_boolean_algebra, lt := generalized_boolean_algebra.lt finset.generalized_boolean_algebra, le_refl := _, le_trans := _, lt_iff_le_not_le := _, le_antisymm := _, le_sup_left := _, le_sup_right := _, sup_le := _, inf := generalized_boolean_algebra.inf finset.generalized_boolean_algebra, inf_le_left := _, inf_le_right := _, le_inf := _, le_sup_inf := _, sdiff := generalized_boolean_algebra.sdiff finset.generalized_boolean_algebra, bot := order_bot.bot finset.order_bot, sup_inf_sdiff := _, inf_inf_sdiff := _, compl := λ (s : finset α), finset.univ \ s, top := order_top.top finset.order_top, inf_compl_le_bot := _, top_le_sup_compl := _, le_top := _, bot_le := _, sdiff_eq := _}

theorem finset.compl_eq_univ_sdiff {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) :

sᶜ = finset.univ \ s

@[simp]

theorem finset.mem_compl {α : Type u_1} [fintype α] {s : finset α} [decidable_eq α] {a : α} :

a ∈ sᶜ ↔ a ∉ s

theorem finset.not_mem_compl {α : Type u_1} [fintype α] {s : finset α} [decidable_eq α] {a : α} :

a ∉ sᶜ ↔ a ∈ s

@[simp, norm_cast]

theorem finset.coe_compl {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) :

↑sᶜ = (↑s)ᶜ

@[simp]

theorem finset.compl_empty {α : Type u_1} [fintype α] [decidable_eq α] :

∅ᶜ = finset.univ

@[simp]

theorem finset.union_compl {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) :

s ∪ sᶜ = finset.univ

@[simp]

theorem finset.inter_compl {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) :

s ∩ sᶜ = ∅

@[simp]

theorem finset.compl_union {α : Type u_1} [fintype α] [decidable_eq α] (s t : finset α) :

(s ∪ t)ᶜ = sᶜ ∩ tᶜ

@[simp]

theorem finset.compl_inter {α : Type u_1} [fintype α] [decidable_eq α] (s t : finset α) :

(s ∩ t)ᶜ = sᶜ ∪ tᶜ

@[simp]

theorem finset.compl_erase {α : Type u_1} [fintype α] {s : finset α} [decidable_eq α] {a : α} :

(s.erase a)ᶜ = has_insert.insert a sᶜ

@[simp]

theorem finset.compl_insert {α : Type u_1} [fintype α] {s : finset α} [decidable_eq α] {a : α} :

(has_insert.insert a s)ᶜ = sᶜ.erase a

@[simp]

theorem finset.insert_compl_self {α : Type u_1} [fintype α] [decidable_eq α] (x : α) :

has_insert.insert x {x}ᶜ = finset.univ

@[simp]

theorem finset.compl_filter {α : Type u_1} [fintype α] [decidable_eq α] (p : α → Prop) [decidable_pred p] [Π (x : α), decidable (¬p x)] :

(finset.filter p finset.univ)ᶜ = finset.filter (λ (x : α), ¬p x) finset.univ

theorem finset.compl_ne_univ_iff_nonempty {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) :

sᶜ ≠ finset.univ ↔ s.nonempty

theorem finset.compl_singleton {α : Type u_1} [fintype α] [decidable_eq α] (a : α) :

{a}ᶜ = finset.univ.erase a

theorem finset.insert_inj_on' {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) :

set.inj_on (λ (a : α), has_insert.insert a s) ↑sᶜ

theorem finset.image_univ_of_surjective {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq α] [fintype β] {f : β → α} (hf : function.surjective f) :

finset.image f finset.univ = finset.univ

theorem finset.map_univ_of_surjective {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] {f : β ↪ α} (hf : function.surjective ⇑f) :

finset.map f finset.univ = finset.univ

@[simp]

theorem finset.map_univ_equiv {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : β ≃ α) :

finset.map f.to_embedding finset.univ = finset.univ

@[simp]

theorem finset.univ_inter {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) :

finset.univ ∩ s = s

@[simp]

theorem finset.inter_univ {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) :

s ∩ finset.univ = s

@[simp]

theorem finset.piecewise_univ {α : Type u_1} [fintype α] [Π (i : α), decidable (i ∈ finset.univ)] {δ : α → Sort u_2} (f g : Π (i : α), δ i) :

finset.univ.piecewise f g = f

theorem finset.piecewise_compl {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) [Π (i : α), decidable (i ∈ s)] [Π (i : α), decidable (i ∈ sᶜ)] {δ : α → Sort u_2} (f g : Π (i : α), δ i) :

sᶜ.piecewise f g = s.piecewise g f

@[simp]

theorem finset.piecewise_erase_univ {α : Type u_1} [fintype α] {δ : α → Sort u_2} [decidable_eq α] (a : α) (f g : Π (a : α), δ a) :

(finset.univ.erase a).piecewise f g = function.update f a (g a)

theorem finset.univ_map_equiv_to_embedding {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (e : α ≃ β) :

finset.map e.to_embedding finset.univ = finset.univ

@[simp]

theorem finset.univ_filter_exists {α : Type u_1} {β : Type u_2} [fintype α] (f : α → β) [fintype β] [decidable_pred (λ (y : β), ∃ (x : α), f x = y)] [decidable_eq β] :

finset.filter (λ (y : β), ∃ (x : α), f x = y) finset.univ = finset.image f finset.univ

theorem finset.univ_filter_mem_range {α : Type u_1} {β : Type u_2} [fintype α] (f : α → β) [fintype β] [decidable_pred (λ (y : β), y ∈ set.range f)] [decidable_eq β] :

finset.filter (λ (y : β), y ∈ set.range f) finset.univ = finset.image f finset.univ

Note this is a special case of (finset.image_preimage f univ _).symm.

theorem finset.coe_filter_univ {α : Type u_1} [fintype α] (p : α → Prop) [decidable_pred p] :

↑(finset.filter p finset.univ) = {x : α | p x}

theorem finset.sup_univ_eq_supr {α : Type u_1} {β : Type u_2} [fintype α] [complete_lattice β] (f : α → β) :

finset.univ.sup f = supr f

A special case of finset.sup_eq_supr that omits the useless x ∈ univ binder.

theorem finset.inf_univ_eq_infi {α : Type u_1} {β : Type u_2} [fintype α] [complete_lattice β] (f : α → β) :

finset.univ.inf f = infi f

A special case of finset.inf_eq_infi that omits the useless x ∈ univ binder.

@[simp]

theorem finset.fold_inf_univ {α : Type u_1} [fintype α] [semilattice_inf α] [order_bot α] (a : α) :

finset.fold has_inf.inf a (λ (x : α), x) finset.univ = ⊥

@[simp]

theorem finset.fold_sup_univ {α : Type u_1} [fintype α] [semilattice_sup α] [order_top α] (a : α) :

finset.fold has_sup.sup a (λ (x : α), x) finset.univ = ⊤

@[protected, instance]

def fintype.decidable_pi_fintype {α : Type u_1} {β : α → Type u_2} [Π (a : α), decidable_eq (β a)] [fintype α] :

decidable_eq (Π (a : α), β a)

Equations

fintype.decidable_pi_fintype = λ (f g : Π (a : α), β a), decidable_of_iff (∀ (a : α), a ∈ fintype.elems α → f a = g a) _

@[protected, instance]

def fintype.decidable_forall_fintype {α : Type u_1} {p : α → Prop} [decidable_pred p] [fintype α] :

decidable (∀ (a : α), p a)

Equations

fintype.decidable_forall_fintype = decidable_of_iff (∀ (a : α), a ∈ finset.univ → p a) fintype.decidable_forall_fintype._proof_1

@[protected, instance]

def fintype.decidable_exists_fintype {α : Type u_1} {p : α → Prop} [decidable_pred p] [fintype α] :

decidable (∃ (a : α), p a)

Equations

fintype.decidable_exists_fintype = decidable_of_iff (∃ (a : α) (H : a ∈ finset.univ), p a) fintype.decidable_exists_fintype._proof_1

@[protected, instance]

def fintype.decidable_mem_range_fintype {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] (f : α → β) :

decidable_pred (λ (_x : β), _x ∈ set.range f)

Equations

fintype.decidable_mem_range_fintype f = λ (x : β), fintype.decidable_exists_fintype

@[protected, instance]

def fintype.decidable_eq_equiv_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] :

decidable_eq (α ≃ β)

Equations

fintype.decidable_eq_equiv_fintype = λ (a b : α ≃ β), decidable_of_iff (a.to_fun = b.to_fun) _

@[protected, instance]

def fintype.decidable_eq_embedding_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] :

decidable_eq (α ↪ β)

Equations

fintype.decidable_eq_embedding_fintype = λ (a b : α ↪ β), decidable_of_iff (⇑a = ⇑b) _

@[protected, instance]

def fintype.decidable_eq_one_hom_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] [has_one α] [has_one β] :

decidable_eq (one_hom α β)

Equations

fintype.decidable_eq_one_hom_fintype = λ (a b : one_hom α β), decidable_of_iff (⇑a = ⇑b) _

@[protected, instance]

def fintype.decidable_eq_zero_hom_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] [has_zero α] [has_zero β] :

decidable_eq (zero_hom α β)

Equations

fintype.decidable_eq_zero_hom_fintype = λ (a b : zero_hom α β), decidable_of_iff (⇑a = ⇑b) _

@[protected, instance]

def fintype.decidable_eq_mul_hom_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] [has_mul α] [has_mul β] :

decidable_eq (α →ₙ* β)

Equations

fintype.decidable_eq_mul_hom_fintype = λ (a b : α →ₙ* β), decidable_of_iff (⇑a = ⇑b) _

@[protected, instance]

def fintype.decidable_eq_add_hom_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] [has_add α] [has_add β] :

decidable_eq (add_hom α β)

Equations

fintype.decidable_eq_add_hom_fintype = λ (a b : add_hom α β), decidable_of_iff (⇑a = ⇑b) _

@[protected, instance]

def fintype.decidable_eq_add_monoid_hom_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] [add_zero_class α] [add_zero_class β] :

decidable_eq (α →+ β)

Equations

fintype.decidable_eq_add_monoid_hom_fintype = λ (a b : α →+ β), decidable_of_iff (⇑a = ⇑b) _

@[protected, instance]

def fintype.decidable_eq_monoid_hom_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] [mul_one_class α] [mul_one_class β] :

decidable_eq (α →* β)

Equations

fintype.decidable_eq_monoid_hom_fintype = λ (a b : α →* β), decidable_of_iff (⇑a = ⇑b) _

@[protected, instance]

def fintype.decidable_eq_monoid_with_zero_hom_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] [mul_zero_one_class α] [mul_zero_one_class β] :

decidable_eq (α →*₀ β)

Equations

fintype.decidable_eq_monoid_with_zero_hom_fintype = λ (a b : α →*₀ β), decidable_of_iff (⇑a = ⇑b) _

@[protected, instance]

def fintype.decidable_eq_ring_hom_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] [semiring α] [semiring β] :

decidable_eq (α →+* β)

Equations

fintype.decidable_eq_ring_hom_fintype = λ (a b : α →+* β), decidable_of_iff (⇑a = ⇑b) _

@[protected, instance]

def fintype.decidable_injective_fintype {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] [fintype α] :

decidable_pred function.injective

Equations

fintype.decidable_injective_fintype = λ (x : α → β), _.mpr fintype.decidable_forall_fintype

@[protected, instance]

def fintype.decidable_surjective_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] [fintype β] :

decidable_pred function.surjective

Equations

fintype.decidable_surjective_fintype = λ (x : α → β), _.mpr fintype.decidable_forall_fintype

@[protected, instance]

def fintype.decidable_bijective_fintype {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] [fintype α] [fintype β] :

decidable_pred function.bijective

Equations

fintype.decidable_bijective_fintype = λ (x : α → β), _.mpr and.decidable

@[protected, instance]

def fintype.decidable_right_inverse_fintype {α : Type u_1} {β : Type u_2} [decidable_eq α] [fintype α] (f : α → β) (g : β → α) :

decidable (function.right_inverse f g)

Equations

fintype.decidable_right_inverse_fintype f g = show decidable (∀ (x : α), g (f x) = x), from fintype.decidable_forall_fintype

@[protected, instance]

def fintype.decidable_left_inverse_fintype {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype β] (f : α → β) (g : β → α) :

decidable (function.left_inverse f g)

Equations

fintype.decidable_left_inverse_fintype f g = show decidable (∀ (x : β), f (g x) = x), from fintype.decidable_forall_fintype

theorem fintype.exists_max {α : Type u_1} [fintype α] [nonempty α] {β : Type u_2} [linear_order β] (f : α → β) :

∃ (x₀ : α), ∀ (x : α), f x ≤ f x₀

theorem fintype.exists_min {α : Type u_1} [fintype α] [nonempty α] {β : Type u_2} [linear_order β] (f : α → β) :

∃ (x₀ : α), ∀ (x : α), f x₀ ≤ f x

def fintype.of_multiset {α : Type u_1} [decidable_eq α] (s : multiset α) (H : ∀ (x : α), x ∈ s) :

Construct a proof of fintype α from a universal multiset

Equations

fintype.of_multiset s H = {elems := s.to_finset, complete := _}

def fintype.of_list {α : Type u_1} [decidable_eq α] (l : list α) (H : ∀ (x : α), x ∈ l) :

Construct a proof of fintype α from a universal list

Equations

fintype.of_list l H = {elems := l.to_finset, complete := _}

theorem fintype.exists_univ_list (α : Type u_1) [fintype α] :

∃ (l : list α), l.nodup ∧ ∀ (x : α), x ∈ l

def fintype.card (α : Type u_1) [fintype α] :

card α is the number of elements in α, defined when α is a fintype.

Equations

fintype.card α = finset.univ.card

def fintype.trunc_equiv_fin (α : Type u_1) [decidable_eq α] [fintype α] :

trunc (α ≃ fin (fintype.card α))

There is (computably) an equivalence between α and fin (card α).

Since it is not unique and depends on which permutation of the universe list is used, the equivalence is wrapped in trunc to preserve computability.

See fintype.equiv_fin for the noncomputable version, and fintype.trunc_equiv_fin_of_card_eq and fintype.equiv_fin_of_card_eq for an equiv α ≃ fin n given fintype.card α = n.

See fintype.trunc_fin_bijection for a version without [decidable_eq α].

Equations

fintype.trunc_equiv_fin α = _.mpr (quot.rec_on_subsingleton finset.univ.val (λ (l : list α) (h : ∀ (x : α), x ∈ l) (nd : l.nodup), trunc.mk (list.nodup.nth_le_equiv_of_forall_mem_list l nd h).symm) finset.mem_univ_val _)

noncomputable def fintype.equiv_fin (α : Type u_1) [fintype α] :

α ≃ fin (fintype.card α)

There is (noncomputably) an equivalence between α and fin (card α).

See fintype.trunc_equiv_fin for the computable version, and fintype.trunc_equiv_fin_of_card_eq and fintype.equiv_fin_of_card_eq for an equiv α ≃ fin n given fintype.card α = n.

Equations

fintype.equiv_fin α = let _inst : decidable_eq α := classical.dec_eq α in (fintype.trunc_equiv_fin α).out

def fintype.trunc_fin_bijection (α : Type u_1) [fintype α] :

trunc {f // function.bijective f}

There is (computably) a bijection between fin (card α) and α.

Since it is not unique and depends on which permutation of the universe list is used, the bijection is wrapped in trunc to preserve computability.

See fintype.trunc_equiv_fin for a version that gives an equivalence given [decidable_eq α].

Equations

fintype.trunc_fin_bijection α = id (quot.rec_on_subsingleton finset.univ.val (λ (l : list α) (h : ∀ (x : α), x ∈ l) (nd : l.nodup), trunc.mk (list.nodup.nth_le_bijection_of_forall_mem_list l nd h)) finset.mem_univ_val _)

@[protected, instance]

def fintype.subsingleton (α : Type u_1) :

subsingleton (fintype α)

@[protected]

def fintype.subtype {α : Type u_1} {p : α → Prop} (s : finset α) (H : ∀ (x : α), x ∈ s ↔ p x) :

fintype {x // p x}

Given a predicate that can be represented by a finset, the subtype associated to the predicate is a fintype.

Equations

fintype.subtype s H = {elems := {val := multiset.pmap subtype.mk s.val _, nodup := _}, complete := _}

theorem fintype.subtype_card {α : Type u_1} {p : α → Prop} (s : finset α) (H : ∀ (x : α), x ∈ s ↔ p x) :

fintype.card {x // p x} = s.card

theorem fintype.card_of_subtype {α : Type u_1} {p : α → Prop} (s : finset α) (H : ∀ (x : α), x ∈ s ↔ p x) [fintype {x // p x}] :

fintype.card {x // p x} = s.card

def fintype.of_finset {α : Type u_1} {p : set α} (s : finset α) (H : ∀ (x : α), x ∈ s ↔ x ∈ p) :

Construct a fintype from a finset with the same elements.

Equations

fintype.of_finset s H = fintype.subtype s H

@[simp]

theorem fintype.card_of_finset {α : Type u_1} {p : set α} (s : finset α) (H : ∀ (x : α), x ∈ s ↔ x ∈ p) :

fintype.card ↥p = s.card

theorem fintype.card_of_finset' {α : Type u_1} {p : set α} (s : finset α) (H : ∀ (x : α), x ∈ s ↔ x ∈ p) [fintype ↥p] :

fintype.card ↥p = s.card

def fintype.of_bijective {α : Type u_1} {β : Type u_2} [fintype α] (f : α → β) (H : function.bijective f) :

If f : α → β is a bijection and α is a fintype, then β is also a fintype.

Equations

fintype.of_bijective f H = {elems := finset.map {to_fun := f, inj' := _} finset.univ, complete := _}

def fintype.of_surjective {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype α] (f : α → β) (H : function.surjective f) :

If f : α → β is a surjection and α is a fintype, then β is also a fintype.

Equations

fintype.of_surjective f H = {elems := finset.image f finset.univ, complete := _}

def function.injective.inv_of_mem_range {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} (hf : function.injective f) :

↥(set.range f) → α

The inverse of an hf : injective function f : α → β, of the type ↥(set.range f) → α. This is the computable version of function.inv_fun that requires fintype α and decidable_eq β, or the function version of applying (equiv.of_injective f hf).symm. This function should not usually be used for actual computation because for most cases, an explicit inverse can be stated that has better computational properties. This function computes by checking all terms a : α to find the f a = b, so it is O(N) where N = fintype.card α.

Equations

hf.inv_of_mem_range = λ (b : ↥(set.range f)), finset.choose (λ (a : α), f a = ↑b) finset.univ _

theorem function.injective.left_inv_of_inv_of_mem_range {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} (hf : function.injective f) (b : ↥(set.range f)) :

f (hf.inv_of_mem_range b) = ↑b

@[simp]

theorem function.injective.right_inv_of_inv_of_mem_range {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} (hf : function.injective f) (a : α) :

hf.inv_of_mem_range ⟨f a, _⟩ = a

theorem function.injective.inv_fun_restrict {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} (hf : function.injective f) [nonempty α] :

(set.range f).restrict (function.inv_fun f) = hf.inv_of_mem_range

theorem function.injective.inv_of_mem_range_surjective {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} (hf : function.injective f) :

function.surjective hf.inv_of_mem_range

def function.embedding.inv_of_mem_range {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] (f : α ↪ β) (b : ↥(set.range ⇑f)) :

α

The inverse of an embedding f : α ↪ β, of the type ↥(set.range f) → α. This is the computable version of function.inv_fun that requires fintype α and decidable_eq β, or the function version of applying (equiv.of_injective f f.injective).symm. This function should not usually be used for actual computation because for most cases, an explicit inverse can be stated that has better computational properties. This function computes by checking all terms a : α to find the f a = b, so it is O(N) where N = fintype.card α.

Equations

f.inv_of_mem_range b = _.inv_of_mem_range b

@[simp]

theorem function.embedding.left_inv_of_inv_of_mem_range {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] (f : α ↪ β) (b : ↥(set.range ⇑f)) :

⇑f (f.inv_of_mem_range b) = ↑b

@[simp]

theorem function.embedding.right_inv_of_inv_of_mem_range {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] (f : α ↪ β) (a : α) :

f.inv_of_mem_range ⟨⇑f a, _⟩ = a

theorem function.embedding.inv_fun_restrict {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] (f : α ↪ β) [nonempty α] :

(set.range ⇑f).restrict (function.inv_fun ⇑f) = f.inv_of_mem_range

theorem function.embedding.inv_of_mem_range_surjective {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] (f : α ↪ β) :

function.surjective f.inv_of_mem_range

noncomputable def fintype.of_injective {α : Type u_1} {β : Type u_2} [fintype β] (f : α → β) (H : function.injective f) :

Given an injective function to a fintype, the domain is also a fintype. This is noncomputable because injectivity alone cannot be used to construct preimages.

Equations

fintype.of_injective f H = let _inst : Π (p : Prop), decidable p := classical.dec in dite (nonempty α) (λ (hα : nonempty α), let _inst_2 : inhabited α := classical.inhabited_of_nonempty hα in fintype.of_surjective (function.inv_fun f) _) (λ (hα : ¬nonempty α), {elems := ∅, complete := _})

def fintype.of_equiv {β : Type u_2} (α : Type u_1) [fintype α] (f : α ≃ β) :

If f : α ≃ β and α is a fintype, then β is also a fintype.

Equations

fintype.of_equiv α f = fintype.of_bijective ⇑f _

theorem fintype.of_equiv_card {α : Type u_1} {β : Type u_2} [fintype α] (f : α ≃ β) :

fintype.card β = fintype.card α

theorem fintype.card_congr {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α ≃ β) :

fintype.card α = fintype.card β

theorem fintype.card_congr' {α β : Type u_1} [fintype α] [fintype β] (h : α = β) :

fintype.card α = fintype.card β

def fintype.trunc_equiv_fin_of_card_eq {α : Type u_1} [fintype α] [decidable_eq α] {n : ℕ} (h : fintype.card α = n) :

trunc (α ≃ fin n)

If the cardinality of α is n, there is computably a bijection between α and fin n.

See fintype.equiv_fin_of_card_eq for the noncomputable definition, and fintype.trunc_equiv_fin and fintype.equiv_fin for the bijection α ≃ fin (card α).

Equations

fintype.trunc_equiv_fin_of_card_eq h = trunc.map (λ (e : α ≃ fin (fintype.card α)), e.trans (fin.cast h).to_equiv) (fintype.trunc_equiv_fin α)

noncomputable def fintype.equiv_fin_of_card_eq {α : Type u_1} [fintype α] {n : ℕ} (h : fintype.card α = n) :

α ≃ fin n

If the cardinality of α is n, there is noncomputably a bijection between α and fin n.

See fintype.trunc_equiv_fin_of_card_eq for the computable definition, and fintype.trunc_equiv_fin and fintype.equiv_fin for the bijection α ≃ fin (card α).

Equations

fintype.equiv_fin_of_card_eq h = let _inst : decidable_eq α := classical.dec_eq α in (fintype.trunc_equiv_fin_of_card_eq h).out

def fintype.trunc_equiv_of_card_eq {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] [decidable_eq α] [decidable_eq β] (h : fintype.card α = fintype.card β) :

trunc (α ≃ β)

Two fintypes with the same cardinality are (computably) in bijection.

See fintype.equiv_of_card_eq for the noncomputable version, and fintype.trunc_equiv_fin_of_card_eq and fintype.equiv_fin_of_card_eq for the specialization to fin.

Equations

fintype.trunc_equiv_of_card_eq h = (fintype.trunc_equiv_fin_of_card_eq h).bind (λ (e : α ≃ fin (fintype.card β)), trunc.map (λ (e' : β ≃ fin (fintype.card β)), e.trans e'.symm) (fintype.trunc_equiv_fin β))

noncomputable def fintype.equiv_of_card_eq {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (h : fintype.card α = fintype.card β) :

α ≃ β

Two fintypes with the same cardinality are (noncomputably) in bijection.

See fintype.trunc_equiv_of_card_eq for the computable version, and fintype.trunc_equiv_fin_of_card_eq and fintype.equiv_fin_of_card_eq for the specialization to fin.

Equations

fintype.equiv_of_card_eq h = let _inst : decidable_eq α := classical.dec_eq α, _inst_3 : decidable_eq β := classical.dec_eq β in (fintype.trunc_equiv_of_card_eq h).out

theorem fintype.card_eq {α : Type u_1} {β : Type u_2} [F : fintype α] [G : fintype β] :

fintype.card α = fintype.card β ↔ nonempty (α ≃ β)

def fintype.of_subsingleton {α : Type u_1} (a : α) [subsingleton α] :

Any subsingleton type with a witness is a fintype (with one term).

Equations

fintype.of_subsingleton a = {elems := {a}, complete := _}

@[simp]

theorem fintype.univ_of_subsingleton {α : Type u_1} (a : α) [subsingleton α] :

finset.univ = {a}

@[simp]

theorem fintype.card_of_subsingleton {α : Type u_1} (a : α) [subsingleton α] :

fintype.card α = 1

Note: this lemma is specifically about fintype.of_subsingleton. For a statement about arbitrary fintype instances, use either fintype.card_le_one_iff_subsingleton or fintype.card_unique.

@[simp]

theorem fintype.card_unique {α : Type u_1} [unique α] [h : fintype α] :

fintype.card α = 1

@[protected, instance]

def fintype.of_is_empty {α : Type u_1} [is_empty α] :

Equations

fintype.of_is_empty = {elems := ∅, complete := _}

@[simp, nolint]

theorem fintype.univ_of_is_empty {α : Type u_1} [is_empty α] :

finset.univ = ∅

Note: this lemma is specifically about fintype.of_is_empty. For a statement about arbitrary fintype instances, use finset.univ_eq_empty.

@[simp]

theorem fintype.card_of_is_empty {α : Type u_1} [is_empty α] :

fintype.card α = 0

Note: this lemma is specifically about fintype.of_is_empty. For a statement about arbitrary fintype instances, use fintype.card_eq_zero_iff.

@[protected, instance]

noncomputable def fintype.of_subsingleton' (α : Type u_1) [subsingleton α] :

Any subsingleton type is (noncomputably) a fintype (with zero or one term).

Equations

fintype.of_subsingleton' α = dite (nonempty α) (λ (h : nonempty α), fintype.of_subsingleton h.some) (λ (h : ¬nonempty α), fintype.of_is_empty)

def set.to_finset {α : Type u_1} (s : set α) [fintype ↥s] :

Construct a finset enumerating a set s, given a fintype instance.

Equations

s.to_finset = {val := multiset.map subtype.val finset.univ.val, nodup := _}

theorem set.to_finset_congr {α : Type u_1} {s t : set α} [fintype ↥s] [fintype ↥t] (h : s = t) :

s.to_finset = t.to_finset

@[simp]

theorem set.mem_to_finset {α : Type u_1} {s : set α} [fintype ↥s] {a : α} :

a ∈ s.to_finset ↔ a ∈ s

@[simp]

theorem set.mem_to_finset_val {α : Type u_1} {s : set α} [fintype ↥s] {a : α} :

a ∈ s.to_finset.val ↔ a ∈ s

def set.decidable_mem_of_fintype {α : Type u_1} [decidable_eq α] (s : set α) [fintype ↥s] (a : α) :

decidable (a ∈ s)

Membership of a set with a fintype instance is decidable.

Using this as an instance leads to potential loops with subtype.fintype under certain decidability assumptions, so it should only be declared a local instance.

Equations

s.decidable_mem_of_fintype a = decidable_of_iff (a ∈ s.to_finset) set.mem_to_finset

@[simp]

theorem set.to_finset_card {α : Type u_1} (s : set α) [fintype ↥s] :

s.to_finset.card = fintype.card ↥s

@[simp]

theorem set.coe_to_finset {α : Type u_1} (s : set α) [fintype ↥s] :

↑(s.to_finset) = s

@[simp]

theorem set.to_finset_inj {α : Type u_1} {s t : set α} [fintype ↥s] [fintype ↥t] :

s.to_finset = t.to_finset ↔ s = t

@[simp]

theorem set.to_finset_mono {α : Type u_1} {s t : set α} [fintype ↥s] [fintype ↥t] :

s.to_finset ⊆ t.to_finset ↔ s ⊆ t

@[simp]

theorem set.to_finset_strict_mono {α : Type u_1} {s t : set α} [fintype ↥s] [fintype ↥t] :

s.to_finset ⊂ t.to_finset ↔ s ⊂ t

@[simp]

theorem set.to_finset_disjoint_iff {α : Type u_1} [decidable_eq α] {s t : set α} [fintype ↥s] [fintype ↥t] :

disjoint s.to_finset t.to_finset ↔ disjoint s t

theorem set.to_finset_inter {α : Type u_1} [decidable_eq α] (s t : set α) [fintype ↥(s ∩ t)] [fintype ↥s] [fintype ↥t] :

(s ∩ t).to_finset = s.to_finset ∩ t.to_finset

theorem set.to_finset_union {α : Type u_1} [decidable_eq α] (s t : set α) [fintype ↥(s ∪ t)] [fintype ↥s] [fintype ↥t] :

(s ∪ t).to_finset = s.to_finset ∪ t.to_finset

theorem set.to_finset_diff {α : Type u_1} [decidable_eq α] (s t : set α) [fintype ↥s] [fintype ↥t] [fintype ↥(s \ t)] :

(s \ t).to_finset = s.to_finset \ t.to_finset

theorem set.to_finset_ne_eq_erase {α : Type u_1} [decidable_eq α] [fintype α] (a : α) [fintype ↥{x : α | x ≠ a}] :

{x : α | x ≠ a}.to_finset = finset.univ.erase a

theorem set.to_finset_compl {α : Type u_1} [decidable_eq α] [fintype α] (s : set α) [fintype ↥s] [fintype ↥sᶜ] :

sᶜ.to_finset = s.to_finset ᶜ

@[simp]

theorem set.to_finset_univ {α : Type u_1} [fintype ↥set.univ] [fintype α] :

set.univ.to_finset = finset.univ

@[simp]

theorem set.to_finset_range {α : Type u_1} {β : Type u_2} [decidable_eq α] [fintype β] (f : β → α) [fintype ↥(set.range f)] :

(set.range f).to_finset = finset.image f finset.univ

theorem set.to_finset_singleton {α : Type u_1} (a : α) [fintype ↥{a}] :

{a}.to_finset = {a}

@[simp]

theorem set.to_finset_insert {α : Type u_1} [decidable_eq α] {a : α} {s : set α} [fintype ↥(has_insert.insert a s)] [fintype ↥s] :

(has_insert.insert a s).to_finset = has_insert.insert a s.to_finset

theorem set.filter_mem_univ_eq_to_finset {α : Type u_1} [fintype α] (s : set α) [fintype ↥s] [decidable_pred (λ (_x : α), _x ∈ s)] :

finset.filter (λ (_x : α), _x ∈ s) finset.univ = s.to_finset

@[simp]

theorem finset.to_finset_coe {α : Type u_1} (s : finset α) [fintype ↥↑s] :

↑s.to_finset = s

theorem finset.card_univ {α : Type u_1} [fintype α] :

finset.univ.card = fintype.card α

theorem finset.eq_univ_of_card {α : Type u_1} [fintype α] (s : finset α) (hs : s.card = fintype.card α) :

s = finset.univ

theorem finset.card_eq_iff_eq_univ {α : Type u_1} [fintype α] (s : finset α) :

s.card = fintype.card α ↔ s = finset.univ

theorem finset.card_le_univ {α : Type u_1} [fintype α] (s : finset α) :

s.card ≤ fintype.card α

theorem finset.card_lt_univ_of_not_mem {α : Type u_1} [fintype α] {s : finset α} {x : α} (hx : x ∉ s) :

s.card < fintype.card α

theorem finset.card_lt_iff_ne_univ {α : Type u_1} [fintype α] (s : finset α) :

s.card < fintype.card α ↔ s ≠ finset.univ

theorem finset.card_compl_lt_iff_nonempty {α : Type u_1} [fintype α] [decidable_eq α] (s : finset α) :

sᶜ.card < fintype.card α ↔ s.nonempty

theorem finset.card_univ_diff {α : Type u_1} [decidable_eq α] [fintype α] (s : finset α) :

(finset.univ \ s).card = fintype.card α - s.card

theorem finset.card_compl {α : Type u_1} [decidable_eq α] [fintype α] (s : finset α) :

sᶜ.card = fintype.card α - s.card

theorem fintype.card_compl_set {α : Type u_1} [fintype α] (s : set α) [fintype ↥s] [fintype ↥sᶜ] :

fintype.card ↥sᶜ = fintype.card α - fintype.card ↥s

@[protected, instance]

def fin.fintype (n : ℕ) :

fintype (fin n)

Equations

fin.fintype n = {elems := finset.fin_range n, complete := _}

theorem fin.univ_def (n : ℕ) :

finset.univ = finset.fin_range n

@[simp]

theorem fintype.card_fin (n : ℕ) :

fintype.card (fin n) = n

@[simp]

theorem finset.card_fin (n : ℕ) :

finset.univ.card = n

theorem fin_injective :

function.injective fin

fin as a map from ℕ to Type is injective. Note that since this is a statement about equality of types, using it should be avoided if possible.

theorem fin.cast_eq_cast' {n m : ℕ} (h : fin n = fin m) :

cast h = ⇑(fin.cast _)

A reversed version of fin.cast_eq_cast that is easier to rewrite with.

theorem card_finset_fin_le {n : ℕ} (s : finset (fin n)) :

theorem fin.equiv_iff_eq {m n : ℕ} :

nonempty (fin m ≃ fin n) ↔ m = n

@[simp]

theorem fin.image_succ_above_univ {n : ℕ} (i : fin (n + 1)) :

finset.image ⇑(i.succ_above) finset.univ = {i}ᶜ

@[simp]

theorem fin.image_succ_univ (n : ℕ) :

finset.image fin.succ finset.univ = {0}ᶜ

@[simp]

theorem fin.image_cast_succ (n : ℕ) :

finset.image ⇑fin.cast_succ finset.univ = {fin.last n}ᶜ

theorem fin.univ_succ (n : ℕ) :

finset.univ = finset.cons 0 (finset.map {to_fun := fin.succ n, inj' := _} finset.univ) _

Embed fin n into fin (n + 1) by prepending zero to the univ

theorem fin.univ_cast_succ (n : ℕ) :

finset.univ = finset.cons (fin.last n) (finset.map fin.cast_succ.to_embedding finset.univ) _

Embed fin n into fin (n + 1) by appending a new fin.last n to the univ

theorem fin.univ_succ_above (n : ℕ) (p : fin (n + 1)) :

finset.univ = finset.cons p (finset.map p.succ_above.to_embedding finset.univ) _

Embed fin n into fin (n + 1) by inserting around a specified pivot p : fin (n + 1) into the univ

@[instance]

def unique.fintype {α : Type u_1} [unique α] :

Equations

unique.fintype = fintype.of_subsingleton inhabited.default

@[protected, instance]

def fintype.subtype_eq {α : Type u_1} (y : α) :

fintype {x // x = y}

Short-circuit instance to decrease search for unique.fintype, since that relies on a subsingleton elimination for unique.

Equations

fintype.subtype_eq y = fintype.subtype {y} _

@[protected, instance]

def fintype.subtype_eq' {α : Type u_1} (y : α) :

fintype {x // y = x}

Short-circuit instance to decrease search for unique.fintype, since that relies on a subsingleton elimination for unique.

Equations

fintype.subtype_eq' y = fintype.subtype {y} _

@[simp]

theorem fintype.card_subtype_eq {α : Type u_1} (y : α) [fintype {x // x = y}] :

fintype.card {x // x = y} = 1

@[simp]

theorem fintype.card_subtype_eq' {α : Type u_1} (y : α) [fintype {x // y = x}] :

fintype.card {x // y = x} = 1

@[simp]

theorem fintype.univ_empty :

finset.univ = ∅

@[simp]

theorem fintype.card_empty :

fintype.card empty = 0

@[simp]

theorem fintype.univ_pempty :

finset.univ = ∅

@[simp]

theorem fintype.card_pempty :

fintype.card pempty = 0

@[protected, instance]

def unit.fintype :

Equations

unit.fintype = fintype.of_subsingleton ()

theorem fintype.univ_unit :

finset.univ = {()}

theorem fintype.card_unit :

fintype.card unit = 1

@[protected, instance]

def punit.fintype :

Equations

punit.fintype = fintype.of_subsingleton punit.star

@[simp]

theorem fintype.univ_punit :

finset.univ = {punit.star}

@[simp]

theorem fintype.card_punit :

fintype.card punit = 1

@[protected, instance]

def bool.fintype :

Equations

bool.fintype = {elems := {val := bool.tt ::ₘ bool.ff ::ₘ 0, nodup := bool.fintype._proof_1}, complete := bool.fintype._proof_2}

@[simp]

theorem fintype.univ_bool :

finset.univ = {bool.tt, bool.ff}

@[protected, instance]

def units_int.fintype :

Equations

units_int.fintype = {elems := {1, -1}, complete := units_int.fintype._proof_1}

@[simp]

theorem units_int.univ :

finset.univ = {1, -1}

@[protected, instance]

def additive.fintype {α : Type u_1} [fintype α] :

fintype (additive α)

Equations

additive.fintype = id

@[protected, instance]

def multiplicative.fintype {α : Type u_1} [fintype α] :

fintype (multiplicative α)

Equations

multiplicative.fintype = id

@[simp]

theorem fintype.card_units_int :

fintype.card ℤ ˣ = 2

@[simp]

theorem fintype.card_bool :

fintype.card bool = 2

@[protected, instance]

def option.fintype {α : Type u_1} [fintype α] :

fintype (option α)

Equations

option.fintype = {elems := ⇑finset.insert_none finset.univ, complete := _}

theorem univ_option (α : Type u_1) [fintype α] :

finset.univ = ⇑finset.insert_none finset.univ

@[simp]

theorem fintype.card_option {α : Type u_1} [fintype α] :

fintype.card (option α) = fintype.card α + 1

def fintype_of_option {α : Type u_1} [fintype (option α)] :

If option α is a fintype then so is α

Equations

fintype_of_option = {elems := ⇑finset.erase_none (fintype.elems (option α)), complete := _}

def fintype_of_option_equiv {α : Type u_1} {β : Type u_2} [fintype α] (f : α ≃ option β) :

A type is a fintype if its successor (using option) is a fintype.

Equations

fintype_of_option_equiv f = fintype_of_option

@[protected, instance]

def sigma.fintype {α : Type u_1} (β : α → Type u_2) [fintype α] [Π (a : α), fintype (β a)] :

fintype (sigma β)

Equations

sigma.fintype β = {elems := finset.univ.sigma (λ (_x : α), finset.univ), complete := _}

@[simp]

theorem finset.univ_sigma_univ {α : Type u_1} {β : α → Type u_2} [fintype α] [Π (a : α), fintype (β a)] :

finset.univ.sigma (λ (a : α), finset.univ) = finset.univ

@[protected, instance]

def prod.fintype (α : Type u_1) (β : Type u_2) [fintype α] [fintype β] :

fintype (α × β)

Equations

prod.fintype α β = {elems := finset.univ.product finset.univ, complete := _}

@[simp]

theorem finset.univ_product_univ {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] :

finset.univ.product finset.univ = finset.univ

@[simp]

theorem fintype.card_prod (α : Type u_1) (β : Type u_2) [fintype α] [fintype β] :

fintype.card (α × β) = fintype.card α * fintype.card β

def fintype.prod_left {α : Type u_1} {β : Type u_2} [decidable_eq α] [fintype (α × β)] [nonempty β] :

Given that α × β is a fintype, α is also a fintype.

Equations

fintype.prod_left = {elems := finset.image prod.fst (fintype.elems (α × β)), complete := _}

def fintype.prod_right {α : Type u_1} {β : Type u_2} [decidable_eq β] [fintype (α × β)] [nonempty α] :

Given that α × β is a fintype, β is also a fintype.

Equations

fintype.prod_right = {elems := finset.image prod.snd (fintype.elems (α × β)), complete := _}

@[protected, instance]

def ulift.fintype (α : Type u_1) [fintype α] :

fintype (ulift α)

Equations

ulift.fintype α = fintype.of_equiv α equiv.ulift.symm

@[simp]

theorem fintype.card_ulift (α : Type u_1) [fintype α] :

fintype.card (ulift α) = fintype.card α

@[protected, instance]

def plift.fintype (α : Type u_1) [fintype α] :

fintype (plift α)

Equations

plift.fintype α = fintype.of_equiv α equiv.plift.symm

@[simp]

theorem fintype.card_plift (α : Type u_1) [fintype α] :

fintype.card (plift α) = fintype.card α

@[protected, instance]

def order_dual.fintype (α : Type u_1) [fintype α] :

fintype αᵒᵈ

Equations

order_dual.fintype α = _inst_1

@[simp]

theorem fintype.card_order_dual (α : Type u_1) [fintype α] :

fintype.card αᵒᵈ = fintype.card α

@[protected, instance]

def lex.fintype (α : Type u_1) [fintype α] :

fintype (lex α)

Equations

lex.fintype α = _inst_1

@[simp]

theorem fintype.card_lex (α : Type u_1) [fintype α] :

fintype.card (lex α) = fintype.card α

theorem univ_sum_type {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] [fintype (α ⊕ β)] [decidable_eq (α ⊕ β)] :

finset.univ = finset.map function.embedding.inl finset.univ ∪ finset.map function.embedding.inr finset.univ

@[protected, instance]

def sum.fintype (α : Type u) (β : Type v) [fintype α] [fintype β] :

fintype (α ⊕ β)

Equations

sum.fintype α β = fintype.of_equiv (Σ (b : bool), cond b (ulift α) (ulift β)) ((equiv.sum_equiv_sigma_bool (ulift α) (ulift β)).symm.trans (equiv.ulift.sum_congr equiv.ulift))

noncomputable def fintype.sum_left {α : Type u_1} {β : Type u_2} [fintype (α ⊕ β)] :

Given that α ⊕ β is a fintype, α is also a fintype. This is non-computable as it uses that sum.inl is an injection, but there's no clear inverse if α is empty.

Equations

fintype.sum_left = fintype.of_injective sum.inl sum.inl_injective

noncomputable def fintype.sum_right {α : Type u_1} {β : Type u_2} [fintype (α ⊕ β)] :

Given that α ⊕ β is a fintype, β is also a fintype. This is non-computable as it uses that sum.inr is an injection, but there's no clear inverse if β is empty.

Equations

fintype.sum_right = fintype.of_injective sum.inr sum.inr_injective

@[simp]

theorem fintype.card_sum {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] :

fintype.card (α ⊕ β) = fintype.card α + fintype.card β

def fintype_of_fintype_ne {α : Type u_1} (a : α) [decidable_pred (λ (_x : α), _x = a)] (h : fintype {b // b ≠ a}) :

If the subtype of all-but-one elements is a fintype then the type itself is a fintype.

Equations

fintype_of_fintype_ne a h = fintype.of_equiv ({a_1 // a_1 = a} ⊕ {a_1 // ¬a_1 = a}) (equiv.sum_compl (λ (_x : α), _x = a))

`fintype (s : finset α)` #

@[protected, instance]

def finset.fintype_coe_sort {α : Type u} (s : finset α) :

Equations

s.fintype_coe_sort = {elems := s.attach, complete := _}

@[simp]

theorem finset.univ_eq_attach {α : Type u} (s : finset α) :

finset.univ = s.attach

theorem fintype.card_le_of_injective {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α → β) (hf : function.injective f) :

fintype.card α ≤ fintype.card β

theorem fintype.card_le_of_embedding {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α ↪ β) :

fintype.card α ≤ fintype.card β

theorem fintype.card_lt_of_injective_of_not_mem {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α → β) (h : function.injective f) {b : β} (w : b ∉ set.range f) :

fintype.card α < fintype.card β

theorem fintype.card_lt_of_injective_not_surjective {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α → β) (h : function.injective f) (h' : ¬function.surjective f) :

fintype.card α < fintype.card β

theorem fintype.card_le_of_surjective {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α → β) (h : function.surjective f) :

fintype.card β ≤ fintype.card α

theorem fintype.card_range_le {α : Type u_1} {β : Type u_2} (f : α → β) [fintype α] [fintype ↥(set.range f)] :

fintype.card ↥(set.range f) ≤ fintype.card α

theorem fintype.card_range {α : Type u_1} {β : Type u_2} {F : Type u_3} [embedding_like F α β] (f : F) [fintype α] [fintype ↥(set.range ⇑f)] :

fintype.card ↥(set.range ⇑f) = fintype.card α

theorem fintype.exists_ne_map_eq_of_card_lt {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α → β) (h : fintype.card β < fintype.card α) :

∃ (x y : α), x ≠ y ∧ f x = f y

The pigeonhole principle for finitely many pigeons and pigeonholes. This is the fintype version of finset.exists_ne_map_eq_of_card_lt_of_maps_to.

theorem fintype.card_eq_one_iff {α : Type u_1} [fintype α] :

fintype.card α = 1 ↔ ∃ (x : α), ∀ (y : α), y = x

theorem fintype.card_eq_zero_iff {α : Type u_1} [fintype α] :

fintype.card α = 0 ↔ is_empty α

theorem fintype.card_eq_zero {α : Type u_1} [fintype α] [is_empty α] :

fintype.card α = 0

theorem fintype.card_eq_one_iff_nonempty_unique {α : Type u_1} [fintype α] :

fintype.card α = 1 ↔ nonempty (unique α)

def fintype.card_eq_zero_equiv_equiv_empty {α : Type u_1} [fintype α] :

fintype.card α = 0 ≃ (α ≃ empty)

A fintype with cardinality zero is equivalent to empty.

Equations

fintype.card_eq_zero_equiv_equiv_empty = (equiv.of_iff fintype.card_eq_zero_iff).trans (equiv.equiv_empty_equiv α).symm

theorem fintype.card_pos_iff {α : Type u_1} [fintype α] :

0 < fintype.card α ↔ nonempty α

theorem fintype.card_pos {α : Type u_1} [fintype α] [h : nonempty α] :

0 < fintype.card α

theorem fintype.card_ne_zero {α : Type u_1} [fintype α] [nonempty α] :

fintype.card α ≠ 0

theorem fintype.card_le_one_iff {α : Type u_1} [fintype α] :

fintype.card α ≤ 1 ↔ ∀ (a b : α), a = b

theorem fintype.card_le_one_iff_subsingleton {α : Type u_1} [fintype α] :

fintype.card α ≤ 1 ↔ subsingleton α

theorem fintype.one_lt_card_iff_nontrivial {α : Type u_1} [fintype α] :

1 < fintype.card α ↔ nontrivial α

theorem fintype.exists_ne_of_one_lt_card {α : Type u_1} [fintype α] (h : 1 < fintype.card α) (a : α) :

∃ (b : α), b ≠ a

theorem fintype.exists_pair_of_one_lt_card {α : Type u_1} [fintype α] (h : 1 < fintype.card α) :

∃ (a b : α), a ≠ b

theorem fintype.card_eq_one_of_forall_eq {α : Type u_1} [fintype α] {i : α} (h : ∀ (j : α), j = i) :

fintype.card α = 1

theorem fintype.one_lt_card {α : Type u_1} [fintype α] [h : nontrivial α] :

1 < fintype.card α

theorem fintype.one_lt_card_iff {α : Type u_1} [fintype α] :

1 < fintype.card α ↔ ∃ (a b : α), a ≠ b

theorem fintype.two_lt_card_iff {α : Type u_1} [fintype α] :

2 < fintype.card α ↔ ∃ (a b c : α), a ≠ b ∧ a ≠ c ∧ b ≠ c

theorem fintype.injective_iff_surjective {α : Type u_1} [fintype α] {f : α → α} :

function.injective f ↔ function.surjective f

theorem fintype.injective_iff_bijective {α : Type u_1} [fintype α] {f : α → α} :

function.injective f ↔ function.bijective f

theorem fintype.surjective_iff_bijective {α : Type u_1} [fintype α] {f : α → α} :

function.surjective f ↔ function.bijective f

theorem fintype.injective_iff_surjective_of_equiv {α : Type u_1} [fintype α] {β : Type u_2} {f : α → β} (e : α ≃ β) :

function.injective f ↔ function.surjective f

theorem function.injective.surjective_of_fintype {α : Type u_1} [fintype α] {β : Type u_2} {f : α → β} (e : α ≃ β) :

function.injective f → function.surjective f

Alias of the forward direction of fintype.injective_iff_surjective_of_equiv.

theorem function.surjective.injective_of_fintype {α : Type u_1} [fintype α] {β : Type u_2} {f : α → β} (e : α ≃ β) :

function.surjective f → function.injective f

Alias of the reverse direction of fintype.injective_iff_surjective_of_equiv.

theorem fintype.card_of_bijective {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] {f : α → β} (hf : function.bijective f) :

fintype.card α = fintype.card β

theorem fintype.bijective_iff_injective_and_card {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α → β) :

function.bijective f ↔ function.injective f ∧ fintype.card α = fintype.card β

theorem fintype.bijective_iff_surjective_and_card {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α → β) :

function.bijective f ↔ function.surjective f ∧ fintype.card α = fintype.card β

theorem function.left_inverse.right_inverse_of_card_le {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] {f : α → β} {g : β → α} (hfg : function.left_inverse f g) (hcard : fintype.card α ≤ fintype.card β) :

function.right_inverse f g

theorem function.right_inverse.left_inverse_of_card_le {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] {f : α → β} {g : β → α} (hfg : function.right_inverse f g) (hcard : fintype.card β ≤ fintype.card α) :

function.left_inverse f g

def equiv.of_left_inverse_of_card_le {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (hβα : fintype.card β ≤ fintype.card α) (f : α → β) (g : β → α) (h : function.left_inverse g f) :

α ≃ β

Construct an equivalence from functions that are inverse to each other.

Equations

equiv.of_left_inverse_of_card_le hβα f g h = {to_fun := f, inv_fun := g, left_inv := h, right_inv := _}

@[simp]

theorem equiv.of_left_inverse_of_card_le_symm_apply {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (hβα : fintype.card β ≤ fintype.card α) (f : α → β) (g : β → α) (h : function.left_inverse g f) (ᾰ : β) :

⇑((equiv.of_left_inverse_of_card_le hβα f g h).symm) ᾰ = g ᾰ

@[simp]

theorem equiv.of_left_inverse_of_card_le_apply {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (hβα : fintype.card β ≤ fintype.card α) (f : α → β) (g : β → α) (h : function.left_inverse g f) (ᾰ : α) :

⇑(equiv.of_left_inverse_of_card_le hβα f g h) ᾰ = f ᾰ

def equiv.of_right_inverse_of_card_le {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (hαβ : fintype.card α ≤ fintype.card β) (f : α → β) (g : β → α) (h : function.right_inverse g f) :

α ≃ β

Construct an equivalence from functions that are inverse to each other.

Equations

equiv.of_right_inverse_of_card_le hαβ f g h = {to_fun := f, inv_fun := g, left_inv := _, right_inv := h}

@[simp]

theorem equiv.of_right_inverse_of_card_le_symm_apply {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (hαβ : fintype.card α ≤ fintype.card β) (f : α → β) (g : β → α) (h : function.right_inverse g f) (ᾰ : β) :

⇑((equiv.of_right_inverse_of_card_le hαβ f g h).symm) ᾰ = g ᾰ

@[simp]

theorem equiv.of_right_inverse_of_card_le_apply {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (hαβ : fintype.card α ≤ fintype.card β) (f : α → β) (g : β → α) (h : function.right_inverse g f) (ᾰ : α) :

⇑(equiv.of_right_inverse_of_card_le hαβ f g h) ᾰ = f ᾰ

theorem fintype.coe_image_univ {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} :

↑(finset.image f finset.univ) = set.range f

@[protected, instance]

def list.subtype.fintype {α : Type u_1} [decidable_eq α] (l : list α) :

fintype {x // x ∈ l}

Equations

list.subtype.fintype l = fintype.of_list l.attach _

@[protected, instance]

def multiset.subtype.fintype {α : Type u_1} [decidable_eq α] (s : multiset α) :

fintype {x // x ∈ s}

Equations

multiset.subtype.fintype s = fintype.of_multiset s.attach _

@[protected, instance]

def finset.subtype.fintype {α : Type u_1} (s : finset α) :

fintype {x // x ∈ s}

Equations

finset.subtype.fintype s = {elems := s.attach, complete := _}

@[protected, instance]

def finset_coe.fintype {α : Type u_1} (s : finset α) :

fintype ↥↑s

Equations

finset_coe.fintype s = finset.subtype.fintype s

@[simp]

theorem fintype.card_coe {α : Type u_1} (s : finset α) [fintype ↥s] :

fintype.card ↥s = s.card

theorem finset.attach_eq_univ {α : Type u_1} {s : finset α} :

s.attach = finset.univ

@[protected, instance]

def plift.fintype_Prop (p : Prop) [decidable p] :

fintype (plift p)

Equations

plift.fintype_Prop p = {elems := dite p (λ (h : p), {{down := h}}) (λ (h : ¬p), ∅), complete := _}

@[protected, instance]

def Prop.fintype :

Equations

Prop.fintype = {elems := {val := true ::ₘ false ::ₘ 0, nodup := Prop.fintype._proof_1}, complete := Prop.fintype._proof_2}

@[simp]

theorem fintype.card_Prop :

fintype.card Prop = 2

@[protected, instance]

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

fintype {x // p x}

Equations

subtype.fintype p = fintype.subtype (finset.filter p finset.univ) _

@[simp]

theorem set.to_finset_eq_empty_iff {α : Type u_1} {s : set α} [fintype ↥s] :

s.to_finset = ∅ ↔ s = ∅

@[simp]

theorem set.to_finset_empty {α : Type u_1} :

∅.to_finset = ∅

def set_fintype {α : Type u_1} [fintype α] (s : set α) [decidable_pred (λ (_x : α), _x ∈ s)] :

A set on a fintype, when coerced to a type, is a fintype.

Equations

set_fintype s = subtype.fintype (λ (x : α), x ∈ s)

theorem set_fintype_card_le_univ {α : Type u_1} [fintype α] (s : set α) [fintype ↥s] :

fintype.card ↥s ≤ fintype.card α

theorem set_fintype_card_eq_univ_iff {α : Type u_1} [fintype α] (s : set α) [fintype ↥s] :

fintype.card ↥s = fintype.card α ↔ s = set.univ

@[simp]

theorem coe_units_equiv_prod_subtype_symm_apply (α : Type u_1) [monoid α] (p : {p // p.fst * p.snd = 1 ∧ p.snd * p.fst = 1}) :

↑(⇑((units_equiv_prod_subtype α).symm) p) = ↑p.fst

@[simp]

theorem units_equiv_prod_subtype_apply_coe (α : Type u_1) [monoid α] (u : αˣ) :

↑(⇑(units_equiv_prod_subtype α) u) = (↑u, ↑u⁻¹)

@[simp]

theorem coe_inv_units_equiv_prod_subtype_symm_apply (α : Type u_1) [monoid α] (p : {p // p.fst * p.snd = 1 ∧ p.snd * p.fst = 1}) :

↑(⇑((units_equiv_prod_subtype α).symm) p)⁻¹ = ↑p.snd

def units_equiv_prod_subtype (α : Type u_1) [monoid α] :

αˣ ≃ {p // p.fst * p.snd = 1 ∧ p.snd * p.fst = 1}

The αˣ type is equivalent to a subtype of α × α.

Equations

units_equiv_prod_subtype α = {to_fun := λ (u : αˣ), ⟨(↑u, ↑u⁻¹), _⟩, inv_fun := λ (p : {p // p.fst * p.snd = 1 ∧ p.snd * p.fst = 1}), {val := ↑p.fst, inv := ↑p.snd, val_inv := _, inv_val := _}, left_inv := _, right_inv := _}

@[simp]

theorem units_equiv_ne_zero_apply_coe (α : Type u_1) [group_with_zero α] (a : αˣ) :

↑(⇑(units_equiv_ne_zero α) a) = ↑a

def units_equiv_ne_zero (α : Type u_1) [group_with_zero α] :

αˣ ≃ {a // a ≠ 0}

In a group_with_zero α, the unit group αˣ is equivalent to the subtype of nonzero elements.

Equations

units_equiv_ne_zero α = {to_fun := λ (a : αˣ), ⟨↑a, _⟩, inv_fun := λ (a : {a // a ≠ 0}), units.mk0 ↑a _, left_inv := _, right_inv := _}

@[simp]

theorem units_equiv_ne_zero_symm_apply (α : Type u_1) [group_with_zero α] (a : {a // a ≠ 0}) :

⇑((units_equiv_ne_zero α).symm) a = units.mk0 ↑a _

@[protected, instance]

def units.fintype {α : Type u_1} [monoid α] [fintype α] [decidable_eq α] :

Equations

units.fintype = fintype.of_equiv {p // p.fst * p.snd = 1 ∧ p.snd * p.fst = 1} (units_equiv_prod_subtype α).symm

theorem fintype.card_units {α : Type u_1} [group_with_zero α] [fintype α] [fintype αˣ] :

fintype.card αˣ = fintype.card α - 1

noncomputable def function.embedding.equiv_of_fintype_self_embedding {α : Type u_1} [fintype α] (e : α ↪ α) :

α ≃ α

An embedding from a fintype to itself can be promoted to an equivalence.

Equations

e.equiv_of_fintype_self_embedding = equiv.of_bijective ⇑e _

@[simp]

theorem function.embedding.equiv_of_fintype_self_embedding_to_embedding {α : Type u_1} [fintype α] (e : α ↪ α) :

e.equiv_of_fintype_self_embedding.to_embedding = e

@[simp]

theorem function.embedding.is_empty_of_card_lt {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (h : fintype.card β < fintype.card α) :

is_empty (α ↪ β)

If ‖β‖ < ‖α‖ there are no embeddings α ↪ β. This is a formulation of the pigeonhole principle.

Note this cannot be an instance as it needs h.

def function.embedding.trunc_of_card_le {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] [decidable_eq α] [decidable_eq β] (h : fintype.card α ≤ fintype.card β) :

trunc (α ↪ β)

A constructive embedding of a fintype α in another fintype β when card α ≤ card β.

Equations

function.embedding.trunc_of_card_le h = (fintype.trunc_equiv_fin α).bind (λ (ea : α ≃ fin (fintype.card α)), trunc.map (λ (eb : β ≃ fin (fintype.card β)), ea.to_embedding.trans ((fin.cast_le h).to_embedding.trans eb.symm.to_embedding)) (fintype.trunc_equiv_fin β))

theorem function.embedding.nonempty_of_card_le {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (h : fintype.card α ≤ fintype.card β) :

nonempty (α ↪ β)

theorem function.embedding.exists_of_card_le_finset {α : Type u_1} {β : Type u_2} [fintype α] {s : finset β} (h : fintype.card α ≤ s.card) :

∃ (f : α ↪ β), set.range ⇑f ⊆ ↑s

@[simp]

theorem finset.univ_map_embedding {α : Type u_1} [fintype α] (e : α ↪ α) :

finset.map e finset.univ = finset.univ

noncomputable def fintype.finset_equiv_set {α : Type u_1} [fintype α] :

finset α ≃ set α

Given fintype α, finset_equiv_set is the equiv between finset α and set α. (All sets on a finite type are finite.)

Equations

fintype.finset_equiv_set = {to_fun := coe coe_to_lift, inv_fun := λ (s : set α), s.to_finset, left_inv := _, right_inv := _}

@[simp]

theorem fintype.finset_equiv_set_apply {α : Type u_1} [fintype α] (s : finset α) :

⇑fintype.finset_equiv_set s = ↑s

@[simp]

theorem fintype.finset_equiv_set_symm_apply {α : Type u_1} [fintype α] (s : set α) [fintype ↥s] :

⇑(fintype.finset_equiv_set.symm) s = s.to_finset

theorem fintype.card_lt_of_surjective_not_injective {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] (f : α → β) (h : function.surjective f) (h' : ¬function.injective f) :

fintype.card β < fintype.card α

def fintype.pi_finset {α : Type u_1} [decidable_eq α] [fintype α] {δ : α → Type u_4} (t : Π (a : α), finset (δ a)) :

finset (Π (a : α), δ a)

Given for all a : α a finset t a of δ a, then one can define the finset fintype.pi_finset t of all functions taking values in t a for all a. This is the analogue of finset.pi where the base finset is univ (but formally they are not the same, as there is an additional condition i ∈ finset.univ in the finset.pi definition).

Equations

fintype.pi_finset t = finset.map {to_fun := λ (f : Π (a : α), a ∈ finset.univ → δ a) (a : α), f a _, inj' := _} (finset.univ.pi t)

@[simp]

theorem fintype.mem_pi_finset {α : Type u_1} [decidable_eq α] [fintype α] {δ : α → Type u_4} {t : Π (a : α), finset (δ a)} {f : Π (a : α), δ a} :

f ∈ fintype.pi_finset t ↔ ∀ (a : α), f a ∈ t a

@[simp]

theorem fintype.coe_pi_finset {α : Type u_1} [decidable_eq α] [fintype α] {δ : α → Type u_4} (t : Π (a : α), finset (δ a)) :

↑(fintype.pi_finset t) = set.univ.pi (λ (a : α), ↑(t a))

theorem fintype.pi_finset_subset {α : Type u_1} [decidable_eq α] [fintype α] {δ : α → Type u_4} (t₁ t₂ : Π (a : α), finset (δ a)) (h : ∀ (a : α), t₁ a ⊆ t₂ a) :

fintype.pi_finset t₁ ⊆ fintype.pi_finset t₂

theorem fintype.pi_finset_disjoint_of_disjoint {α : Type u_1} [decidable_eq α] [fintype α] {δ : α → Type u_4} [Π (a : α), decidable_eq (δ a)] (t₁ t₂ : Π (a : α), finset (δ a)) {a : α} (h : disjoint (t₁ a) (t₂ a)) :

disjoint (fintype.pi_finset t₁) (fintype.pi_finset t₂)

pi #

@[protected, instance]

def pi.fintype {α : Type u_1} {β : α → Type u_2} [decidable_eq α] [fintype α] [Π (a : α), fintype (β a)] :

fintype (Π (a : α), β a)

A dependent product of fintypes, indexed by a fintype, is a fintype.

Equations

pi.fintype = {elems := fintype.pi_finset (λ (_x : α), finset.univ), complete := _}

@[simp]

theorem fintype.pi_finset_univ {α : Type u_1} {β : α → Type u_2} [decidable_eq α] [fintype α] [Π (a : α), fintype (β a)] :

fintype.pi_finset (λ (a : α), finset.univ) = finset.univ

@[protected, instance]

def d_array.fintype {n : ℕ} {α : fin n → Type u_1} [Π (n : fin n), fintype (α n)] :

fintype (d_array n α)

Equations

d_array.fintype = fintype.of_equiv (Π (i : fin n), α i) (equiv.d_array_equiv_fin α).symm

@[protected, instance]

def array.fintype {n : ℕ} {α : Type u_1} [fintype α] :

fintype (array n α)

Equations

array.fintype = d_array.fintype

@[protected, instance]

def vector.fintype {α : Type u_1} [fintype α] {n : ℕ} :

fintype (vector α n)

Equations

vector.fintype = fintype.of_equiv (fin n → α) (equiv.vector_equiv_fin α n).symm

@[protected, instance]

def quotient.fintype {α : Type u_1} [fintype α] (s : setoid α) [decidable_rel has_equiv.equiv] :

fintype (quotient s)

Equations

quotient.fintype s = fintype.of_surjective quotient.mk _

@[protected, instance]

def finset.fintype {α : Type u_1} [fintype α] :

fintype (finset α)

Equations

finset.fintype = {elems := finset.univ.powerset, complete := _}

@[protected, instance]

def function.embedding.fintype {α : Type u_1} {β : Type u_2} [fintype α] [fintype β] [decidable_eq α] [decidable_eq β] :

fintype (α ↪ β)

Equations

function.embedding.fintype = fintype.of_equiv {f // function.injective f} (equiv.subtype_injective_equiv_embedding α β)

@[protected, instance]

def sym.sym'.fintype {α : Type u_1} [decidable_eq α] [fintype α] {n : ℕ} :

fintype (sym.sym' α n)

Equations

sym.sym'.fintype = quotient.fintype (vector.perm.is_setoid α n)

@[protected, instance]

def sym.fintype {α : Type u_1} [decidable_eq α] [fintype α] {n : ℕ} :

fintype (sym α n)

Equations

sym.fintype = fintype.of_equiv (sym.sym' α n) sym.sym_equiv_sym'.symm

@[simp]

theorem fintype.card_finset {α : Type u_1} [fintype α] :

fintype.card (finset α) = 2 ^ fintype.card α

theorem finset.mem_powerset_len_univ_iff {α : Type u_1} [fintype α] {s : finset α} {k : ℕ} :

s ∈ finset.powerset_len k finset.univ ↔ s.card = k

@[simp]

theorem finset.univ_filter_card_eq (α : Type u_1) [fintype α] (k : ℕ) :

finset.filter (λ (s : finset α), s.card = k) finset.univ = finset.powerset_len k finset.univ

@[simp]

theorem fintype.card_finset_len {α : Type u_1} [fintype α] (k : ℕ) :

fintype.card {s // s.card = k} = (fintype.card α).choose k

theorem fintype.card_subtype_le {α : Type u_1} [fintype α] (p : α → Prop) [decidable_pred p] :

fintype.card {x // p x} ≤ fintype.card α

theorem fintype.card_subtype_lt {α : Type u_1} [fintype α] {p : α → Prop} [decidable_pred p] {x : α} (hx : ¬p x) :

fintype.card {x // p x} < fintype.card α

theorem fintype.card_subtype {α : Type u_1} [fintype α] (p : α → Prop) [decidable_pred p] :

fintype.card {x // p x} = (finset.filter p finset.univ).card

theorem fintype.card_subtype_or {α : Type u_1} (p q : α → Prop) [fintype {x // p x}] [fintype {x // q x}] [fintype {x // p x ∨ q x}] :

fintype.card {x // p x ∨ q x} ≤ fintype.card {x // p x} + fintype.card {x // q x}

theorem fintype.card_subtype_or_disjoint {α : Type u_1} (p q : α → Prop) (h : disjoint p q) [fintype {x // p x}] [fintype {x // q x}] [fintype {x // p x ∨ q x}] :

fintype.card {x // p x ∨ q x} = fintype.card {x // p x} + fintype.card {x // q x}

@[simp]

theorem fintype.card_subtype_compl {α : Type u_1} [fintype α] (p : α → Prop) [fintype {x // p x}] [fintype {x // ¬p x}] :

fintype.card {x // ¬p x} = fintype.card α - fintype.card {x // p x}

theorem card_subtype_mono {α : Type u_1} (p q : α → Prop) (h : p ≤ q) [fintype {x // p x}] [fintype {x // q x}] :

fintype.card {x // p x} ≤ fintype.card {x // q x}

theorem fintype.card_compl_eq_card_compl {α : Type u_1} [fintype α] (p q : α → Prop) [fintype {x // p x}] [fintype {x // ¬p x}] [fintype {x // q x}] [fintype {x // ¬q x}] (h : fintype.card {x // p x} = fintype.card {x // q x}) :

fintype.card {x // ¬p x} = fintype.card {x // ¬q x}

If two subtypes of a fintype have equal cardinality, so do their complements.

theorem fintype.card_quotient_le {α : Type u_1} [fintype α] (s : setoid α) [decidable_rel has_equiv.equiv] :

fintype.card (quotient s) ≤ fintype.card α

theorem fintype.card_quotient_lt {α : Type u_1} [fintype α] {s : setoid α} [decidable_rel has_equiv.equiv] {x y : α} (h1 : x ≠ y) (h2 : x ≈ y) :

fintype.card (quotient s) < fintype.card α

@[protected, instance]

def psigma.fintype {α : Type u_1} {β : α → Type u_2} [fintype α] [Π (a : α), fintype (β a)] :

fintype (Σ' (a : α), β a)

Equations

psigma.fintype = fintype.of_equiv (Σ (i : α), β i) (equiv.psigma_equiv_sigma (λ (a : α), β a)).symm

@[protected, instance]

def psigma.fintype_prop_left {α : Prop} {β : α → Type u_1} [decidable α] [Π (a : α), fintype (β a)] :

fintype (Σ' (a : α), β a)

Equations

psigma.fintype_prop_left = dite α (λ (h : α), fintype.of_equiv (β h) {to_fun := λ (x : β h), ⟨h, x⟩, inv_fun := psigma.snd (λ (a : α), β a), left_inv := _, right_inv := _}) (λ (h : ¬α), {elems := ∅, complete := _})

@[protected, instance]

def psigma.fintype_prop_right {α : Type u_1} {β : α → Prop} [Π (a : α), decidable (β a)] [fintype α] :

fintype (Σ' (a : α), β a)

Equations

psigma.fintype_prop_right = fintype.of_equiv {a // β a} {to_fun := λ (_x : {a // β a}), psigma.fintype_prop_right._match_1 _x, inv_fun := λ (_x : Σ' (a : α), β a), psigma.fintype_prop_right._match_2 _x, left_inv := _, right_inv := _}
psigma.fintype_prop_right._match_1 ⟨x, y⟩ = ⟨x, y⟩
psigma.fintype_prop_right._match_2 ⟨x, y⟩ = ⟨x, y⟩

@[protected, instance]

def psigma.fintype_prop_prop {α : Prop} {β : α → Prop} [decidable α] [Π (a : α), decidable (β a)] :

fintype (Σ' (a : α), β a)

Equations

psigma.fintype_prop_prop = dite (∃ (a : α), β a) (λ (h : ∃ (a : α), β a), {elems := {⟨_, _⟩}, complete := _}) (λ (h : ¬∃ (a : α), β a), {elems := ∅, complete := _})

@[protected, instance]

def set.fintype {α : Type u_1} [fintype α] :

fintype (set α)

Equations

set.fintype = {elems := finset.map {to_fun := coe coe_to_lift, inj' := _} finset.univ.powerset, complete := _}

@[simp]

theorem fintype.card_set {α : Type u_1} [fintype α] :

fintype.card (set α) = 2 ^ fintype.card α

@[protected, instance]

def pfun_fintype (p : Prop) [decidable p] (α : p → Type u_1) [Π (hp : p), fintype (α hp)] :

fintype (Π (hp : p), α hp)

Equations

pfun_fintype p α = dite p (λ (hp : p), fintype.of_equiv (α hp) {to_fun := λ (a : α hp) (_x : p), a, inv_fun := λ (f : Π (hp : p), α hp), f hp, left_inv := _, right_inv := _}) (λ (hp : ¬p), {elems := {λ (h : p), _.elim}, complete := _})

@[simp]

theorem finset.univ_pi_univ {α : Type u_1} {β : α → Type u_2} [decidable_eq α] [fintype α] [Π (a : α), fintype (β a)] :

finset.univ.pi (λ (a : α), finset.univ) = finset.univ

theorem mem_image_univ_iff_mem_range {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} {b : β} :

b ∈ finset.image f finset.univ ↔ b ∈ set.range f

def quotient.fin_choice_aux {ι : Type u_1} [decidable_eq ι] {α : ι → Type u_2} [S : Π (i : ι), setoid (α i)] (l : list ι) :

(Π (i : ι), i ∈ l → quotient (S i)) → quotient pi_setoid

An auxiliary function for quotient.fin_choice. Given a collection of setoids indexed by a type ι, a (finite) list l of indices, and a function that for each i ∈ l gives a term of the corresponding quotient type, then there is a corresponding term in the quotient of the product of the setoids indexed by l.

Equations

quotient.fin_choice_aux (i :: l) f = (f i _).lift_on₂ (quotient.fin_choice_aux l (λ (j : ι) (h : j ∈ l), f j _)) (λ (a : α i) (l_1 : Π (i : ι), i ∈ l → α i), ⟦(λ (j : ι) (h : j ∈ i :: l), dite (j = i) (λ (e : j = i), _.mpr a) (λ (e : ¬j = i), l_1 j _))⟧) _
quotient.fin_choice_aux list.nil f = ⟦(λ (i : ι), false.elim)⟧

theorem quotient.fin_choice_aux_eq {ι : Type u_1} [decidable_eq ι] {α : ι → Type u_2} [S : Π (i : ι), setoid (α i)] (l : list ι) (f : Π (i : ι), i ∈ l → α i) :

quotient.fin_choice_aux l (λ (i : ι) (h : i ∈ l), ⟦f i h⟧) = ⟦f⟧

def quotient.fin_choice {ι : Type u_1} [decidable_eq ι] [fintype ι] {α : ι → Type u_2} [S : Π (i : ι), setoid (α i)] (f : Π (i : ι), quotient (S i)) :

quotient pi_setoid

Given a collection of setoids indexed by a fintype ι and a function that for each i : ι gives a term of the corresponding quotient type, then there is corresponding term in the quotient of the product of the setoids.

Equations

quotient.fin_choice f = quotient.lift_on (quotient.rec_on finset.univ.val (λ (l : list ι), quotient.fin_choice_aux l (λ (i : ι) (_x : i ∈ l), f i)) _) (λ (f : Π (i : ι), i ∈ finset.univ.val → α i), ⟦(λ (i : ι), f i _)⟧) quotient.fin_choice._proof_2

theorem quotient.fin_choice_eq {ι : Type u_1} [decidable_eq ι] [fintype ι] {α : ι → Type u_2} [Π (i : ι), setoid (α i)] (f : Π (i : ι), α i) :

quotient.fin_choice (λ (i : ι), ⟦f i⟧) = ⟦f⟧

def perms_of_list {α : Type u_1} [decidable_eq α] :

list α → list (equiv.perm α)

Given a list, produce a list of all permutations of its elements.

Equations

perms_of_list (a :: l) = perms_of_list l ++ l.bind (λ (b : α), list.map (λ (f : equiv.perm α), equiv.swap a b * f) (perms_of_list l))
perms_of_list list.nil = [1]

theorem length_perms_of_list {α : Type u_1} [decidable_eq α] (l : list α) :

(perms_of_list l).length = l.length.factorial

theorem mem_perms_of_list_of_mem {α : Type u_1} [decidable_eq α] {l : list α} {f : equiv.perm α} (h : ∀ (x : α), ⇑f x ≠ x → x ∈ l) :

f ∈ perms_of_list l

theorem mem_of_mem_perms_of_list {α : Type u_1} [decidable_eq α] {l : list α} {f : equiv.perm α} :

f ∈ perms_of_list l → ∀ {x : α}, ⇑f x ≠ x → x ∈ l

theorem mem_perms_of_list_iff {α : Type u_1} [decidable_eq α] {l : list α} {f : equiv.perm α} :

f ∈ perms_of_list l ↔ ∀ {x : α}, ⇑f x ≠ x → x ∈ l

theorem nodup_perms_of_list {α : Type u_1} [decidable_eq α] {l : list α} (hl : l.nodup) :

(perms_of_list l).nodup

def perms_of_finset {α : Type u_1} [decidable_eq α] (s : finset α) :

finset (equiv.perm α)

Given a finset, produce the finset of all permutations of its elements.

Equations

perms_of_finset s = quotient.hrec_on s.val (λ (l : list α) (hl : multiset.nodup ⟦l⟧), {val := ↑(perms_of_list l), nodup := _}) perms_of_finset._proof_2 _

theorem mem_perms_of_finset_iff {α : Type u_1} [decidable_eq α] {s : finset α} {f : equiv.perm α} :

f ∈ perms_of_finset s ↔ ∀ {x : α}, ⇑f x ≠ x → x ∈ s

theorem card_perms_of_finset {α : Type u_1} [decidable_eq α] (s : finset α) :

(perms_of_finset s).card = s.card.factorial

def fintype_perm {α : Type u_1} [decidable_eq α] [fintype α] :

fintype (equiv.perm α)

The collection of permutations of a fintype is a fintype.

Equations

fintype_perm = {elems := perms_of_finset finset.univ, complete := _}

@[protected, instance]

def equiv.fintype {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] [fintype α] [fintype β] :

fintype (α ≃ β)

Equations

equiv.fintype = dite (fintype.card β = fintype.card α) (λ (h : fintype.card β = fintype.card α), (fintype.trunc_equiv_fin α).rec_on_subsingleton (λ (eα : α ≃ fin (fintype.card α)), (fintype.trunc_equiv_fin β).rec_on_subsingleton (λ (eβ : β ≃ fin (fintype.card β)), fintype.of_equiv (equiv.perm α) ((equiv.refl α).equiv_congr (eα.trans (h.rec_on eβ.symm)))))) (λ (h : ¬fintype.card β = fintype.card α), {elems := ∅, complete := _})

theorem fintype.card_perm {α : Type u_1} [decidable_eq α] [fintype α] :

fintype.card (equiv.perm α) = (fintype.card α).factorial

theorem fintype.card_equiv {α : Type u_1} {β : Type u_2} [decidable_eq α] [decidable_eq β] [fintype α] [fintype β] (e : α ≃ β) :

fintype.card (α ≃ β) = (fintype.card α).factorial

theorem univ_eq_singleton_of_card_one {α : Type u_1} [fintype α] (x : α) (h : fintype.card α = 1) :

finset.univ = {x}

def fintype.choose_x {α : Type u_1} [fintype α] (p : α → Prop) [decidable_pred p] (hp : ∃! (a : α), p a) :

{a // p a}

Given a fintype α and a predicate p, associate to a proof that there is a unique element of α satisfying p this unique element, as an element of the corresponding subtype.

Equations

fintype.choose_x p hp = ⟨finset.choose p finset.univ _, _⟩

def fintype.choose {α : Type u_1} [fintype α] (p : α → Prop) [decidable_pred p] (hp : ∃! (a : α), p a) :

α

Given a fintype α and a predicate p, associate to a proof that there is a unique element of α satisfying p this unique element, as an element of α.

Equations

fintype.choose p hp = ↑(fintype.choose_x p hp)

theorem fintype.choose_spec {α : Type u_1} [fintype α] (p : α → Prop) [decidable_pred p] (hp : ∃! (a : α), p a) :

p (fintype.choose p hp)

@[simp]

theorem fintype.choose_subtype_eq {α : Type u_1} (p : α → Prop) [fintype {a // p a}] [decidable_eq α] (x : {a // p a}) (h : (∃! (a : {a // p a}), ↑a = ↑x) := _) :

fintype.choose (λ (y : {a // p a}), ↑y = ↑x) h = x

def fintype.bij_inv {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} (f_bij : function.bijective f) (b : β) :

α

bij_inv f is the unique inverse to a bijection f. This acts as a computable alternative to function.inv_fun.

Equations

fintype.bij_inv f_bij b = fintype.choose (λ (a : α), f a = b) _

theorem fintype.left_inverse_bij_inv {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} (f_bij : function.bijective f) :

function.left_inverse (fintype.bij_inv f_bij) f

theorem fintype.right_inverse_bij_inv {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} (f_bij : function.bijective f) :

function.right_inverse (fintype.bij_inv f_bij) f

theorem fintype.bijective_bij_inv {α : Type u_1} {β : Type u_2} [fintype α] [decidable_eq β] {f : α → β} (f_bij : function.bijective f) :

function.bijective (fintype.bij_inv f_bij)

theorem fintype.well_founded_of_trans_of_irrefl {α : Type u_1} [fintype α] (r : α → α → Prop) [is_trans α r] [is_irrefl α r] :

theorem fintype.preorder.well_founded_lt {α : Type u_1} [fintype α] [preorder α] :

well_founded has_lt.lt

theorem fintype.preorder.well_founded_gt {α : Type u_1} [fintype α] [preorder α] :

well_founded gt

@[instance]

theorem fintype.linear_order.is_well_order_lt {α : Type u_1} [fintype α] [linear_order α] :

is_well_order α has_lt.lt

@[instance]

theorem fintype.linear_order.is_well_order_gt {α : Type u_1} [fintype α] [linear_order α] :

is_well_order α gt

@[class]

structure infinite (α : Type u_4) :

Prop

not_fintype : fintype α → false

A type is said to be infinite if it has no fintype instance. Note that infinite α is equivalent to is_empty (fintype α).

Instances of this typeclass

theorem not_fintype (α : Type u_1) [h1 : infinite α] [h2 : fintype α] :

@[protected]

theorem fintype.false {α : Type u_1} [infinite α] (h : fintype α) :

@[protected]

theorem infinite.false {α : Type u_1} [fintype α] (h : infinite α) :

@[simp]

theorem is_empty_fintype {α : Type u_1} :

is_empty (fintype α) ↔ infinite α

noncomputable def fintype_of_not_infinite {α : Type u_1} (h : ¬infinite α) :

A non-infinite type is a fintype.

Equations

fintype_of_not_infinite h = _.some

noncomputable def fintype_or_infinite (α : Type u_1) :

psum (fintype α) (infinite α)

Any type is (classically) either a fintype, or infinite.

One can obtain the relevant typeclasses via cases fintype_or_infinite α; resetI.

Equations

fintype_or_infinite α = dite (infinite α) (λ (h : infinite α), psum.inr h) (λ (h : ¬infinite α), psum.inl (fintype_of_not_infinite h))

theorem finset.exists_minimal {α : Type u_1} [preorder α] (s : finset α) (h : s.nonempty) :

∃ (m : α) (H : m ∈ s), ∀ (x : α), x ∈ s → ¬x < m

theorem finset.exists_maximal {α : Type u_1} [preorder α] (s : finset α) (h : s.nonempty) :

∃ (m : α) (H : m ∈ s), ∀ (x : α), x ∈ s → ¬m < x

theorem infinite.exists_not_mem_finset {α : Type u_1} [infinite α] (s : finset α) :

∃ (x : α), x ∉ s

@[protected, instance]

def infinite.nontrivial (α : Type u_1) [H : infinite α] :

@[protected]

theorem infinite.nonempty (α : Type u_1) [infinite α] :

theorem infinite.of_injective {α : Type u_1} {β : Type u_2} [infinite β] (f : β → α) (hf : function.injective f) :

theorem infinite.of_surjective {α : Type u_1} {β : Type u_2} [infinite β] (f : α → β) (hf : function.surjective f) :

@[protected, instance]

def nat.infinite :

@[protected, instance]

def int.infinite :

@[protected, instance]

def infinite.set {α : Type u_1} [infinite α] :

infinite (set α)

@[protected, instance]

def finset.infinite {α : Type u_1} [infinite α] :

infinite (finset α)

@[protected, instance]

def multiset.infinite {α : Type u_1} [nonempty α] :

infinite (multiset α)

@[protected, instance]

def list.infinite {α : Type u_1} [nonempty α] :

infinite (list α)

@[protected, instance]

def option.infinite {α : Type u_1} [infinite α] :

infinite (option α)

@[protected, instance]

def sum.infinite_of_left {α : Type u_1} {β : Type u_2} [infinite α] :

infinite (α ⊕ β)

@[protected, instance]

def sum.infinite_of_right {α : Type u_1} {β : Type u_2} [infinite β] :

infinite (α ⊕ β)

@[simp]

theorem infinite_sum {α : Type u_1} {β : Type u_2} :

infinite (α ⊕ β) ↔ infinite α ∨ infinite β

@[protected, instance]

def prod.infinite_of_right {α : Type u_1} {β : Type u_2} [nonempty α] [infinite β] :

infinite (α × β)

@[protected, instance]

def prod.infinite_of_left {α : Type u_1} {β : Type u_2} [infinite α] [nonempty β] :

infinite (α × β)

@[simp]

theorem infinite_prod {α : Type u_1} {β : Type u_2} :

infinite (α × β) ↔ infinite α ∧ nonempty β ∨ nonempty α ∧ infinite β

noncomputable def infinite.nat_embedding (α : Type u_1) [infinite α] :

Embedding of ℕ into an infinite type.

Equations

infinite.nat_embedding α = {to_fun := nat_embedding_aux α _inst_1, inj' := _}

theorem infinite.exists_subset_card_eq (α : Type u_1) [infinite α] (n : ℕ) :

∃ (s : finset α), s.card = n

noncomputable def fintype_of_finset_card_le {ι : Type u_1} (n : ℕ) (w : ∀ (s : finset ι), s.card ≤ n) :

If every finset in a type has bounded cardinality, that type is finite.

Equations

fintype_of_finset_card_le n w = fintype_of_not_infinite _

theorem not_injective_infinite_fintype {α : Type u_1} {β : Type u_2} [infinite α] [fintype β] (f : α → β) :

¬function.injective f

theorem fintype.exists_ne_map_eq_of_infinite {α : Type u_1} {β : Type u_2} [infinite α] [fintype β] (f : α → β) :

∃ (x y : α), x ≠ y ∧ f x = f y

The pigeonhole principle for infinitely many pigeons in finitely many pigeonholes. If there are infinitely many pigeons in finitely many pigeonholes, then there are at least two pigeons in the same pigeonhole.

See also: fintype.exists_ne_map_eq_of_card_lt, fintype.exists_infinite_fiber.

@[protected, instance]

def function.embedding.is_empty {α : Type u_1} {β : Type u_2} [infinite α] [fintype β] :

is_empty (α ↪ β)

@[protected, instance]

noncomputable def function.embedding.fintype' {α : Type u_1} {β : Type u_2} [fintype β] :

fintype (α ↪ β)

Equations

function.embedding.fintype' = (fintype_or_infinite α).cases_on (λ (val : fintype α), function.embedding.fintype) (λ (val : infinite α), fintype.of_is_empty)

theorem fintype.exists_infinite_fiber {α : Type u_1} {β : Type u_2} [infinite α] [fintype β] (f : α → β) :

∃ (y : β), infinite ↥(f ⁻¹' {y})

The strong pigeonhole principle for infinitely many pigeons in finitely many pigeonholes. If there are infinitely many pigeons in finitely many pigeonholes, then there is a pigeonhole with infinitely many pigeons.

See also: fintype.exists_ne_map_eq_of_infinite

theorem not_surjective_fintype_infinite {α : Type u_1} {β : Type u_2} [fintype α] [infinite β] (f : α → β) :

¬function.surjective f

def trunc_of_multiset_exists_mem {α : Type u_1} (s : multiset α) :

(∃ (x : α), x ∈ s) → trunc α

For s : multiset α, we can lift the existential statement that ∃ x, x ∈ s to a trunc α.

Equations

trunc_of_multiset_exists_mem s = quotient.rec_on_subsingleton s (λ (l : list α) (h : ∃ (x : α), x ∈ ⟦l⟧), trunc_of_multiset_exists_mem._match_1 l h l h)
trunc_of_multiset_exists_mem._match_1 l h (a :: _x) _x_1 = trunc.mk a
trunc_of_multiset_exists_mem._match_1 l h list.nil _x = false.elim _

def trunc_of_nonempty_fintype (α : Type u_1) [nonempty α] [fintype α] :

A nonempty fintype constructively contains an element.

Equations

trunc_of_nonempty_fintype α = trunc_of_multiset_exists_mem finset.univ.val _

def trunc_of_card_pos {α : Type u_1} [fintype α] (h : 0 < fintype.card α) :

A fintype with positive cardinality constructively contains an element.

Equations

trunc_of_card_pos h = let _inst : nonempty α := _ in trunc_of_nonempty_fintype α

def trunc_sigma_of_exists {α : Type u_1} [fintype α] {P : α → Prop} [decidable_pred P] (h : ∃ (a : α), P a) :

trunc (Σ' (a : α), P a)

By iterating over the elements of a fintype, we can lift an existential statement ∃ a, P a to trunc (Σ' a, P a), containing data.

Equations

trunc_sigma_of_exists h = trunc_of_nonempty_fintype (Σ' (a : α), P a)

@[simp]

theorem multiset.count_univ {α : Type u_1} [fintype α] [decidable_eq α] (a : α) :

multiset.count a finset.univ.val = 1

def fintype.trunc_rec_empty_option {P : Type u → Sort v} (of_equiv : Π {α β : Type u}, α ≃ β → P α → P β) (h_empty : P pempty) (h_option : Π {α : Type u} [_inst_1 : fintype α] [_inst_2 : decidable_eq α], P α → P (option α)) (α : Type u) [fintype α] [decidable_eq α] :

trunc (P α)

A recursor principle for finite types, analogous to nat.rec. It effectively says that every fintype is either empty or option α, up to an equiv.

Equations

fintype.trunc_rec_empty_option of_equiv h_empty h_option α = trunc.bind ((λ (n : ℕ), nat.rec ((fintype.trunc_equiv_of_card_eq fintype.trunc_rec_empty_option._proof_1).bind (λ (e : pempty ≃ ulift (fin 0)), trunc.mk (of_equiv e h_empty))) (λ (n : ℕ) (ih : trunc (P (ulift (fin n)))), (fintype.trunc_equiv_of_card_eq _).bind (λ (e : option (ulift (fin n)) ≃ ulift (fin n.succ)), trunc.map (λ (ih : P (ulift (fin n))), of_equiv e (h_option ih)) ih)) n) (fintype.card α)) (λ (h : P (ulift (fin (fintype.card α)))), trunc.map (λ (e : α ≃ fin (fintype.card α)), of_equiv (equiv.ulift.trans e.symm) h) (fintype.trunc_equiv_fin α))

theorem fintype.induction_empty_option' {P : Π (α : Type u) [_inst_1 : fintype α], Prop} (of_equiv : ∀ (α β : Type u) [_inst_2 : fintype β] (e : α ≃ β), P α → P β) (h_empty : P pempty) (h_option : ∀ (α : Type u) [_inst_3 : fintype α], P α → P (option α)) (α : Type u) [fintype α] :

P α

An induction principle for finite types, analogous to nat.rec. It effectively says that every fintype is either empty or option α, up to an equiv.

theorem fintype.induction_empty_option {P : Type u → Prop} (of_equiv : ∀ {α β : Type u}, α ≃ β → P α → P β) (h_empty : P pempty) (h_option : ∀ {α : Type u} [_inst_1 : fintype α], P α → P (option α)) (α : Type u) [fintype α] :

P α

An induction principle for finite types, analogous to nat.rec. It effectively says that every fintype is either empty or option α, up to an