Chapter 01 — Real Numbers

Proofs omitted. Hover over highlighted terms to see their Lean types.

Reading sections

1.1 — Basic Properties

Lean authors: Zichen Wang, Zaiwen Wen.

Source header

Definition 1.1.1: An ordered set is a set S with a relation < such that (i) (trichotomy) for all x y ∈ S, exactly one of x < y, x = y, or y < x holds, and (ii) (transitivity) if x < y and y < z then x < z. We write x ≤ y if x < y or x = y, and define >, ≥ analogously.

universe u structure OrderedSet (α : Type u) where lt : α → α → Prop trichotomous : ∀ x y, lt x y ∨ x = y ∨ lt y x irrefl : ∀ x, ¬ lt x x trans : ∀ {x y z}, lt x y → lt y z → lt x z

Lean source

The weak order associated to an ordered set.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) def le (x y : α) : Prop := S.lt x y ∨ x = y

Lean source

The axioms of an ordered set give a strict total order in mathlib's sense.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) theorem toStrictTotalOrder : IsStrictTotalOrder α S.lt

Lean source

A strict total order in mathlib yields the ordered-set structure described in Definition 1.1.1.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) def ofStrictTotalOrder {lt : α → α → Prop} (h : IsStrictTotalOrder α lt) : OrderedSet α

Lean source

An element bounding every member of E above.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) def IsUpperBound (b : α) : Prop := ∀ ⦃x⦄, x ∈ E → S.le x b

Lean source

An element bounding every member of E below.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) def IsLowerBound (b : α) : Prop := ∀ ⦃x⦄, x ∈ E → S.le b x

Lean source

Existence of an upper bound for E.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) def BoundedAbove : Prop := ∃ b, IsUpperBound (S := S) (E := E) b

Lean source

Existence of a lower bound for E.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) def BoundedBelow : Prop := ∃ b, IsLowerBound (S := S) (E := E) b

Lean source

An upper bound that is minimal among all upper bounds.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) def IsLeastUpperBound (b₀ : α) : Prop := IsUpperBound (S := S) (E := E) b₀ ∧ ∀ b, IsUpperBound (S := S) (E := E) b → S.le b₀ b

Lean source

A lower bound that is maximal among all lower bounds.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) def IsGreatestLowerBound (b₀ : α) : Prop := IsLowerBound (S := S) (E := E) b₀ ∧ ∀ b, IsLowerBound (S := S) (E := E) b → S.le b b₀

Lean source

A set that is both bounded above and bounded below.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) def Bounded : Prop := BoundedAbove (S := S) (E := E) ∧ BoundedBelow (S := S) (E := E)

Lean source

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) noncomputable def supremum (h : ∃ b₀, IsLeastUpperBound (S := S) (E := E) b₀) : α := Classical.choose h

Lean source

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) noncomputable def infimum (h : ∃ b₀, IsGreatestLowerBound (S := S) (E := E) b₀) : α := Classical.choose h

Lean source

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) lemma supremum_spec (h : ∃ b₀, IsLeastUpperBound (S := S) (E := E) b₀) : IsLeastUpperBound (S := S) (E := E) (supremum (S := S) (E := E) h)

Lean source

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) lemma infimum_spec (h : ∃ b₀, IsGreatestLowerBound (S := S) (E := E) b₀) : IsGreatestLowerBound (S := S) (E := E) (infimum (S := S) (E := E) h)

Lean source

Definition 1.1.3: An ordered set has the least-upper-bound property if every nonempty subset that is bounded above has a least upper bound (supremum) in the set.

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) def LeastUpperBoundProperty : Prop := ∀ {E : Set α}, E.Nonempty → BoundedAbove (S := S) (E := E) → ∃ b₀, IsLeastUpperBound (S := S) (E := E) b₀

Lean source

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) variable [Preorder α] lemma boundedAbove_iff_bddAbove (hle : ∀ x y, S.le x y ↔ x ≤ y) : BoundedAbove (S := S) (E := E) ↔ BddAbove E

Lean source

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) variable [Preorder α] lemma boundedBelow_iff_bddBelow (hle : ∀ x y, S.le x y ↔ x ≤ y) : BoundedBelow (S := S) (E := E) ↔ BddBelow E

Lean source

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) variable [Preorder α] lemma leastUpperBound_iff_isLUB {b₀ : α} (hle : ∀ x y, S.le x y ↔ x ≤ y) : IsLeastUpperBound (S := S) (E := E) b₀ ↔ IsLUB E b₀

Lean source

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) variable [Preorder α] lemma greatestLowerBound_iff_isGLB {b₀ : α} (hle : ∀ x y, S.le x y ↔ x ≤ y) : IsGreatestLowerBound (S := S) (E := E) b₀ ↔ IsGLB E b₀

