Cardinal arithmetic

Arithmetic operations on cardinals are defined in SetTheory/Cardinal/Basic.lean. However, proving the important theorem c * c = c for infinite cardinals and its corollaries requires the use of ordinal numbers. This is done within this file.

Main statements

• Cardinal.mul_eq_max and Cardinal.add_eq_max state that the product (resp. sum) of two infinite cardinals is just their maximum. Several variations around this fact are also given.
• Cardinal.mk_list_eq_mk: when α is infinite, α and List α have the same cardinality.

Tags

cardinal arithmetic (for infinite cardinals)

Properties of mul

theorem Cardinal.mul_eq_self {c : Cardinal.{u_1}} (h : Cardinal.aleph0 ≤ c) : c * c = c

If α is an infinite type, then α × α and α have the same cardinality.

theorem Cardinal.mul_eq_max {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (ha : Cardinal.aleph0 ≤ a) (hb : Cardinal.aleph0 ≤ b) : a * b = a ⊔ b

If α and β are infinite types, then the cardinality of α × β is the maximum of the cardinalities of α and β.

@[simp]

theorem Cardinal.mul_mk_eq_max {α : Type u} {β : Type u} [Infinite α] [Infinite β] : Cardinal.mk α * Cardinal.mk β = Cardinal.mk α ⊔ Cardinal.mk β

@[simp]

theorem Cardinal.aleph_mul_aleph (o₁ : Ordinal.{u_1}) (o₂ : Ordinal.{u_1}) : Cardinal.aleph o₁ * Cardinal.aleph o₂ = Cardinal.aleph (o₁ ⊔ o₂)

@[simp]

theorem Cardinal.aleph0_mul_eq {a : Cardinal.{u_1}} (ha : Cardinal.aleph0 ≤ a) : Cardinal.aleph0 * a = a

@[simp]

theorem Cardinal.mul_aleph0_eq {a : Cardinal.{u_1}} (ha : Cardinal.aleph0 ≤ a) : a * Cardinal.aleph0 = a

theorem Cardinal.aleph0_mul_mk_eq {α : Type u_1} [Infinite α] : Cardinal.aleph0 * Cardinal.mk α = Cardinal.mk α

theorem Cardinal.mk_mul_aleph0_eq {α : Type u_1} [Infinite α] : Cardinal.mk α * Cardinal.aleph0 = Cardinal.mk α

@[simp]

theorem Cardinal.aleph0_mul_aleph (o : Ordinal.{u_1}) : Cardinal.aleph0 * Cardinal.aleph o = Cardinal.aleph o

@[simp]

theorem Cardinal.aleph_mul_aleph0 (o : Ordinal.{u_1}) : Cardinal.aleph o * Cardinal.aleph0 = Cardinal.aleph o

theorem Cardinal.mul_lt_of_lt {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} {c : Cardinal.{u_1}} (hc : Cardinal.aleph0 ≤ c) (h1 : a < c) (h2 : b < c) : a * b < c

theorem Cardinal.mul_le_max_of_aleph0_le_left {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (h : Cardinal.aleph0 ≤ a) : a * b ≤ a ⊔ b

theorem Cardinal.mul_eq_max_of_aleph0_le_left {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (h : Cardinal.aleph0 ≤ a) (h' : b ≠ 0) : a * b = a ⊔ b

theorem Cardinal.mul_le_max_of_aleph0_le_right {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (h : Cardinal.aleph0 ≤ b) : a * b ≤ a ⊔ b

theorem Cardinal.mul_eq_max_of_aleph0_le_right {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (h' : a ≠ 0) (h : Cardinal.aleph0 ≤ b) : a * b = a ⊔ b

theorem Cardinal.mul_eq_max' {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (h : Cardinal.aleph0 ≤ a * b) : a * b = a ⊔ b

theorem Cardinal.mul_le_max (a : Cardinal.{u_1}) (b : Cardinal.{u_1}) : a * b ≤ a ⊔ b ⊔ Cardinal.aleph0

theorem Cardinal.mul_eq_left {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (ha : Cardinal.aleph0 ≤ a) (hb : b ≤ a) (hb' : b ≠ 0) : a * b = a

theorem Cardinal.mul_eq_right {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (hb : Cardinal.aleph0 ≤ b) (ha : a ≤ b) (ha' : a ≠ 0) : a * b = b

theorem Cardinal.le_mul_left {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (h : b ≠ 0) : a ≤ b * a

theorem Cardinal.le_mul_right {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (h : b ≠ 0) : a ≤ a * b

theorem Cardinal.mul_eq_left_iff {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} : a * b = a ↔ Cardinal.aleph0 ⊔ b ≤ a ∧ b ≠ 0 ∨ b = 1 ∨ a = 0

Properties of add

theorem Cardinal.add_eq_self {c : Cardinal.{u_1}} (h : Cardinal.aleph0 ≤ c) : c + c = c

If α is an infinite type, then α ⊕ α and α have the same cardinality.

theorem Cardinal.add_eq_max {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (ha : Cardinal.aleph0 ≤ a) : a + b = a ⊔ b

If α is an infinite type, then the cardinality of α ⊕ β is the maximum of the cardinalities of α and β.

theorem Cardinal.add_eq_max' {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (ha : Cardinal.aleph0 ≤ b) : a + b = a ⊔ b

@[simp]

theorem Cardinal.add_mk_eq_max {α : Type u} {β : Type u} [Infinite α] : Cardinal.mk α + Cardinal.mk β = Cardinal.mk α ⊔ Cardinal.mk β

@[simp]

theorem Cardinal.add_mk_eq_max' {α : Type u} {β : Type u} [Infinite β] : Cardinal.mk α + Cardinal.mk β = Cardinal.mk α ⊔ Cardinal.mk β

theorem Cardinal.add_le_max (a : Cardinal.{u_1}) (b : Cardinal.{u_1}) : a + b ≤ a ⊔ b ⊔ Cardinal.aleph0

theorem Cardinal.add_le_of_le {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} {c : Cardinal.{u_1}} (hc : Cardinal.aleph0 ≤ c) (h1 : a ≤ c) (h2 : b ≤ c) : a + b ≤ c

theorem Cardinal.add_lt_of_lt {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} {c : Cardinal.{u_1}} (hc : Cardinal.aleph0 ≤ c) (h1 : a < c) (h2 : b < c) : a + b < c

theorem Cardinal.eq_of_add_eq_of_aleph0_le {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} {c : Cardinal.{u_1}} (h : a + b = c) (ha : a < c) (hc : Cardinal.aleph0 ≤ c) : b = c

theorem Cardinal.add_eq_left {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (ha : Cardinal.aleph0 ≤ a) (hb : b ≤ a) : a + b = a

theorem Cardinal.add_eq_right {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} (hb : Cardinal.aleph0 ≤ b) (ha : a ≤ b) : a + b = b

theorem Cardinal.add_eq_left_iff {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} : a + b = a ↔ Cardinal.aleph0 ⊔ b ≤ a ∨ b = 0

theorem Cardinal.add_eq_right_iff {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} : a + b = b ↔ Cardinal.aleph0 ⊔ a ≤ b ∨ a = 0

theorem Cardinal.add_nat_eq {a : Cardinal.{u_1}} (n : ℕ) (ha : Cardinal.aleph0 ≤ a) : a + ↑n = a

theorem Cardinal.nat_add_eq {a : Cardinal.{u_1}} (n : ℕ) (ha : Cardinal.aleph0 ≤ a) : ↑n + a = a

theorem Cardinal.add_one_eq {a : Cardinal.{u_1}} (ha : Cardinal.aleph0 ≤ a) : a + 1 = a

theorem Cardinal.mk_add_one_eq {α : Type u_1} [Infinite α] : Cardinal.mk α + 1 = Cardinal.mk α

theorem Cardinal.eq_of_add_eq_add_left {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} {c : Cardinal.{u_1}} (h : a + b = a + c) (ha : a < Cardinal.aleph0) : b = c

theorem Cardinal.eq_of_add_eq_add_right {a : Cardinal.{u_1}} {b : Cardinal.{u_1}} {c : Cardinal.{u_1}} (h : a + b = c + b) (hb : b < Cardinal.aleph0) : a = c

Properties of ciSup

theorem Cardinal.ciSup_add {ι : Type u} (f : ι → Cardinal.{v}) [Nonempty ι] (hf : BddAbove (Set.range f)) (c : Cardinal.{v}) : (⨆ (i : ι), f i) + c = ⨆ (i : ι), f i + c

theorem Cardinal.add_ciSup {ι : Type u} (f : ι → Cardinal.{v}) [Nonempty ι] (hf : BddAbove (Set.range f)) (c : Cardinal.{v}) : c + ⨆ (i : ι), f i = ⨆ (i : ι), c + f i

theorem Cardinal.ciSup_add_ciSup {ι : Type u} {ι' : Type w} (f : ι → Cardinal.{v}) [Nonempty ι] [Nonempty ι'] (hf : BddAbove (Set.range f)) (g : ι' → Cardinal.{v}) (hg : BddAbove (Set.range g)) : (⨆ (i : ι), f i) + ⨆ (j : ι'), g j = ⨆ (i : ι), ⨆ (j : ι'), f i + g j

theorem Cardinal.ciSup_mul {ι : Type u} (f : ι → Cardinal.{v}) (c : Cardinal.{v}) : (⨆ (i : ι), f i) * c = ⨆ (i : ι), f i * c

theorem Cardinal.mul_ciSup {ι : Type u} (f : ι → Cardinal.{v}) (c : Cardinal.{v}) : c * ⨆ (i : ι), f i = ⨆ (i : ι), c * f i

theorem Cardinal.ciSup_mul_ciSup {ι : Type u} {ι' : Type w} (f : ι → Cardinal.{v}) (g : ι' → Cardinal.{v}) : (⨆ (i : ι), f i) * ⨆ (j : ι'), g j = ⨆ (i : ι), ⨆ (j : ι'), f i * g j

Properties of aleph

@[simp]

theorem Cardinal.aleph_add_aleph (o₁ : Ordinal.{u_1}) (o₂ : Ordinal.{u_1}) : Cardinal.aleph o₁ + Cardinal.aleph o₂ = Cardinal.aleph (o₁ ⊔ o₂)

theorem Cardinal.principal_add_ord {c : Cardinal.{u_1}} (hc : Cardinal.aleph0 ≤ c) : Ordinal.Principal (fun (x1 x2 : Ordinal.{u_1}) => x1 + x2) c.ord

theorem Cardinal.principal_add_aleph (o : Ordinal.{u_1}) : Ordinal.Principal (fun (x1 x2 : Ordinal.{u_1}) => x1 + x2) (Cardinal.aleph o).ord

theorem Cardinal.add_right_inj_of_lt_aleph0 {α : Cardinal.{u_1}} {β : Cardinal.{u_1}} {γ : Cardinal.{u_1}} (γ₀ : γ < Cardinal.aleph0) : α + γ = β + γ ↔ α = β

@[simp]

theorem Cardinal.add_nat_inj {α : Cardinal.{u_1}} {β : Cardinal.{u_1}} (n : ℕ) : α + ↑n = β + ↑n ↔ α = β

@[simp]

theorem Cardinal.add_one_inj {α : Cardinal.{u_1}} {β : Cardinal.{u_1}} : α + 1 = β + 1 ↔ α = β

theorem Cardinal.add_le_add_iff_of_lt_aleph0 {α : Cardinal.{u_1}} {β : Cardinal.{u_1}} {γ : Cardinal.{u_1}} (γ₀ : γ < Cardinal.aleph0) : α + γ ≤ β + γ ↔ α ≤ β

@[simp]

theorem Cardinal.add_nat_le_add_nat_iff {α : Cardinal.{u_1}} {β : Cardinal.{u_1}} (n : ℕ) : α + ↑n ≤ β + ↑n ↔ α ≤ β

@[deprecated Cardinal.add_nat_le_add_nat_iff]

theorem Cardinal.add_nat_le_add_nat_iff_of_lt_aleph_0 {α : Cardinal.{u_1}} {β : Cardinal.{u_1}} (n : ℕ) : α + ↑n ≤ β + ↑n ↔ α ≤ β

Alias of Cardinal.add_nat_le_add_nat_iff.

@[simp]

theorem Cardinal.add_one_le_add_one_iff {α : Cardinal.{u_1}} {β : Cardinal.{u_1}} : α + 1 ≤ β + 1 ↔ α ≤ β

@[deprecated Cardinal.add_one_le_add_one_iff]

theorem Cardinal.add_one_le_add_one_iff_of_lt_aleph_0 {α : Cardinal.{u_1}} {β : Cardinal.{u_1}} : α + 1 ≤ β + 1 ↔ α ≤ β

Alias of Cardinal.add_one_le_add_one_iff.

Properties about power

theorem Cardinal.pow_le {κ : Cardinal.{u}} {μ : Cardinal.{u}} (H1 : Cardinal.aleph0 ≤ κ) (H2 : μ < Cardinal.aleph0) : κ ^ μ ≤ κ

theorem Cardinal.pow_eq {κ : Cardinal.{u}} {μ : Cardinal.{u}} (H1 : Cardinal.aleph0 ≤ κ) (H2 : 1 ≤ μ) (H3 : μ < Cardinal.aleph0) : κ ^ μ = κ

theorem Cardinal.power_self_eq {c : Cardinal.{u_1}} (h : Cardinal.aleph0 ≤ c) : c ^ c = 2 ^ c

theorem Cardinal.prod_eq_two_power {ι : Type u} [Infinite ι] {c : ι → Cardinal.{v}} (h₁ : ∀ (i : ι), 2 ≤ c i) (h₂ : ∀ (i : ι), Cardinal.lift.{u, v} (c i) ≤ Cardinal.lift.{v, u} (Cardinal.mk ι)) : Cardinal.prod c = 2 ^ Cardinal.lift.{v, u} (Cardinal.mk ι)

theorem Cardinal.power_eq_two_power {c₁ : Cardinal.{u_1}} {c₂ : Cardinal.{u_1}} (h₁ : Cardinal.aleph0 ≤ c₁) (h₂ : 2 ≤ c₂) (h₂' : c₂ ≤ c₁) : c₂ ^ c₁ = 2 ^ c₁

theorem Cardinal.nat_power_eq {c : Cardinal.{u}} (h : Cardinal.aleph0 ≤ c) {n : ℕ} (hn : 2 ≤ n) : ↑n ^ c = 2 ^ c

theorem Cardinal.power_nat_le {c : Cardinal.{u}} {n : ℕ} (h : Cardinal.aleph0 ≤ c) : c ^ n ≤ c

theorem Cardinal.power_nat_eq {c : Cardinal.{u}} {n : ℕ} (h1 : Cardinal.aleph0 ≤ c) (h2 : 1 ≤ n) : c ^ n = c

theorem Cardinal.power_nat_le_max {c : Cardinal.{u}} {n : ℕ} : c ^ ↑n ≤ c ⊔ Cardinal.aleph0

theorem Cardinal.powerlt_aleph0 {c : Cardinal.{u_1}} (h : Cardinal.aleph0 ≤ c) : c ^< Cardinal.aleph0 = c

theorem Cardinal.powerlt_aleph0_le (c : Cardinal.{u_1}) : c ^< Cardinal.aleph0 ≤ c ⊔ Cardinal.aleph0

Computing cardinality of various types

theorem Cardinal.mk_equiv_eq_zero_iff_lift_ne {α : Type u} {β' : Type v} : Cardinal.mk (α ≃ β') = 0 ↔ Cardinal.lift.{v, u} (Cardinal.mk α) ≠ Cardinal.lift.{u, v} (Cardinal.mk β')

theorem Cardinal.mk_equiv_eq_zero_iff_ne {α : Type u} {β : Type u} : Cardinal.mk (α ≃ β) = 0 ↔ Cardinal.mk α ≠ Cardinal.mk β

theorem Cardinal.mk_equiv_comm {α : Type u} {β' : Type v} : Cardinal.mk (α ≃ β') = Cardinal.mk (β' ≃ α)

This lemma makes lemmas assuming Infinite α applicable to the situation where we have Infinite β instead.

theorem Cardinal.mk_embedding_eq_zero_iff_lift_lt {α : Type u} {β' : Type v} : Cardinal.mk (α ↪ β') = 0 ↔ Cardinal.lift.{u, v} (Cardinal.mk β') < Cardinal.lift.{v, u} (Cardinal.mk α)

theorem Cardinal.mk_embedding_eq_zero_iff_lt {α : Type u} {β : Type u} : Cardinal.mk (α ↪ β) = 0 ↔ Cardinal.mk β < Cardinal.mk α

theorem Cardinal.mk_arrow_eq_zero_iff {α : Type u} {β' : Type v} : Cardinal.mk (α → β') = 0 ↔ Cardinal.mk α ≠ 0 ∧ Cardinal.mk β' = 0

theorem Cardinal.mk_surjective_eq_zero_iff_lift {α : Type u} {β' : Type v} : Cardinal.mk ↑{f : α → β' | Function.Surjective f} = 0 ↔ Cardinal.lift.{v, u} (Cardinal.mk α) < Cardinal.lift.{u, v} (Cardinal.mk β') ∨ Cardinal.mk α ≠ 0 ∧ Cardinal.mk β' = 0

theorem Cardinal.mk_surjective_eq_zero_iff {α : Type u} {β : Type u} : Cardinal.mk ↑{f : α → β | Function.Surjective f} = 0 ↔ Cardinal.mk α < Cardinal.mk β ∨ Cardinal.mk α ≠ 0 ∧ Cardinal.mk β = 0

theorem Cardinal.mk_equiv_le_embedding (α : Type u) (β' : Type v) : Cardinal.mk (α ≃ β') ≤ Cardinal.mk (α ↪ β')

theorem Cardinal.mk_embedding_le_arrow (α : Type u) (β' : Type v) : Cardinal.mk (α ↪ β') ≤ Cardinal.mk (α → β')

theorem Cardinal.mk_perm_eq_self_power {α : Type u} [Infinite α] : Cardinal.mk (Equiv.Perm α) = Cardinal.mk α ^ Cardinal.mk α

theorem Cardinal.mk_perm_eq_two_power {α : Type u} [Infinite α] : Cardinal.mk (Equiv.Perm α) = 2 ^ Cardinal.mk α

theorem Cardinal.mk_equiv_eq_arrow_of_lift_eq {α : Type u} {β' : Type v} [Infinite α] (leq : Cardinal.lift.{v, u} (Cardinal.mk α) = Cardinal.lift.{u, v} (Cardinal.mk β')) : Cardinal.mk (α ≃ β') = Cardinal.mk (α → β')

theorem Cardinal.mk_equiv_eq_arrow_of_eq {α : Type u} {β : Type u} [Infinite α] (eq : Cardinal.mk α = Cardinal.mk β) : Cardinal.mk (α ≃ β) = Cardinal.mk (α → β)

theorem Cardinal.mk_equiv_of_lift_eq {α : Type u} {β' : Type v} [Infinite α] (leq : Cardinal.lift.{v, u} (Cardinal.mk α) = Cardinal.lift.{u, v} (Cardinal.mk β')) : Cardinal.mk (α ≃ β') = 2 ^ Cardinal.lift.{v, u} (Cardinal.mk α)

theorem Cardinal.mk_equiv_of_eq {α : Type u} {β : Type u} [Infinite α] (eq : Cardinal.mk α = Cardinal.mk β) : Cardinal.mk (α ≃ β) = 2 ^ Cardinal.mk α

theorem Cardinal.mk_embedding_eq_arrow_of_lift_le {α : Type u} {β' : Type v} [Infinite α] (lle : Cardinal.lift.{u, v} (Cardinal.mk β') ≤ Cardinal.lift.{v, u} (Cardinal.mk α)) : Cardinal.mk (β' ↪ α) = Cardinal.mk (β' → α)

theorem Cardinal.mk_embedding_eq_arrow_of_le {α : Type u} {β : Type u} [Infinite α] (le : Cardinal.mk β ≤ Cardinal.mk α) : Cardinal.mk (β ↪ α) = Cardinal.mk (β → α)

theorem Cardinal.mk_surjective_eq_arrow_of_lift_le {α : Type u} {β' : Type v} [Infinite α] (lle : Cardinal.lift.{u, v} (Cardinal.mk β') ≤ Cardinal.lift.{v, u} (Cardinal.mk α)) : Cardinal.mk ↑{f : α → β' | Function.Surjective f} = Cardinal.mk (α → β')

theorem Cardinal.mk_surjective_eq_arrow_of_le {α : Type u} {β : Type u} [Infinite α] (le : Cardinal.mk β ≤ Cardinal.mk α) : Cardinal.mk ↑{f : α → β | Function.Surjective f} = Cardinal.mk (α → β)

@[simp]

theorem Cardinal.mk_list_eq_mk (α : Type u) [Infinite α] : Cardinal.mk (List α) = Cardinal.mk α

theorem Cardinal.mk_list_eq_aleph0 (α : Type u) [Countable α] [Nonempty α] : Cardinal.mk (List α) = Cardinal.aleph0

theorem Cardinal.mk_list_eq_max_mk_aleph0 (α : Type u) [Nonempty α] : Cardinal.mk (List α) = Cardinal.mk α ⊔ Cardinal.aleph0

theorem Cardinal.mk_list_le_max (α : Type u) : Cardinal.mk (List α) ≤ Cardinal.aleph0 ⊔ Cardinal.mk α

@[simp]

theorem Cardinal.mk_finset_of_infinite (α : Type u) [Infinite α] : Cardinal.mk (Finset α) = Cardinal.mk α

theorem Cardinal.mk_bounded_set_le_of_infinite (α : Type u) [Infinite α] (c : Cardinal.{u}) : Cardinal.mk { t : Set α // Cardinal.mk ↑t ≤ c } ≤ Cardinal.mk α ^ c

theorem Cardinal.mk_bounded_set_le (α : Type u) (c : Cardinal.{u}) : Cardinal.mk { t : Set α // Cardinal.mk ↑t ≤ c } ≤ (Cardinal.mk α ⊔ Cardinal.aleph0) ^ c

theorem Cardinal.mk_bounded_subset_le {α : Type u} (s : Set α) (c : Cardinal.{u}) : Cardinal.mk { t : Set α // t ⊆ s ∧ Cardinal.mk ↑t ≤ c } ≤ (Cardinal.mk ↑s ⊔ Cardinal.aleph0) ^ c

Properties of compl

theorem Cardinal.mk_compl_of_infinite {α : Type u_1} [Infinite α] (s : Set α) (h2 : Cardinal.mk ↑s < Cardinal.mk α) : Cardinal.mk ↑sᶜ = Cardinal.mk α

theorem Cardinal.mk_compl_finset_of_infinite {α : Type u_1} [Infinite α] (s : Finset α) : Cardinal.mk ↑(↑s)ᶜ = Cardinal.mk α

theorem Cardinal.mk_compl_eq_mk_compl_infinite {α : Type u_1} [Infinite α] {s : Set α} {t : Set α} (hs : Cardinal.mk ↑s < Cardinal.mk α) (ht : Cardinal.mk ↑t < Cardinal.mk α) : Cardinal.mk ↑sᶜ = Cardinal.mk ↑tᶜ

theorem Cardinal.mk_compl_eq_mk_compl_finite_lift {α : Type u} {β : Type v} [Finite α] {s : Set α} {t : Set β} (h1 : Cardinal.lift.{max v w, u} (Cardinal.mk α) = Cardinal.lift.{max u w, v} (Cardinal.mk β)) (h2 : Cardinal.lift.{max v w, u} (Cardinal.mk ↑s) = Cardinal.lift.{max u w, v} (Cardinal.mk ↑t)) : Cardinal.lift.{max v w, u} (Cardinal.mk ↑sᶜ) = Cardinal.lift.{max u w, v} (Cardinal.mk ↑tᶜ)

theorem Cardinal.mk_compl_eq_mk_compl_finite {α : Type u} {β : Type u} [Finite α] {s : Set α} {t : Set β} (h1 : Cardinal.mk α = Cardinal.mk β) (h : Cardinal.mk ↑s = Cardinal.mk ↑t) : Cardinal.mk ↑sᶜ = Cardinal.mk ↑tᶜ

theorem Cardinal.mk_compl_eq_mk_compl_finite_same {α : Type u} [Finite α] {s : Set α} {t : Set α} (h : Cardinal.mk ↑s = Cardinal.mk ↑t) : Cardinal.mk ↑sᶜ = Cardinal.mk ↑tᶜ

Extending an injection to an equiv

theorem Cardinal.extend_function {α : Type u_1} {β : Type u_2} {s : Set α} (f : ↑s ↪ β) (h : Nonempty (↑sᶜ ≃ ↑(Set.range ⇑f)ᶜ)) : ∃ (g : α ≃ β), ∀ (x : ↑s), g ↑x = f x

theorem Cardinal.extend_function_finite {α : Type u} {β : Type v} [Finite α] {s : Set α} (f : ↑s ↪ β) (h : Nonempty (α ≃ β)) : ∃ (g : α ≃ β), ∀ (x : ↑s), g ↑x = f x

theorem Cardinal.extend_function_of_lt {α : Type u_1} {β : Type u_2} {s : Set α} (f : ↑s ↪ β) (hs : Cardinal.mk ↑s < Cardinal.mk α) (h : Nonempty (α ≃ β)) : ∃ (g : α ≃ β), ∀ (x : ↑s), g ↑x = f x

Cardinality of ordinals

theorem Ordinal.lift_card_iSup_le_sum_card {ι : Type u} [Small.{v, u} ι] (f : ι → Ordinal.{v}) : Cardinal.lift.{u, v} (⨆ (i : ι), f i).card ≤ Cardinal.sum fun (i : ι) => (f i).card

theorem Ordinal.card_iSup_le_sum_card {ι : Type u} (f : ι → Ordinal.{max u v} ) : (⨆ (i : ι), f i).card ≤ Cardinal.sum fun (i : ι) => (f i).card

theorem Ordinal.card_iSup_Iio_le_sum_card {o : Ordinal.{u}} (f : Ordinal.{u} → Ordinal.{max u v} ) : (⨆ (a : ↑(Set.Iio o)), f ↑a).card ≤ Cardinal.sum fun (i : o.toType) => (f ↑(o.enumIsoToType.symm i)).card

theorem Ordinal.card_iSup_Iio_le_card_mul_iSup {o : Ordinal.{u}} (f : Ordinal.{u} → Ordinal.{max u v} ) : (⨆ (a : ↑(Set.Iio o)), f ↑a).card ≤ Cardinal.lift.{v, u} o.card * ⨆ (a : ↑(Set.Iio o)), (f ↑a).card

Cardinal operations with ordinal indices

Results on cardinality of ordinal-indexed families of sets.

theorem Ordinal.Cardinal.mk_iUnion_Ordinal_le_of_le {β : Type u_1} {o : Ordinal.{u_1}} {c : Cardinal.{u_1}} (ho : o.card ≤ c) (hc : Cardinal.aleph0 ≤ c) (A : Ordinal.{u_1} → Set β) (hA : ∀ j < o, Cardinal.mk ↑(A j) ≤ c) : Cardinal.mk ↑(⋃ (j : Ordinal.{u_1}), ⋃ (_ : j < o), A j) ≤ c

Bounding the cardinal of an ordinal-indexed union of sets.