Chapter 00 — Introduction
Proofs omitted. Hover over highlighted terms to see their Lean types.
Reading sections
0.3 — Basic Set Theory — Part 1
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 0.3.1: A set is a collection of objects called elements or members. A set with no objects is the empty set, written ∅ (or {}).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev ElementCollection (α : Type u) := Set α
The empty set from Definition 0.3.1 is mathlib's ∅.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev emptyElementCollection (α : Type u) : ElementCollection α :=
(∅ : Set α)
The book's notion of set coincides with mathlib's Set.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem elementCollection_eq_set (α : Type u) : ElementCollection α = Set α
Definition 0.3.2: (i) A ⊆ B means every x ∈ A also satisfies x ∈ B; (ii) A = B when each is a subset of the other (otherwise A ≠ B); (iii) A ⊂ B when A ⊆ B but A ≠ B.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev subsetElementCollection {α : Type u} (A B : ElementCollection α) : Prop :=
A ⊆ B
The book's notion of subset is mathlib's ⊆.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem subsetElementCollection_iff {α : Type u} {A B : ElementCollection α} :
subsetElementCollection A B ↔ A ⊆ B
The book's definition of equality of sets is mutual inclusion.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem elementCollection_eq_iff_subset_subset {α : Type u} {A B : ElementCollection α} :
A = B ↔ subsetElementCollection A B ∧ subsetElementCollection B A
Book notion of a proper subset: contained but not equal.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev properSubsetElementCollection {α : Type u} (A B : ElementCollection α) : Prop :=
subsetElementCollection A B ∧ A ≠ B
The book's notion of proper subset coincides with mathlib's strict subset ⊂.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem properSubsetElementCollection_iff {α : Type u} {A B : ElementCollection α} :
properSubsetElementCollection A B ↔ A ⊂ B
Example 0.3.3: Standard sets of numbers: the naturals ℕ, integers ℤ, rationals ℚ, even naturals {2m}, and reals ℝ, with inclusions ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def naturalsInReals : Set ℝ :=
Set.range fun n : ℕ => (n : ℝ)
Example 0.3.3 (continued).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def integersInReals : Set ℝ :=
Set.range fun z : ℤ => (z : ℝ)
Example 0.3.3 (continued).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def rationalsInReals : Set ℝ :=
Set.range fun q : ℚ => (q : ℝ)
Example 0.3.3 (continued).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def evenNaturalsInReals : Set ℝ :=
Set.range fun m : ℕ => (2 * m : ℝ)
Example 0.3.3: The canonical embeddings realize the chain ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem naturalsInReals_subset_integersInReals :
naturalsInReals ⊆ integersInReals
Example 0.3.3 (continued).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem integersInReals_subset_rationalsInReals :
integersInReals ⊆ rationalsInReals
Example 0.3.3 (continued).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem rationalsInReals_subset_reals :
rationalsInReals ⊆ (Set.univ : Set ℝ)
Definition 0.3.4: (i) union A ∪ B = {x : x ∈ A ∨ x ∈ B}; (ii) intersection A ∩ B = {x : x ∈ A ∧ x ∈ B}; (iii) relative complement (set difference) `A \ B = {x : x ∈ A ∧ x ∉ B}; (iv) complement Bᶜ` means the difference from the ambient universe or an understood superset; (v) sets are disjoint when their intersection is empty.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev unionElementCollection (A B : ElementCollection α) : ElementCollection α :=
A ∪ B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem mem_unionElementCollection {A B : ElementCollection α} {x : α} :
x ∈ unionElementCollection A B ↔ x ∈ A ∨ x ∈ B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev intersectionElementCollection (A B : ElementCollection α) :
ElementCollection α :=
A ∩ B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem mem_intersectionElementCollection {A B : ElementCollection α} {x : α} :
x ∈ intersectionElementCollection A B ↔ x ∈ A ∧ x ∈ B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev relativeComplementElementCollection (A B : ElementCollection α) :
ElementCollection α :=
A \ B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem mem_relativeComplementElementCollection {A B : ElementCollection α} {x : α} :
x ∈ relativeComplementElementCollection A B ↔ x ∈ A ∧ x ∉ B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev complementElementCollection (B : ElementCollection α) : ElementCollection α :=
Set.compl B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem mem_complementElementCollection {B : ElementCollection α} {x : α} :
x ∈ complementElementCollection B ↔ x ∉ B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev disjointElementCollections (A B : ElementCollection α) : Prop :=
Disjoint A B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem disjointElementCollections_iff {A B : ElementCollection α} :
disjointElementCollections A B ↔ A ∩ B = (∅ : Set α)
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma deMorgan_compl_union {B C : Set α} : (B ∪ C)ᶜ = Bᶜ ∩ Cᶜ
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma deMorgan_compl_inter {B C : Set α} : (B ∩ C)ᶜ = Bᶜ ∪ Cᶜ
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma deMorgan_diff_union {A B C : Set α} :
A \ (B ∪ C) = (A \ B) ∩ (A \ C)
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma deMorgan_diff_inter {A B C : Set α} :
A \ (B ∩ C) = (A \ B) ∪ (A \ C)
Theorem 0.3.5 (DeMorgan). For sets A, B, C, (B ∪ C)ᶜ = Bᶜ ∩ Cᶜ and (B ∩ C)ᶜ = Bᶜ ∪ Cᶜ; more generally, A \ (B ∪ C) = (A \ B) ∩ (A \ C) and A \ (B ∩ C) = (A \ B) ∪ (A \ C).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem deMorgan_sets {A B C : Set α} :
(B ∪ C)ᶜ = Bᶜ ∩ Cᶜ ∧
(B ∩ C)ᶜ = Bᶜ ∪ Cᶜ ∧
A \ (B ∪ C) = (A \ B) ∩ (A \ C) ∧
A \ (B ∩ C) = (A \ B) ∪ (A \ C)0.3 — Basic Set Theory — Part 2
Lean authors: Zichen Wang, Zaiwen Wen.
Theorem 0.3.6 (principle of induction). Let P : ℕ → Prop. If (i) the basis statement P 1 holds and (ii) the induction step says P n → P (n + 1) for each n, then P (n + 1) holds for every natural number n.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem principle_of_induction (P : ℕ → Prop) (h₁ : P 1)
(hstep : ∀ n, P n → P (n + 1)) : ∀ n : ℕ, P (n + 1)
Example 0.3.7: For all natural numbers n, the inequality 2^(n - 1) ≤ n! holds, proved by induction on n.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma pow_two_le_factorial_succ : ∀ n : ℕ, 2 ^ n ≤ Nat.factorial (n + 1)
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem pow_two_pred_le_factorial : ∀ n : ℕ, 2 ^ (n - 1) ≤ Nat.factorial n
Example 0.3.8: For any real c ≠ 1 and any natural number n, the finite geometric sum satisfies 1 + c + c^2 + ⋯ + c^n = (1 - c^(n+1)) / (1 - c).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma rewrite_neg_ratio (c : ℝ) (m : ℕ) :
(c ^ m - 1) / (c - 1) = (1 - c ^ m) / (1 - c)
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem geometric_sum_closed_form {c : ℝ} (hc : c ≠ 1) (n : ℕ) :
(Finset.sum (Finset.range (n + 1)) fun i => c ^ i) = (1 - c ^ (n + 1)) / (1 - c)
Theorem 0.3.9 (principle of strong induction). Let P : ℕ → Prop. (i) The basis statem/ent P 1 is true. (ii) If P k holds for all k = 1, 2, …, n, then P (n + 1) is true. Then P n holds for all natural numbers n.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem principle_of_strong_induction (P : ℕ → Prop) (h₁ : P 1)
(hstep : ∀ n, (∀ k, 1 ≤ k → k ≤ n → P k) → P (n + 1)) :
∀ n : ℕ, P (n + 1)0.3 — Basic Set Theory — Part 3
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 0.3.10: For sets A and B, the Cartesian product is the set of ordered pairs (x, y) with x ∈ A and y ∈ B, written A × B.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev cartesianProductElementCollection (A : Set α) (B : Set β) : Set (α × β) :=
A ×ˢ B
The book's Cartesian product coincides with mathlib's set product.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem cartesianProductElementCollection_eq (A : Set α) (B : Set β) :
cartesianProductElementCollection A B = A ×ˢ B
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem mem_cartesianProductElementCollection {A : Set α} {B : Set β} {x : α} {y : β} :
(x, y) ∈ cartesianProductElementCollection (A := A) (B := B) ↔ x ∈ A ∧ y ∈ B
Definition 0.3.11: A function f : A → B is a subset of A × B sending each element of A to a unique y ∈ B; this subset is called the graph of the function. The set A is the domain, R(f) = { y ∈ B | ∃ x ∈ A, (x, y) ∈ f } is the range, and B is the codomain.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def IsFunctionGraph (f : Set (α × β)) (A : Set α) (B : Set β) : Prop :=
(∀ x ∈ A, ∃! y : β, (x, y) ∈ f) ∧ f ⊆ A ×ˢ B
The range of a relation f viewed as the graph of a function with domain A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def functionGraphRange (f : Set (α × β)) (A : Set α) : Set β :=
{ y | ∃ x, x ∈ A ∧ (x, y) ∈ f }
The book's notion of a functional subset of A × B is equivalent to an ordinary mathlib function with domain the subtype of A and codomain B.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
noncomputable def isFunctionGraph_equiv_subtype (A : Set α) (B : Set β) :
{f : Set (α × β) // IsFunctionGraph f A B} ≃ ({x // x ∈ A} → B)
Example 0.3.12: Functions between spaces of functions include the derivative sending a differentiable real function to another real function, the Laplace transform viewed as a function taking functions to functions, and the definite integral assigning a number to a continuous function on [0,1].
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem calculus_function_space_examples :
(∃ _F : {f : ℝ → ℝ // Differentiable ℝ f} → ℝ → ℝ, True) ∧
(∃ _L : (ℝ → ℝ) → ℝ → ℝ, True) ∧
(∃ _I : {g : ℝ → ℝ // ContinuousOn g (Set.Icc (0 : ℝ) 1)} → ℝ, True)
Definition 0.3.13: For a function f : A → B, the image (direct image) of C ⊆ A is f(C) = { f x ∈ B | x ∈ C }, and the inverse image of D ⊆ B is f ⁻¹(D) = { x ∈ A | f x ∈ D }.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev directImageElementCollection (f : α → β) (C : Set α) : Set β :=
Set.image f C
The book's image of a subset is mathlib's Set.image.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem directImageElementCollection_eq (f : α → β) (C : Set α) :
directImageElementCollection f C = Set.image f C
The inverse image of a subset under f.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev inverseImageElementCollection (f : α → β) (D : Set β) : Set α :=
f ⁻¹' D
The book's inverse image coincides with mathlib's preimage.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem inverseImageElementCollection_eq (f : α → β) (D : Set β) :
inverseImageElementCollection f D = (f ⁻¹' D)
Example 0.3.14: For f(x) = sin (π x), one has f([0, 1/2]) = [0, 1] and f ⁻¹({0}) = ℤ, etc.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
noncomputable def sinPiFunction : ℝ → ℝ := fun x => Real.sin (Real.pi * x)
Example 0.3.14: The image of [0, 1/2] under x ↦ sin (π x) is [0, 1].
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem sinPiFunction_image_half_interval :
Set.image sinPiFunction (Set.Icc (0 : ℝ) (1 / 2)) = Set.Icc (0 : ℝ) 1
Example 0.3.14: The preimage of {0} under x ↦ sin (π x) is the set of integers.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem sinPiFunction_preimage_zero :
sinPiFunction ⁻¹' ({0} : Set ℝ) = Set.range fun n : ℤ => (n : ℝ)
Proposition 0.3.15: For a function f : A → B and subsets C, D of B, f ⁻¹'(C ∪ D) = f ⁻¹' C ∪ f ⁻¹' D, f ⁻¹'(C ∩ D) = f ⁻¹' C ∩ f ⁻¹' D, and f ⁻¹'(Cᶜ) = (f ⁻¹' C)ᶜ.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem preimage_union_inter_compl {f : α → β} {C D : Set β} :
f ⁻¹' (C ∪ D) = f ⁻¹' C ∪ f ⁻¹' D ∧
f ⁻¹' (C ∩ D) = f ⁻¹' C ∩ f ⁻¹' D ∧
f ⁻¹' (Cᶜ) = (f ⁻¹' C)ᶜ
Proposition 0.3.16: For a function f : A → B and subsets C, D of A, f (C ∪ D) = f (C) ∪ f (D) and f (C ∩ D) ⊆ f (C) ∩ f (D).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem image_union_inter_subset {f : α → β} {C D : Set α} :
f '' (C ∪ D) = f '' C ∪ f '' D ∧
f '' (C ∩ D) ⊆ f '' C ∩ f '' D
Definition 0.3.17: A function f : A → B is injective (one-to-one) if f x₁ = f x₂ implies x₁ = x₂, equivalently each fiber f ⁻¹' {y} is empty or a singleton; it is surjective (onto) if f(A) = B, i.e., its range equals its codomain; it is bijective if both.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev injectiveFunction (f : α → β) : Prop :=
Function.Injective f
The book's injectivity is mathlib's Function.Injective.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem injectiveFunction_iff {f : α → β} :
injectiveFunction f ↔ Function.Injective f
The book's notion of surjective function.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev surjectiveFunction (f : α → β) : Prop :=
Function.Surjective f
The book's surjectivity coincides with mathlib's Function.Surjective.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem surjectiveFunction_iff {f : α → β} :
surjectiveFunction f ↔ Function.Surjective f
The book's bijection is a function that is both injective and surjective.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev bijectiveFunction (f : α → β) : Prop :=
Function.Bijective f
The book's bijectivity is mathlib's Function.Bijective.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem bijectiveFunction_iff {f : α → β} :
bijectiveFunction f ↔ Function.Bijective f
Definition 0.3.18: For functions f : A → B and g : B → C, the composition g ∘ f : A → C is given by (g ∘ f) x = g (f x).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev functionComposition (g : β → γ) (f : α → β) : α → γ :=
g ∘ f
The book's composition of functions is mathlib's function composition.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem functionComposition_eq (g : β → γ) (f : α → β) :
functionComposition (g := g) (f := f) = g ∘ f
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem functionComposition_apply (g : β → γ) (f : α → β) (x : α) :
functionComposition (g := g) (f := f) x = g (f x)
Helper: from a functional graph, choose the output in B for each x ∈ A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
noncomputable def functionGraphToSubtypeFun (f : Set (α × β)) (A : Set α) (B : Set β)
(hf : IsFunctionGraph f A B) : {x // x ∈ A} → B
Helper: the chosen value from a functional graph lies in the graph.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma functionGraphToSubtypeFun_mem (f : Set (α × β)) (A : Set α) (B : Set β)
(hf : IsFunctionGraph f A B) (x : {x // x ∈ A}) :
(x.1, (functionGraphToSubtypeFun f A B hf x).1) ∈ f
Helper: uniqueness for the chosen value from a functional graph.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma functionGraphToSubtypeFun_eq_of_mem (f : Set (α × β)) (A : Set α) (B : Set β)
(hf : IsFunctionGraph f A B) (x : {x // x ∈ A}) {y : β}
(hy : (x.1, y) ∈ f) :
y = (functionGraphToSubtypeFun f A B hf x).1
Helper: the graph set associated to a subtype-valued function.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def subtypeFunGraph (A : Set α) (B : Set β) (g : {x // x ∈ A} → B) : Set (α × β) :=
Set.range (fun x => (x.1, (g x).1))
Helper: the graph of a subtype-valued function is functional with domain A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma subtypeFunGraph_isFunctionGraph (A : Set α) (B : Set β) (g : {x // x ∈ A} → B) :
IsFunctionGraph (subtypeFunGraph A B g) A B
Helper: pick a constant function in the derivative-function space.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma exists_const_derivative_space :
∃ _F : {f : ℝ → ℝ // Differentiable ℝ f} → ℝ → ℝ, True
Helper: pick a constant function in the Laplace-transform space.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma exists_const_laplace_space :
∃ _L : (ℝ → ℝ) → ℝ → ℝ, True
Helper: pick a constant function in the integral-assigning space.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma exists_const_integral_space :
∃ _I : {g : ℝ → ℝ // ContinuousOn g (Set.Icc (0 : ℝ) 1)} → ℝ, True
Helper: values of sin (π x) on [0, 1/2] lie in [0, 1].
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma sinPiFunction_image_subset_Icc :
Set.image sinPiFunction (Set.Icc (0 : ℝ) (1 / 2)) ⊆ Set.Icc (0 : ℝ) 1
Helper: every y ∈ [0,1] is of the form sin (π x) for some x ∈ [0,1/2].
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma sinPiFunction_surj_Icc :
Set.Icc (0 : ℝ) 1 ⊆ Set.image sinPiFunction (Set.Icc (0 : ℝ) (1 / 2))
Helper: sin (π x) = 0 iff x is an integer.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma sinPiFunction_preimage_zero_iff (x : ℝ) :
sinPiFunction x = 0 ↔ ∃ n : ℤ, (n : ℝ) = x0.3 — Basic Set Theory — Part 4
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 0.3.19: For a set A, a binary relation on A is a subset R ⊆ A × A of ordered pairs where the relation is said to hold; we write a R b instead of (a, b) ∈ R.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev BinaryRelationOn (A : Set α) : Type _ :=
Set (Subtype A × Subtype A)
The book's binary relations on a set A correspond to mathlib relations on the subtype of A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def binaryRelationOn_equiv_relation (A : Set α) :
BinaryRelationOn A ≃ (Subtype A → Subtype A → Prop)
Example 0.3.20: On the finite set A = {1,2,3} the relation < corresponds to the set of pairs {(1,2), (1,3), (2,3)}, so 1 < 2 holds but 3 < 1 does not. The relation = is given by {(1,1), (2,2), (3,3)}. Any subset of A × A is a relation; for example † = {(1,2), (2,1), (2,3), (3,1)} satisfies 1 † 2 and 3 † 1 but not 1 † 3.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def finiteExampleSet : Set ℕ := {x | x = 1 ∨ x = 2 ∨ x = 3}
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def exampleLtRelationPairs : Set (ℕ × ℕ) :=
{p | p = (1, 2) ∨ p = (1, 3) ∨ p = (2, 3)}
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def exampleEqRelationPairs : Set (ℕ × ℕ) :=
{p | p = (1, 1) ∨ p = (2, 2) ∨ p = (3, 3)}
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def daggerRelationPairs : Set (ℕ × ℕ) :=
{p | p = (1, 2) ∨ p = (2, 1) ∨ p = (2, 3) ∨ p = (3, 1)}
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem example_relation_membership :
(1, 2) ∈ exampleLtRelationPairs ∧ (3, 1) ∉ exampleLtRelationPairs ∧
(1, 1) ∈ exampleEqRelationPairs ∧ (3, 3) ∈ exampleEqRelationPairs ∧
(1, 2) ∈ daggerRelationPairs ∧ (3, 1) ∈ daggerRelationPairs ∧
(1, 3) ∉ daggerRelationPairs
Definition 0.3.21: A relation R on a set A is (i) reflexive if a R a for all a ∈ A; (ii) symmetric if a R b implies b R a; (iii) transitive if a R b and b R c imply a R c. A relation that is reflexive, symmetric, and transitive is an equivalence relation.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev ReflexiveRelationOn (A : Set α) (R : Subtype A → Subtype A → Prop) : Prop :=
Reflexive R
The book's reflexive relation on A is mathlib's Reflexive predicate on the underlying relation on Subtype A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem reflexiveRelationOn_iff (A : Set α) (R : Subtype A → Subtype A → Prop) :
ReflexiveRelationOn A R ↔ Reflexive R
The book's symmetric relation on A is mathlib's Symmetric predicate on the underlying relation on Subtype A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev SymmetricRelationOn (A : Set α) (R : Subtype A → Subtype A → Prop) : Prop :=
Symmetric R
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem symmetricRelationOn_iff (A : Set α) (R : Subtype A → Subtype A → Prop) :
SymmetricRelationOn A R ↔ Symmetric R
The book's transitive relation on A is mathlib's Transitive predicate on the underlying relation on Subtype A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev TransitiveRelationOn (A : Set α) (R : Subtype A → Subtype A → Prop) : Prop :=
Transitive R
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem transitiveRelationOn_iff (A : Set α) (R : Subtype A → Subtype A → Prop) :
TransitiveRelationOn A R ↔ Transitive R
The book's notion of equivalence relation collects reflexivity, symmetry, and transitivity.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev equivalenceRelationOn (A : Set α) (R : Subtype A → Subtype A → Prop) : Prop :=
ReflexiveRelationOn A R ∧ SymmetricRelationOn A R ∧ TransitiveRelationOn A R
The book's equivalence relations on A coincide with mathlib's Equivalence structure for relations on Subtype A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem equivalenceRelationOn_iff_equivalence (A : Set α)
(R : Subtype A → Subtype A → Prop) :
equivalenceRelationOn A R ↔ Equivalence R
Example 0.3.22: On A = {1,2,3}, the usual < is transitive but neither reflexive nor symmetric. The relation ≤ (restricted to A) given by {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)} is reflexive and transitive but not symmetric. The relation ⋆ with pairs {(1,1),(1,2),(2,1),(2,2),(3,3)} is an equivalence relation.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def exampleRelationLtOnA : Subtype finiteExampleSet → Subtype finiteExampleSet → Prop :=
fun x y => x.1 < y.1
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def exampleRelationLeOnA : Subtype finiteExampleSet → Subtype finiteExampleSet → Prop :=
fun x y => x.1 ≤ y.1
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def exampleStarRelation (x y : Subtype finiteExampleSet) : Prop :=
(x.1 ≤ 2 ∧ y.1 ≤ 2) ∨ (x.1 = 3 ∧ y.1 = 3)
Any element of finiteExampleSet is at most 2 or equal to 3.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma finiteExampleSet_le2_or_eq3 (x : Subtype finiteExampleSet) :
x.1 ≤ 2 ∨ x.1 = 3
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem exampleRelationLt_properties :
Transitive exampleRelationLtOnA ∧ ¬ Reflexive exampleRelationLtOnA ∧
¬ Symmetric exampleRelationLtOnA
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem exampleRelationLe_properties :
Reflexive exampleRelationLeOnA ∧ Transitive exampleRelationLeOnA ∧
¬ Symmetric exampleRelationLeOnA
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem exampleStarRelation_equivalence : Equivalence exampleStarRelation
Definition 0.3.23: For a set A with an equivalence relation R and an element a ∈ A, the equivalence class of a, denoted [a], is the set { x ∈ A | a R x }.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def equivalenceClass (A : Set α) (R : Subtype A → Subtype A → Prop) (a : Subtype A) :
Set (Subtype A) :=
{x | R a x}
The book's equivalence class agrees with the class coming from the Setoid built from the equivalence relation R on A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem equivalenceClass_eq_setoid_r (A : Set α) (R : Subtype A → Subtype A → Prop)
(hR : Equivalence R) (a : Subtype A) :
equivalenceClass A R a =
{x : Subtype A | ({ r := R, iseqv := hR } : Setoid (Subtype A)).r a x}
Proposition 0.3.24: If R is an equivalence relation on A, then every a ∈ A lies in exactly one equivalence class. Moreover, a R b if and only if [a] = [b].
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem equivalenceClass_unique (A : Set α) (R : Subtype A → Subtype A → Prop)
(hR : Equivalence R) (a : Subtype A) :
a ∈ equivalenceClass A R a ∧
∀ b : Subtype A,
a ∈ equivalenceClass A R b → equivalenceClass A R b = equivalenceClass A R a
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem related_iff_equivalenceClass_eq (A : Set α) (R : Subtype A → Subtype A → Prop)
(hR : Equivalence R) (a b : Subtype A) :
R a b ↔ equivalenceClass A R a = equivalenceClass A R b
Example 0.3.25: Rational numbers can be presented as equivalence classes of pairs (a, b) with a ∈ ℤ and a positive b ∈ ℕ under the relation (a, b) ∼ (c, d) when a * d = b * c. The class of (a, b) is typically written a / b.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def RatPair : Type :=
{p : ℤ × ℕ // 0 < p.2}
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def ratPairRel (p q : RatPair) : Prop :=
p.1.1 * (q.1.2 : ℤ) = q.1.1 * (p.1.2 : ℤ)
The relation used to define rationals as pairs is an equivalence relation.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem ratPairRel_equivalence : Equivalence ratPairRel
The setoid of rational-number representatives as pairs of an integer and a natural number with positive denominator.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def ratPairSetoid : Setoid RatPair :=
{ r := ratPairRel
iseqv := ratPairRel_equivalence }
Rational numbers as the quotient of integer–natural pairs by the relation (a, b) ∼ (c, d) when a * d = b * c.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev rationalNumbersQuot : Type :=
Quot ratPairSetoid
Interpret a numerator–denominator pair as a rational number.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def ratPairToRat (p : RatPair) : ℚ :=
(p.1.1 : ℚ) / (p.1.2 : ℚ)
Cross-multiplication characterizes when two pairs represent the same rational.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma ratPairRel_iff_toRat_eq (p q : RatPair) :
ratPairRel p q ↔ ratPairToRat p = ratPairToRat q
The quotient of integer–natural pairs is equivalent to mathlib's rationals ℚ.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
noncomputable def rationalNumbersQuot_equiv_rat : rationalNumbersQuot ≃ ℚ0.3 — Basic Set Theory — Part 5
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 0.3.26: Sets A and B have the same cardinality when there exists a bijection f : A → B. The cardinality |A| is the equivalence class of all sets with the same cardinality as A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def sameCardinality (A : Type u) (B : Type v) : Prop :=
Nonempty (A ≃ B)
The book's notion of equal cardinalities matches mathlib's equality of cardinals.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem sameCardinality_iff_cardinal_eq {A : Type u} {B : Type v} :
sameCardinality A B ↔
Cardinal.lift.{v, u} (Cardinal.mk A) = Cardinal.lift.{u, v} (Cardinal.mk B)
The cardinality class of a set A is the collection of all sets bijective to A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def cardinalityClass (A : Type u) : Set (Type u) :=
{B | sameCardinality A B}
The book's cardinality |A| corresponds to the mathlib cardinal Cardinal.mk A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev cardinality (A : Type u) : Cardinal :=
Cardinal.mk A
Definition 0.3.27: A set has cardinality n when it is in bijection with {1, 2, …, n} (or is empty when n = 0); such sets are called finite. A set is infinite if it is not finite.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def elementCollectionCardEq (A : Set α) (n : ℕ) : Prop :=
Nonempty ((Subtype A) ≃ Fin n)
The book's notion of a finite set: it has the same cardinality as some {1, …, n}.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev finiteElementCollection (A : Set α) : Prop :=
∃ n, elementCollectionCardEq (A := A) n
The book's finite sets correspond to mathlib's Set.Finite.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem finiteElementCollection_iff_setFinite {A : Set α} :
finiteElementCollection (A := A) ↔ Set.Finite A
The book's infinite sets are those that are not finite.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev infiniteElementCollection (A : Set α) : Prop :=
¬ finiteElementCollection (A := A)
The book's infinite sets correspond to mathlib's Set.Infinite.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem infiniteElementCollection_iff_setInfinite {A : Set α} :
infiniteElementCollection (A := A) ↔ Set.Infinite A
Definition 0.3.28: We write |A| ≤ |B| if there is an injection from A to B; |A| = |B| when the two have the same cardinality; |A| < |B| when |A| ≤ |B| but the cardinalities are not equal.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def cardinalLe (A : Type u) (B : Type v) : Prop :=
∃ f : A → B, Function.Injective f
The book's |A| ≤ |B| corresponds to the cardinal inequality of Cardinal.mk.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem cardinalLe_iff {A : Type u} {B : Type v} :
cardinalLe A B ↔ Cardinal.lift.{v, u} (Cardinal.mk A) ≤ Cardinal.lift.{u, v} (Cardinal.mk B)
The book's strict cardinal inequality |A| < |B| means |A| ≤ |B| but not equal.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def cardinalLt (A : Type u) (B : Type v) : Prop :=
cardinalLe A B ∧ ¬ sameCardinality A B
The book's |A| < |B| matches the strict inequality of cardinals.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem cardinalLt_iff {A : Type u} {B : Type v} :
cardinalLt A B ↔ Cardinal.lift.{v, u} (Cardinal.mk A) < Cardinal.lift.{u, v} (Cardinal.mk B)
Definition 0.3.29: A set is countably infinite if its cardinality equals that of the natural numbers; it is countable if it is finite or countably infinite; otherwise it is uncountable.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def countablyInfiniteElementCollection (A : Set α) : Prop :=
Nonempty ((Subtype A) ≃ ℕ)
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem countablyInfiniteElementCollection_iff_cardinal_eq_nat {A : Set α} :
countablyInfiniteElementCollection (A := A) ↔ Cardinal.mk (Subtype A) = Cardinal.aleph0
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def countableElementCollection (A : Set α) : Prop :=
finiteElementCollection (A := A) ∨ countablyInfiniteElementCollection (A := A)
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def uncountableElementCollection (A : Set α) : Prop :=
¬ countableElementCollection (A := A)
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem countableElementCollection_iff_setCountable {A : Set α} :
countableElementCollection (A := A) ↔ Set.Countable A
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem uncountableElementCollection_iff_not_setCountable {A : Set α} :
uncountableElementCollection (A := A) ↔ ¬ Set.Countable A
Example 0.3.30: The set E of even natural numbers has the same cardinality as ℕ; the bijection is given by n ↦ 2n.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
def evenNaturals : Set ℕ := {n | Even n}
The map n ↦ 2n is a bijection from ℕ onto the even naturals.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma evenNaturals_map_bijective :
Function.Bijective
(fun n : ℕ => (⟨2 * n, by
change Even (2 * n)
exact even_two_mul n⟩ : Subtype evenNaturals))
An explicit equivalence between ℕ and the even naturals.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma equiv_nat_evenNaturals : Nonempty (ℕ ≃ Subtype evenNaturals)
Example 0.3.30 (continued).
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem evenNaturals_sameCardinality_nat :
sameCardinality (Subtype evenNaturals) ℕ
Example 0.3.31: The Cartesian product ℕ × ℕ is countably infinite, for example via the diagonal enumeration (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ….
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem natProd_countablyInfinite :
countablyInfiniteElementCollection (A := (Set.univ : Set (ℕ × ℕ)))
ℚ is denumerable, so we can pick an explicit equivalence with ℕ.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
lemma rat_equiv_nat : Nonempty (ℚ ≃ ℕ)
Example 0.3.32: The set of rational numbers is countable (in fact countably infinite), e.g., by enumerating positive fractions in a grid and then inserting 0 and their negatives.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem rationals_countablyInfinite :
countablyInfiniteElementCollection (A := (Set.univ : Set ℚ))
Definition 0.3.33: The power set 𝒫(A) of a set A is the set of all subsets of A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
abbrev powerSetElementCollection (A : Set α) : Set (Set α) :=
𝒫 A
The book's power set of A is mathlib's 𝒫 A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem powerSetElementCollection_eq (A : Set α) :
powerSetElementCollection (A := A) = 𝒫 A
Membership in the power set means being a subset.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem mem_powerSetElementCollection {A : Set α} {B : Set α} :
B ∈ powerSetElementCollection (A := A) ↔ B ⊆ A
Theorem 0.3.34 (Cantor). For any set A, the cardinality of A is strictly less than the cardinality of its power set 𝒫 A; in particular there is no surjection from A onto 𝒫 A.
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem cantor_cardinal_lt (A : Type u) : Cardinal.mk A < Cardinal.mk (Set A)
open scoped BigOperators
universe u v w
variable {α : Type u} {β : Type v} {γ : Type w}
theorem no_surjection_to_powerSet (A : Type u) (f : A → Set A) :
¬ Function.Surjective f