Lean source

universe u namespace OrderedSet variable {α : Type u} (S : OrderedSet α) (E : Set α) variable [Preorder α] lemma leastUpperBoundProperty_iff (hle : ∀ x y, S.le x y ↔ x ≤ y) : LeastUpperBoundProperty (S := S) ↔ ∀ {E : Set α}, E.Nonempty → BddAbove E → ∃ b₀, IsLUB E b₀

Lean source

Example 1.1.4: The subset {x : ℚ | x^2 < 2} has no supremum in ℚ, so ℚ does not have the least-upper-bound property. Equivalently, there is no rational square root of 2.

universe u theorem rat_sq_lt_two_has_no_sup : ¬ ∃ q : ℚ, IsLUB {x : ℚ | x * x < (2 : ℚ)} q

Lean source

No rational number has square equal to 2.

universe u theorem rational_sq_eq_two_absurd : ¬ ∃ x : ℚ, x * x = (2 : ℚ)

Lean source

Definition 1.1.5: A field is a set F with addition and multiplication such that (A1) if x,y ∈ F then x + y ∈ F; (A2) addition is commutative; (A3) addition is associative; (A4) there is 0 ∈ F with 0 + x = x; (A5) every x has an additive inverse -x with x + (-x) = 0; (M1) if x,y ∈ F then x * y ∈ F; (M2) multiplication is commutative; (M3) multiplication is associative; (M4) there is 1 ∈ F with 1 * x = x and 1 ≠ 0; (M5) every x ≠ 0 has a multiplicative inverse x⁻¹ with x * x⁻¹ = 1; and (D) distributivity x * (y + z) = x * y + x * z holds.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] structure FieldAxioms (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] : Prop where add_comm : ∀ x y : F, x + y = y + x add_assoc : ∀ x y z : F, (x + y) + z = x + (y + z) zero_add : ∀ x : F, 0 + x = x add_left_neg : ∀ x : F, x + (-x) = 0 mul_comm : ∀ x y : F, x * y = y * x mul_assoc : ∀ x y z : F, (x * y) * z = x * (y * z) one_mul : ∀ x : F, (1 : F) * x = x mul_inv_cancel : ∀ {x : F}, x ≠ 0 → x * x⁻¹ = (1 : F) distrib : ∀ x y z : F, x * (y + z) = x * y + x * z one_ne_zero : (1 : F) ≠ (0 : F)

Lean source

Mathlib's Field structure satisfies the axioms in Definition 1.1.5.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) lemma field_axioms_of_field [Field F] : FieldAxioms (F := F)

Lean source

From the field axioms we can derive the right identity for addition.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) lemma FieldAxioms.add_zero [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] (h : FieldAxioms (F := F)) (x : F) : x + 0 = x

Lean source

From the field axioms we can derive right multiplication by 1.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) lemma FieldAxioms.mul_one [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] (h : FieldAxioms (F := F)) (x : F) : x * (1 : F) = x

Lean source

From the field axioms we obtain right distributivity.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) lemma FieldAxioms.right_distrib [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] (h : FieldAxioms (F := F)) (x y z : F) : (x + y) * z = x * z + y * z

Lean source

From the field axioms we can show that x * 0 = 0.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) lemma FieldAxioms.mul_zero [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] (h : FieldAxioms (F := F)) (x : F) : x * (0 : F) = 0

Lean source

From the field axioms we can show that 0 * x = 0.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) lemma FieldAxioms.zero_mul [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] (h : FieldAxioms (F := F)) (x : F) : (0 : F) * x = 0

Lean source

Construct a mathlib Field structure from the axioms in Definition 1.1.5.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) noncomputable def field_structure_from_axioms [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] (h : FieldAxioms (F := F)) : Field F

Lean source

The axioms in Definition 1.1.5 recover the existence of a mathlib Field structure.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) lemma field_of_field_axioms [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] (h : FieldAxioms (F := F)) : Nonempty (Field F)

Lean source

The book's axioms for a field are equivalent to the existence of a mathlib Field structure using the same operations.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) theorem field_iff_field_axioms : (∃ inst : Field F, (by let _ : Field F := inst; exact FieldAxioms (F := F))) ↔ Nonempty (Field F)

Lean source

Example 1.1.6: The rationals ℚ form a field, while the integers ℤ fail axiom (M5) because 2 has no multiplicative inverse; this is the only field axiom that does not hold for ℤ.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) theorem rationals_field : Nonempty (Field ℚ)

Lean source

The multiplicative inverse required by (M5) for 2 : ℤ does not exist.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) theorem two_mul_eq_one_int_absurd : ¬ ∃ x : ℤ, (2 : ℤ) * x = 1

Lean source

The usual ring structure on the integers does not extend to a field structure.

