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.
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
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
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
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 α
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
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
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
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
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
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₀
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)
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
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
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)
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)
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₀
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
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
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₀
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₀
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₀
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
No rational number has square equal to 2.
universe u
theorem rational_sq_eq_two_absurd : ¬ ∃ x : ℚ, x * x = (2 : ℚ)
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)
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)
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
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
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
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
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
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
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)
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)
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 ℚ)
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
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 ℤ
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
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
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
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
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
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)
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
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
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
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
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
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
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
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
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)
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 ℂ)
universe u
variable (F : Type u)
lemma complex_I_square_pos [LinearOrder ℂ] [IsStrictOrderedRing ℂ] :
(0 : ℂ) < (Complex.I : ℂ) ^ 2
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 ℂ
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 infA1.2 — The Set of Real Numbers
Lean authors: Zichen Wang, Zaiwen Wen.
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))
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)
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
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 : ℝ)
The book's notation √2 realized via the mathlib square root.
universe u v
noncomputable def sqrtTwo : ℝ := Real.sqrt 2
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 : ℝ)
Uniqueness of the positive square root of 2.
universe u v
lemma sqrtTwo_unique {r : ℝ} (hr : 0 < r ∧ r ^ 2 = (2 : ℝ)) : r = sqrtTwo
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)
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 : ℝ)
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)
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
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
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)
(i) The extended supremum of the empty set is -∞.
universe u v
lemma extendedSup_empty : extendedSup (∅ : Set ℝ) = (⊥ : EReal)
(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)
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)
(iii) The extended infimum of the empty set is ∞.
universe u v
lemma extendedInf_empty : extendedInf (∅ : Set ℝ) = (⊤ : EReal)
(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.
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|)
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|
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|
open scoped BigOperators
theorem real_abs_sub_le (x y : ℝ) : |x - y| ≤ |x| + |y|
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 → ℝ) :
open scoped BigOperators
lemma abs_x_le_five_of_mem_interval {x : ℝ} (hx : x ∈ Set.Icc (-1 : ℝ) 5) :
open scoped BigOperators
lemma abs_quad_le_linear_in_abs (x : ℝ) :
open scoped BigOperators
lemma poly_bound_at_abs_le_five {a : ℝ} (ha0 : 0 ≤ |a|) (ha : |a| ≤ 5) :
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) :
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
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.
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)
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.
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)
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
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
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)
open Filter
open scoped BigOperators
lemma decimalPrefix_nonneg (digits : ℕ → Fin 10) (n : ℕ) :
0 ≤ decimalPrefix digits n
open Filter
open scoped BigOperators
lemma decimalPrefix_le_succ (digits : ℕ → Fin 10) (n : ℕ) :
decimalPrefix digits n ≤ decimalPrefix digits (n + 1)
open Filter
open scoped BigOperators
lemma decimalPrefix_monotone (digits : ℕ → Fin 10) :
Monotone (decimalPrefix digits)
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
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
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
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 < ε
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
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
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
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
open Filter
open scoped BigOperators
lemma exists_digits_decimalBoundsStrict {x : ℝ} (hx : x ∈ Set.Ioc (0 : ℝ) 1) :
∃ digits : ℕ → Fin 10, decimalBoundsStrict digits x
open Filter
open scoped BigOperators
lemma decimalBoundsStrict_digits_unique {x : ℝ} {digits₁ digits₂ : ℕ → Fin 10}
(h₁ : decimalBoundsStrict digits₁ x) (h₂ : decimalBoundsStrict digits₂ x) :
digits₁ = digits₂
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
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 : ℝ)
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)
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)
Triangular numbers: triangle n = 1 + 2 + … + n.
open Filter
open scoped BigOperators
def Nat.triangle : ℕ → ℕ
open Filter
open scoped BigOperators
@[simp] lemma Nat.triangle_zero : Nat.triangle 0 = 0
open Filter
open scoped BigOperators
lemma Nat.triangle_succ' (n : ℕ) :
Nat.triangle (n + 1) = Nat.triangle n + (n + 1)
Digits for Example 1.5.4: 1 at triangular indices and 0 otherwise.
open Filter
open scoped BigOperators
noncomputable def digitsInc : ℕ → Fin 10
open Filter
open scoped BigOperators
lemma digitsInc_triangle (k : ℕ) : digitsInc (Nat.triangle (k + 1)) = 1
open Filter
open scoped BigOperators
lemma digitsInc_zero {n : ℕ} (h : ¬ ∃ k, n = Nat.triangle (k + 1)) :
digitsInc n = 0
open Filter
open scoped BigOperators
lemma digitsInc_le_one (n : ℕ) : (digitsInc n : ℝ) ≤ 1
open Filter
open scoped BigOperators
lemma triangle_strictMono : StrictMono Nat.triangle
open Filter
open scoped BigOperators
lemma le_triangle_succ (k : ℕ) : k ≤ Nat.triangle (k + 1)
open Filter
open scoped BigOperators
lemma digitsInc_nonperiodic_gap :
∀ N P, 0 < P → ∃ n ≥ N, digitsInc n = 1 ∧ digitsInc (n + P) = 0
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)
open Filter
open scoped BigOperators
lemma decimalWithIncreasingZeroBlocks_bounds :
decimalBoundsStrict digitsInc decimalWithIncreasingZeroBlocks
The number decimalWithIncreasingZeroBlocks from Example 1.5.4 is irrational.
open Filter
open scoped BigOperators
theorem irrational_decimalWithIncreasingZeroBlocks :
Irrational decimalWithIncreasingZeroBlocks