Finite Cardinality Functions

Main Definitions

• Nat.card α is the cardinality of α as a natural number. If α is infinite, Nat.card α = 0.
• PartENat.card α is the cardinality of α as an extended natural number (using Part ℕ). If α is infinite, PartENat.card α = ⊤.

def Nat.card (α : Type u_3) : ℕ

Nat.card α is the cardinality of α as a natural number. If α is infinite, Nat.card α = 0.

Equations

• Nat.card α = Cardinal.toNat (Cardinal.mk α)

@[simp]

theorem Nat.card_eq_fintype_card {α : Type u_1} [Fintype α] : Nat.card α = Fintype.card α

theorem Fintype.card_eq_nat_card {α : Type u_1} : ∀ {x : Fintype α}, Fintype.card α = Nat.card α

Because this theorem takes Fintype α as a non-instance argument, it can be used in particular when Fintype.card ends up with different instance than the one found by inference

theorem Nat.card_eq_finsetCard {α : Type u_1} (s : Finset α) : Nat.card { x : α // x ∈ s } = s.card

theorem Nat.card_eq_card_toFinset {α : Type u_1} (s : Set α) [Fintype ↑s] : Nat.card ↑s = s.toFinset.card

theorem Nat.card_eq_card_finite_toFinset {α : Type u_1} {s : Set α} (hs : s.Finite) : Nat.card ↑s = hs.toFinset.card

@[simp]

theorem Nat.card_of_isEmpty {α : Type u_1} [IsEmpty α] : Nat.card α = 0

@[simp]

theorem Nat.card_eq_zero_of_infinite {α : Type u_1} [Infinite α] : Nat.card α = 0

theorem Set.Infinite.card_eq_zero {α : Type u_1} {s : Set α} (hs : s.Infinite) : Nat.card ↑s = 0

theorem Nat.card_eq_zero {α : Type u_1} : Nat.card α = 0 ↔ IsEmpty α ∨ Infinite α

theorem Nat.card_ne_zero {α : Type u_1} : Nat.card α ≠ 0 ↔ Nonempty α ∧ Finite α

theorem Nat.card_pos_iff {α : Type u_1} : 0 < Nat.card α ↔ Nonempty α ∧ Finite α

@[simp]

theorem Nat.card_pos {α : Type u_1} [Nonempty α] [Finite α] : 0 < Nat.card α

theorem Nat.finite_of_card_ne_zero {α : Type u_1} (h : Nat.card α ≠ 0) : Finite α

theorem Nat.card_congr {α : Type u_1} {β : Type u_2} (f : α ≃ β) : Nat.card α = Nat.card β

theorem Nat.card_le_card_of_injective {α : Type u} {β : Type v} [Finite β] (f : α → β) (hf : Function.Injective f) : Nat.card α ≤ Nat.card β

theorem Nat.card_le_card_of_surjective {α : Type u} {β : Type v} [Finite α] (f : α → β) (hf : Function.Surjective f) : Nat.card β ≤ Nat.card α

theorem Nat.card_eq_of_bijective {α : Type u_1} {β : Type u_2} (f : α → β) (hf : Function.Bijective f) : Nat.card α = Nat.card β

theorem Nat.card_eq_of_equiv_fin {α : Type u_3} {n : ℕ} (f : α ≃ Fin n) : Nat.card α = n

theorem Nat.card_mono {α : Type u_1} {s : Set α} {t : Set α} (ht : t.Finite) (h : s ⊆ t) : Nat.card ↑s ≤ Nat.card ↑t

theorem Nat.card_image_le {α : Type u_1} {s : Set α} : ∀ {α_1 : Type u_3} {f : α → α_1}, s.Finite → Nat.card ↑(f '' s) ≤ Nat.card ↑s

theorem Nat.card_image_of_injOn {α : Type u_1} {s : Set α} : ∀ {β : Type u_3} {f : α → β}, Set.InjOn f s → Nat.card ↑(f '' s) = Nat.card ↑s

theorem Nat.card_image_of_injective {α : Type u_1} : ∀ {β : Type u_3} {f : α → β}, Function.Injective f → ∀ (s : Set α), Nat.card ↑(f '' s) = Nat.card ↑s

theorem Nat.card_image_equiv {α : Type u_1} {β : Type u_2} {s : Set α} (e : α ≃ β) : Nat.card ↑(⇑e '' s) = Nat.card ↑s

theorem Nat.card_preimage_of_injOn {β : Type u_2} : ∀ {α : Type u_3} {f : α → β} {s : Set β}, Set.InjOn f (f ⁻¹' s) → s ⊆ Set.range f → Nat.card ↑(f ⁻¹' s) = Nat.card ↑s

theorem Nat.card_preimage_of_injective {β : Type u_2} : ∀ {α : Type u_3} {f : α → β} {s : Set β}, Function.Injective f → s ⊆ Set.range f → Nat.card ↑(f ⁻¹' s) = Nat.card ↑s

def Nat.equivFinOfCardPos {α : Type u_3} (h : Nat.card α ≠ 0) : α ≃ Fin (Nat.card α)

If the cardinality is positive, that means it is a finite type, so there is an equivalence between α and Fin (Nat.card α). See also Finite.equivFin.

Equations

• One or more equations did not get rendered due to their size.

theorem Nat.card_of_subsingleton {α : Type u_1} (a : α) [Subsingleton α] : Nat.card α = 1

theorem Nat.card_unique {α : Type u_1} [Unique α] : Nat.card α = 1

theorem Nat.card_eq_one_iff_unique {α : Type u_1} : Nat.card α = 1 ↔ Subsingleton α ∧ Nonempty α

theorem Nat.card_eq_two_iff {α : Type u_1} : Nat.card α = 2 ↔ ∃ (x : α) (y : α), x ≠ y ∧ {x, y} = Set.univ

theorem Nat.card_eq_two_iff' {α : Type u_1} (x : α) : Nat.card α = 2 ↔ ∃! y : α, y ≠ x

@[simp]

theorem Nat.card_sum {α : Type u_1} {β : Type u_2} [Finite α] [Finite β] : Nat.card (α ⊕ β) = Nat.card α + Nat.card β

@[simp]

theorem Nat.card_prod (α : Type u_3) (β : Type u_4) : Nat.card (α × β) = Nat.card α * Nat.card β

@[simp]

theorem Nat.card_ulift (α : Type u_3) : Nat.card (ULift.{u_4, u_3} α) = Nat.card α

@[simp]

theorem Nat.card_plift (α : Type u_3) : Nat.card (PLift α) = Nat.card α

theorem Nat.card_pi {α : Type u_1} {β : α → Type u_3} [Fintype α] : Nat.card ((a : α) → β a) = ∏ a : α, Nat.card (β a)

theorem Nat.card_fun {α : Type u_1} {β : Type u_2} [Finite α] : Nat.card (α → β) = Nat.card β ^ Nat.card α

@[simp]

theorem Nat.card_zmod (n : ℕ) : Nat.card (ZMod n) = n

theorem Set.card_singleton_prod {α : Type u_1} {β : Type u_2} (a : α) (t : Set β) : Nat.card ↑({a} ×ˢ t) = Nat.card ↑t

theorem Set.card_prod_singleton {α : Type u_1} {β : Type u_2} (s : Set α) (b : β) : Nat.card ↑(s ×ˢ {b}) = Nat.card ↑s

def PartENat.card (α : Type u_3) : PartENat

PartENat.card α is the cardinality of α as an extended natural number. If α is infinite, PartENat.card α = ⊤.

Equations

• PartENat.card α = Cardinal.toPartENat (Cardinal.mk α)

@[simp]

theorem PartENat.card_eq_coe_fintype_card {α : Type u_1} [Fintype α] : PartENat.card α = ↑(Fintype.card α)

@[simp]

theorem PartENat.card_eq_top_of_infinite {α : Type u_1} [Infinite α] : PartENat.card α = ⊤

@[simp]

theorem PartENat.card_sum (α : Type u_3) (β : Type u_4) : PartENat.card (α ⊕ β) = PartENat.card α + PartENat.card β

theorem PartENat.card_congr {α : Type u_3} {β : Type u_4} (f : α ≃ β) : PartENat.card α = PartENat.card β

@[simp]

theorem PartENat.card_ulift (α : Type u_3) : PartENat.card (ULift.{u_4, u_3} α) = PartENat.card α

@[simp]

theorem PartENat.card_plift (α : Type u_3) : PartENat.card (PLift α) = PartENat.card α

theorem PartENat.card_image_of_injOn {α : Type u} {β : Type v} {f : α → β} {s : Set α} (h : Set.InjOn f s) : PartENat.card ↑(f '' s) = PartENat.card ↑s

theorem PartENat.card_image_of_injective {α : Type u} {β : Type v} (f : α → β) (s : Set α) (h : Function.Injective f) : PartENat.card ↑(f '' s) = PartENat.card ↑s

@[simp]

theorem Cardinal.natCast_le_toPartENat_iff {n : ℕ} {c : Cardinal.{u_3}} : ↑n ≤ Cardinal.toPartENat c ↔ ↑n ≤ c

@[simp]

theorem Cardinal.toPartENat_le_natCast_iff {c : Cardinal.{u_3}} {n : ℕ} : Cardinal.toPartENat c ≤ ↑n ↔ c ≤ ↑n

@[simp]

theorem Cardinal.natCast_eq_toPartENat_iff {n : ℕ} {c : Cardinal.{u_3}} : ↑n = Cardinal.toPartENat c ↔ ↑n = c

@[simp]

theorem Cardinal.toPartENat_eq_natCast_iff {c : Cardinal.{u_3}} {n : ℕ} : Cardinal.toPartENat c = ↑n ↔ c = ↑n

@[simp]

theorem Cardinal.natCast_lt_toPartENat_iff {n : ℕ} {c : Cardinal.{u_3}} : ↑n < Cardinal.toPartENat c ↔ ↑n < c

@[simp]

theorem Cardinal.toPartENat_lt_natCast_iff {n : ℕ} {c : Cardinal.{u_3}} : Cardinal.toPartENat c < ↑n ↔ c < ↑n

theorem PartENat.card_eq_zero_iff_empty (α : Type u_3) : PartENat.card α = 0 ↔ IsEmpty α

theorem PartENat.card_le_one_iff_subsingleton (α : Type u_3) : PartENat.card α ≤ 1 ↔ Subsingleton α

theorem PartENat.one_lt_card_iff_nontrivial (α : Type u_3) : 1 < PartENat.card α ↔ Nontrivial α