universe u variable (F : Type u) [Add F] [Mul F] [Zero F] [One F] [Neg F] [Inv F] variable (F : Type u) theorem integers_not_field : ¬ IsField ℤ

Lean source

Definition 1.1.7: An ordered field is a field equipped with a strict total order such that (i) x < y implies x + z < y + z for all x y z, and (ii) 0 < x and 0 < y imply 0 < x * y. Elements with 0 < x are positive, those with x < 0 are negative, 0 < x ∨ x = 0 are nonnegative, and x < 0 ∨ x = 0 are nonpositive.

universe u structure OrderedFieldAxioms (F : Type u) [Field F] [LT F] : Prop where order : IsStrictTotalOrder F (· < ·) add_lt_add : ∀ {x y z : F}, x < y → x + z < y + z mul_pos : ∀ {x y : F}, 0 < x → 0 < y → 0 < x * y

Lean source

An element is positive if it is greater than zero.

universe u variable (F : Type u) [Field F] [LT F] def isPositive (x : F) : Prop := 0 < x

Lean source

An element is negative if it is less than zero.

universe u variable (F : Type u) [Field F] [LT F] def isNegative (x : F) : Prop := x < 0

Lean source

An element is nonnegative if it is positive or zero.

universe u variable (F : Type u) [Field F] [LT F] def isNonnegative (x : F) : Prop := 0 < x ∨ x = 0

Lean source

An element is nonpositive if it is negative or zero.

universe u variable (F : Type u) [Field F] [LT F] def isNonpositive (x : F) : Prop := x < 0 ∨ x = 0

Lean source

Mathlib's ordered ring structure (Field together with a linear order and compatibility axioms) satisfies the ordered-field axioms in Definition 1.1.7.

universe u variable (F : Type u) lemma orderedFieldAxioms_of_isStrictOrderedRing [Field F] [LinearOrder F] [IsStrictOrderedRing F] : OrderedFieldAxioms (F := F)

Lean source

The book's ordered-field axioms are equivalent to the existence of a mathlib structure using the same operations.

universe u variable (F : Type u) theorem orderedField_iff_isStrictOrderedRing [Field F] [LinearOrder F] : OrderedFieldAxioms (F := F) ↔ IsStrictOrderedRing F

Lean source

Proposition 1.1.8: Let F be an ordered field and x y z w ∈ F. (i) If x > 0, then -x < 0 (and conversely). (ii) If x > 0 and y < z, then x * y < x * z. (iii) If x < 0 and y < z, then x * y > x * z. (iv) If x ≠ 0, then x^2 > 0. (v) If 0 < x < y, then 0 < 1 / y < 1 / x. (vi) If 0 < x < y, then x^2 < y^2. (vii) If x ≤ y and z ≤ w, then x + z ≤ y + w.

universe u variable (F : Type u) variable {F : Type u} [Field F] [LinearOrder F] [IsStrictOrderedRing F] variable {x y z w : F} theorem orderedField_neg_of_pos_iff : x > 0 ↔ -x < 0

Lean source

universe u variable (F : Type u) variable {F : Type u} [Field F] [LinearOrder F] [IsStrictOrderedRing F] variable {x y z w : F} theorem orderedField_mul_lt_mul_left_of_pos (hx : 0 < x) (hyz : y < z) : x * y < x * z

Lean source

universe u variable (F : Type u) variable {F : Type u} [Field F] [LinearOrder F] [IsStrictOrderedRing F] variable {x y z w : F} theorem orderedField_mul_gt_mul_left_of_neg (hx : x < 0) (hyz : y < z) : x * y > x * z

Lean source

universe u variable (F : Type u) variable {F : Type u} [Field F] [LinearOrder F] [IsStrictOrderedRing F] variable {x y z w : F} theorem orderedField_sq_pos_of_ne_zero (hx : x ≠ 0) : x ^ 2 > 0

Lean source

universe u variable (F : Type u) variable {F : Type u} [Field F] [LinearOrder F] [IsStrictOrderedRing F] variable {x y z w : F} theorem orderedField_inv_bounds_of_lt (hx : 0 < x) (hxy : x < y) : 0 < (1 / y) ∧ 1 / y < 1 / x

Lean source

universe u variable (F : Type u) variable {F : Type u} [Field F] [LinearOrder F] [IsStrictOrderedRing F] variable {x y z w : F} theorem orderedField_sq_lt_sq_of_pos_of_lt (hx : 0 < x) (hxy : x < y) : x ^ 2 < y ^ 2

Lean source

universe u variable (F : Type u) variable {F : Type u} [Field F] [LinearOrder F] [IsStrictOrderedRing F] variable {x y z w : F} theorem orderedField_add_le_add (hxy : x ≤ y) (hzw : z ≤ w) : x + z ≤ y + w

