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.

Source header

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

Lean source

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)

Lean source

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

Lean source

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|

Lean source

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)

Lean source

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)

Lean source

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)

Lean source

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)

Lean source

open scoped BigOperators RealInnerProductSpace universe u lemma euclideanStandardDist_eq_dist (n : ℕ) (x y : EuclideanSpace ℝ (Fin n)) : euclideanStandardDist n x y = dist x y

Lean source

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

Lean source

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₂‖

Lean source

open scoped BigOperators RealInnerProductSpace universe u lemma complex_abs_sq (z : ℂ) : ‖z‖ ^ 2 = z.re ^ 2 + z.im ^ 2

Lean source

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

Lean source

open scoped BigOperators RealInnerProductSpace universe u lemma discreteDist_nonneg {X : Type u} [DecidableEq X] (x y : X) : 0 ≤ discreteDist x y

Lean source

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

Lean source

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

Lean source

open scoped BigOperators RealInnerProductSpace universe u lemma discreteDist_metricAxioms (X : Type u) [DecidableEq X] : MetricAxioms X (fun x y => discreteDist x y)

Lean source

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)

Lean source

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‖

Lean source

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}

Lean source

open scoped BigOperators RealInnerProductSpace universe u noncomputable def greatCircleDist (x y : spherePoints 1) : ℝ := Real.arccos (inner (𝕜 := ℝ) (x : EuclideanSpace ℝ (Fin 3)) (y : EuclideanSpace ℝ (Fin 3)))

Lean source

open scoped BigOperators RealInnerProductSpace universe u lemma spherePoints_norm_eq_one (x : spherePoints 1) : ‖(x : EuclideanSpace ℝ (Fin 3))‖ = 1

Lean source

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

Lean source

open scoped BigOperators RealInnerProductSpace universe u lemma greatCircleDist_triangle (x y z : spherePoints 1) : greatCircleDist x z ≤ greatCircleDist x y + greatCircleDist y z

Lean source

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)

Lean source

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

Lean source

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}

Lean source

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

Lean source

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

Lean source

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

Lean source

open scoped BigOperators RealInnerProductSpace universe u def boundedSpace {X : Type u} [MetricSpace X] : Prop := boundedSubset (X := X) (S := Set.univ)

Lean source

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 S

7.2 — Open and Closed Sets

Lean authors: Zichen Wang, Zaiwen Wen.

Source header

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

Lean source

Closed ball with center x and radius δ.

variable {X : Type*} [PseudoMetricSpace X] (x : X) (δ : ℝ) def closedBall : Set X := {y : X | dist y x ≤ δ}

Lean source

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 δ

Lean source

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 δ

Lean source

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

Lean source

variable (x δ : ℝ) lemma real_closedBall_eq_Icc : closedBall x δ = Set.Icc (x - δ) (x + δ)

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

lemma real_Ici_zero_isClosed : IsClosed (Set.Ici (0 : ℝ))

Lean source

lemma real_Ico_zero_one_not_isOpen : ¬ IsOpen (Set.Ico (0 : ℝ) 1)

Lean source

lemma real_Ico_zero_one_not_isClosed : ¬ IsClosed (Set.Ico (0 : ℝ) 1)

Lean source

lemma singleton_isClosed {X : Type*} [PseudoMetricSpace X] [T1Space X] (x : X) : IsClosed ({x} : Set X)

Lean source

lemma real_singleton_zero_not_isOpen : ¬ IsOpen ({0} : Set ℝ)

Lean source

lemma singleton_isOpen_of_subsingleton {X : Type*} [PseudoMetricSpace X] [Subsingleton X] (x : X) : IsOpen ({x} : Set X)

Lean source

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

Lean source

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

Lean source

lemma iInter_openIntervals_eq_singleton : (⋂ n : ℕ, Set.Ioo (-(1 / (n.succ : ℝ))) (1 / (n.succ : ℝ))) = ({0} : Set ℝ)

Lean source

lemma not_isOpen_iInter_openIntervals : ¬ IsOpen (⋂ n : ℕ, Set.Ioo (-(1 / (n.succ : ℝ))) (1 / (n.succ : ℝ)))

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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

Lean source

lemma image_preimage_subtype_eq {X : Type*} {V U : Set X} (hUV : U ⊆ V) : Subtype.val '' (Subtype.val ⁻¹' U : Set V) = U

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

The book's notion of a connected metric space agrees with ConnectedSpace.

theorem isConnectedMetricSpace_iff_connectedSpace (X : Type*) [PseudoMetricSpace X] : IsConnectedMetricSpace X ↔ ConnectedSpace X

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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

Lean source

noncomputable local instance discretePseudoMetricSpaceBool : PseudoMetricSpace Bool

Lean source

noncomputable local instance : UniformSpace Bool

Lean source

noncomputable local instance : TopologicalSpace Bool

Lean source

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)

Lean source

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}

Lean source

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

Lean source

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)

Lean source

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

Lean source

lemma image_subtype_lt_one_eq_Ioo : Subtype.val '' {x : Set.Ioi (0 : ℝ) | (x : ℝ) < 1} = Set.Ioo (0 : ℝ) 1

Lean source

lemma closure_subtype_rewrite (x : Set.Ioi (0 : ℝ)) : x ∈ closure ({x : Set.Ioi (0 : ℝ) | (x : ℝ) < 1}) ↔ (x : ℝ) ∈ closure (Set.Ioo (0 : ℝ) 1)

Lean source

lemma mem_target_set_iff_le_one (x : Set.Ioi (0 : ℝ)) : (x : ℝ) ∈ Set.Icc (0 : ℝ) 1 ↔ (x : ℝ) ≤ 1

Lean source

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}

Lean source

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

Lean source

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}

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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)

Lean source

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

Lean source

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)

Lean source

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

Lean source

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.

Source header

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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)

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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 ≤ ε

Lean source

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

Lean source

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)

Lean source

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)

Lean source

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)

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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 p

7.4 — Completeness and Compactness

Lean authors: Zichen Wang, Zaiwen Wen.

Source header

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

Proposition 7.4.4 (sequential version). Every Cauchy sequence in ℝ^n converges.

universe u v lemma metricCauchyCompleteSpace_euclideanSpace (n : ℕ) : metricCauchyCompleteSpace (X := EuclideanSpace ℝ (Fin n))

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

See also: Example 7.4.8 (ii).

universe u v theorem real_Ioo_zero_one_not_compact : ¬ IsCompact (Set.Ioo (0 : ℝ) 1)

Lean source

See also: Example 7.4.8 (iii).

universe u v theorem real_singleton_zero_compact : IsCompact ({0} : Set ℝ)

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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 i

7.5 — Continuous Functions

Lean authors: Zichen Wang, Zaiwen Wen.

Source header

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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)

Lean source

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

Lean source

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)

Lean source

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

Lean source

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

Lean source

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)

Lean source

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)

Lean source

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}

Lean source

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}

Lean source

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}

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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

Lean source

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)

Lean source

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)

Lean source

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

Lean source

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

Lean source

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

Lean source

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)

Lean source

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₂

Lean source

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.

Source header

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 φ

Lean source

universe u v variable {X : Type u} [PseudoMetricSpace X] variable {Y : Type v} [PseudoMetricSpace Y] def fixedPoint (φ : X → X) (x : X) : Prop := φ x = x

Lean source

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

Lean source

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

Lean source

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