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.

Source header

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 α

Lean source

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 α)

Lean source

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 α

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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 : ℝ)

Lean source

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 : ℝ)

Lean source

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 : ℝ)

Lean source

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 : ℝ)

Lean source

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

Lean source

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

Lean source

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 ℝ)

Lean source

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

Lean source

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

Lean source

open scoped BigOperators universe u v w variable {α : Type u} {β : Type v} {γ : Type w} abbrev intersectionElementCollection (A B : ElementCollection α) : ElementCollection α := A ∩ B

Lean source

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

Lean source

open scoped BigOperators universe u v w variable {α : Type u} {β : Type v} {γ : Type w} abbrev relativeComplementElementCollection (A B : ElementCollection α) : ElementCollection α := A \ B

Lean source

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

Lean source

open scoped BigOperators universe u v w variable {α : Type u} {β : Type v} {γ : Type w} abbrev complementElementCollection (B : ElementCollection α) : ElementCollection α := Set.compl B

Lean source

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

Lean source

open scoped BigOperators universe u v w variable {α : Type u} {β : Type v} {γ : Type w} abbrev disjointElementCollections (A B : ElementCollection α) : Prop := Disjoint A B

Lean source

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 α)

Lean source

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ᶜ

Lean source

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ᶜ

Lean source

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)

Lean source

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)

Lean source

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.

Source header

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)

Lean source

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)

Lean source

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

Lean source

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)

Lean source

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)

Lean source

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.

Source header

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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 }

Lean source

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)

Lean source

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)

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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)

Lean source

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

Lean source

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 : ℝ)

Lean source

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)ᶜ

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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

Lean source

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))

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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))

Lean source

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 : ℝ) = x

0.3 — Basic Set Theory — Part 4

Lean authors: Zichen Wang, Zaiwen Wen.

Source header

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)

Lean source

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)

Lean source

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}

Lean source

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)}

Lean source

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)}

Lean source

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)}

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

open scoped BigOperators universe u v w variable {α : Type u} {β : Type v} {γ : Type w} theorem exampleRelationLt_properties : Transitive exampleRelationLtOnA ∧ ¬ Reflexive exampleRelationLtOnA ∧ ¬ Symmetric exampleRelationLtOnA

Lean source

open scoped BigOperators universe u v w variable {α : Type u} {β : Type v} {γ : Type w} theorem exampleRelationLe_properties : Reflexive exampleRelationLeOnA ∧ Transitive exampleRelationLeOnA ∧ ¬ Symmetric exampleRelationLeOnA

Lean source

open scoped BigOperators universe u v w variable {α : Type u} {β : Type v} {γ : Type w} theorem exampleStarRelation_equivalence : Equivalence exampleStarRelation

Lean source

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}

Lean source

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}

Lean source

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

Lean source

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

Lean source

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}

Lean source

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 : ℤ)

Lean source

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

Lean source

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 }

Lean source

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

Lean source

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 : ℚ)

Lean source

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

Lean source

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.

Source header

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)

Lean source

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)

Lean source

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}

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

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)

Lean source

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) ≃ ℕ)

Lean source

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

Lean source

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)

Lean source

open scoped BigOperators universe u v w variable {α : Type u} {β : Type v} {γ : Type w} def uncountableElementCollection (A : Set α) : Prop := ¬ countableElementCollection (A := A)

Lean source

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

Lean source

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

Lean source

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}

Lean source

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))

Lean source

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)

Lean source

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) ℕ

Lean source

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 (ℕ × ℕ)))

Lean source

ℚ 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 (ℚ ≃ ℕ)

Lean source

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 ℚ))

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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