Lean source

Proposition 1.1.9: In an ordered field, if x * y > 0 then either both x and y are positive or both are negative.

universe u variable (F : Type u) theorem pos_mul_same_sign {F : Type u} [Field F] [LinearOrder F] [IsStrictOrderedRing F] {x y : F} (h : x * y > 0) : (0 < x ∧ 0 < y) ∨ (x < 0 ∧ y < 0)

Lean source

Example 1.1.10: The complex numbers ℂ = {x + iy | x y ∈ ℝ} satisfy I^2 = -1 and form a field. No ordering of ℂ can make it an ordered field: in every ordered field, -1 < 0 and squares of nonzero elements are positive, but (I : ℂ)^2 = -1.

universe u variable (F : Type u) theorem complex_field : Nonempty (Field ℂ)

Lean source

universe u variable (F : Type u) lemma complex_I_square_pos [LinearOrder ℂ] [IsStrictOrderedRing ℂ] : (0 : ℂ) < (Complex.I : ℂ) ^ 2

Lean source

There is no way to equip ℂ with a linear order making it an ordered field.

universe u variable (F : Type u) theorem complex_not_linearOrderedField : ¬ ∃ _ : LinearOrder ℂ, IsStrictOrderedRing ℂ

Lean source

Proposition 1.1.11: In an ordered field with the least-upper-bound property, every nonempty subset that is bounded below has an infimum.

universe u variable (F : Type u) theorem infimum_exists_of_bddBelow {F : Type u} [Field F] [LinearOrder F] [IsStrictOrderedRing F] (lub : ∀ {E : Set F}, E.Nonempty → BddAbove E → ∃ b₀, IsLUB E b₀) {A : Set F} (hA : A.Nonempty) (hB : BddBelow A) : ∃ infA, IsGLB A infA

1.2 — The Set of Real Numbers

Lean authors: Zichen Wang, Zaiwen Wen.

Source header

Theorem 1.2.1: There exists an ordered field ℝ with the least-upper-bound property containing the rationals ℚ; such a structure is unique up to an order-preserving field isomorphism.

universe u v theorem real_exists_complete_ordered_field : ∃ (R : Type) (hF : Field R) (hL : LinearOrder R) (hS : IsStrictOrderedRing R), by let _ : Field R := hF let _ : LinearOrder R := hL let _ : IsStrictOrderedRing R := hS exact (∀ {E : Set R}, E.Nonempty → BddAbove E → ∃ supE, IsLUB E supE) ∧ Function.Injective (fun q : ℚ => (q : R))

Lean source

Any two ordered fields with the least-upper-bound property that contain the rationals are isomorphic as ordered fields.

universe u v theorem real_unique_complete_ordered_field (R : Type u) [Field R] [ConditionallyCompleteLinearOrder R] [IsStrictOrderedRing R] (S : Type v) [Field S] [ConditionallyCompleteLinearOrder S] [IsStrictOrderedRing S] : Nonempty (R ≃+* S)

Lean source

Proposition 1.2.2: If a real number x satisfies x ≤ ε for every ε > 0, then x ≤ 0.

universe u v theorem real_le_zero_of_le_pos {x : ℝ} (h : ∀ ε > 0, x ≤ ε) : x ≤ 0

Lean source

Example 1.2.3: There exists a unique positive real number r such that r ^ 2 = 2; this number is denoted √2.

universe u v theorem exists_unique_pos_sq_eq_two : ∃! r : ℝ, 0 < r ∧ r ^ 2 = (2 : ℝ)

Lean source

The book's notation √2 realized via the mathlib square root.

universe u v noncomputable def sqrtTwo : ℝ := Real.sqrt 2

Lean source

The element sqrtTwo is positive and squares to 2, matching the defining property of √2.

universe u v lemma sqrtTwo_spec : 0 < sqrtTwo ∧ sqrtTwo ^ 2 = (2 : ℝ)

Lean source

Uniqueness of the positive square root of 2.

universe u v lemma sqrtTwo_unique {r : ℝ} (hr : 0 < r ∧ r ^ 2 = (2 : ℝ)) : r = sqrtTwo

Lean source

Theorem 1.2.4: (i) (Archimedean property) If x, y ∈ ℝ with x > 0, then there exists n ∈ ℕ such that n * x > y. (ii) (ℚ is dense in ℝ) If x, y ∈ ℝ with x < y, then there exists r ∈ ℚ such that x < r < y.

universe u v theorem archimedean_and_rat_dense : (∀ x y : ℝ, 0 < x → ∃ n : ℕ, (n : ℝ) * x > y) ∧ (∀ x y : ℝ, x < y → ∃ r : ℚ, x < (r : ℝ) ∧ (r : ℝ) < y)

Lean source

