Chapter 07 — Metric Spaces
Proofs omitted. Hover over highlighted terms to see their Lean types.
Reading sections
7.1 — Metric Spaces
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 7.1.1: A metric on a set X is a function d : X × X → ℝ satisfying (i) d x y ≥ 0 (nonnegativity), (ii) d x y = 0 iff x = y (identity of indiscernibles), (iii) d x y = d y x (symmetry), and (iv) d x z ≤ d x y + d y z (triangle inequality). The pair (X, d) is a metric space.
open scoped BigOperators RealInnerProductSpace
universe u
structure MetricAxioms (X : Type u) (d : X → X → ℝ) : Prop where
nonneg : ∀ x y, 0 ≤ d x y
eq_zero : ∀ x y, d x y = 0 ↔ x = y
symm : ∀ x y, d x y = d y x
triangle : ∀ x y z, d x z ≤ d x y + d y z
A mathlib MetricSpace structure satisfies the book's metric axioms.
open scoped BigOperators RealInnerProductSpace
universe u
lemma metricSpace_metricAxioms (X : Type u) [MetricSpace X] :
MetricAxioms X (fun x y => dist x y)
The metric axioms ensure there is a corresponding mathlib MetricSpace whose distance is the given function.
open scoped BigOperators RealInnerProductSpace
universe u
theorem metricAxioms_iff_metricSpace (X : Type u) (d : X → X → ℝ) :
MetricAxioms X d ↔ ∃ inst : MetricSpace X, inst.dist = d
Example 7.1.2: The standard metric on ℝ is given by d x y = |x - y|, and with this metric ℝ is a metric space.
open scoped BigOperators RealInnerProductSpace
universe u
theorem real_standard_metric (x y : ℝ) : dist x y = |x - y|
Example 7.1.3: On ℝ we can define a nonstandard metric d x y = |x - y| / (|x - y| + 1), which is symmetric, vanishes on the diagonal, satisfies the triangle inequality, and is bounded by 1, so every pair of points is at distance < 1.
open scoped BigOperators RealInnerProductSpace
universe u
noncomputable def realNonstandardDist (x y : ℝ) : ℝ :=
|x - y| / (|x - y| + 1)
open scoped BigOperators RealInnerProductSpace
universe u
lemma realNonstandardDist_metric_axioms :
(∀ x y, 0 ≤ realNonstandardDist x y) ∧
(∀ x, realNonstandardDist x x = 0) ∧
(∀ x y, realNonstandardDist x y = realNonstandardDist y x) ∧
(∀ x y z, realNonstandardDist x z ≤
realNonstandardDist x y + realNonstandardDist y z) ∧
(∀ x y, realNonstandardDist x y < 1)
Lemma 7.1.4 (Cauchy--Schwarz inequality): For vectors x = (x₁, x₂, …, xₙ) and y = (y₁, y₂, …, yₙ) in ℝⁿ, ((∑ₖ xₖ yₖ)²) ≤ (∑ₖ xₖ²)(∑ₖ yₖ²).
open scoped BigOperators RealInnerProductSpace
universe u
lemma cauchySchwarz_fin (n : ℕ) (x y : Fin n → ℝ) :
(∑ k : Fin n, x k * y k) ^ 2 ≤
(∑ k : Fin n, (x k) ^ 2) * (∑ k : Fin n, (y k) ^ 2)
Example 7.1.5: The standard metric on ℝⁿ is d x y = √(∑ k, (x k - y k) ^ 2), and the triangle inequality follows from the Cauchy--Schwarz inequality.
open scoped BigOperators RealInnerProductSpace
universe u
noncomputable def euclideanStandardDist (n : ℕ)
(x y : EuclideanSpace ℝ (Fin n)) : ℝ :=
Real.sqrt (∑ k : Fin n, (x k - y k) ^ 2)
open scoped BigOperators RealInnerProductSpace
universe u
lemma euclideanStandardDist_eq_dist (n : ℕ)
(x y : EuclideanSpace ℝ (Fin n)) :
euclideanStandardDist n x y = dist x y
open scoped BigOperators RealInnerProductSpace
universe u
lemma euclideanStandardDist_triangle (n : ℕ)
(x y z : EuclideanSpace ℝ (Fin n)) :
euclideanStandardDist n x z ≤
euclideanStandardDist n x y + euclideanStandardDist n y z
Example 7.1.6: Viewing ℂ as ℝ², the metric is the Euclidean one, so dist z₁ z₂ = |z₁ - z₂|. The complex modulus is |x + iy| = √(x^2 + y^2), and its square is x^2 + y^2.
open scoped BigOperators RealInnerProductSpace
universe u
lemma complex_dist_eq_abs (z₁ z₂ : ℂ) :
dist z₁ z₂ = ‖z₁ - z₂‖
open scoped BigOperators RealInnerProductSpace
universe u
lemma complex_abs_sq (z : ℂ) :
‖z‖ ^ 2 = z.re ^ 2 + z.im ^ 2
Example 7.1.7: On any set with decidable equality, the discrete distance d x y = 1 if x ≠ y and d x x = 0 defines a metric. In finite cases this places every distinct pair at distance 1; for infinite sets it still provides a genuine metric space structure.
open scoped BigOperators RealInnerProductSpace
universe u
noncomputable def discreteDist {X : Type u} [DecidableEq X] (x y : X) : ℝ :=
if x = y then 0 else 1
open scoped BigOperators RealInnerProductSpace
universe u
lemma discreteDist_nonneg {X : Type u} [DecidableEq X] (x y : X) :
0 ≤ discreteDist x y
open scoped BigOperators RealInnerProductSpace
universe u
lemma discreteDist_eq_zero_iff {X : Type u} [DecidableEq X] (x y : X) :
discreteDist x y = 0 ↔ x = y
open scoped BigOperators RealInnerProductSpace
universe u
lemma discreteDist_triangle {X : Type u} [DecidableEq X]
(x y z : X) :
discreteDist x z ≤ discreteDist x y + discreteDist y z
open scoped BigOperators RealInnerProductSpace
universe u
lemma discreteDist_metricAxioms (X : Type u) [DecidableEq X] :
MetricAxioms X (fun x y => discreteDist x y)
open scoped BigOperators RealInnerProductSpace
universe u
theorem discreteDist_metric_space (X : Type u) [DecidableEq X] :
∃ inst : MetricSpace X,
inst.dist = (fun x y : X => discreteDist x y)
Example 7.1.8: On the space C([a,b], ℝ) of continuous real-valued functions on the interval [a,b], the metric is given by d f g = sup_{x ∈ [a,b]} |f x - g x|, which agrees with the uniform norm ‖f - g‖. Whenever we view C([a,b], ℝ) as a metric space, this is the understood distance.
open scoped BigOperators RealInnerProductSpace
universe u
lemma continuous_interval_dist_eq_uniform {a b : ℝ}
(f g : ContinuousMap (Set.Icc a b) ℝ) :
dist f g = ‖f - g‖
Example 7.1.9: On the unit sphere S² ⊂ ℝ³, the great circle distance between two points is the angle between the lines from the origin, so if x = (x₁,x₂,x₃) and y = (y₁,y₂,y₃), then d x y = arccos (x₁ y₁ + x₂ y₂ + x₃ y₃). This distance satisfies the usual metric axioms (the triangle inequality requires more work). On a sphere of radius r, the distance scales to r • θ.
open scoped BigOperators RealInnerProductSpace
universe u
abbrev spherePoints (r : ℝ) :=
{p : EuclideanSpace ℝ (Fin 3) // dist p 0 = r}
open scoped BigOperators RealInnerProductSpace
universe u
noncomputable def greatCircleDist
(x y : spherePoints 1) : ℝ :=
Real.arccos (inner (𝕜 := ℝ) (x : EuclideanSpace ℝ (Fin 3)) (y : EuclideanSpace ℝ (Fin 3)))
open scoped BigOperators RealInnerProductSpace
universe u
lemma spherePoints_norm_eq_one (x : spherePoints 1) :
‖(x : EuclideanSpace ℝ (Fin 3))‖ = 1
open scoped BigOperators RealInnerProductSpace
universe u
lemma greatCircleDist_eq_angle (x y : spherePoints 1) :
greatCircleDist x y =
InnerProductGeometry.angle (x : EuclideanSpace ℝ (Fin 3))
(y : EuclideanSpace ℝ (Fin 3))
open scoped BigOperators RealInnerProductSpace
universe u
lemma greatCircleDist_triangle (x y z : spherePoints 1) :
greatCircleDist x z ≤ greatCircleDist x y + greatCircleDist y z
open scoped BigOperators RealInnerProductSpace
universe u
lemma greatCircleDist_metric_axioms :
(∀ x y : spherePoints 1, 0 ≤ greatCircleDist x y) ∧
(∀ x : spherePoints 1, greatCircleDist x x = 0) ∧
(∀ x y : spherePoints 1, greatCircleDist x y = greatCircleDist y x) ∧
(∀ x y z : spherePoints 1, greatCircleDist x z ≤
greatCircleDist x y + greatCircleDist y z)
Scaling the great circle distance to a sphere of radius r by multiplying the angular separation by r.
open scoped BigOperators RealInnerProductSpace
universe u
noncomputable def greatCircleDistOfRadius (r : ℝ)
(x y : spherePoints r) : ℝ :=
r * Real.arccos
(inner (𝕜 := ℝ) (x : EuclideanSpace ℝ (Fin 3)) (y : EuclideanSpace ℝ (Fin 3)) / (r ^ 2))
Proposition 7.1.10: For a metric space (X, d) and subset Y ⊆ X, the restriction of the distance function to Y × Y defines a metric on Y.
open scoped BigOperators RealInnerProductSpace
universe u
def restricted_dist_metric {X : Type u} [MetricSpace X] (Y : Set X) :
MetricSpace {x : X // x ∈ Y}
Definition 7.1.11: For a metric space (X, d) and subset Y ⊆ X, the restriction of d to Y × Y endows Y with the subspace metric.
open scoped BigOperators RealInnerProductSpace
universe u
def subspaceMetric {X : Type u} [MetricSpace X] (Y : Set X) :
MetricSpace {x : X // x ∈ Y} :=
restricted_dist_metric Y
The subspace metric agrees with the standard metric structure that mathlib provides on the subtype Y.
open scoped BigOperators RealInnerProductSpace
universe u
lemma subspaceMetric_eq_subtype {X : Type u} [MetricSpace X] (Y : Set X) :
subspaceMetric (X := X) Y =
(inferInstance : MetricSpace {x : X // x ∈ Y})
Definition 7.1.12: In a metric space (X, d), a subset S ⊆ X is bounded if there exists a point p and real number B with dist p x ≤ B for every x ∈ S. The space itself is bounded when its entire underlying set is bounded.
open scoped BigOperators RealInnerProductSpace
universe u
def boundedSubset {X : Type u} [MetricSpace X] (S : Set X) : Prop :=
∃ p : X, ∃ B : ℝ, ∀ x ∈ S, dist p x ≤ B
open scoped BigOperators RealInnerProductSpace
universe u
def boundedSpace {X : Type u} [MetricSpace X] : Prop :=
boundedSubset (X := X) (S := Set.univ)
The book's boundedness agrees with the standard bornological notion in a metric space.
open scoped BigOperators RealInnerProductSpace
universe u
lemma boundedSubset_iff_isBounded {X : Type u} [MetricSpace X] [Nonempty X] (S : Set X) :
boundedSubset (X := X) S ↔ Bornology.IsBounded S7.2 — Open and Closed Sets
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 7.2.1. In a metric space (X, d), the open ball (ball) of radius δ > 0 around x is B(x, δ) = { y ∈ X | d(x, y) < δ }, and the closed ball is C(x, δ) = { y ∈ X | d(x, y) ≤ δ }.
variable {X : Type*} [PseudoMetricSpace X] (x : X) (δ : ℝ)
def openBall : Set X := {y : X | dist y x < δ}
Closed ball with center x and radius δ.
variable {X : Type*} [PseudoMetricSpace X] (x : X) (δ : ℝ)
def closedBall : Set X := {y : X | dist y x ≤ δ}
The book's open ball agrees with Metric.ball.
variable {X : Type*} [PseudoMetricSpace X] (x : X) (δ : ℝ)
theorem openBall_eq_metric_ball : openBall x δ = Metric.ball x δ
The book's closed ball agrees with Metric.closedBall.
variable {X : Type*} [PseudoMetricSpace X] (x : X) (δ : ℝ)
theorem closedBall_eq_metric_closedBall :
closedBall x δ = Metric.closedBall x δ
Example 7.2.2. In ℝ with its usual metric, the open ball B(x, δ) of radius δ > 0 around x is the open interval (x - δ, x + δ), and the closed ball C(x, δ) is the closed interval [x - δ, x + δ].
variable (x δ : ℝ)
lemma real_openBall_eq_Ioo :
openBall x δ = Set.Ioo (x - δ) (x + δ)
variable (x δ : ℝ)
lemma real_closedBall_eq_Icc :
closedBall x δ = Set.Icc (x - δ) (x + δ)
lemma mem_unitInterval_ball_half_iff
(y : { y : ℝ // y ∈ Set.Icc (0 : ℝ) 1 }) :
y ∈ Metric.ball
(x :=
(⟨0, by
constructor <;> norm_num⟩ :
{ y : ℝ // y ∈ Set.Icc (0 : ℝ) 1 }))
(1 / 2 : ℝ) ↔
(y : ℝ) < (1 / 2 : ℝ)
Example 7.2.3. In the subspace [0, 1] ⊆ ℝ, the open ball of radius 1/2 around 0 consists of those points of [0, 1] whose underlying real coordinate is < 1/2, so it differs from the ambient ball (-1/2, 1/2) ⊆ ℝ.
lemma unitInterval_ball_half :
Metric.ball
(x :=
(⟨0, by
constructor <;> norm_num⟩ :
{ y : ℝ // y ∈ Set.Icc (0 : ℝ) 1 }))
(1 / 2 : ℝ) =
{ y : { y : ℝ // y ∈ Set.Icc (0 : ℝ) 1 } |
(y : ℝ) < (1 / 2 : ℝ) }
Definition 7.2.4. In a metric space (X, d), a subset V ⊆ X is open if for every x ∈ V there exists δ > 0 such that the ball B(x, δ) is contained in V. A subset E ⊆ X is closed if its complement X \ E is open. If x ∈ V and V is open, then V is an open (or simply a) neighborhood of x.
def IsOpenMetric {X : Type*} [PseudoMetricSpace X] (V : Set X) : Prop :=
∀ x ∈ V, ∃ δ > 0, Metric.ball x δ ⊆ V
A set is closed in the metric sense if its complement is open.
def IsClosedMetric {X : Type*} [PseudoMetricSpace X] (E : Set X) : Prop :=
IsOpenMetric (Eᶜ)
The book's notion of an open set agrees with the topological notion coming from the metric space structure.
theorem isOpenMetric_iff_isOpen {X : Type*} [PseudoMetricSpace X] (V : Set X) :
IsOpenMetric V ↔ IsOpen V
The book's notion of a closed set agrees with IsClosed.
theorem isClosedMetric_iff_isClosed {X : Type*} [PseudoMetricSpace X]
(E : Set X) :
IsClosedMetric E ↔ IsClosed E
An open set in the metric sense is a neighborhood of each of its points.
theorem isOpenMetric.mem_nhds {X : Type*} [PseudoMetricSpace X] {V : Set X}
{x : X} (hV : IsOpenMetric V) (hx : x ∈ V) : V ∈ nhds x
Example 7.2.5. Basic examples of open and closed subsets of ℝ and singletons in metric spaces: (0, ∞) is open; [0, ∞) is closed; [0, 1) is neither open nor closed; singletons are closed in any metric space, but need not be open (e.g. {0} ⊂ ℝ), while in a one-point metric space {x} is open.
lemma real_Ioi_zero_isOpen : IsOpen (Set.Ioi (0 : ℝ))
lemma real_Ici_zero_isClosed : IsClosed (Set.Ici (0 : ℝ))
lemma real_Ico_zero_one_not_isOpen : ¬ IsOpen (Set.Ico (0 : ℝ) 1)
lemma real_Ico_zero_one_not_isClosed : ¬ IsClosed (Set.Ico (0 : ℝ) 1)
lemma singleton_isClosed {X : Type*} [PseudoMetricSpace X] [T1Space X] (x : X) :
IsClosed ({x} : Set X)
lemma real_singleton_zero_not_isOpen : ¬ IsOpen ({0} : Set ℝ)
lemma singleton_isOpen_of_subsingleton {X : Type*} [PseudoMetricSpace X]
[Subsingleton X] (x : X) :
IsOpen ({x} : Set X)
Proposition 7.2.6. In a metric space (X, d): (i) ∅ and the whole space X are open; (ii) a finite intersection of open sets is open; (iii) an arbitrary union of open sets is open.
lemma open_sets_basic {X : Type*} [PseudoMetricSpace X] :
(IsOpen (∅ : Set X) ∧ IsOpen (Set.univ : Set X)) ∧
(∀ {ι : Type*} (s : Finset ι) (V : ι → Set X),
(∀ i, IsOpen (V i)) → IsOpen (⋂ i ∈ s, V i)) ∧
(∀ {ι : Sort*} (V : ι → Set X),
(∀ i, IsOpen (V i)) → IsOpen (⋃ i, V i))
Example 7.2.7. An infinite intersection of open sets need not be open: ⋂ₙ (-1/(n+1), 1/(n+1)) = {0}, so unlike finite intersections, arbitrary intersections of opens may fail to be open.
lemma iInter_openIntervals_subset_singleton :
(⋂ n : ℕ, Set.Ioo (-(1 / (n.succ : ℝ))) (1 / (n.succ : ℝ))) ⊆
({0} : Set ℝ)
lemma iInter_openIntervals_eq_singleton :
(⋂ n : ℕ, Set.Ioo (-(1 / (n.succ : ℝ))) (1 / (n.succ : ℝ))) =
({0} : Set ℝ)
lemma not_isOpen_iInter_openIntervals :
¬ IsOpen (⋂ n : ℕ, Set.Ioo (-(1 / (n.succ : ℝ))) (1 / (n.succ : ℝ)))
Proposition 7.2.8. In a metric space (X, d): (i) ∅ and X are closed; an arbitrary intersection of closed sets is closed; a finite union of closed sets is closed.
lemma closed_sets_basic {X : Type*} [PseudoMetricSpace X] :
(IsClosed (∅ : Set X) ∧ IsClosed (Set.univ : Set X)) ∧
(∀ {ι : Sort*} (E : ι → Set X),
(∀ i, IsClosed (E i)) → IsClosed (⋂ i, E i)) ∧
(∀ {ι : Type*} (s : Finset ι) (E : ι → Set X),
(∀ i, IsClosed (E i)) → IsClosed (⋃ i ∈ s, E i))
Proposition 7.2.9. In a metric space (X, d), for any center x and radius δ > 0, the open ball B(x, δ) is open and the closed ball C(x, δ) is closed.
lemma openBall_isOpen_closedBall_isClosed {X : Type*} [PseudoMetricSpace X]
(x : X) {δ : ℝ} (_hδ : 0 < δ) :
IsOpen (openBall x δ) ∧ IsClosed (closedBall x δ)
Proposition 7.2.10. If a < b in ℝ, then the intervals (a, b), (a, ∞) and (-∞, b) are open in ℝ, while [a, b], [a, ∞) and (-∞, b] are closed in ℝ.
lemma real_intervals_open_closed {a b : ℝ} (_h : a < b) :
IsOpen (Set.Ioo a b) ∧ IsOpen (Set.Ioi a) ∧ IsOpen (Set.Iio b) ∧
IsClosed (Set.Icc a b) ∧ IsClosed (Set.Ici a) ∧ IsClosed (Set.Iic b)
lemma preimage_eq_iff_inter_image_subtype {X : Type*} {Y : Set X} (U : Set Y)
(V : Set X) :
Subtype.val ⁻¹' V = U ↔ V ∩ Y = Subtype.val '' U
lemma subspace_open_exists_open_superset {X : Type*} [PseudoMetricSpace X]
{Y : Set X} {U : Set Y} :
IsOpen U → ∃ V : Set X, IsOpen V ∧ V ∩ Y = Subtype.val '' U
lemma exists_open_superset_subspace_open {X : Type*} [PseudoMetricSpace X]
{Y : Set X} {U : Set Y} :
(∃ V : Set X, IsOpen V ∧ V ∩ Y = Subtype.val '' U) → IsOpen U
lemma image_preimage_subtype_eq {X : Type*} {V U : Set X} (hUV : U ⊆ V) :
Subtype.val '' (Subtype.val ⁻¹' U : Set V) = U
Proposition 7.2.11. For a metric space (X, d) and subset Y ⊆ X, a subset U ⊆ Y is open in the subspace topology if and only if there exists an open V ⊆ X with V ∩ Y = U.
lemma subspace_open_iff {X : Type*} [PseudoMetricSpace X] {Y : Set X} (U : Set Y) :
IsOpen U ↔ ∃ V : Set X, IsOpen V ∧ V ∩ Y = Subtype.val '' U
Proposition 7.2.12. In a metric space (X, d), if V ⊆ X is open and E ⊆ X is closed, then: (i) a subset U ⊆ V is open in the subspace topology on V iff U is open in X; (ii) a subset F ⊆ E is closed in the subspace topology on E iff F is closed in X.
lemma open_in_open_subspace_iff {X : Type*} [PseudoMetricSpace X] {V U : Set X}
(hV : IsOpen V) (hUV : U ⊆ V) :
IsOpen (Subtype.val ⁻¹' U : Set V) ↔ IsOpen U
lemma closed_in_closed_subspace_iff {X : Type*} [PseudoMetricSpace X]
{E F : Set X} (hE : IsClosed E) (hFE : F ⊆ E) :
IsClosed (Subtype.val ⁻¹' F : Set E) ↔ IsClosed F
Definition 7.2.13. A nonempty metric space (X, d) is connected if the only clopen subsets are ∅ and the whole space. A nonempty space that is not connected is called disconnected. A nonempty subset A ⊆ X is connected when it is connected with the subspace topology.
def IsConnectedMetricSpace (X : Type*) [PseudoMetricSpace X] : Prop :=
Nonempty X ∧
∀ V : Set X, IsOpen V → IsClosed V → V = (∅ : Set X) ∨ V = Set.univ
The book's notion of a connected metric space agrees with ConnectedSpace.
theorem isConnectedMetricSpace_iff_connectedSpace (X : Type*)
[PseudoMetricSpace X] :
IsConnectedMetricSpace X ↔ ConnectedSpace X
A subset is connected in the book's sense when it is connected with the subspace topology.
def IsConnectedSubset {X : Type*} [PseudoMetricSpace X] (A : Set X) : Prop :=
IsConnected A
Proposition 7.2.14. A nonempty subset S of a metric space is disconnected iff there are open sets U₁ and U₂ in the ambient space such that U₁ ∩ U₂ ∩ S = ∅, both intersections U₁ ∩ S and U₂ ∩ S are nonempty, and S = (U₁ ∩ S) ∪ (U₂ ∩ S).
lemma disconnected_iff_exists_open_separation {X : Type*} [PseudoMetricSpace X]
{S : Set X} (hS : S.Nonempty) :
¬ IsConnectedSubset S ↔
∃ U₁ U₂ : Set X,
IsOpen U₁ ∧ IsOpen U₂ ∧
U₁ ∩ U₂ ∩ S = (∅ : Set X) ∧
(U₁ ∩ S).Nonempty ∧ (U₂ ∩ S).Nonempty ∧
S = (U₁ ∩ S) ∪ (U₂ ∩ S)
A set missing z is contained in the union of (-∞, z) and (z, ∞).
lemma subset_union_Iio_Ioi_of_not_mem {S : Set ℝ} {z : ℝ} (hz : z ∉ S) :
S ⊆ Set.Iio z ∪ Set.Ioi z
Example 7.2.15. If a set S ⊆ ℝ contains points x and y with x < z < y for some z ∉ S, then S is disconnected, for instance by the separation (-∞, z) and (z, ∞).
lemma real_set_disconnected_of_gap {S : Set ℝ} {x y z : ℝ}
(hx : x ∈ S) (hy : y ∈ S) (hxz : x < z) (hzy : z < y) (hz : z ∉ S) :
¬ IsConnectedSubset (S : Set ℝ)
Proposition 7.2.16. A nonempty subset of ℝ is connected if and only if it is an interval or a single point.
lemma real_connected_iff_interval_or_singleton {S : Set ℝ} (hS : S.Nonempty) :
IsConnected S ↔ Set.OrdConnected S ∨ ∃ x : ℝ, S = ({x} : Set ℝ)
noncomputable local instance discretePseudoMetricSpaceBool :
PseudoMetricSpace Bool
noncomputable local instance : UniformSpace Bool
noncomputable local instance : TopologicalSpace Bool
Example 7.2.17. In a two point space with the discrete metric, the ball of radius 2 around one point is the whole space, which splits into two disjoint open singletons and is therefore not connected.
lemma discrete_two_point_ball_not_connected :
Metric.ball (x := true) (2 : ℝ) = (Set.univ : Set Bool) ∧
¬ IsConnected (Set.univ : Set Bool)
Definition 7.2.18. In a metric space (X, d) and for A ⊆ X, the closure Ā is the intersection of all closed sets containing A.
def closureByClosed {X : Type*} [PseudoMetricSpace X] (A : Set X) : Set X :=
⋂₀ {E : Set X | IsClosed E ∧ A ⊆ E}
The closure defined as the intersection of closed supersets agrees with the topological closure.
theorem closureByClosed_eq_closure {X : Type*} [PseudoMetricSpace X]
(A : Set X) : closureByClosed A = closure A
Proposition 7.2.19. For a subset A of a metric space, the closure Ā is closed and contains A, and if A is already closed then Ā = A.
lemma closure_properties {X : Type*} [PseudoMetricSpace X] (A : Set X) :
IsClosed (closure A) ∧ A ⊆ closure A ∧ (IsClosed A → closure A = A)
Example 7.2.20. The closure of (0, 1) in ℝ is [0, 1].
lemma closure_openInterval_zero_one :
closure (Set.Ioo (0 : ℝ) 1) = Set.Icc (0 : ℝ) 1
lemma image_subtype_lt_one_eq_Ioo :
Subtype.val '' {x : Set.Ioi (0 : ℝ) | (x : ℝ) < 1} = Set.Ioo (0 : ℝ) 1
lemma closure_subtype_rewrite (x : Set.Ioi (0 : ℝ)) :
x ∈ closure ({x : Set.Ioi (0 : ℝ) | (x : ℝ) < 1}) ↔
(x : ℝ) ∈ closure (Set.Ioo (0 : ℝ) 1)
lemma mem_target_set_iff_le_one (x : Set.Ioi (0 : ℝ)) :
(x : ℝ) ∈ Set.Icc (0 : ℝ) 1 ↔ (x : ℝ) ≤ 1
Example 7.2.21. In the ambient metric space (0, ∞), the closure of (0, 1) is (0, 1], since 0 is not available as a limit point but 1 remains a boundary point.
lemma closure_Ioo_in_Ioi_eq_Ioc :
closure ({x : Set.Ioi (0 : ℝ) | (x : ℝ) < 1}) =
{x : Set.Ioi (0 : ℝ) | (x : ℝ) ≤ 1}
Proposition 7.2.22. In a metric space (X, d) and subset A ⊆ X, a point x lies in the closure Ā if and only if every open ball around x meets A, that is, B(x, δ) ∩ A ≠ ∅ for all δ > 0.
lemma mem_closure_iff_ball_intersects {X : Type*} [PseudoMetricSpace X]
{A : Set X} {x : X} :
x ∈ closure A ↔
∀ δ > 0, (Metric.ball x δ ∩ A).Nonempty
Definition 7.2.23. In a metric space (X, d) and a subset A ⊆ X, the interior of A is the set of points x ∈ A for which there exists δ > 0 with B(x, δ) ⊆ A. The boundary of A is ∂A = \overline{A} \setminus Aᵒ.
def metricInterior {X : Type*} [PseudoMetricSpace X] (A : Set X) : Set X :=
{x | x ∈ A ∧ ∃ δ > 0, Metric.ball x δ ⊆ A}
The metric description of the interior agrees with the topological interior coming from the metric space structure.
theorem metricInterior_eq_interior {X : Type*} [PseudoMetricSpace X]
(A : Set X) : metricInterior A = interior A
The boundary of a subset is its closure minus its interior.
def metricBoundary {X : Type*} [PseudoMetricSpace X] (A : Set X) : Set X :=
closure A \ metricInterior A
The boundary defined via closure and interior agrees with the topological frontier.
theorem metricBoundary_eq_frontier {X : Type*} [PseudoMetricSpace X]
(A : Set X) : metricBoundary A = frontier A
Example 7.2.24. For A = (0, 1] ⊆ ℝ, the closure is [0, 1], the interior is (0, 1), and the boundary is {0, 1}.
lemma closure_interior_boundary_Ioc_zero_one :
closure (Set.Ioc (0 : ℝ) 1) = Set.Icc (0 : ℝ) 1 ∧
interior (Set.Ioc (0 : ℝ) 1) = Set.Ioo (0 : ℝ) 1 ∧
frontier (Set.Ioc (0 : ℝ) 1) = ({0, 1} : Set ℝ)
Example 7.2.25. For the discrete metric on the two-point set X = {a, b} and A = {a}, we have Ā = Aᵒ = A and ∂A = ∅.
lemma closure_interior_boundary_discrete_pair :
closure ({true} : Set Bool) = ({true} : Set Bool) ∧
interior ({true} : Set Bool) = ({true} : Set Bool) ∧
frontier ({true} : Set Bool) = (∅ : Set Bool)
Proposition 7.2.26. In a metric space, the interior of any subset is open and the boundary is closed.
lemma interior_open_boundary_closed {X : Type*} [PseudoMetricSpace X]
(A : Set X) : IsOpen (interior A) ∧ IsClosed (frontier A)
lemma not_mem_interior_iff_ball_meets_compl {X : Type*} [PseudoMetricSpace X]
{A : Set X} {x : X} :
x ∉ interior A ↔ ∀ δ > 0, (Metric.ball x δ ∩ Aᶜ).Nonempty
Proposition 7.2.26. For a subset A of a metric space, the interior Aᵒ is open and the boundary ∂A is closed.
lemma metricInterior_open_metricBoundary_closed {X : Type*}
[PseudoMetricSpace X] (A : Set X) :
IsOpen (metricInterior A) ∧ IsClosed (metricBoundary A)
Proposition 7.2.27. A point x lies in the boundary ∂A of a subset A of a metric space if and only if every open ball around x meets both A and its complement.
lemma mem_frontier_iff_ball_intersects {X : Type*} [PseudoMetricSpace X]
{A : Set X} {x : X} :
x ∈ frontier A ↔
∀ δ > 0,
(Metric.ball x δ ∩ A).Nonempty ∧ (Metric.ball x δ ∩ Aᶜ).Nonempty
Corollary 7.2.28. For a subset A of a metric space, the boundary is the intersection of the closures of A and its complement: ∂A = Ā ∩ \overline{Aᶜ}.
lemma frontier_eq_closure_inter_closure_compl {X : Type*} [PseudoMetricSpace X]
(A : Set X) : frontier A = closure A ∩ closure (Aᶜ)7.3 — Sequences and Convergence
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 7.3.1. A sequence in a metric space (X, d) is a function x : ℕ → X, written xₙ for its terms and {xₙ} for the whole sequence. It is bounded if there exists p ∈ X and B ∈ ℝ such that dist p (xₙ) ≤ B for all n. Equivalently, the image set {xₙ : n ∈ ℕ} is bounded. A subsequence of {xₙ} is any sequence of the form {x_{n_k}} where n_{k+1} > n_k for all k.
universe u
variable (X : Type u) [PseudoMetricSpace X]
def MetricSequence (X : Type u) : Type u :=
ℕ → X
A sequence is bounded when all of its terms lie in a ball of finite radius around some point of the space.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
def MetricBoundedSequence (x : MetricSequence X) : Prop :=
∃ p : X, ∃ B : ℝ, ∀ n, dist p (x n) ≤ B
A bounded sequence's range lies in a closed ball.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma range_subset_closedBall_of_boundedSequence (x : MetricSequence X) :
MetricBoundedSequence (X := X) x →
∃ p B, Set.range x ⊆ Metric.closedBall p B
A bounded range yields a pointwise distance bound for the sequence.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma metricBoundedSequence_of_isBounded_range (x : MetricSequence X) :
Bornology.IsBounded (Set.range x) → MetricBoundedSequence (X := X) x
The book's notion of a bounded sequence agrees with boundedness of its range in the bornology of the metric space.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricBoundedSequence_iff_isBounded_range (x : MetricSequence X) :
MetricBoundedSequence (X := X) x ↔ Bornology.IsBounded (Set.range x)
A subsequence of x is obtained by precomposing with a strictly increasing map of indices.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
def IsMetricSubsequence (y x : MetricSequence X) : Prop :=
∃ n : ℕ → ℕ, StrictMono n ∧ ∀ k, y k = x (n k)
Definition 7.3.2. A sequence {xₙ} in a metric space converges to a point p if for every ε > 0 there exists M ∈ ℕ such that dist (xₙ) p < ε for all n ≥ M. In this case p is a limit of the sequence.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
def MetricConvergesTo (x : MetricSequence X) (p : X) : Prop :=
∀ ε > 0, ∃ M : ℕ, ∀ ⦃n⦄, M ≤ n → dist (x n) p < ε
A sequence is convergent when it has a (not necessarily unique) limit.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
def MetricConvergentSequence (x : MetricSequence X) : Prop :=
∃ p : X, MetricConvergesTo (X := X) x p
The book's notion of convergence agrees with the usual filter convergence of sequences.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricConvergesTo_iff_tendsto (x : MetricSequence X) (p : X) :
MetricConvergesTo (X := X) x p ↔ Filter.Tendsto x Filter.atTop (nhds p)
A sequence is divergent when it does not converge.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
def MetricDivergentSequence (x : MetricSequence X) : Prop :=
¬ MetricConvergentSequence (X := X) x
Proposition 7.3.3. A convergent sequence in a metric space has a unique limit.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricConvergentSequence_limit_unique {X : Type u} [MetricSpace X]
{x : MetricSequence X} {p q : X} (hp : MetricConvergesTo (X := X) x p)
(hq : MetricConvergesTo (X := X) x q) : p = q
Proposition 7.3.4. A convergent sequence in a metric space is bounded.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricConvergentSequence_bounded {X : Type u} [PseudoMetricSpace X]
{x : MetricSequence X} (hx : MetricConvergentSequence (X := X) x) :
MetricBoundedSequence (X := X) x
Nonnegative reals have distance to zero equal to themselves.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma real_dist_eq_self_of_nonneg {r : ℝ} (hr : 0 ≤ r) : dist r 0 = r
Distances to a limit point converge to zero.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma metricConvergesTo_dist_to_zero {X : Type u} [PseudoMetricSpace X]
{x : MetricSequence X} {p : X} (hx : MetricConvergesTo (X := X) x p) :
MetricConvergesTo (X := ℝ) (fun n => dist (x n) p) 0
A distance bound by a sequence tending to zero forces convergence.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma metricConvergesTo_of_dist_le_of_tendsto {X : Type u} [PseudoMetricSpace X]
{x : MetricSequence X} {p : X} {a : ℕ → ℝ} (ha : ∀ n, dist (x n) p ≤ a n)
(hat : Filter.Tendsto a Filter.atTop (nhds (0 : ℝ))) :
MetricConvergesTo (X := X) x p
Proposition 7.3.5. A sequence in a metric space converges to p if and only if there is a real sequence controlling the distances to p that itself tends to zero.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricConvergesTo_iff_exists_distance_bound {X : Type u} [PseudoMetricSpace X]
{x : MetricSequence X} {p : X} :
MetricConvergesTo (X := X) x p ↔
∃ a : ℕ → ℝ, (∀ n, dist (x n) p ≤ a n) ∧
Filter.Tendsto a Filter.atTop (nhds (0 : ℝ))
Proposition 7.3.6. (i) A subsequence of a sequence converging to p also converges to p. (ii) If some tail of a sequence converges to p, then the original sequence converges to p.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricConvergesTo_subsequence {X : Type u} [PseudoMetricSpace X]
{x y : MetricSequence X} {p : X} (hx : MetricConvergesTo (X := X) x p)
(hy : IsMetricSubsequence (X := X) y x) :
MetricConvergesTo (X := X) y p
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricConvergesTo_of_tail {X : Type u} [PseudoMetricSpace X]
{x : MetricSequence X} {p : X} {K : ℕ}
(hx : MetricConvergesTo (X := X) (fun n => x (n + K.succ)) p) :
MetricConvergesTo (X := X) x p
The distance between evaluations of two continuous functions is controlled by their supremum distance.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma dist_eval_le_sup {a b : ℝ} (h k : C(Set.Icc a b, ℝ)) (x : Set.Icc a b) :
dist (h x) (k x) ≤ dist h k
A uniform pointwise bound on two continuous functions gives a bound on their supremum distance.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma sup_norm_le_of_pointwise {a b : ℝ} (h k : C(Set.Icc a b, ℝ)) {ε : ℝ}
(hε : 0 ≤ ε) (hpoint : ∀ x : Set.Icc a b, dist (h x) (k x) ≤ ε) :
dist h k ≤ ε
Example 7.3.7. For continuous real-valued functions on a closed interval [a, b] endowed with the uniform (supremum) norm, convergence of a sequence in the metric space sense is the same as uniform convergence.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem uniformConvergence_iff_convergesInSupMetric {a b : ℝ}
(f : MetricSequence C(Set.Icc a b, ℝ)) (g : C(Set.Icc a b, ℝ)) :
(∀ ε > 0, ∃ M : ℕ, ∀ ⦃n⦄, M ≤ n → ∀ x : Set.Icc a b,
dist (f n x) (g x) < ε) ↔
MetricConvergesTo (X := C(Set.Icc a b, ℝ)) f g
Proposition 7.3.9. A sequence in Euclidean space ℝⁿ converges if and only if each coordinate sequence converges, and the limit vector has the coordinatewise limits.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricConvergesTo_euclidean_iff_coordinates {n : ℕ}
(x : MetricSequence (EuclideanSpace ℝ (Fin n)))
(l : EuclideanSpace ℝ (Fin n)) :
MetricConvergesTo (X := EuclideanSpace ℝ (Fin n)) x l ↔
∀ k : Fin n, MetricConvergesTo (X := ℝ) (fun m => x m k) (l k)
A sequence in ℝⁿ converges exactly when every coordinate sequence converges. In this case the limit is the vector of the coordinate limits.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem convergent_euclidean_iff_coordinates {n : ℕ}
(x : MetricSequence (EuclideanSpace ℝ (Fin n))) :
MetricConvergentSequence (X := EuclideanSpace ℝ (Fin n)) x ↔
∀ k : Fin n, MetricConvergentSequence (X := ℝ) (fun m => x m k)
Convergence of complex numbers is equivalent to convergence of the real and imaginary parts.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma tendsto_complex_iff_real_im (z : MetricSequence ℂ) (x y : ℝ) :
Filter.Tendsto z Filter.atTop (nhds (x + y * Complex.I)) ↔
Filter.Tendsto (fun n => (z n).re) Filter.atTop (nhds x) ∧
Filter.Tendsto (fun n => (z n).im) Filter.atTop (nhds y)
Example 7.3.10. In the complex plane viewed as ℝ², a sequence zₙ = xₙ + i yₙ converges to x + i y if and only if the real parts converge to x and the imaginary parts converge to y.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricConvergesTo_complex_iff_re_im (z : MetricSequence ℂ) (x y : ℝ) :
MetricConvergesTo (X := ℂ) z (x + y * Complex.I) ↔
MetricConvergesTo (X := ℝ) (fun n => (z n).re) x ∧
MetricConvergesTo (X := ℝ) (fun n => (z n).im) y
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma metricConvergesTo_eventually_mem_open {x : MetricSequence X} {p : X} {U : Set X}
(hx : MetricConvergesTo (X := X) x p) (hUopen : IsOpen U) (hpU : p ∈ U) :
∃ M : ℕ, ∀ ⦃n⦄, M ≤ n → x n ∈ U
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma tendsto_of_eventually_mem_open {x : MetricSequence X} {p : X}
(hx : ∀ {U : Set X}, IsOpen U → p ∈ U →
∃ M : ℕ, ∀ ⦃n⦄, M ≤ n → x n ∈ U) :
Filter.Tendsto x Filter.atTop (nhds p)
Proposition 7.3.11. A sequence in a metric space converges to p exactly when eventually all of its terms lie in every open neighborhood of p.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricConvergesTo_iff_eventually_mem_nhds {x : MetricSequence X} {p : X} :
MetricConvergesTo (X := X) x p ↔
∀ {U : Set X}, IsOpen U → p ∈ U →
∃ M : ℕ, ∀ ⦃n⦄, M ≤ n → x n ∈ U
Proposition 7.3.12. In a metric space, a closed set contains the limit of a convergent sequence of its points.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem mem_closed_of_converges {X : Type u} [PseudoMetricSpace X] {E : Set X}
(hE : IsClosed E) {x : MetricSequence X} (hx : ∀ n, x n ∈ E) {p : X}
(hxlim : MetricConvergesTo (X := X) x p) : p ∈ E
Proposition 7.3.13. A point lies in the closure of a set in a metric space exactly when it is the limit of a sequence of points from that set.
universe u
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem mem_closure_iff_metricConvergesTo_seq {X : Type u} [PseudoMetricSpace X]
{A : Set X} {p : X} :
p ∈ closure A ↔ ∃ x : MetricSequence X,
(∀ n, x n ∈ A) ∧ MetricConvergesTo (X := X) x p7.4 — Completeness and Compactness
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 7.4.1. A sequence {xₙ} in a metric space is Cauchy when for every ε > 0 there exists M ∈ ℕ such that dist (xₙ) (xₖ) < ε for all n, k ≥ M.
universe u v
open Filter
variable (X : Type u) [PseudoMetricSpace X]
def MetricCauchySequence (x : ℕ → X) : Prop :=
∀ ε > 0, ∃ M : ℕ, ∀ ⦃n k : ℕ⦄, M ≤ n → M ≤ k → dist (x n) (x k) < ε
The book's notion of a Cauchy sequence agrees with the standard filter based definition in mathlib.
universe u v
open Filter
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem metricCauchySequence_iff_cauchySeq (x : ℕ → X) :
MetricCauchySequence (X := X) x ↔ CauchySeq x
Proposition 7.4.2. A sequence in a metric space that converges to a point is Cauchy.
universe u v
open Filter
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
lemma metricCauchySequence_of_tendsto {x : ℕ → X} {l : X}
(hx : Tendsto x atTop (nhds l)) : MetricCauchySequence (X := X) x
Definition 7.4.3. A metric space is complete (Cauchy-complete) when every Cauchy sequence converges to a point of the space.
universe u v
open Filter
variable (X : Type u) [PseudoMetricSpace X]
def metricCauchyCompleteSpace : Prop :=
∀ x : ℕ → X, MetricCauchySequence (X := X) x → ∃ l : X, Tendsto x atTop (nhds l)
The book's sequential notion of completeness is equivalent to the standard CompleteSpace typeclass in mathlib.
universe u v
open Filter
variable (X : Type u) [PseudoMetricSpace X]
theorem metricCauchyCompleteSpace_iff_completeSpace :
metricCauchyCompleteSpace (X := X) ↔ CompleteSpace X
Proposition 7.4.4 (sequential version). Every Cauchy sequence in ℝ^n converges.
universe u v
lemma metricCauchyCompleteSpace_euclideanSpace (n : ℕ) :
metricCauchyCompleteSpace (X := EuclideanSpace ℝ (Fin n))
Proposition 7.4.4. The Euclidean space ℝ^n with its standard metric is complete.
universe u v
instance instCompleteSpace_realEuclideanSpace (n : ℕ) :
CompleteSpace (EuclideanSpace ℝ (Fin n))
Proposition 7.4.5. The metric space of continuous real-valued functions on the closed interval [a,b], equipped with the uniform norm metric, is complete.
universe u v
instance instCompleteSpace_continuousMap_interval (a b : ℝ) :
CompleteSpace (ContinuousMap (Set.Icc a b) ℝ)
Proposition 7.4.6. If (X,d) is a complete metric space and E ⊆ X is closed, then E is complete with the subspace metric.
universe u v
instance instCompleteSpace_closed_subset {X : Type u} [PseudoMetricSpace X]
[CompleteSpace X] {E : Set X} (hE : IsClosed E) : CompleteSpace E
Definition 7.4.7. A subset K of a metric space is compact when every open cover of K admits a finite subcover.
universe u v
variable (X : Type u) [PseudoMetricSpace X]
def compactCoverProperty (K : Set X) : Prop :=
∀ (ι : Type u) (U : ι → Set X), (∀ i, IsOpen (U i)) →
K ⊆ ⋃ i, U i → ∃ t : Finset ι, K ⊆ ⋃ i ∈ t, U i
The book's finite-subcover compactness property agrees with IsCompact.
universe u v
variable (X : Type u) [PseudoMetricSpace X]
variable {X}
theorem compactCoverProperty_iff_isCompact {K : Set X} :
compactCoverProperty (X := X) K ↔ IsCompact K
Example 7.4.8. In ℝ with the standard metric: (i) the whole space ℝ is not compact; (ii) the open interval (0,1) is not compact; (iii) the singleton {0} is compact.
universe u v
theorem real_univ_not_compact : ¬ IsCompact (Set.univ : Set ℝ)
See also: Example 7.4.8 (ii).
universe u v
theorem real_Ioo_zero_one_not_compact : ¬ IsCompact (Set.Ioo (0 : ℝ) 1)
See also: Example 7.4.8 (iii).
universe u v
theorem real_singleton_zero_compact : IsCompact ({0} : Set ℝ)
universe u v
open Filter
open scoped Topology
lemma compact_isClosed {X : Type u} [PseudoMetricSpace X] [T2Space X]
{K : Set X} (hK : IsCompact K) : IsClosed K
universe u v
open Filter
open scoped Topology
lemma compact_isBounded {X : Type u} [PseudoMetricSpace X]
{K : Set X} (hK : IsCompact K) : Bornology.IsBounded K
Proposition 7.4.9. In a metric space, a compact subset is closed and bounded.
universe u v
open Filter
open scoped Topology
theorem compact_isClosed_and_bounded {X : Type u} [PseudoMetricSpace X]
[T2Space X]
{K : Set X} (hK : IsCompact K) : IsClosed K ∧ Bornology.IsBounded K
Lemma 7.4.10 (Lebesgue covering lemma). If every sequence in a subset K of a metric space has a subsequence converging to a point of K, then for every open cover of K there exists δ > 0 such that every x ∈ K has some open set in the cover containing the ball B(x, δ).
universe u v
open Filter
open scoped Topology
lemma lebesgue_covering_lemma {X : Type u} [PseudoMetricSpace X] {K : Set X}
(hseq : ∀ u : ℕ → X, (∀ n, u n ∈ K) →
∃ l ∈ K, ∃ φ : ℕ → ℕ, StrictMono φ ∧ Tendsto (u ∘ φ) atTop (𝓝 l))
{I : Type v} (U : I → Set X) (hUopen : ∀ i, IsOpen (U i))
(hcover : K ⊆ ⋃ i, U i) :
∃ δ > 0, ∀ x ∈ K, ∃ i : I, Metric.ball x δ ⊆ U i
Theorem 7.4.11. In a metric space, a subset is compact if and only if every sequence in the subset has a subsequence converging to a point of the subset.
universe u v
open Filter
open scoped Topology
theorem compact_iff_isSeqCompact {X : Type u} [PseudoMetricSpace X]
{K : Set X} : IsCompact K ↔ IsSeqCompact K
Example 7.4.12. A closed bounded interval [a,b] ⊆ ℝ is sequentially compact: every sequence in Set.Icc a b admits a convergent subsequence with limit still in the interval.
universe u v
open Filter
open scoped Topology
theorem real_interval_isSeqCompact (a b : ℝ) :
IsSeqCompact (Set.Icc a b)
Proposition 7.4.13. In a metric space, a closed subset of a compact set is compact.
universe u v
open Filter
open scoped Topology
theorem compact_of_closed_subset {X : Type u} [PseudoMetricSpace X]
{K E : Set X} (hK : IsCompact K) (hE : IsClosed E) (hEK : E ⊆ K) :
IsCompact E
Theorem 7.4.14 (Heine--Borel). A closed bounded subset K ⊆ ℝ^n is compact.
universe u v
open Filter
open scoped Topology
theorem heineBorel_closed_bounded {n : ℕ}
{K : Set (EuclideanSpace ℝ (Fin n))}
(hclosed : IsClosed K) (hbounded : Bornology.IsBounded K) :
IsCompact K
universe u v
open Filter
open scoped Topology
variable {X : Type u} [PseudoMetricSpace X] [DecidableEq X]
variable (hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
variable (hXinf : Infinite X)
lemma discreteMetric_dist_lt_one_iff_eq
(hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
{x y : X} :
dist x y < 1 ↔ x = y
universe u v
open Filter
open scoped Topology
variable {X : Type u} [PseudoMetricSpace X] [DecidableEq X]
variable (hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
variable (hXinf : Infinite X)
lemma discreteMetric_ball_eq_singleton
(hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
(x : X) {r : ℝ}
(hrpos : 0 < r) (hrle : r ≤ 1) :
Metric.ball x r = ({x} : Set X)
universe u v
open Filter
open scoped Topology
variable {X : Type u} [PseudoMetricSpace X] [DecidableEq X]
variable (hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
variable (hXinf : Infinite X)
lemma discreteMetric_cauchySeq_eventually_const
(hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
(u : ℕ → X)
(hu : CauchySeq u) :
∃ x0, u =ᶠ[atTop] fun _ => x0
universe u v
open Filter
open scoped Topology
variable {X : Type u} [PseudoMetricSpace X] [DecidableEq X]
variable (hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
variable (hXinf : Infinite X)
theorem discreteMetric_complete
(hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1)) :
CompleteSpace X
universe u v
open Filter
open scoped Topology
variable {X : Type u} [PseudoMetricSpace X] [DecidableEq X]
variable (hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
variable (hXinf : Infinite X)
theorem discreteMetric_closed_and_bounded
(hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
(hXinf : Infinite X) (K : Set X) :
IsClosed K ∧ Bornology.IsBounded K
universe u v
open Filter
open scoped Topology
variable {X : Type u} [PseudoMetricSpace X] [DecidableEq X]
variable (hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
variable (hXinf : Infinite X)
theorem discreteMetric_compact_iff_finite
(hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
(K : Set X) :
IsCompact K ↔ Set.Finite K
universe u v
open Filter
open scoped Topology
variable {X : Type u} [PseudoMetricSpace X] [DecidableEq X]
variable (hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
variable (hXinf : Infinite X)
theorem discreteMetric_lebesgue_covering
(hdiscrete : ∀ x y : X, dist x y = (if x = y then 0 else 1))
(K : Set X)
{I : Type v} (U : I → Set X) (hUopen : ∀ i, IsOpen (U i))
(hcover : K ⊆ ⋃ i, U i) :
∀ x ∈ K, ∃ i : I, Metric.ball x (1 / 2 : ℝ) ⊆ U i7.5 — Continuous Functions
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 7.5.1. A function f : X → Y between metric spaces is continuous at c if for every ε > 0 there is δ > 0 such that dist x c < δ implies dist (f x) (f c) < ε. When this holds for every c, the function is continuous.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
def metricContinuousAt (f : X → Y) (c : X) : Prop :=
∀ ε > 0, ∃ δ > 0, ∀ ⦃x : X⦄, dist x c < δ → dist (f x) (f c) < ε
The book's ε-δ continuity at a point agrees with mathlib's ContinuousAt.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem metricContinuousAt_iff_continuousAt (f : X → Y) (c : X) :
metricContinuousAt (X := X) (Y := Y) f c ↔ ContinuousAt f c
Proposition 7.5.2. A map between metric spaces is continuous at c if and only if every sequence converging to c has image sequence converging to f c.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem continuousAt_iff_tendsto_seq {f : X → Y} {c : X} :
ContinuousAt f c ↔
∀ x : ℕ → X, Tendsto x atTop (𝓝 c) →
Tendsto (fun n => f (x n)) atTop (𝓝 (f c))
A function is (globally) continuous when it is continuous at every point.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
def metricContinuous (f : X → Y) : Prop :=
∀ c : X, metricContinuousAt (X := X) (Y := Y) f c
The book's notion of a continuous function coincides with Continuous.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem metricContinuous_iff_continuous (f : X → Y) :
metricContinuous (X := X) (Y := Y) f ↔ Continuous f
Example 7.5.3. A polynomial on ℝ × ℝ (and more generally on finitely many variables) defines a continuous function.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem polynomial_two_vars_continuous (p : MvPolynomial (Fin 2) ℝ) :
Continuous (fun x : Fin 2 → ℝ => MvPolynomial.eval x p)
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem polynomial_finite_vars_continuous {n : ℕ} (p : MvPolynomial (Fin n) ℝ) :
Continuous (fun x : Fin n → ℝ => MvPolynomial.eval x p)
Example 7.5.4. A complex-valued function on a metric space is continuous at c exactly when its real and imaginary parts are continuous at c.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem continuousAt_complex_iff_real_im {X : Type u} [PseudoMetricSpace X]
{f : X → ℂ} {c : X} :
ContinuousAt f c ↔
ContinuousAt (fun x => Complex.re (f x)) c ∧
ContinuousAt (fun x => Complex.im (f x)) c
Lemma 7.5.5. A continuous function maps compact sets to compact sets.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
lemma compact_image_of_continuous {X : Type u} [PseudoMetricSpace X]
{Y : Type v} [PseudoMetricSpace Y] {f : X → Y} (hf : Continuous f)
{K : Set X} (hK : IsCompact K) : IsCompact (f '' K)
Theorem 7.5.6. A continuous real-valued function on a nonempty compact metric space is bounded and attains both its absolute minimum and maximum.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem continuous_on_compact_real_extrema {X : Type u} [PseudoMetricSpace X]
[CompactSpace X] [Nonempty X] {f : X → ℝ} (hf : Continuous f) :
∃ x_min x_max : X, ∀ x : X, f x_min ≤ f x ∧ f x ≤ f x_max
Lemma 7.5.7. A function between metric spaces is continuous at a point exactly when every open neighborhood of its value has a preimage that is an open neighborhood of the point.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
lemma continuousAt_iff_preimage_open_nhds {f : X → Y} {c : X} :
ContinuousAt f c ↔
∀ ⦃U : Set Y⦄, IsOpen U → f c ∈ U →
∃ V : Set X, IsOpen V ∧ c ∈ V ∧ V ⊆ f ⁻¹' U
Theorem 7.5.8. A function between metric spaces is continuous if and only if for every open set in the codomain, its preimage is open in the domain.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem continuous_iff_preimage_open {f : X → Y} :
Continuous f ↔ ∀ U : Set Y, IsOpen U → IsOpen (f ⁻¹' U)
Example 7.5.9. For a continuous function, closed sets pull back to closed sets. In particular, if f : X → ℝ is continuous, then its zero set and its nonnegative set are closed, while the positive set is open.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem preimage_closed_of_continuous {f : X → Y} (hf : Continuous f)
{E : Set Y} (hE : IsClosed E) : IsClosed (f ⁻¹' E)
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem zero_set_closed_of_continuous {f : X → ℝ} (hf : Continuous f) :
IsClosed {x : X | f x = 0}
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem nonneg_preimage_closed_of_continuous {f : X → ℝ} (hf : Continuous f) :
IsClosed {x : X | 0 ≤ f x}
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem pos_preimage_open_of_continuous {f : X → ℝ} (hf : Continuous f) :
IsOpen {x : X | 0 < f x}
Definition 7.5.10. A function between metric spaces is uniformly continuous if for every ε > 0 there exists δ > 0 such that dist p q < δ implies dist (f p) (f q) < ε.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
def metricUniformContinuous (f : X → Y) : Prop :=
∀ ε > 0, ∃ δ > 0, ∀ ⦃p q : X⦄, dist p q < δ → dist (f p) (f q) < ε
The book's notion of uniform continuity agrees with mathlib's UniformContinuous.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem metricUniformContinuous_iff_uniformContinuous (f : X → Y) :
metricUniformContinuous (X := X) (Y := Y) f ↔ UniformContinuous f
Theorem 7.5.11. A continuous function from a compact metric space to another metric space is uniformly continuous.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem continuous_uniformContinuous_of_compact [CompactSpace X] {f : X → Y}
(hf : Continuous f) : UniformContinuous f
Proposition 7.5.12. If f : [a,b] × [c,d] → ℝ is continuous, then g : [c,d] → ℝ defined by g y = ∫ x in a..b, f (x,y) is continuous.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem intervalIntegral_continuous_on_rectangle {a b c d : ℝ}
(f : ℝ → ℝ → ℝ)
(hf : Continuous fun p : ℝ × ℝ => f p.1 p.2) :
Continuous (fun y : Set.Icc c d => ∫ x in a..b, f x y)
Example 7.5.13. A K-Lipschitz map between metric spaces is uniformly continuous. Conversely, the square root on [0,1] is uniformly continuous but fails to be Lipschitz.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem lipschitz_uniformContinuous {K : NNReal} {f : X → Y}
(hf : LipschitzWith K f) : UniformContinuous f
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem sqrt_uniformContinuous_on_Icc :
UniformContinuous (fun x : Set.Icc (0 : ℝ) 1 => Real.sqrt x)
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem sqrt_not_Lipschitz_on_Icc :
¬ ∃ K : NNReal, LipschitzWith K (fun x : Set.Icc (0 : ℝ) 1 => Real.sqrt x)
Definition 7.5.14. In a metric space (X, d) and subset S, a point p is a cluster point of S if every open ball around p meets S at some point other than p.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
def metricClusterPoint (p : X) (S : Set X) : Prop :=
∀ ε > 0, (Metric.ball p ε ∩ (S \ {p})).Nonempty
The book's notion of cluster point agrees with the topological description as belonging to the closure of S \ {p}.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem metricClusterPoint_iff_mem_closure_diff (p : X) (S : Set X) :
metricClusterPoint (X := X) p S ↔ p ∈ closure (S \ {p})
Definition 7.5.15. For metric spaces (X, d_X), (Y, d_Y), subset S, and cluster point p of S, a function f : X → Y has limit L at p along S when every punctured neighborhood of p in S is sent within any ε-ball around L. If the limit is unique we write lim_{x → p} f x = L.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
def metricLimitWithin (f : X → Y) (S : Set X) (p : X) (L : Y) : Prop :=
∀ ε > 0, ∃ δ > 0, ∀ ⦃x : X⦄, x ∈ S → x ≠ p → dist x p < δ → dist (f x) L < ε
The ε-δ limit within a set agrees with mathlib's Tendsto along the punctured neighborhood filter.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem metricLimitWithin_iff_tendsto (f : X → Y) (S : Set X) (p : X) (L : Y) :
metricLimitWithin (X := X) (Y := Y) f S p L ↔
Tendsto f (𝓝[S \ {p}] p) (𝓝 L)
Proposition 7.5.16. If p is a cluster point of S and a function has a limit along S at p, that limit is unique.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
theorem metricLimitWithin_unique {S : Set X} {p : X} {f : X → Y} {L₁ L₂ : Y}
[T2Space Y]
(hp : metricClusterPoint (X := X) p S)
(h₁ : metricLimitWithin (X := X) (Y := Y) f S p L₁)
(h₂ : metricLimitWithin (X := X) (Y := Y) f S p L₂) :
L₁ = L₂
Lemma 7.5.17. A function on a subset of a metric space has limit L at a cluster point p of the subset exactly when every sequence in the subset avoiding p and converging to p has image sequence converging to L.
open Filter Topology
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
lemma metricLimitWithin_iff_tendsto_seq {S : Set X} {p : X} {f : X → Y} {L : Y}
(hp : metricClusterPoint (X := X) p S) :
metricLimitWithin (X := X) (Y := Y) f S p L ↔
∀ x : ℕ → X, (∀ n, x n ∈ S \ {p}) →
Tendsto x atTop (𝓝 p) →
Tendsto (fun n => f (x n)) atTop (𝓝 L)7.6 — Fixed Point Theorem and Picard's Theorem Again
Lean authors: Zichen Wang, Zaiwen Wen.
Definition 7.6.1. A map φ : X → Y between metric spaces is a contraction if it is k-Lipschitz for some k < 1, i.e., there exists k < 1 such that dist (φ p) (φ q) ≤ k * dist p q for all p, q. For a self-map φ : X → X, a point x is a fixed point when φ x = x.
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
def contraction (φ : X → Y) : Prop :=
∃ k : NNReal, (k : ℝ) < 1 ∧ LipschitzWith k φ
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
def fixedPoint (φ : X → X) (x : X) : Prop :=
φ x = x
The book's fixed point notion coincides with Function.IsFixedPt.
universe u v
variable {X : Type u} [PseudoMetricSpace X]
variable {Y : Type v} [PseudoMetricSpace Y]
omit [PseudoMetricSpace X]
theorem fixedPoint_iff_isFixedPt (φ : X → X) (x : X) :
fixedPoint (X := X) φ x ↔ Function.IsFixedPt φ x
Theorem 7.6.2 (contraction mapping principle or Banach fixed point theorem). If (X, d) is a nonempty complete metric space and φ : X → X is a contraction, then φ has a unique fixed point.
universe u v
theorem contraction_unique_fixedPoint
(X : Type u) [MetricSpace X] [CompleteSpace X] [Nonempty X]
(φ : X → X) (hφ : contraction (X := X) (Y := X) φ) :
∃! x : X, fixedPoint (X := X) φ x
Theorem 7.6.3 (Picard's theorem on existence and uniqueness). Let I = [a, b] and J = [c, d] be closed bounded intervals in ℝ with x₀ ∈ (a, b) and y₀ ∈ (c, d). Suppose F : ℝ → ℝ → ℝ is continuous on I × J and Lipschitz in the second variable with Lipschitz constant L, meaning |F x y - F x z| ≤ L * |y - z| for all x ∈ I and y, z ∈ J. Then there exists h > 0 with [x₀ - h, x₀ + h] ⊆ I and a unique differentiable function f : ℝ → ℝ with values in J such that f x₀ = y₀ and f' x = F x (f x) on [x₀ - h, x₀ + h].
universe u v
theorem metric_picard_existence_uniqueness
{a b c d x₀ y₀ L : ℝ}
(hI : a ≤ b) (hJ : c ≤ d)
(hx₀ : x₀ ∈ Set.Ioo a b) (hy₀ : y₀ ∈ Set.Ioo c d)
(F : ℝ → ℝ → ℝ)
(hF_cont : ContinuousOn (fun p : ℝ × ℝ => F p.1 p.2)
(Set.Icc a b ×ˢ Set.Icc c d))
(hL_nonneg : 0 ≤ L)
(hF_lip : ∀ x ∈ Set.Icc a b, ∀ y ∈ Set.Icc c d, ∀ z ∈ Set.Icc c d,
|F x y - F x z| ≤ L * |y - z|) :
∃ h > 0,
Set.Icc (x₀ - h) (x₀ + h) ⊆ Set.Icc a b ∧
∃ f : ℝ → ℝ,
DifferentiableOn ℝ f (Set.Icc (x₀ - h) (x₀ + h)) ∧
(∀ x ∈ Set.Icc (x₀ - h) (x₀ + h), f x ∈ Set.Icc c d) ∧
f x₀ = y₀ ∧
(∀ x ∈ Set.Icc (x₀ - h) (x₀ + h), HasDerivAt f (F x (f x)) x) ∧
∀ g : ℝ → ℝ,
DifferentiableOn ℝ g (Set.Icc (x₀ - h) (x₀ + h)) →
(∀ x ∈ Set.Icc (x₀ - h) (x₀ + h), g x ∈ Set.Icc c d) →
g x₀ = y₀ →
(∀ x ∈ Set.Icc (x₀ - h) (x₀ + h), HasDerivAt g (F x (g x)) x) →
Set.EqOn g f (Set.Icc (x₀ - h) (x₀ + h))