Corollary 1.2.5: The infimum of the set {1 / n : n ∈ ℕ} is 0.

universe u v theorem inf_nat_inv_eq_zero : sInf (Set.range fun n : ℕ => (1 : ℝ) / (n.succ : ℝ)) = (0 : ℝ)

Lean source

Proposition 1.2.6: Let A ⊆ ℝ be nonempty. (i) If A is bounded above, then sup (x + A) = x + sup A. (ii) If A is bounded below, then inf (x + A) = x + inf A. (iii) If x > 0 and A is bounded above, then sup (x * A) = x * sup A. (iv) If x > 0 and A is bounded below, then inf (x * A) = x * inf A. (v) If x < 0 and A is bounded below, then sup (x * A) = x * inf A. (vi) If x < 0 and A is bounded above, then inf (x * A) = x * sup A.

universe u v theorem sup_inf_arithmetic {A : Set ℝ} (hA : A.Nonempty) : (∀ x, BddAbove A → sSup ((fun a => x + a) '' A) = x + sSup A) ∧ (∀ x, BddBelow A → sInf ((fun a => x + a) '' A) = x + sInf A) ∧ (∀ {x : ℝ}, 0 < x → BddAbove A → sSup ((fun a => x * a) '' A) = x * sSup A) ∧ (∀ {x : ℝ}, 0 < x → BddBelow A → sInf ((fun a => x * a) '' A) = x * sInf A) ∧ (∀ {x : ℝ}, x < 0 → BddBelow A → sSup ((fun a => x * a) '' A) = x * sInf A) ∧ (∀ {x : ℝ}, x < 0 → BddAbove A → sInf ((fun a => x * a) '' A) = x * sSup A)

Lean source

Proposition 1.2.7: If nonempty sets A, B ⊆ ℝ satisfy x ≤ y whenever x ∈ A and y ∈ B, then A is bounded above, B is bounded below, and sSup A ≤ sInf B.

universe u v theorem sup_le_inf_of_forall_le {A B : Set ℝ} (hA : A.Nonempty) (hB : B.Nonempty) (h : ∀ x ∈ A, ∀ y ∈ B, x ≤ y) : BddAbove A ∧ BddBelow B ∧ sSup A ≤ sInf B

Lean source

Proposition 1.2.8: If S ⊆ ℝ is nonempty and bounded above, then for every ε > 0 there exists x ∈ S with sSup S - ε < x ≤ sSup S.

universe u v lemma exists_mem_between_sub_sup {S : Set ℝ} (hS : S.Nonempty) (hSb : BddAbove S) {ε : ℝ} (hε : 0 < ε) : ∃ x ∈ S, sSup S - ε < x ∧ x ≤ sSup S

Lean source

Definition 1.2.9: For a subset A ⊆ ℝ, extend sup and inf to the extended reals so that (i) sup ∅ = -∞, (ii) if A is unbounded above then sup A = ∞, (iii) inf ∅ = ∞, and (iv) if A is unbounded below then inf A = -∞. These agree with sSup and sInf on EReal when we view A as a set of extended real numbers.

universe u v noncomputable def extendedSup (A : Set ℝ) : EReal := sSup (Set.image (fun x : ℝ => (x : EReal)) A)

Lean source

(i) The extended supremum of the empty set is -∞.

universe u v lemma extendedSup_empty : extendedSup (∅ : Set ℝ) = (⊥ : EReal)

Lean source

(ii) If a set of reals is not bounded above, its extended supremum is ∞.

universe u v lemma extendedSup_not_bddAbove {A : Set ℝ} (hA : ¬ BddAbove A) : extendedSup A = (⊤ : EReal)

Lean source

The extended infimum of a set of reals, computed in EReal.

universe u v noncomputable def extendedInf (A : Set ℝ) : EReal := sInf (Set.image (fun x : ℝ => (x : EReal)) A)

Lean source

(iii) The extended infimum of the empty set is ∞.

universe u v lemma extendedInf_empty : extendedInf (∅ : Set ℝ) = (⊤ : EReal)

Lean source

(iv) If a set of reals is not bounded below, its extended infimum is -∞.

universe u v lemma extendedInf_not_bddBelow {A : Set ℝ} (hA : ¬ BddBelow A) : extendedInf A = (⊥ : EReal)

1.3 — Absolute Value and Bounded Functions

Lean authors: Zichen Wang, Zaiwen Wen.

Source header

Proposition 1.3.1: (i) |x| ≥ 0, and |x| = 0 if and only if x = 0. (ii) | -x| = |x| for all real x. (iii) |x * y| = |x| * |y| for all real x, y. (iv) |x| ^ 2 = x ^ 2 for all real x. (v) |x| ≤ y if and only if -y ≤ x ∧ x ≤ y. (vi) -(|x|) ≤ x ∧ x ≤ |x| for all real x.

open scoped BigOperators theorem abs_basic_properties (x y : ℝ) : (0 ≤ |x| ∧ (|x| = 0 ↔ x = 0)) ∧ (|-x| = |x|) ∧ (|x * y| = |x| * |y|) ∧ (|x| ^ 2 = x ^ 2) ∧ (|x| ≤ y ↔ (-y ≤ x ∧ x ≤ y)) ∧ (-|x| ≤ x ∧ x ≤ |x|)

Lean source

Proposition 1.3.2 (Triangle Inequality): For all real numbers x and y, we have |x + y| ≤ |x| + |y|.

open scoped BigOperators theorem real_abs_add_le (x y : ℝ) : |x + y| ≤ |x| + |y|

Lean source

Corollary 1.3.3: (i) (reverse triangle inequality) For real x, y, | |x| - |y| | ≤ |x - y|. (ii) For real x, y, |x - y| ≤ |x| + |y|.

open scoped BigOperators theorem real_abs_abs_sub_abs_le (x y : ℝ) : |(|x| - |y|)| ≤ |x - y|

Lean source

open scoped BigOperators theorem real_abs_sub_le (x y : ℝ) : |x - y| ≤ |x| + |y|

Lean source

Corollary 1.3.4: For real numbers x_1, x_2, ..., x_n, the absolute value of their sum is at most the sum of their absolute values.

open scoped BigOperators theorem real_abs_sum_le_sum_abs {n : ℕ} (f : Fin n → ℝ) :

Lean source

open scoped BigOperators lemma abs_x_le_five_of_mem_interval {x : ℝ} (hx : x ∈ Set.Icc (-1 : ℝ) 5) :

Lean source

open scoped BigOperators lemma abs_quad_le_linear_in_abs (x : ℝ) :

Lean source

open scoped BigOperators lemma poly_bound_at_abs_le_five {a : ℝ} (ha0 : 0 ≤ |a|) (ha : |a| ≤ 5) :

Lean source

Example 1.3.5: On the interval [-1, 5], the quadratic x ^ 2 - 9 * x + 1 is bounded in absolute value by 71; that is, a permissible M satisfying |x ^ 2 - 9 * x + 1| ≤ M for all x in this interval is M = 71.

open scoped BigOperators lemma abs_quadratic_bound_on_interval (x : ℝ) (hx : x ∈ Set.Icc (-1 : ℝ) 5) :

Lean source

Definition 1.3.6: A function f : D → ℝ is bounded if there exists a real M such that |f x| ≤ M for all x ∈ D.

open scoped BigOperators def isBoundedOnReal (D : Set ℝ) (f : D → ℝ) : Prop := ∃ M : ℝ, ∀ x : D, |f x| ≤ M

Lean source

Proposition 1.3.7: If f, g : D → ℝ are bounded functions on a nonempty set D with f x ≤ g x for every x ∈ D, then the supremum of the range of f is at most the supremum of the range of g, and the infimum of the range of f is at most the infimum of the range of g.

open scoped BigOperators lemma sup_inf_monotone_on_nonempty {D : Set ℝ} (hD : D.Nonempty) {f g : D → ℝ} (hf : isBoundedOnReal D f) (hg : isBoundedOnReal D g) (hfg : ∀ x : D, f x ≤ g x) : sSup (Set.range f) ≤ sSup (Set.range g) ∧ sInf (Set.range f) ≤ sInf (Set.range g)

1.4 — Intervals and the Size of R

Lean authors: Zichen Wang, Zaiwen Wen.

Source header

Proposition 1.4.1: A set I ⊆ ℝ is an interval if and only if it contains at least two points and, whenever a, c ∈ I and a < b < c, the point b also belongs to I.

theorem interval_real_iff_two_points_and_between (I : Set ℝ) : (Set.OrdConnected I ∧ ∃ a c, a ≠ c ∧ a ∈ I ∧ c ∈ I) ↔ (∃ a c, a ≠ c ∧ a ∈ I ∧ c ∈ I) ∧ (∀ {a c b}, a ∈ I → c ∈ I → a < b → b < c → b ∈ I)

Lean source

Theorem 1.4.2 (Cantor): The set of real numbers ℝ is uncountable.

theorem cantor_real_uncountable : Uncountable ℝ

1.5 — Decimal Representation of the Reals

Lean authors: Zichen Wang, Zaiwen Wen.

Source header

The partial sum D n of the decimal expansion determined by digits.

open Filter open scoped BigOperators noncomputable def decimalPrefix (digits : ℕ → Fin 10) (n : ℕ) : ℝ := (Finset.range n).sum fun i => (digits (i + 1) : ℝ) / (10 : ℝ) ^ (i + 1)

Lean source

The decimal digits digits approximate x with the bounds D n ≤ x ≤ D n + 1/10^n.

open Filter open scoped BigOperators def decimalBounds (digits : ℕ → Fin 10) (x : ℝ) : Prop := ∀ n : ℕ, decimalPrefix digits n ≤ x ∧ x ≤ decimalPrefix digits n + 1 / (10 : ℝ) ^ n

Lean source

The decimal digits digits approximate x with strict lower bounds D n < x and start with a leading 0 digit.

open Filter open scoped BigOperators def decimalBoundsStrict (digits : ℕ → Fin 10) (x : ℝ) : Prop := digits 0 = 0 ∧ ∀ n : ℕ, decimalPrefix digits n < x ∧ x ≤ decimalPrefix digits n + 1 / (10 : ℝ) ^ n

Lean source

Expanding one more digit in the decimal prefix.

open Filter open scoped BigOperators lemma decimalPrefix_succ (digits : ℕ → Fin 10) (n : ℕ) : decimalPrefix digits (n + 1) = decimalPrefix digits n + (digits (n + 1) : ℝ) / (10 : ℝ) ^ (n + 1)

Lean source

open Filter open scoped BigOperators lemma decimalPrefix_nonneg (digits : ℕ → Fin 10) (n : ℕ) : 0 ≤ decimalPrefix digits n

Lean source

open Filter open scoped BigOperators lemma decimalPrefix_le_succ (digits : ℕ → Fin 10) (n : ℕ) : decimalPrefix digits n ≤ decimalPrefix digits (n + 1)

Lean source

open Filter open scoped BigOperators lemma decimalPrefix_monotone (digits : ℕ → Fin 10) : Monotone (decimalPrefix digits)

Lean source

Bounding the tail of the decimal prefix by a geometric sum.

open Filter open scoped BigOperators lemma decimalPrefix_tail_le (digits : ℕ → Fin 10) (n k : ℕ) : decimalPrefix digits (n + k) ≤ decimalPrefix digits n + 1 / (10 : ℝ) ^ n

Lean source

Each decimal prefix is bounded above by 1.

open Filter open scoped BigOperators lemma decimalPrefix_le_one (digits : ℕ → Fin 10) (n : ℕ) : decimalPrefix digits n ≤ 1

Lean source

A global bound on any prefix in terms of the n-th prefix.

open Filter open scoped BigOperators lemma decimalPrefix_le_prefix_add (digits : ℕ → Fin 10) (n m : ℕ) : decimalPrefix digits m ≤ decimalPrefix digits n + 1 / (10 : ℝ) ^ n

Lean source

Powers 1/10^n can be made arbitrarily small.

open Filter open scoped BigOperators lemma one_div_pow_ten_lt {ε : ℝ} (hε : 0 < ε) : ∃ n : ℕ, 1 / (10 : ℝ) ^ n < ε

Lean source

Using the supremum of decimal prefixes gives an x satisfying the decimal bounds.

open Filter open scoped BigOperators lemma exists_sup_decimalBounds (digits : ℕ → Fin 10) : ∃ x ∈ Set.Icc (0 : ℝ) 1, decimalBounds digits x

Lean source

The value determined by a given digit stream satisfying decimal bounds is unique.

open Filter open scoped BigOperators lemma decimalBounds_value_unique (digits : ℕ → Fin 10) {x y : ℝ} (hx : decimalBounds digits x) (hy : decimalBounds digits y) : x = y

Lean source

open Filter open scoped BigOperators lemma decimalBounds_strict_of_pos_digits {digits : ℕ → Fin 10} {x : ℝ} (hzero : digits 0 = 0) (hpos : ∀ n, 0 < (digits (n + 1) : ℝ)) (h : decimalBounds digits x) : decimalBoundsStrict digits x

Lean source

open Filter open scoped BigOperators lemma diagonal_digits_value (digits : ℕ → Fin 10) (hzero : digits 0 = 0) (hpos : ∀ n, 0 < (digits (n + 1) : ℝ)) : ∃! y : ℝ, y ∈ Set.Icc (0 : ℝ) 1 ∧ decimalBoundsStrict digits y

Lean source

open Filter open scoped BigOperators lemma exists_digits_decimalBoundsStrict {x : ℝ} (hx : x ∈ Set.Ioc (0 : ℝ) 1) : ∃ digits : ℕ → Fin 10, decimalBoundsStrict digits x

Lean source

open Filter open scoped BigOperators lemma decimalBoundsStrict_digits_unique {x : ℝ} {digits₁ digits₂ : ℕ → Fin 10} (h₁ : decimalBoundsStrict digits₁ x) (h₂ : decimalBoundsStrict digits₂ x) : digits₁ = digits₂

Lean source

Proposition 1.5.1. (i) Every infinite sequence of digits 0.d1d2d3… represents a unique real number x ∈ [0, 1] such that D n ≤ x ≤ D n + 1/10^n for all n ∈ ℕ, where D n is the partial sum of the first n digits. (ii) For every x ∈ (0, 1] there exists an infinite sequence of digits representing x, and there is a unique representation satisfying D n < x ≤ D n + 1/10^n for all n ∈ ℕ.

open Filter open scoped BigOperators theorem decimal_expansion_properties : (∀ digits : ℕ → Fin 10, ∃! x : ℝ, x ∈ Set.Icc (0 : ℝ) 1 ∧ decimalBounds digits x) ∧ ∀ x : ℝ, x ∈ Set.Ioc (0 : ℝ) 1 → (∃ digits : ℕ → Fin 10, decimalBounds digits x) ∧ ∃! digits : ℕ → Fin 10, decimalBoundsStrict digits x

Lean source

Diagonal number built from an enumeration of (0, 1] differs from every entry.

open Filter open scoped BigOperators lemma diagonal_not_in_enumeration (f : ℕ → Set.Ioc (0 : ℝ) 1) : ∃ y ∈ Set.Ioc (0 : ℝ) 1, ∀ n : ℕ, y ≠ (f n : ℝ)

Lean source

Theorem 1.5.2 (Cantor): The set (0, 1] is uncountable.

open Filter open scoped BigOperators theorem cantor_uncountable_Ioc : ¬ Set.Countable (Set.Ioc (0 : ℝ) 1)

Lean source

Proposition 1.5.3: If a rational number x ∈ (0, 1] has decimal expansion 0.d₁d₂d₃…, then its digits eventually repeat, i.e., there exist positive integers N and P such that dₙ = dₙ₊ₚ for all n ≥ N.

open Filter open scoped BigOperators theorem rational_decimal_digits_eventually_periodic (x : ℚ) (digits : ℕ → Fin 10) (_hx : (x : ℝ) ∈ Set.Ioc (0 : ℝ) 1) (hx_digits : decimalBounds digits (x : ℝ)) : ∃ N P : ℕ, 0 < N ∧ 0 < P ∧ ∀ {n}, N ≤ n → digits n = digits (n + P)

Lean source

Triangular numbers: triangle n = 1 + 2 + … + n.

open Filter open scoped BigOperators def Nat.triangle : ℕ → ℕ

Lean source

open Filter open scoped BigOperators @[simp] lemma Nat.triangle_zero : Nat.triangle 0 = 0

Lean source

open Filter open scoped BigOperators lemma Nat.triangle_succ' (n : ℕ) : Nat.triangle (n + 1) = Nat.triangle n + (n + 1)

Lean source

Digits for Example 1.5.4: 1 at triangular indices and 0 otherwise.

open Filter open scoped BigOperators noncomputable def digitsInc : ℕ → Fin 10

Lean source

open Filter open scoped BigOperators lemma digitsInc_triangle (k : ℕ) : digitsInc (Nat.triangle (k + 1)) = 1

Lean source

open Filter open scoped BigOperators lemma digitsInc_zero {n : ℕ} (h : ¬ ∃ k, n = Nat.triangle (k + 1)) : digitsInc n = 0

Lean source

open Filter open scoped BigOperators lemma digitsInc_le_one (n : ℕ) : (digitsInc n : ℝ) ≤ 1

Lean source

open Filter open scoped BigOperators lemma triangle_strictMono : StrictMono Nat.triangle

Lean source

open Filter open scoped BigOperators lemma le_triangle_succ (k : ℕ) : k ≤ Nat.triangle (k + 1)

Lean source

open Filter open scoped BigOperators lemma digitsInc_nonperiodic_gap : ∀ N P, 0 < P → ∃ n ≥ N, digitsInc n = 1 ∧ digitsInc (n + P) = 0

Lean source

Example 1.5.4: The real number with decimal expansion 0.101001000100001…, whose 1s occur at the positions 1, 3, 6, 10, … (each separated by an increasing block of zeros), is irrational.

open Filter open scoped BigOperators noncomputable def decimalWithIncreasingZeroBlocks : ℝ := ∑' n : ℕ, (digitsInc (n + 1) : ℝ) / (10 : ℝ) ^ (n + 1)

Lean source

open Filter open scoped BigOperators lemma decimalWithIncreasingZeroBlocks_bounds : decimalBoundsStrict digitsInc decimalWithIncreasingZeroBlocks

Lean source

The number decimalWithIncreasingZeroBlocks from Example 1.5.4 is irrational.

open Filter open scoped BigOperators theorem irrational_decimalWithIncreasingZeroBlocks : Irrational decimalWithIncreasingZeroBlocks