Chapter 01 — Metric Spaces

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

Reading sections

1.1 — Definitions and Examples — Part 1

Lean authors: Zichen Wang, Wanli Ma, Ziyu Wang, Zaiwen Wen.

Source header

Theorem 1.1: summing (-a i) * b i gives the negative of the sum of a i * b i.

lemma sum_neg_mul_eq_neg_sum_mul (n : ℕ) (a b : Fin n → ℝ) : Finset.univ.sum (fun i : Fin n => (-a i) * b i) = - Finset.univ.sum (fun i : Fin n => a i * b i)

Lean source

Theorem 1.1: negation does not change the sum of squares.

lemma sum_neg_sq_eq_sum_sq (n : ℕ) (a : Fin n → ℝ) : Finset.univ.sum (fun i : Fin n => (-a i) ^ (2 : ℕ)) = Finset.univ.sum (fun i : Fin n => (a i) ^ (2 : ℕ))

Lean source

Theorem 1.1: the upper bound for the Cauchy--Schwarz sum.

lemma cauchySchwarz_sum_mul_upper (n : ℕ) (a b : Fin n → ℝ) : Finset.univ.sum (fun i : Fin n => a i * b i) ≤ Real.sqrt (Finset.univ.sum (fun i : Fin n => (a i) ^ (2 : ℕ))) * Real.sqrt (Finset.univ.sum (fun i : Fin n => (b i) ^ (2 : ℕ)))

Lean source

Theorem 1.1: the lower bound for the Cauchy--Schwarz sum.

lemma cauchySchwarz_sum_mul_lower (n : ℕ) (a b : Fin n → ℝ) : -(Real.sqrt (Finset.univ.sum (fun i : Fin n => (a i) ^ (2 : ℕ))) * Real.sqrt (Finset.univ.sum (fun i : Fin n => (b i) ^ (2 : ℕ)))) ≤ Finset.univ.sum (fun i : Fin n => a i * b i)

Lean source

Theorem 1.1: absolute-value form of the finite Cauchy--Schwarz inequality.

lemma cauchySchwarz_abs_sum_mul (n : ℕ) (a b : Fin n → ℝ) :

Lean source

Theorem 1.1 (Cauchy--Schwarz inequality): let n ≥ 1 and a b : Fin n → ℝ. Then |∑ i, a i * b i| ≤ (∑ i, (a i)^2)^{1/2} * (∑ i, (b i)^2)^{1/2}.

theorem cauchySchwarz_fin_sum_real (n : ℕ) (hn : 1 ≤ n) (a b : Fin n → ℝ) :

Lean source

Theorem 1.2 (Triangle inequality in ℝ^n for the Euclidean norm): let n ≥ 1 and a b : Fin n → ℝ. Then (∑ i, (a i + b i)^2)^{1/2} ≤ (∑ i, (a i)^2)^{1/2} + (∑ i, (b i)^2)^{1/2}.

theorem triangle_inequality_euclidean_norm_fin (n : ℕ) (hn : 1 ≤ n) (a b : Fin n → ℝ) : Real.sqrt (Finset.univ.sum (fun i : Fin n => (a i + b i) ^ (2 : ℕ))) ≤ Real.sqrt (Finset.univ.sum (fun i : Fin n => (a i) ^ (2 : ℕ))) + Real.sqrt (Finset.univ.sum (fun i : Fin n => (b i) ^ (2 : ℕ)))

Lean source

Definition 1.1 (Convergence of a real sequence from index m).

def RealSeqConvergesFrom (x : Nat -> Real) (m : Nat) (x0 : Real) : Prop := ∀ ε > 0, ∃ N ≥ m, ∀ n ≥ N, |x0 - x n| ≤ ε

Lean source

Definition 1.2: the distance function on ℝ.

abbrev realDist (x y : ℝ) : ℝ := dist x y

Lean source

Lemma 1.1: a real sequence starting at m converges to x iff lim_{n→∞} d(x_n,x)=0, where d(a,b)=|a-b| is the usual metric on ℝ.

lemma realSeqConvergesFrom_iff_realDist_tendsto_zero (m : Nat) (x : Nat → Real) (x0 : Real) : RealSeqConvergesFrom x m x0 ↔ RealSeqConvergesFrom (fun n => realDist (x n) x0) m 0

Lean source

Definition 1.3 (Metric space): a metric satisfies the usual axioms.

structure TaoMetricAxioms {X : Type*} (d : X → X → ℝ) : Prop where eq_zero_iff : ∀ x y, d x y = 0 ↔ x = y comm : ∀ x y, d x y = d y x triangle : ∀ x y z, d x z ≤ d x y + d y z nonneg : ∀ x y, 0 ≤ d x y

Lean source

If d x x = 0 and d x y = 0 → x = y, then d x y = 0 ↔ x = y.

lemma eq_zero_iff_of_self_of_eq_zero_imp {X : Type*} {d : X → X → ℝ} (hself : ∀ x, d x x = 0) (himp : ∀ x y, d x y = 0 → x = y) : ∀ x y, d x y = 0 ↔ x = y

Lean source

From d x y = 0 ↔ x = y we get d x x = 0.

lemma self_of_eq_zero_iff {X : Type*} {d : X → X → ℝ} (hiff : ∀ x y, d x y = 0 ↔ x = y) : ∀ x, d x x = 0

Lean source

From d x y = 0 ↔ x = y we get d x y = 0 → x = y.

lemma eq_of_eq_zero_of_eq_zero_iff {X : Type*} {d : X → X → ℝ} (hiff : ∀ x y, d x y = 0 ↔ x = y) : ∀ x y, d x y = 0 → x = y

Lean source

Proposition 1.1: the standard zero-distance formulations are equivalent.

lemma proposition_1_1 {X : Type*} {d : X → X → ℝ} : ((∀ x, d x x = 0) ∧ (∀ x y, d x y = 0 → x = y)) ↔ (∀ x y, d x y = 0 ↔ x = y)

Lean source

The distance of a metric space satisfies TaoMetricAxioms.

lemma metricAxioms_dist {X : Type*} [MetricSpace X] : TaoMetricAxioms (fun x y : X => dist x y)

Lean source

The real distance satisfies TaoMetricAxioms.

lemma metricAxioms_realDist : TaoMetricAxioms (fun x y : ℝ => realDist x y)

Lean source

A metric satisfies d x x = 0.

lemma TaoMetricAxioms.self {X : Type*} {d : X → X → ℝ} (h : TaoMetricAxioms d) (x : X) : d x x = 0

Lean source

The real distance equals the absolute value of the difference.

lemma realDist_eq_abs_sub (x y : ℝ) : realDist x y = |x - y|

Lean source

The absolute value of a difference equals the real distance.

lemma abs_sub_eq_realDist (x y : ℝ) : |x - y| = realDist x y

Lean source

Definition 1.4 (Standard metric on ℝ).

def standardMetric (x y : ℝ) : ℝ := |x - y|

Lean source

The standard metric agrees with realDist on ℝ.

lemma standardMetric_eq_realDist (x y : ℝ) : standardMetric x y = realDist x y

Lean source

The standard metric on ℝ satisfies TaoMetricAxioms.

lemma metricAxioms_standardMetric : TaoMetricAxioms (fun x y : ℝ => standardMetric x y)

Lean source

Definition 1.5: for a metric space (X, d) and Y ⊆ X, the induced metric on Y is the restriction d|_{Y×Y} given by d|_{Y×Y}(y1, y2) = d(y1, y2); the subspace induced by Y is the metric space (Y, d|_{Y×Y}).

def inducedMetric {X : Type*} [MetricSpace X] (Y : Set X) : Subtype Y → Subtype Y → ℝ := fun y1 y2 => dist (y1 : X) (y2 : X)

Lean source

The metric space structure on a subset induced by the ambient metric.

abbrev subspaceMetricSpace {X : Type*} [MetricSpace X] (Y : Set X) : MetricSpace (Subtype Y) := inferInstance

Lean source

Definition 1.6: for n ≥ 1, the Euclidean (ℓ^2) metric on ℝ^n is d_{ℓ^2}(x,y) = √(∑ i, (x i - y i)^2); the metric space (ℝ^n, d_{ℓ^2}) is called Euclidean space of dimension n.

noncomputable abbrev euclideanMetric (n : ℕ) : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n) → ℝ := dist

Lean source

Definition 1.7: for n ≥ 1, the taxicab (ℓ^1) metric on ℝ^n is d_{ℓ^1}(x,y) = ∑ i, |x i - y i|, where x = (x_1, ..., x_n) and y = (y_1, ..., y_n).

def taxicabMetric (n : ℕ) (x y : Fin n → ℝ) : ℝ := Finset.univ.sum (fun i => |x i - y i|)

Lean source

The ℓ^2 distance on ℝ^n given by sqrt (∑ i, |x i - y i|^2).

noncomputable def l2Distance (n : ℕ) (x y : Fin n → ℝ) : ℝ := Real.sqrt (Finset.univ.sum (fun i => |x i - y i| ^ (2 : ℕ)))

Lean source

Proposition 1.2: the sum of squares of |x i - y i| is bounded by the square of the sum.

lemma sum_abs_sub_sq_le_sq_sum_abs_sub (n : ℕ) (x y : Fin n → ℝ) : (Finset.univ.sum (fun i => |x i - y i| ^ (2 : ℕ))) ≤ (Finset.univ.sum (fun i => |x i - y i|)) ^ (2 : ℕ)

Lean source

Proposition 1.2: the ℓ² distance is bounded above by the ℓ¹ distance.

lemma l2Distance_le_taxicabMetric (n : ℕ) (x y : Fin n → ℝ) : l2Distance n x y ≤ taxicabMetric n x y

Lean source

Proposition 1.2: the ℓ¹ distance is bounded by √n times the ℓ² distance.

lemma taxicabMetric_le_sqrt_n_mul_l2Distance (n : ℕ) (x y : Fin n → ℝ) : taxicabMetric n x y ≤ Real.sqrt (n : ℝ) * l2Distance n x y

Lean source

Proposition 1.2: Let n ≥ 1 and x,y ∈ ℝ^n. Define d_{ℓ^1}(x,y) = ∑ i, |x i - y i| and d_{ℓ^2}(x,y) = (∑ i, |x i - y i|^2)^{1/2}. Then d_{ℓ^2}(x,y) ≤ d_{ℓ^1}(x,y) ≤ √n * d_{ℓ^2}(x,y).

theorem l2Distance_le_l1Distance_le_sqrt_n_l2Distance (n : ℕ) (hn : 1 ≤ n) (x y : Fin n → ℝ) : l2Distance n x y ≤ taxicabMetric n x y ∧ taxicabMetric n x y ≤ Real.sqrt (n : ℝ) * l2Distance n x y

Lean source

Definition 1.8: for n ≥ 1, the sup norm (ℓ^∞) metric on ℝ^n is d_{ℓ^∞}(x,y) = sup { |x i - y i| : 1 ≤ i ≤ n }, where x = (x_1, ..., x_n) and y = (y_1, ..., y_n).

noncomputable def supNormMetric (n : ℕ) (x y : Fin n → ℝ) : ℝ := sSup (Set.range (fun i : Fin n => |x i - y i|))

Lean source

Proposition 1.3: the range of coordinate differences is nonempty when n ≥ 1.

lemma prop_1_3_range_abs_sub_nonempty (n : ℕ) (hn : 1 ≤ n) (x y : Fin n → ℝ) : (Set.range (fun i : Fin n => |x i - y i|)).Nonempty

Lean source

Proposition 1.3: the range of coordinate differences is bounded above.

lemma prop_1_3_bddAbove_range_abs_sub (n : ℕ) (x y : Fin n → ℝ) : BddAbove (Set.range (fun i : Fin n => |x i - y i|))

Lean source

Proposition 1.3: each coordinate difference is bounded by the sup norm metric.

lemma prop_1_3_abs_sub_le_supNormMetric (n : ℕ) (x y : Fin n → ℝ) : ∀ i : Fin n, |x i - y i| ≤ supNormMetric n x y

Lean source

Proposition 1.3: the sup norm metric is nonnegative.

lemma prop_1_3_supNormMetric_nonneg (n : ℕ) (hn : 1 ≤ n) (x y : Fin n → ℝ) : 0 ≤ supNormMetric n x y

Lean source

Proposition 1.3: each coordinate difference is bounded by the ℓ² distance.

lemma prop_1_3_abs_sub_le_l2Distance (n : ℕ) (x y : Fin n → ℝ) : ∀ i : Fin n, |x i - y i| ≤ l2Distance n x y

Lean source

Proposition 1.3: the ℓ² distance is bounded by √n times the sup norm metric.

lemma prop_1_3_l2Distance_le_sqrt_n_mul_supNormMetric (n : ℕ) (hn : 1 ≤ n) (x y : Fin n → ℝ) : l2Distance n x y ≤ Real.sqrt (n : ℝ) * supNormMetric n x y

Lean source

Proposition 1.3: Let n ≥ 1. For all x,y ∈ ℝ^n, the metrics d_{ℓ^∞} and d_{ℓ^2} satisfy (1/√n) d_{ℓ^2}(x,y) ≤ d_{ℓ^∞}(x,y) ≤ d_{ℓ^2}(x,y). Equivalently, for all v ∈ ℝ^n, (1/√n) ‖v‖_2 ≤ ‖v‖_∞ ≤ ‖v‖_2.

theorem one_div_sqrt_n_l2Distance_le_supNormMetric_le_l2Distance (n : ℕ) (hn : 1 ≤ n) (x y : Fin n → ℝ) : (1 / Real.sqrt (n : ℝ)) * l2Distance n x y ≤ supNormMetric n x y ∧ supNormMetric n x y ≤ l2Distance n x y

Lean source

Definition 1.9 (Convergence of sequences in metric spaces): a sequence (x^{(n)})_{n=m}^∞ in a metric space converges to x if for every ε > 0 there exists an integer N ≥ m such that dist (x n) x ≤ ε for all n ≥ N (equivalently, dist (x n) x → 0 as n → ∞).

def MetricSeqConvergesFrom {X : Type*} [MetricSpace X] (x : ℤ → X) (m : ℤ) (x0 : X) : Prop := ∀ ε > 0, ∃ N ≥ m, ∀ n ≥ N, dist (x n) x0 ≤ ε

Lean source

Proposition 1.4: if a sequence in a metric space converges to x0 from index m, then any tail starting at m' ≥ m also converges to x0.

theorem tail_converges_of_converges {X : Type*} [MetricSpace X] (x : ℤ → X) (m : ℤ) (x0 : X) : MetricSeqConvergesFrom x m x0 → ∀ m' ≥ m, MetricSeqConvergesFrom x m' x0

Lean source

Convergence from index m with respect to a specified distance function.

def SeqConvergesFromWith {X : Type*} (d : X → X → ℝ) (x : ℕ → X) (m : ℕ) (x0 : X) : Prop := ∀ ε > 0, ∃ N ≥ m, ∀ n ≥ N, d (x n) x0 ≤ ε

Lean source

Proposition 1.5: transfer convergence when one distance is pointwise bounded by another.

lemma seqConvergesFromWith_of_le {X : Type*} {d1 d2 : X → X → ℝ} {x : ℕ → X} {m : ℕ} {x0 : X} (h : ∀ u v, d1 u v ≤ d2 u v) : SeqConvergesFromWith d2 x m x0 → SeqConvergesFromWith d1 x m x0

Lean source

Proposition 1.5: transfer convergence under a pointwise bound by a positive multiple.

lemma seqConvergesFromWith_of_le_mul {X : Type*} {d1 d2 : X → X → ℝ} {x : ℕ → X} {m : ℕ} {x0 : X} {C : ℝ} (hC : 0 < C) (h : ∀ u v, d1 u v ≤ C * d2 u v) : SeqConvergesFromWith d2 x m x0 → SeqConvergesFromWith d1 x m x0

Lean source

Proposition 1.5: a uniform index for finitely many coordinate bounds.

lemma exists_uniform_index_forall_fin (n : ℕ) (m : ℕ) {P : Fin n → ℕ → Prop} (h : ∀ j : Fin n, ∃ Nj ≥ m, ∀ k ≥ Nj, P j k) : ∃ N ≥ m, ∀ k ≥ N, ∀ j : Fin n, P j k

Lean source

Proposition 1.5 (Equivalence of ℓ^1, ℓ^2, ℓ^∞ convergence in ℝ^n): let n ∈ ℕ, let (x^{(k)})_{k=m}^∞ be a sequence in ℝ^n with x^{(k)} = (x_1^{(k)}, ..., x_n^{(k)}), and let x = (x_1, ..., x_n). Then the following are equivalent: (a) x^{(k)} → x with respect to d_{ℓ^2}, (b) x^{(k)} → x with respect to d_{ℓ^1}, (c) x^{(k)} → x with respect to d_{ℓ^∞}, and (d) for every 1 ≤ j ≤ n, the real sequence (x_j^{(k)})_{k=m}^∞ converges to x_j.

theorem equiv_l1_l2_linf_convergence_Rn (n : ℕ) (m : ℕ) (x : ℕ → Fin n → ℝ) (x0 : Fin n → ℝ) : (SeqConvergesFromWith (l2Distance n) x m x0 ↔ SeqConvergesFromWith (taxicabMetric n) x m x0) ∧ (SeqConvergesFromWith (taxicabMetric n) x m x0 ↔ SeqConvergesFromWith (supNormMetric n) x m x0) ∧ (SeqConvergesFromWith (supNormMetric n) x m x0 ↔ ∀ j : Fin n, RealSeqConvergesFrom (fun k => x k j) m (x0 j))

Lean source

The discrete metric on a type: d(a,b)=0 if a=b and d(a,b)=1 otherwise.

noncomputable def discreteMetric {X : Type*} (a b : X) : ℝ := @ite ℝ (a = b) (Classical.decEq (α := X) a b) 0 1

Lean source

Proposition 1.6: in the discrete metric, the bound ≤ 1/2 forces equality.

lemma discreteMetric_le_one_half_iff_eq {X : Type*} (a b : X) : discreteMetric (X := X) a b ≤ (1 / 2 : ℝ) ↔ a = b

Lean source

Proposition 1.6: convergence in the discrete metric implies eventual equality.

lemma discreteMetric_eventually_eq_of_converges {X : Type*} (x : ℕ → X) (m : ℕ) (x0 : X) : SeqConvergesFromWith (discreteMetric (X := X)) x m x0 → ∃ N ≥ m, ∀ n ≥ N, x n = x0

Lean source

Proposition 1.6: eventual equality implies convergence in the discrete metric.

lemma discreteMetric_converges_of_eventually_eq {X : Type*} (x : ℕ → X) (m : ℕ) (x0 : X) : (∃ N ≥ m, ∀ n ≥ N, x n = x0) → SeqConvergesFromWith (discreteMetric (X := X)) x m x0

Lean source

Proposition 1.6 (Convergence in the discrete metric): a sequence converges to x0 with respect to the discrete metric iff it is eventually constantly equal to x0.

theorem discreteMetric_converges_iff_eventually_eq {X : Type*} (x : ℕ → X) (m : ℕ) (x0 : X) : SeqConvergesFromWith (discreteMetric (X := X)) x m x0 ↔ ∃ N ≥ m, ∀ n ≥ N, x n = x0

Lean source

Proposition 1.7 (Uniqueness of limits): if a sequence converges to x0 and also to x1 with respect to a metric d, then x0 = x1.

theorem metric_limit_unique {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) (x0 x1 : X) : SeqConvergesFromWith (d := dist) x m x0 → SeqConvergesFromWith (d := dist) x m x1 → x0 = x1

Lean source

Proposition 1.8: Let (X, d) be a metric space and let f : X → X be a bijection. Define d'(x,y) = d (f x) (f y). Then d' is a metric on X.

theorem metricAxioms_comp_bijective {X : Type*} {d : X → X → ℝ} (hd : TaoMetricAxioms d) {f : X → X} (hf : Function.Bijective f) : TaoMetricAxioms (fun x y => d (f x) (f y))

Lean source

Proposition 1.9 (prop:1.9): 0 and 1 lie in the closed unit interval.

lemma zero_mem_Icc_zero_one_and_one_mem_Icc_zero_one : (0 : ℝ) ∈ Set.Icc (0 : ℝ) 1 ∧ (1 : ℝ) ∈ Set.Icc (0 : ℝ) 1

Lean source

Proposition 1.9 (prop:1.9): the map on the closed unit interval that sends 0 to 1, 1 to 0, and fixes every x ∈ (0,1).

noncomputable def swapEndpointsOnUnitInterval : {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1} → {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1} := fun x => if _ : (x : ℝ) = 0 then ⟨1, (zero_mem_Icc_zero_one_and_one_mem_Icc_zero_one).2⟩ else if _ : (x : ℝ) = 1 then ⟨0, (zero_mem_Icc_zero_one_and_one_mem_Icc_zero_one).1⟩ else x

Lean source

Proposition 1.9 (prop:1.9): the metric d'(x,y)=|f(x)-f(y)| on the closed unit interval induced by swapEndpointsOnUnitInterval.

noncomputable def swapEndpointsMetric (x y : {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1}) : ℝ := |(swapEndpointsOnUnitInterval x : ℝ) - (swapEndpointsOnUnitInterval y : ℝ)|

Lean source

Proposition 1.9 (prop:1.9): 1/n lies in [0,1] for positive n.

lemma one_div_mem_Icc_zero_one_of_nat_pos (n : ℕ) (hn : n ≠ 0) : ((1 : ℝ) / (n : ℝ)) ∈ Set.Icc (0 : ℝ) 1

Lean source

Helper for Theorem 1.2: expand the sum of squares of a i + b i.

lemma helperForTheorem_1_2_sum_add_sq (n : ℕ) (a b : Fin n → ℝ) : Finset.univ.sum (fun i : Fin n => (a i + b i) ^ (2 : ℕ)) = Finset.univ.sum (fun i : Fin n => (a i) ^ (2 : ℕ)) + Finset.univ.sum (fun i : Fin n => (b i) ^ (2 : ℕ)) + 2 * Finset.univ.sum (fun i : Fin n => a i * b i)

Lean source

Helper for Theorem 1.2: squared form of the triangle inequality.

lemma helperForTheorem_1_2_sum_add_sq_le_rhs_sq (n : ℕ) (a b : Fin n → ℝ) : Finset.univ.sum (fun i : Fin n => (a i + b i) ^ (2 : ℕ)) ≤ (Real.sqrt (Finset.univ.sum (fun i : Fin n => (a i) ^ (2 : ℕ))) + Real.sqrt (Finset.univ.sum (fun i : Fin n => (b i) ^ (2 : ℕ)))) ^ (2 : ℕ)

1.1 — Definitions and Examples — Part 2

Lean authors: Zichen Wang, Wanli Ma, Ziyu Wang, Zaiwen Wen.

Source header

Proposition 1.9 (prop:1.9): the sequence (1/n)_{n≥1} viewed as a map ℕ → [0,1].

noncomputable def oneOverNatSeqInUnitInterval : ℕ → {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1} := fun n => if h : n = 0 then ⟨1, (zero_mem_Icc_zero_one_and_one_mem_Icc_zero_one).2⟩ else ⟨(1 : ℝ) / (n : ℝ), one_div_mem_Icc_zero_one_of_nat_pos n h⟩

Lean source

Proposition 1.9 (prop:1.9): the point 1 in the closed unit interval.

def unitIntervalOne : {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1} := ⟨1, (zero_mem_Icc_zero_one_and_one_mem_Icc_zero_one).2⟩

Lean source

Proposition 1.9 (prop:1.9): the point 0 in the closed unit interval.

def unitIntervalZero : {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1} := ⟨0, (zero_mem_Icc_zero_one_and_one_mem_Icc_zero_one).1⟩

Lean source

Proposition 1.9 (prop:1.9): explicit values of swapEndpointsOnUnitInterval.

lemma swapEndpointsOnUnitInterval_apply_simp : (swapEndpointsOnUnitInterval unitIntervalOne = unitIntervalZero) ∧ (swapEndpointsOnUnitInterval unitIntervalZero = unitIntervalOne) ∧ (∀ x : {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1}, ((x : ℝ) ≠ 0) → ((x : ℝ) ≠ 1) → swapEndpointsOnUnitInterval x = x)

Lean source

Proposition 1.9 (prop:1.9): coercions and interior points of the sequence.

lemma oneOverNatSeqInUnitInterval_coe_succ_and_interior : (∀ n, ((oneOverNatSeqInUnitInterval (Nat.succ n) : {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1}) : ℝ) = (1 : ℝ) / (Nat.succ n : ℝ)) ∧ (∀ n ≥ 2, ((oneOverNatSeqInUnitInterval n : {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1}) : ℝ) ≠ 0 ∧ ((oneOverNatSeqInUnitInterval n : {x : ℝ // x ∈ Set.Icc (0 : ℝ) 1}) : ℝ) ≠ 1)

Lean source

Proposition 1.9 (prop:1.9): the swapped metric on the sequence near 1.

lemma swapEndpointsMetric_oneOverNatSeq_unitIntervalOne : ∀ n ≥ 2, swapEndpointsMetric (oneOverNatSeqInUnitInterval n) unitIntervalOne = (1 : ℝ) / (n : ℝ)

Lean source

Proposition 1.9: let X = [0,1] with the usual metric d(x,y)=|x-y|, let f swap 0 and 1 and fix all x ∈ (0,1), and define d'(x,y)=|f(x)-f(y)|. Then the sequence (1/n)_{n≥1} converges to 1 with respect to d'.

theorem oneOverNat_converges_to_one_swapEndpointsMetric : SeqConvergesFromWith (d := swapEndpointsMetric) oneOverNatSeqInUnitInterval 1 unitIntervalOne

Lean source

Proposition 1.10: if x_n → x and y_n → y in a metric space, then d(x_n,y_n) converges to d(x,y).

theorem dist_seq_converges_of_converges {X : Type*} [MetricSpace X] (x y : ℕ → X) (x0 y0 : X) : SeqConvergesFromWith (d := dist) x 1 x0 → SeqConvergesFromWith (d := dist) y 1 y0 → RealSeqConvergesFrom (fun n => dist (x n) (y n)) 1 (dist x0 y0)

Lean source

Proposition 1.30 (Comparison of ℓ^1 and ℓ^2 metrics): let n ≥ 1 and x,y ∈ ℝ^n. Then d_{ℓ^2}(x,y) ≤ d_{ℓ^1}(x,y) ≤ √n * d_{ℓ^2}(x,y).

theorem l2Distance_le_l1Distance_le_sqrt_n_l2Distance_prop (n : ℕ) (hn : 1 ≤ n) (x y : Fin n → ℝ) : l2Distance n x y ≤ taxicabMetric n x y ∧ taxicabMetric n x y ≤ Real.sqrt (n : ℝ) * l2Distance n x y

Lean source

Proposition 1.31 (Comparison of ℓ^2 and ℓ^∞ metrics): let n ≥ 1 and x,y ∈ ℝ^n. Then (1/√n) d_{ℓ^2}(x,y) ≤ d_{ℓ^∞}(x,y) ≤ d_{ℓ^2}(x,y).

theorem one_div_sqrt_n_l2Distance_le_supNormMetric_le_l2Distance_prop (n : ℕ) (hn : 1 ≤ n) (x y : Fin n → ℝ) : (1 / Real.sqrt (n : ℝ)) * l2Distance n x y ≤ supNormMetric n x y ∧ supNormMetric n x y ≤ l2Distance n x y

Lean source

Proposition 1.32 (Equivalence of ℓ^1, ℓ^2, ℓ^∞ metrics): let n ≥ 1. A sequence in ℝ^n converges to x with respect to one of these metrics iff it converges to x with respect to each of the other two metrics.

theorem l1_l2_linf_convergence_equiv_Rn_metrics (n : ℕ) (hn : 1 ≤ n) (x : ℕ → Fin n → ℝ) (x0 : Fin n → ℝ) : SeqConvergesFromWith (taxicabMetric n) x 1 x0 ↔ (SeqConvergesFromWith (l2Distance n) x 1 x0 ∧ SeqConvergesFromWith (supNormMetric n) x 1 x0)

Lean source

Helper for Proposition 1.10: bound the difference of distances by a sum.

lemma helperForProposition_1_10_abs_dist_dist_le {X : Type*} [MetricSpace X] (a b c d : X) :

Lean source

Helper for Proposition 1.10: combine two eventual bounds past a max index.

lemma helperForProposition_1_10_max_index_eventually {P Q : ℕ → Prop} {N1 N2 : ℕ} (hP : ∀ n ≥ N1, P n) (hQ : ∀ n ≥ N2, Q n) : ∀ n ≥ max N1 N2, P n ∧ Q n

1.2 — Some Point-Set Topology of Metric Spaces

Lean authors: Zichen Wang, Wanli Ma, Ziyu Wang, Zaiwen Wen.

Source header

Definition 1.10 (Balls): Let (X,d) be a metric space, let x0 ∈ X, and let r > 0. The (open) ball in X centered at x0 with radius r is the set B_{(X,d)}(x0,r) = {x ∈ X : d(x,x0) < r}.

abbrev taoOpenBall (X : Type*) [MetricSpace X] (x0 : X) (r : Real) : Set X := Metric.ball x0 r

Lean source

Definition 1.11 (Interior/exterior/boundary points): Let (X,d) be a metric space and E ⊆ X. (1) x ∈ X is an interior point of E iff there exists r > 0 with B(x,r) ⊆ E. (2) x ∈ X is an exterior point of E iff there exists r > 0 with B(x,r) ⊆ Eᶜ. (3) x ∈ X is a boundary point of E iff for every r > 0, both B(x,r) ∩ E ≠ ∅ and B(x,r) ∩ Eᶜ ≠ ∅.

def IsInteriorPoint {X : Type*} [MetricSpace X] (E : Set X) (x : X) : Prop := ∃ r : ℝ, 0 < r ∧ Metric.ball x r ⊆ E

Lean source

A point is an exterior point of E if some positive ball around it is contained in Eᶜ.

def IsExteriorPoint {X : Type*} [MetricSpace X] (E : Set X) (x : X) : Prop := ∃ r : ℝ, 0 < r ∧ Metric.ball x r ⊆ Eᶜ

Lean source

A point is a boundary point of E if every positive ball meets both E and Eᶜ.

def IsBoundaryPoint {X : Type*} [MetricSpace X] (E : Set X) (x : X) : Prop := ∀ r : ℝ, 0 < r → ((Metric.ball x r) ∩ E).Nonempty ∧ ((Metric.ball x r) ∩ Eᶜ).Nonempty

Lean source

Interior points defined via balls coincide with membership in interior.

lemma isInteriorPoint_iff_mem_interior {X : Type*} [MetricSpace X] (E : Set X) (x : X) : IsInteriorPoint E x ↔ x ∈ interior E

Lean source

Exterior points defined via balls coincide with membership in interior of the complement.

lemma isExteriorPoint_iff_mem_interior_compl {X : Type*} [MetricSpace X] (E : Set X) (x : X) : IsExteriorPoint E x ↔ x ∈ interior (Eᶜ)

Lean source

Characterize closure via nonempty intersections of all positive balls.

lemma mem_closure_iff_forall_ball_inter_nonempty {X : Type*} [MetricSpace X] (s : Set X) (x : X) : x ∈ closure s ↔ ∀ r : ℝ, 0 < r → ((Metric.ball x r) ∩ s).Nonempty

Lean source

Boundary points are exactly those in the closures of the set and its complement.

lemma isBoundaryPoint_iff_mem_closure_inter_closure_compl {X : Type*} [MetricSpace X] (E : Set X) (x : X) : IsBoundaryPoint E x ↔ x ∈ closure E ∩ closure (Eᶜ)

Lean source

Boundary points defined via balls coincide with membership in frontier.

lemma isBoundaryPoint_iff_mem_frontier {X : Type*} [MetricSpace X] (E : Set X) (x : X) : IsBoundaryPoint E x ↔ x ∈ frontier E

Lean source

Definition 1.12 (Interior, exterior, boundary): Let (X,d) be a metric space and E ⊆ X. (1) x ∈ X is an interior point of E iff there exists r > 0 with B(x,r) ⊆ E. (2) x ∈ X is an exterior point of E iff there exists r > 0 with B(x,r) ∩ E = ∅. (3) x ∈ X is a boundary point of E iff it is neither interior nor exterior. The interior (resp. exterior, boundary) of E is the set of all interior (resp. exterior, boundary) points.

def interiorSet {X : Type*} [MetricSpace X] (E : Set X) : Set X := {x | IsInteriorPoint E x}

Lean source

The exterior set of E as the set of exterior points.

def exteriorSet {X : Type*} [MetricSpace X] (E : Set X) : Set X := {x | IsExteriorPoint E x}

Lean source

The boundary set of E as the set of points that are neither interior nor exterior.

def boundarySet {X : Type*} [MetricSpace X] (E : Set X) : Set X := {x | ¬ IsInteriorPoint E x ∧ ¬ IsExteriorPoint E x}

Lean source

The book's interior set agrees with interior.

lemma interiorSet_eq_interior {X : Type*} [MetricSpace X] (E : Set X) : interiorSet E = interior E

Lean source

The book's exterior set agrees with interior (Eᶜ).

lemma exteriorSet_eq_interior_compl {X : Type*} [MetricSpace X] (E : Set X) : exteriorSet E = interior (Eᶜ)

Lean source

The book's boundary set agrees with frontier.

lemma boundarySet_eq_frontier {X : Type*} [MetricSpace X] (E : Set X) : boundarySet E = frontier E

Lean source

Proposition 1.11: Let (X,d) be a metric space and E ⊆ X. Define int(E) = {x ∈ X : ∃ r > 0, B(x,r) ⊆ E}, ext(E) = int(X \ E), and ∂E = X \ (int(E) ∪ ext(E)), where B(x,r) = {y ∈ X : d(x,y) < r}. Then: (1) If x0 ∈ int(E), then x0 ∈ E. (2) If x0 ∈ ext(E), then x0 ∉ E. (3) int(E) ∩ ext(E) = ∅. (4) If x0 ∈ ∂E, then it is possible that x0 ∈ E and it is possible that x0 ∉ E.

lemma proposition_1_11 {X : Type*} [MetricSpace X] (E : Set X) : (∀ x0, x0 ∈ interiorSet E → x0 ∈ E) ∧ (∀ x0, x0 ∈ exteriorSet E → x0 ∉ E) ∧ (interiorSet E ∩ exteriorSet E = (∅ : Set X)) ∧ (∀ x0, x0 ∈ boundarySet E → (x0 ∈ E ∨ x0 ∉ E))

Lean source

If a point lies in the interior set, then it lies in the set.

lemma mem_of_mem_interiorSet {X : Type*} [MetricSpace X] {E : Set X} {x0 : X} : x0 ∈ interiorSet E → x0 ∈ E

Lean source

If a point lies in the exterior set, then it is not in the set.

lemma mem_compl_of_mem_exteriorSet {X : Type*} [MetricSpace X] {E : Set X} {x0 : X} : x0 ∈ exteriorSet E → x0 ∉ E

Lean source

The interior and exterior sets are disjoint.

lemma interiorSet_inter_exteriorSet_eq_empty {X : Type*} [MetricSpace X] (E : Set X) : interiorSet E ∩ exteriorSet E = (∅ : Set X)

Lean source

A boundary point may or may not lie in the set.

lemma mem_or_not_mem_of_mem_boundarySet {X : Type*} [MetricSpace X] {E : Set X} {x0 : X} : x0 ∈ boundarySet E → (x0 ∈ E ∨ x0 ∉ E)

Lean source

Proposition 1.12: Let E = [1,2) ⊆ ℝ with the standard metric. Then interior E = (1,2), interior (Eᶜ) = (-∞,1) ∪ (2,∞), and frontier E = {1,2}. In particular, 1 ∈ E ∩ frontier E and 2 ∈ frontier E \ E.

lemma real_Ico_interior_exterior_boundary : let E : Set ℝ := Set.Ico (1 : ℝ) 2 ; interior E = Set.Ioo (1 : ℝ) 2 ∧ interior (Eᶜ) = Set.Iio (1 : ℝ) ∪ Set.Ioi (2 : ℝ) ∧ frontier E = ({1, 2} : Set ℝ) ∧ (1 : ℝ) ∈ E ∩ frontier E ∧ (2 : ℝ) ∈ frontier E \ E

Lean source

Proposition 1.13: Let X be a set equipped with the discrete metric d_disc with d_disc(x,y)=0 if x=y and d_disc(x,y)=1 if x≠y. For every E ⊆ X, int(E)=E, ext(E)=X \ E, and ∂E=∅.

lemma proposition_1_13 {X : Type*} [MetricSpace X] [DiscreteTopology X] (E : Set X) : interiorSet E = E ∧ exteriorSet E = Eᶜ ∧ boundarySet E = (∅ : Set X)

Lean source

Definition 1.13 (Closure): Let (X,d) be a metric space and E ⊆ X. A point x ∈ X is an adherent point of E iff for every r > 0, B(x,r) ∩ E ≠ ∅, where B(x,r) = {y ∈ X : d(x,y) < r}. The closure \overline{E} is the set of all adherent points: \overline{E} = {x ∈ X : ∀ r > 0, B(x,r) ∩ E ≠ ∅}.

def closureSet {X : Type*} [MetricSpace X] (E : Set X) : Set X := {x | ∀ r : ℝ, 0 < r → (Metric.ball x r ∩ E).Nonempty}

Lean source

A point is adherent to E if every positive ball around it meets E.

def IsAdherentPoint {X : Type*} [MetricSpace X] (E : Set X) (x : X) : Prop := ∀ r : ℝ, 0 < r → (Metric.ball x r ∩ E).Nonempty

Lean source

Adherent points coincide with membership in closure.

lemma isAdherentPoint_iff_mem_closure {X : Type*} [MetricSpace X] (E : Set X) (x : X) : IsAdherentPoint E x ↔ x ∈ closure E

Lean source

The closure of E as the set of adherent points.

lemma closureSet_eq_setOf_isAdherentPoint {X : Type*} [MetricSpace X] (E : Set X) : closureSet E = {x | IsAdherentPoint E x}

Lean source

The book's closure set agrees with closure.

lemma closureSet_eq_closure {X : Type*} [MetricSpace X] (E : Set X) : closureSet E = closure E

Lean source

Proposition 1.14: Let (X,d) be a metric space, E ⊆ X, and x0 ∈ X. The following are equivalent: (a) x0 is adherent to E, i.e., every r > 0 has B(x0,r) ∩ E ≠ ∅; (b) x0 is either an interior point of E or a boundary point of E; (c) there exists a sequence (x_n) in E with x_n → x0.

lemma proposition_1_14 {X : Type*} [MetricSpace X] (E : Set X) (x0 : X) : (IsAdherentPoint E x0 ↔ IsInteriorPoint E x0 ∨ IsBoundaryPoint E x0) ∧ (IsAdherentPoint E x0 ↔ ∃ u : ℕ → X, (∀ n, u n ∈ E) ∧ Filter.Tendsto u Filter.atTop (nhds x0))

Lean source

Theorem 1.3: Let (X,d) be a metric space and E ⊆ X. Define int(E) = {x ∈ X : ∃ r > 0, B(x,r) ⊆ E}, ext(E) = int(X \ E), ∂E = X \ (int(E) ∪ ext(E)), and \overline{E} = {x ∈ X : ∀ r > 0, B(x,r) ∩ E ≠ ∅}. Then \overline{E} = int(E) ∪ ∂E = X \ ext(E).

theorem closureSet_eq_interiorSet_union_boundarySet_and_compl_exteriorSet {X : Type*} [MetricSpace X] (E : Set X) : closureSet E = interiorSet E ∪ boundarySet E ∧ closureSet E = (exteriorSet E)ᶜ

Lean source

The closure equals the union of the interior and boundary, and equals the complement of the exterior.

lemma closureSet_eq_interiorSet_union_boundarySet_and_compl_exteriorSet' {X : Type*} [MetricSpace X] (E : Set X) : closureSet E = interiorSet E ∪ boundarySet E ∧ closureSet E = (exteriorSet E)ᶜ

Lean source

Definition 1.14 (Open and closed sets): Let (X,d) be a metric space and E ⊆ X. The set E is called closed if ∂E ⊆ E. The set E is called open if ∂E ∩ E = ∅.

def IsClosedSet {X : Type*} [MetricSpace X] (E : Set X) : Prop := frontier E ⊆ E

Lean source

A set is open in the book's sense if its frontier is disjoint from it.

def IsOpenSet {X : Type*} [MetricSpace X] (E : Set X) : Prop := frontier E ∩ E = (∅ : Set X)

Lean source

The book's closed-set predicate is equivalent to IsClosed.

lemma isClosedSet_iff_isClosed {X : Type*} [MetricSpace X] (E : Set X) : IsClosedSet E ↔ IsClosed E

Lean source

The book's open-set predicate is equivalent to IsOpen.

lemma isOpenSet_iff_isOpen {X : Type*} [MetricSpace X] (E : Set X) : IsOpenSet E ↔ IsOpen E

Lean source

Proposition 1.15: Let (X,d) be a metric space. Then X and ∅ are both open and closed subsets of X.

lemma proposition_1_15 {X : Type*} [MetricSpace X] : IsOpen (Set.univ : Set X) ∧ IsClosed (Set.univ : Set X) ∧ IsOpen (∅ : Set X) ∧ IsClosed (∅ : Set X)

Lean source

In a metric space, Set.univ and ∅ are both open and closed.

lemma open_closed_univ_empty {X : Type*} [MetricSpace X] : IsOpen (Set.univ : Set X) ∧ IsClosed (Set.univ : Set X) ∧ IsOpen (∅ : Set X) ∧ IsClosed (∅ : Set X)

Lean source

Proposition 1.16: Let (X, d_disc) be a set equipped with the discrete metric d_disc(x,y)=0 if x=y and d_disc(x,y)=1 if x≠y. Then every subset E ⊆ X is open and closed in the metric topology induced by d_disc.

lemma proposition_1_16 {X : Type*} [MetricSpace X] [DiscreteTopology X] (E : Set X) : IsOpen E ∧ IsClosed E

Lean source

Proposition 1.17 (Basic properties of open and closed sets): Let (X,d) be a metric space. (a) For E ⊆ X, E is open iff E = int(E); equivalently, E is open iff for every x ∈ E there exists r > 0 such that B(x,r) ⊆ E. (b) For E ⊆ X, E is closed iff it contains all its adherent points; equivalently, E is closed iff every convergent sequence in E has its limit in E. (c) For x0 ∈ X and r > 0, B(x0,r) is open and {x ∈ X : d(x,x0) ≤ r} is closed. (d) For x0 ∈ X, the singleton {x0} is closed. (e) For E ⊆ X, E is open iff X \ E is closed. (f) Finite intersections of open sets are open; finite unions of closed sets are closed. (g) Arbitrary unions of open sets are open; arbitrary intersections of closed sets are closed. (h) For E ⊆ X, int(E) is the largest open set contained in E, and \overline{E} is the smallest closed set containing E.

lemma proposition_1_17 {X : Type*} [MetricSpace X] : (∀ E : Set X, (IsOpen E ↔ E = interior E) ∧ (IsOpen E ↔ ∀ x ∈ E, ∃ r : ℝ, 0 < r ∧ Metric.ball x r ⊆ E)) ∧ (∀ E : Set X, (IsClosed E ↔ ∀ x, IsAdherentPoint E x → x ∈ E) ∧ (IsClosed E ↔ ∀ u : ℕ → X, (∀ n, u n ∈ E) → ∀ x, Filter.Tendsto u Filter.atTop (nhds x) → x ∈ E)) ∧ (∀ x0 : X, ∀ r : ℝ, 0 < r → IsOpen (Metric.ball x0 r) ∧ IsClosed (Metric.closedBall x0 r)) ∧ (∀ x0 : X, IsClosed ({x0} : Set X)) ∧ (∀ E : Set X, IsOpen E ↔ IsClosed (Eᶜ)) ∧ (∀ n : ℕ, ∀ E : Fin n → Set X, (∀ i, IsOpen (E i)) → IsOpen (⋂ i, E i)) ∧ (∀ n : ℕ, ∀ F : Fin n → Set X, (∀ i, IsClosed (F i)) → IsClosed (⋃ i, F i)) ∧ (∀ {I : Type*} (E : I → Set X), (∀ i, IsOpen (E i)) → IsOpen (⋃ i, E i)) ∧ (∀ {I : Type*} (F : I → Set X), (∀ i, IsClosed (F i)) → IsClosed (⋂ i, F i)) ∧ (∀ E : Set X, IsOpen (interior E) ∧ interior E ⊆ E ∧ (∀ V, IsOpen V → V ⊆ E → V ⊆ interior E) ∧ IsClosed (closure E) ∧ E ⊆ closure E ∧ (∀ K, IsClosed K → E ⊆ K → closure E ⊆ K))

Lean source

Basic properties of open and closed sets in a metric space (Proposition 1.17).

lemma proposition_1_17' {X : Type*} [MetricSpace X] : (∀ E : Set X, (IsOpen E ↔ E = interior E) ∧ (IsOpen E ↔ ∀ x ∈ E, ∃ r : ℝ, 0 < r ∧ Metric.ball x r ⊆ E)) ∧ (∀ E : Set X, (IsClosed E ↔ ∀ x, IsAdherentPoint E x → x ∈ E) ∧ (IsClosed E ↔ ∀ u : ℕ → X, (∀ n, u n ∈ E) → ∀ x, Filter.Tendsto u Filter.atTop (nhds x) → x ∈ E)) ∧ (∀ x0 : X, ∀ r : ℝ, 0 < r → IsOpen (Metric.ball x0 r) ∧ IsClosed (Metric.closedBall x0 r)) ∧ (∀ x0 : X, IsClosed ({x0} : Set X)) ∧ (∀ E : Set X, IsOpen E ↔ IsClosed (Eᶜ)) ∧ (∀ n : ℕ, ∀ E : Fin n → Set X, (∀ i, IsOpen (E i)) → IsOpen (⋂ i, E i)) ∧ (∀ n : ℕ, ∀ F : Fin n → Set X, (∀ i, IsClosed (F i)) → IsClosed (⋃ i, F i)) ∧ (∀ {I : Type*} (E : I → Set X), (∀ i, IsOpen (E i)) → IsOpen (⋃ i, E i)) ∧ (∀ {I : Type*} (F : I → Set X), (∀ i, IsClosed (F i)) → IsClosed (⋂ i, F i)) ∧ (∀ E : Set X, IsOpen (interior E) ∧ interior E ⊆ E ∧ (∀ V, IsOpen V → V ⊆ E → V ⊆ interior E) ∧ IsClosed (closure E) ∧ E ⊆ closure E ∧ (∀ K, IsClosed K → E ⊆ K → closure E ⊆ K))

Lean source

Proposition 1.35 (Open and closed are not complementary notions): Let (X,d) be a metric space. (1) There exist subsets of X that are both open and closed (e.g., X itself and ∅). (2) There may exist subsets of X that are neither open nor closed. (3) A subset E ⊆ X is open iff its complement X \ E is closed. In particular, knowing that a set is not open does not imply that it is closed, and vice versa.

lemma proposition_1_35 : (∀ {X : Type*} [MetricSpace X], IsOpen (Set.univ : Set X) ∧ IsClosed (Set.univ : Set X) ∧ IsOpen (∅ : Set X) ∧ IsClosed (∅ : Set X)) ∧ (∃ (X : Type*), ∃ h : MetricSpace X, ∃ E : Set X, ¬ IsOpen E ∧ ¬ IsClosed E) ∧ (∀ {X : Type*} [MetricSpace X], ∀ E : Set X, IsOpen E ↔ IsClosed (Eᶜ))

Lean source

Helper for Proposition 1.12: 1 < 2 in ℝ.

lemma helperForProposition_1_12_one_lt_two : (1 : ℝ) < 2

Lean source

Helper for Proposition 1.12: interior of Ico is Ioo.

lemma helperForProposition_1_12_interior_Ico : interior (Set.Ico (1 : ℝ) 2) = Set.Ioo (1 : ℝ) 2

Lean source

Helper for Proposition 1.12: interior of the complement of Ico.

lemma helperForProposition_1_12_interior_compl_Ico : interior ((Set.Ico (1 : ℝ) 2)ᶜ) = Set.Iio (1 : ℝ) ∪ Set.Ioi (2 : ℝ)

Lean source

Helper for Proposition 1.12: frontier of Ico is {1,2}.

lemma helperForProposition_1_12_frontier_Ico : frontier (Set.Ico (1 : ℝ) 2) = ({1, 2} : Set ℝ)

Lean source

Helper for Proposition 1.13: a singleton contains a positive-radius ball.

lemma helperForProposition_1_13_exists_ball_subset_singleton {X : Type*} [MetricSpace X] [DiscreteTopology X] (x : X) : ∃ r : ℝ, 0 < r ∧ Metric.ball x r ⊆ ({x} : Set X)

Lean source

Helper for Proposition 1.13: points of E are interior points in the discrete topology.

lemma helperForProposition_1_13_mem_interiorSet_of_mem {X : Type*} [MetricSpace X] [DiscreteTopology X] {E : Set X} {x : X} : x ∈ E → x ∈ interiorSet E

Lean source

Helper for Proposition 1.13: points of Eᶜ are exterior points in the discrete topology.

lemma helperForProposition_1_13_mem_exteriorSet_of_mem_compl {X : Type*} [MetricSpace X] [DiscreteTopology X] {E : Set X} {x : X} : x ∈ Eᶜ → x ∈ exteriorSet E

Lean source

Helper for Proposition 1.13: the boundary set is empty in the discrete topology.

lemma helperForProposition_1_13_boundarySet_eq_empty {X : Type*} [MetricSpace X] [DiscreteTopology X] (E : Set X) : boundarySet E = (∅ : Set X)

Lean source

Helper for Proposition 1.14: adherent points coincide with closure membership.

lemma helperForProposition_1_14_isAdherentPoint_iff_mem_closure {X : Type*} [MetricSpace X] (E : Set X) (x0 : X) : IsAdherentPoint E x0 ↔ x0 ∈ closure E

Lean source

Helper for Proposition 1.14: adherent points are interior or boundary points.

lemma helperForProposition_1_14_adherent_iff_interior_or_boundary {X : Type*} [MetricSpace X] (E : Set X) (x0 : X) : IsAdherentPoint E x0 ↔ IsInteriorPoint E x0 ∨ IsBoundaryPoint E x0

Lean source

Helper for Proposition 1.14: adherent points admit convergent sequences from the set.

lemma helperForProposition_1_14_adherent_iff_exists_seq_tendsto {X : Type*} [MetricSpace X] (E : Set X) (x0 : X) : IsAdherentPoint E x0 ↔ ∃ u : ℕ → X, (∀ n, u n ∈ E) ∧ Filter.Tendsto u Filter.atTop (nhds x0)

Lean source

Helper for Theorem 1.3: the closure set is the complement of the exterior set.

lemma helperForTheorem_1_3_closureSet_eq_compl_exteriorSet {X : Type*} [MetricSpace X] (E : Set X) : closureSet E = (exteriorSet E)ᶜ

Lean source

Helper for Theorem 1.3: interior union boundary equals the complement of the exterior set.

lemma helperForTheorem_1_3_interiorSet_union_boundarySet_eq_compl_exteriorSet {X : Type*} [MetricSpace X] (E : Set X) : interiorSet E ∪ boundarySet E = (exteriorSet E)ᶜ

Lean source

Helper for Proposition 1.17: the two characterizations of open sets in part (a).

lemma helperForProposition_1_17_part_a {X : Type*} [MetricSpace X] (E : Set X) : (IsOpen E ↔ E = interior E) ∧ (IsOpen E ↔ ∀ x ∈ E, ∃ r : ℝ, 0 < r ∧ Metric.ball x r ⊆ E)

Lean source

Helper for Proposition 1.17: closed sets via adherent points and sequential limits.

lemma helperForProposition_1_17_part_b {X : Type*} [MetricSpace X] (E : Set X) : (IsClosed E ↔ ∀ x, IsAdherentPoint E x → x ∈ E) ∧ (IsClosed E ↔ ∀ u : ℕ → X, (∀ n, u n ∈ E) → ∀ x, Filter.Tendsto u Filter.atTop (nhds x) → x ∈ E)

Lean source

Helper for Proposition 1.17: parts (c)-(g) on balls, complements, and unions/intersections.

lemma helperForProposition_1_17_parts_c_to_g {X : Type*} [MetricSpace X] : (∀ x0 : X, ∀ r : ℝ, 0 < r → IsOpen (Metric.ball x0 r) ∧ IsClosed (Metric.closedBall x0 r)) ∧ (∀ x0 : X, IsClosed ({x0} : Set X)) ∧ (∀ E : Set X, IsOpen E ↔ IsClosed (Eᶜ)) ∧ (∀ n : ℕ, ∀ E : Fin n → Set X, (∀ i, IsOpen (E i)) → IsOpen (⋂ i, E i)) ∧ (∀ n : ℕ, ∀ F : Fin n → Set X, (∀ i, IsClosed (F i)) → IsClosed (⋃ i, F i)) ∧ (∀ {I : Type*} (E : I → Set X), (∀ i, IsOpen (E i)) → IsOpen (⋃ i, E i)) ∧ (∀ {I : Type*} (F : I → Set X), (∀ i, IsClosed (F i)) → IsClosed (⋂ i, F i))

Lean source

Helper for Proposition 1.17: interior is maximal open, closure is minimal closed.

lemma helperForProposition_1_17_part_h {X : Type*} [MetricSpace X] (E : Set X) : IsOpen (interior E) ∧ interior E ⊆ E ∧ (∀ V, IsOpen V → V ⊆ E → V ⊆ interior E) ∧ IsClosed (closure E) ∧ E ⊆ closure E ∧ (∀ K, IsClosed K → E ⊆ K → closure E ⊆ K)

Lean source

Helper for Proposition 1.35: Ico (1,2) is not open in ℝ.

lemma real_Ico_one_two_not_isOpen : ¬ IsOpen (Set.Ico (1 : ℝ) 2)

Lean source

Helper for Proposition 1.35: Ico (1,2) is not closed in ℝ.

lemma real_Ico_one_two_not_isClosed : ¬ IsClosed (Set.Ico (1 : ℝ) 2)

Lean source

Helper for Proposition 1.35: the lifted Ico (1,2) is not open.

lemma ulift_Ico_one_two_not_isOpen : ¬ IsOpen ((ULift.down : ULift ℝ → ℝ) ⁻¹' Set.Ico (1 : ℝ) 2)

Lean source

Helper for Proposition 1.35: the lifted Ico (1,2) is not closed.

lemma ulift_Ico_one_two_not_isClosed : ¬ IsClosed ((ULift.down : ULift ℝ → ℝ) ⁻¹' Set.Ico (1 : ℝ) 2)

1.3 — Relative Topology

Lean authors: Zichen Wang, Wanli Ma, Ziyu Wang, Zaiwen Wen.

Source header

Definition 1.15 (Relative topology). Let (X,d) be a metric space and let Y be a subset of X. The induced metric subspace on Y is the metric space (Y, d restricted to Y x Y). A subset E of Y is relatively open in Y if for every y in E there exists r > 0 such that {z in Y | dist y z < r} is contained in E. A subset E of Y is relatively closed in Y if it is closed in the induced metric space, equivalently if Y \ E is relatively open in Y. Used in Proposition 1.18.

variable {X : Type*} [MetricSpace X] abbrev inducedMetricSubspace (Y : Set X) := {x : X // Y x}

Lean source

A subset E of Y is relatively open in Y if it is open in the metric subspace induced on Y. Used in Proposition 1.18.

variable {X : Type*} [MetricSpace X] def IsRelOpen (Y E : Set X) : Prop := And (Set.Subset E Y) (IsOpen (Set.preimage (Subtype.val : {x // Y x} -> X) E))

Lean source

A subset E of Y is relatively closed in Y if it is closed in the metric subspace induced on Y. Used in Proposition 1.18.

variable {X : Type*} [MetricSpace X] def IsRelClosed (Y E : Set X) : Prop := And (Set.Subset E Y) (IsClosed (Set.preimage (Subtype.val : {x // Y x} -> X) E))

Lean source

Proposition 1.18. Let (X,d) be a metric space, let Y be a subset of X, and let E be a subset of Y. (a) E is open in the subspace metric space on Y iff there exists an open set V in X such that E = Set.inter V Y. (b) E is closed in the subspace metric space on Y iff there exists a closed set K in X such that E = Set.inter K Y.

variable {X : Type*} [MetricSpace X] theorem relOpen_relClosed_iff_eq_inter {Y E : Set X} : (IsRelOpen Y E ↔ ∃ V : Set X, IsOpen V ∧ E = Set.inter V Y) ∧ (IsRelClosed Y E ↔ ∃ K : Set X, IsClosed K ∧ E = Set.inter K Y)

Lean source

Part (a) for Proposition 1.18: relative openness in Y iff E = Set.inter V Y for some open V in X.

variable {X : Type*} [MetricSpace X] lemma isRelOpen_iff_eq_inter {Y E : Set X} : IsRelOpen Y E ↔ ∃ V : Set X, IsOpen V ∧ E = Set.inter V Y

Lean source

Part (b): relative closedness in Y iff E = Set.inter K Y for some closed K in X. Used in Proposition 1.18.

variable {X : Type*} [MetricSpace X] lemma isRelClosed_iff_eq_inter {Y E : Set X} : IsRelClosed Y E ↔ ∃ K : Set X, IsClosed K ∧ E = Set.inter K Y

Lean source

Helper for Proposition 1.18: preimage of an intersection with Y under the subtype inclusion equals the preimage of the first set.

variable {X : Type*} [MetricSpace X] lemma helperForProposition_1_18_preimage_inter_eq {Y V : Set X} : Set.preimage (Subtype.val : {x // Y x} → X) (Set.inter V Y) = Set.preimage (Subtype.val : {x // Y x} → X) V

Lean source

Helper for Proposition 1.18: recover E = V ∩ Y from equality of preimages.

variable {X : Type*} [MetricSpace X] lemma helperForProposition_1_18_eq_inter_of_preimage_eq {Y E V : Set X} (hEY : E ⊆ Y) (hpre : Set.preimage (Subtype.val : {x // Y x} → X) V = Set.preimage (Subtype.val : {x // Y x} → X) E) : E = Set.inter V Y

1.4 — Cauchy Sequences and Complete Metric Spaces — Part 1

Lean authors: Zichen Wang, Wanli Ma, Ziyu Wang, Zaiwen Wen.

Source header

Definition 1.16 (Subsequences): Let (X,d) be a metric space, let (x^(n))_{n=m}^infty be a sequence in X, and let (n_j) be a strictly increasing sequence of integers with n_j >= m (equivalently, m <= n_1 < n_2 < n_3 < ...). The sequence (x^(n_j))_{j=1}^infty is called a subsequence of (x^(n))_{n=m}^infty.

open Filter def IsSubsequenceFrom {X : Type*} [MetricSpace X] (x : Nat -> X) (m : Nat) (y : Nat -> X) : Prop := Exists fun n : Nat -> Nat => And (StrictMono n) (And (forall j, m <= n j) (y = fun j => x (n j)))

Lean source

A strictly increasing subsequence of a convergent sequence has the same limit.

open Filter lemma tendsto_subseq_of_tendsto {X : Type*} [MetricSpace X] (x : ℕ → X) {x0 : X} (hx : Tendsto x atTop (nhds x0)) {n : ℕ → ℕ} (hn : StrictMono n) : Tendsto (fun j => x (n j)) atTop (nhds x0)

Lean source

Definition 1.17 (Limit point of a sequence): Let (X,d) be a metric space, let m be a starting index, and let (x^(n))_{n=m}^infty be a sequence in X. A point L ∈ X is called a limit point of (x^(n))_{n=m}^infty if for every N ≥ m and every ε > 0 there exists an integer n ≥ N such that d(x^(n), L) ≤ ε.

open Filter def IsLimitPointSeqFrom {X : Type*} [MetricSpace X] (x : Nat → X) (m : Nat) (L : X) : Prop := ∀ N ≥ m, ∀ ε > 0, ∃ n ≥ N, dist (x n) L ≤ ε

Lean source

A point is a limit point of a sequence from index m if every tail gets within any ε > 0.

open Filter lemma isLimitPointSeqFrom_iff {X : Type*} [MetricSpace X] (x : Nat → X) (m : Nat) (L : X) : IsLimitPointSeqFrom x m L ↔ ∀ N ≥ m, ∀ ε > 0, ∃ n ≥ N, dist (x n) L ≤ ε

Lean source

Definition 1.18 (Cauchy sequence): Let (X,d) be a metric space, let m ∈ ℕ, and let (x^(n))_{n=m}^∞ be a sequence in X. The sequence is called a Cauchy sequence if for every ε > 0 there exists an integer N ≥ m such that d(x^(j), x^(k)) < ε for all j, k ≥ N.

open Filter def IsCauchySeqFrom {X : Type*} [MetricSpace X] (x : Nat → X) (m : Nat) : Prop := ∀ ε > 0, ∃ N ≥ m, ∀ j ≥ N, ∀ k ≥ N, dist (x j) (x k) < ε

Lean source

A Cauchy sequence from index m gives a CauchySeq for the shifted tail.

open Filter lemma isCauchySeqFrom_imp_cauchySeq_tail {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) : IsCauchySeqFrom x m → CauchySeq (fun n => x (n + m))

Lean source

A CauchySeq of the shifted tail yields a Cauchy sequence from index m.

open Filter lemma cauchySeq_tail_imp_isCauchySeqFrom {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) : CauchySeq (fun n => x (n + m)) → IsCauchySeqFrom x m

Lean source

A sequence is Cauchy from index m iff its shifted tail is a CauchySeq.

open Filter lemma isCauchySeqFrom_iff_cauchySeq_tail {X : Type*} [MetricSpace X] (x : Nat → X) (m : Nat) : IsCauchySeqFrom x m ↔ CauchySeq (fun n => x (n + m))

Lean source

A point L is a limit point of the tail iff some strictly increasing subsequence has dist to L tending to 0.

open Filter lemma limitPointSeqFrom_iff_subseq_tendsto {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) (L : X) : (∀ ε > 0, ∀ N ≥ m, ∃ n ≥ N, dist (x n) L < ε) ↔ ∃ n : ℕ → ℕ, StrictMono n ∧ m ≤ n 0 ∧ Tendsto (fun j => dist (x (n j)) L) atTop (nhds 0)

Lean source

Lemma 1.3 (Convergent sequences are Cauchy): Let (X,d) be a metric space and let (x^(n))_{n=m}^∞ be a sequence in X such that x^(n) → x0 ∈ X as n → ∞. Then (x^(n))_{n=m}^∞ is a Cauchy sequence, i.e., for every ε > 0 there exists N ≥ m such that for all n, n' ≥ N one has d(x^(n), x^(n')) < ε. A convergent tail of a sequence is Cauchy from its starting index.

open Filter lemma convergentSeqFrom_isCauchy {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) {x0 : X} (hx : Tendsto (fun n => x (n + m)) atTop (nhds x0)) : IsCauchySeqFrom x m

Lean source

Lemma 1.4: Let (X,d) be a metric space and let (x^{(n)})_{n=m}^∞ be a Cauchy sequence in X. Suppose there exists a subsequence (x^{(n_j)}) and a point x0 ∈ X such that x^{(n_j)} → x0 as j → ∞. Then x^{(n)} → x0 as n → ∞.

open Filter lemma tendsto_of_cauchySeqFrom_of_subseq_tendsto {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) {x0 : X} (hx : IsCauchySeqFrom x m) {n : ℕ → ℕ} (hn : StrictMono n) (hnm : ∀ j, m ≤ n j) (hsub : Tendsto (fun j => x (n j)) atTop (nhds x0)) : Tendsto (fun k => x (k + m)) atTop (nhds x0)

Lean source

A subsequence of a Cauchy tail is Cauchy (from index 0).

open Filter lemma cauchySeqFrom_subseq {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) (y : ℕ → X) (hx : IsCauchySeqFrom x m) (hsub : IsSubsequenceFrom x m y) : IsCauchySeqFrom y 0

Lean source

A metric space is complete if every Cauchy sequence converges.

open Filter def IsCompleteMetricSpace (X : Type*) [MetricSpace X] : Prop := ∀ x : ℕ → X, CauchySeq x → ∃ L : X, Tendsto x atTop (nhds L)

Lean source

The book's Cauchy-sequence definition of completeness is equivalent to CompleteSpace.

open Filter theorem isCompleteMetricSpace_iff_completeSpace (X : Type*) [MetricSpace X] : IsCompleteMetricSpace X ↔ CompleteSpace X

Lean source

Proposition 1.20: Let (X,d) be a metric space and let Y ⊆ X be equipped with the subspace metric d|_{Y×Y}. (a) If (Y, d|_{Y×Y}) is complete, then Y is closed in X. (b) If (X,d) is complete and Y is closed in X, then (Y, d|_{Y×Y}) is complete.

open Filter theorem completeSpace_subtype_closed {X : Type*} [MetricSpace X] {Y : Set X} : (CompleteSpace Y → IsClosed Y) ∧ (CompleteSpace X → IsClosed Y → CompleteSpace Y)

Lean source

Proposition 1.21: Let (X,d) be a metric space, let m ∈ ℕ, and let (x^(n))_{n=m}^∞ be a sequence in X. Let L ∈ X. Assume that L is a limit point of the sequence, i.e., for every ε > 0 and every N ≥ m there exists n ≥ N such that d(x^(n), L) < ε. Then L is an adherent point of the set A := {x^(n) : n ≥ m}, i.e., for every ε > 0 there exists a ∈ A such that d(a, L) < ε. A limit point of a tail of a sequence is an adherent point of the tail set.

open Filter lemma limitPointSeqFrom_adherent_point {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) (L : X) (hL : ∀ ε > 0, ∀ N ≥ m, ∃ n ≥ N, dist (x n) L < ε) : ∀ ε > 0, ∃ a ∈ {a | ∃ n ≥ m, a = x n}, dist a L < ε

Lean source

Proposition 1.22: Let (X,d) be a metric space, and let (x_n)_{n∈ℕ} be a Cauchy sequence in X. If x_n → x and x_n → y for some x,y ∈ X, then x = y. Equivalently, a Cauchy sequence in a metric space has at most one limit.

open Filter theorem cauchySeq_limit_unique {X : Type*} [MetricSpace X] (x : ℕ → X) {x0 y0 : X} (hx : CauchySeq x) (hx' : Tendsto x atTop (nhds x0)) (hy' : Tendsto x atTop (nhds y0)) : x0 = y0

Lean source

A Cauchy sequence in a metric space has at most one limit.

open Filter lemma cauchySeq_limit_unique' {X : Type*} [MetricSpace X] (x : ℕ → X) {x0 y0 : X} (hx : CauchySeq x) (hx' : Tendsto x atTop (nhds x0)) (hy' : Tendsto x atTop (nhds y0)) : x0 = y0

Lean source

Definition 1.20 (Completion via formal limits): Let (X,d) be a metric space. (1) For every Cauchy sequence (x_n)_{n=1}^∞ in X, introduce a formal symbol LIM_{n→∞} x_n. (2) Define an equivalence relation ~ on such formal symbols by LIM x_n ~ LIM y_n iff lim_{n→∞} d(x_n,y_n) = 0. (3) Define X̄ to be the set of equivalence classes modulo ~. (4) Define d_{X̄} : X̄ × X̄ → [0,∞) by d_{X̄}(LIM x_n, LIM y_n) := lim_{n→∞} d(x_n,y_n), where representatives are chosen from the corresponding equivalence classes.

open Filter universe u def FormalLimit (X : Type u) [MetricSpace X] : Type u := { x : ℕ → X // CauchySeq x }

Lean source

The relation identifying two formal limits when their pointwise distance tends to 0.

open Filter universe u def FormalLimitRel (X : Type u) [MetricSpace X] (x y : FormalLimit X) : Prop := Tendsto (fun n => dist (x.1 n) (y.1 n)) atTop (nhds 0)

Lean source

The formal-limit relation is an equivalence relation.

open Filter universe u lemma formalLimitRel_equivalence (X : Type u) [MetricSpace X] : Equivalence (FormalLimitRel (X := X))

Lean source

Proposition 1.24: Let (X,d) be a metric space. Define X̄ as the set of equivalence classes of Cauchy sequences in X, where two Cauchy sequences (x_n) and (y_n) are equivalent if d(x_n,y_n) → 0 as n → ∞. For classes [(x_n)], [(y_n)] ∈ X̄, define d_{X̄}([(x_n)],[(y_n)]) := lim_{n→∞} d(x_n,y_n). Then d_{X̄} is well-defined and (X̄, d_{X̄}) is a metric space.

open Filter universe u theorem completionViaFormalLimitsDist_wellDefined_and_metricSpace (X : Type u) [MetricSpace X] : (∀ x y x' y' : FormalLimit X, FormalLimitRel (X := X) x x' → FormalLimitRel (X := X) y y' → completionViaFormalLimitsDist X (Quotient.mk (FormalLimitSetoid (X := X)) x) (Quotient.mk (FormalLimitSetoid (X := X)) y) = completionViaFormalLimitsDist X (Quotient.mk (FormalLimitSetoid (X := X)) x') (Quotient.mk (FormalLimitSetoid (X := X)) y')) ∧ Nonempty (MetricSpace (CompletionViaFormalLimits X))

Lean source

Helper for Proposition 1.19: the bound 1/(k+1) is always positive.

open Filter lemma helperForProposition_1_19_one_div_pos (k : ℕ) : 0 < (1 : ℝ) / ((k : ℝ) + 1)

Lean source

Helper for Proposition 1.19: extend the tail condition to any starting index.

open Filter lemma helperForProposition_1_19_extend_tail {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) (L : X) (h : ∀ ε > 0, ∀ N ≥ m, ∃ n ≥ N, dist (x n) L < ε) : ∀ ε > 0, ∀ N, ∃ n ≥ N, dist (x n) L < ε

Lean source

Helper for Proposition 1.19: a squeeze argument for the bound 1/(k+1).

open Filter lemma helperForProposition_1_19_tendsto_of_one_div_bound (f : ℕ → ℝ) (hf0 : ∀ k, 0 ≤ f k) (hf : ∀ k, f k ≤ (1 : ℝ) / ((k : ℝ) + 1)) : Tendsto f atTop (nhds 0)

Lean source

Helper for Lemma 1.3: extend a tail distance bound to any index beyond N0 + m.

open Filter lemma helperForLemma_1_3_dist_lt_of_tail_dist_lt {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) (x0 : X) {N0 j : ℕ} {r : ℝ} (h : ∀ n ≥ N0, dist (x (n + m)) x0 < r) (hj : N0 + m ≤ j) : dist (x j) x0 < r

Lean source

Helper for Lemma 1.4: a strictly increasing subsequence is eventually beyond any index.

open Filter lemma helperForLemma_1_4_eventually_ge_subseqIndex {n : ℕ → ℕ} (hn : StrictMono n) (N : ℕ) : ∃ J, ∀ j ≥ J, N ≤ n j

Lean source

Helper for Lemma 1.4: pick a subsequence index beyond N that is ε-close to x0.

open Filter lemma helperForLemma_1_4_choose_subseqIndex_close {X : Type*} [MetricSpace X] (x : ℕ → X) {x0 : X} {n : ℕ → ℕ} (hn : StrictMono n) (hsub : Tendsto (fun j => x (n j)) atTop (nhds x0)) {N : ℕ} {ε : ℝ} (hε : 0 < ε) : ∃ j, N ≤ n j ∧ dist (x (n j)) x0 < ε

Lean source

Helper for Lemma 1.5: a strictly increasing index map dominates any lower bound.

open Filter lemma helperForLemma_1_5_le_apply_of_le {n : ℕ → ℕ} (hn : StrictMono n) {N j : ℕ} (hNj : N ≤ j) : N ≤ n j

Lean source

Helper for Proposition 1.21: specialize the limit-point hypothesis at N = m.

open Filter lemma helperForProposition_1_21_exists_index_ge_m {X : Type*} [MetricSpace X] (x : ℕ → X) (m : ℕ) (L : X) (hL : ∀ ε > 0, ∀ N ≥ m, ∃ n ≥ N, dist (x n) L < ε) : ∀ ε > 0, ∃ n ≥ m, dist (x n) L < ε

Lean source

Helper for Proposition 1.21: an index n ≥ m gives membership in the tail set.

open Filter lemma helperForProposition_1_21_mem_tail_set {X : Type*} (x : ℕ → X) (m n : ℕ) (hn : n ≥ m) : x n ∈ {a | ∃ n ≥ m, a = x n}

Lean source

Helper for Proposition 1.23: reflexivity of the formal-limit relation.

open Filter universe u lemma helperForProposition_1_23_refl (X : Type u) [MetricSpace X] (x : FormalLimit X) : FormalLimitRel (X := X) x x

Lean source

Helper for Proposition 1.23: symmetry of the formal-limit relation.

open Filter universe u lemma helperForProposition_1_23_symm (X : Type u) [MetricSpace X] (x y : FormalLimit X) : FormalLimitRel (X := X) x y → FormalLimitRel (X := X) y x

Lean source

Helper for Proposition 1.23: transitivity of the formal-limit relation.

open Filter universe u lemma helperForProposition_1_23_trans (X : Type u) [MetricSpace X] (x y z : FormalLimit X) : FormalLimitRel (X := X) x y → FormalLimitRel (X := X) y z → FormalLimitRel (X := X) x z

Lean source

Helper for Proposition 1.24: the setoid induced by the formal-limit relation.

open Filter universe u def FormalLimitSetoid (X : Type u) [MetricSpace X] : Setoid (FormalLimit X) := { r := FormalLimitRel (X := X), iseqv := formalLimitRel_equivalence (X := X) }

Lean source

Helper for Proposition 1.24: the completion via formal limits as a quotient of formal symbols.

open Filter universe u def CompletionViaFormalLimits (X : Type u) [MetricSpace X] : Type u := Quotient (FormalLimitSetoid (X := X))

Lean source

Helper for Proposition 1.24: the pointwise distance between two Cauchy representatives is itself a Cauchy sequence.

open Filter universe u lemma helperForProposition_1_24_distSeq_cauchy (X : Type u) [MetricSpace X] (x y : FormalLimit X) : CauchySeq (fun n : ℕ => dist (x.1 n) (y.1 n))

Lean source

Helper for Proposition 1.24: define the representative-level distance via limUnder.

open Filter universe u noncomputable def helperForProposition_1_24_formalLimitDist (X : Type u) [MetricSpace X] (x y : FormalLimit X) : ℝ := limUnder atTop (fun n : ℕ => dist (x.1 n) (y.1 n))

Lean source

Helper for Proposition 1.24: the representative-level distance is the limit of pointwise distances.

open Filter universe u lemma helperForProposition_1_24_formalLimitDist_tendsto (X : Type u) [MetricSpace X] (x y : FormalLimit X) : Tendsto (fun n : ℕ => dist (x.1 n) (y.1 n)) atTop (nhds (helperForProposition_1_24_formalLimitDist (X := X) x y))

Lean source

Helper for Proposition 1.24: the representative-level distance respects the formal-limit equivalence relation.

open Filter universe u lemma helperForProposition_1_24_formalLimitDist_congr (X : Type u) [MetricSpace X] (x y x' y' : FormalLimit X) : FormalLimitRel (X := X) x x' → FormalLimitRel (X := X) y y' → helperForProposition_1_24_formalLimitDist (X := X) x y = helperForProposition_1_24_formalLimitDist (X := X) x' y'

Lean source

Helper for Proposition 1.24: the distance on the formal completion, defined by limits of distances.

open Filter universe u noncomputable def completionViaFormalLimitsDist (X : Type u) [MetricSpace X] : CompletionViaFormalLimits X → CompletionViaFormalLimits X → ℝ := fun qx qy => Quotient.liftOn₂ qx qy (fun x y => helperForProposition_1_24_formalLimitDist (X := X) x y) (helperForProposition_1_24_formalLimitDist_congr (X := X))

Lean source

Helper for Proposition 1.24: the coerced sequence of a formal limit is Cauchy in the completion.

open Filter universe u lemma helperForProposition_1_24_formalLimit_coe_cauchy (X : Type u) [MetricSpace X] (x : FormalLimit X) : CauchySeq (fun n => (x.1 n : UniformSpace.Completion X))

Lean source

Helper for Proposition 1.24: send a formal limit to the limit of its coerced sequence.

open Filter universe u noncomputable def helperForProposition_1_24_formalLimit_to_uniformCompletion (X : Type u) [MetricSpace X] (x : FormalLimit X) : UniformSpace.Completion X := let hCauchy : CauchySeq (fun n => (x.1 n : UniformSpace.Completion X)) := helperForProposition_1_24_formalLimit_coe_cauchy (X := X) x let _ : Nonempty (UniformSpace.Completion X) := hCauchy.1.nonempty limUnder atTop (fun n => (x.1 n : UniformSpace.Completion X))

Lean source

Helper for Proposition 1.24: the coerced sequence converges to its chosen completion point.

open Filter universe u lemma helperForProposition_1_24_formalLimit_to_uniformCompletion_tendsto (X : Type u) [MetricSpace X] (x : FormalLimit X) : Tendsto (fun n => (x.1 n : UniformSpace.Completion X)) atTop (nhds (helperForProposition_1_24_formalLimit_to_uniformCompletion (X := X) x))

Lean source

Helper for Proposition 1.24: equivalent formal limits map to the same completion point.

open Filter universe u lemma helperForProposition_1_24_formalLimit_to_uniformCompletion_congr (X : Type u) [MetricSpace X] (x y : FormalLimit X) : FormalLimitRel (X := X) x y → helperForProposition_1_24_formalLimit_to_uniformCompletion (X := X) x = helperForProposition_1_24_formalLimit_to_uniformCompletion (X := X) y

Lean source

Helper for Proposition 1.24: the map from the formal completion to the uniform completion.

open Filter universe u noncomputable def helperForProposition_1_24_completion_to_uniformCompletion (X : Type u) [MetricSpace X] : CompletionViaFormalLimits X → UniformSpace.Completion X := Quotient.lift (helperForProposition_1_24_formalLimit_to_uniformCompletion (X := X)) (helperForProposition_1_24_formalLimit_to_uniformCompletion_congr (X := X))

Lean source

Helper for Proposition 1.24: powers of 1/2 tend to 0.

open Filter universe u lemma helperForProposition_1_24_tendsto_pow_one_half : Tendsto (fun n : ℕ => (1 / 2 : ℝ) ^ n) atTop (nhds (0 : ℝ))

Lean source

Helper for Proposition 1.24: powers of 1/2 are eventually below any positive threshold.

open Filter universe u lemma helperForProposition_1_24_pow_eventually_lt (ε : ℝ) (hε : 0 < ε) : ∃ N, ∀ n ≥ N, (1 / 2 : ℝ) ^ n < ε

Lean source

Helper for Proposition 1.24: the map to the uniform completion is surjective.

open Filter universe u lemma helperForProposition_1_24_completion_to_uniformCompletion_surjective (X : Type u) [MetricSpace X] : Function.Surjective (helperForProposition_1_24_completion_to_uniformCompletion (X := X))

Lean source

Helper for Proposition 1.24: the map to the uniform completion is injective.

open Filter universe u lemma helperForProposition_1_24_completion_to_uniformCompletion_injective (X : Type u) [MetricSpace X] : Function.Injective (helperForProposition_1_24_completion_to_uniformCompletion (X := X))

Lean source

Helper for Proposition 1.24: the formal-limit completion is (noncanonically) equivalent to the uniform completion.

open Filter universe u theorem completionViaFormalLimits_equiv_uniformCompletion (X : Type u) [MetricSpace X] : Nonempty (CompletionViaFormalLimits X ≃ UniformSpace.Completion X)

Lean source

Helper for Proposition 1.24: dist vanishes on identical classes.

open Filter universe u lemma helperForProposition_1_24_completionDist_self (X : Type u) [MetricSpace X] : ∀ q : CompletionViaFormalLimits X, completionViaFormalLimitsDist X q q = 0

Lean source

Helper for Proposition 1.24: the formal-limit distance is symmetric.

open Filter universe u lemma helperForProposition_1_24_completionDist_comm (X : Type u) [MetricSpace X] : ∀ qx qy : CompletionViaFormalLimits X, completionViaFormalLimitsDist X qx qy = completionViaFormalLimitsDist X qy qx

Lean source

Helper for Proposition 1.24: the formal-limit distance satisfies the triangle inequality.

open Filter universe u lemma helperForProposition_1_24_completionDist_triangle (X : Type u) [MetricSpace X] : ∀ qx qy qz : CompletionViaFormalLimits X, completionViaFormalLimitsDist X qx qz ≤ completionViaFormalLimitsDist X qx qy + completionViaFormalLimitsDist X qy qz

Lean source

Helper for Proposition 1.24: distance zero gives equality in the quotient.

open Filter universe u lemma helperForProposition_1_24_completionDist_eq_zero (X : Type u) [MetricSpace X] : ∀ {qx qy : CompletionViaFormalLimits X}, completionViaFormalLimitsDist X qx qy = 0 → qx = qy

Lean source

Helper for Proposition 1.24: the edist field is ENNReal.ofReal of the distance.

open Filter universe u lemma helperForProposition_1_24_completion_edist_dist (X : Type u) [MetricSpace X] : ∀ x y : CompletionViaFormalLimits X, (fun a b => ENNReal.ofReal (completionViaFormalLimitsDist X a b)) x y = ENNReal.ofReal (completionViaFormalLimitsDist X x y)

Lean source

Helper for Proposition 1.24: the pseudo-metric structure on the formal completion.

open Filter universe u noncomputable def helperForProposition_1_24_completionPseudoMetricSpace (X : Type u) [MetricSpace X] : PseudoMetricSpace (CompletionViaFormalLimits X)

Lean source

Helper for Proposition 1.24: the formal-limit completion carries a metric-space structure.

open Filter universe u noncomputable def helperForProposition_1_24_completionMetricSpace (X : Type u) [MetricSpace X] : MetricSpace (CompletionViaFormalLimits X) := MetricSpace.mk (toPseudoMetricSpace := helperForProposition_1_24_completionPseudoMetricSpace (X := X)) (helperForProposition_1_24_completionDist_eq_zero (X := X))

Lean source

Helper for Proposition 1.24: the formal-limit distance does not depend on the chosen Cauchy representatives.

open Filter universe u lemma completionViaFormalLimitsDist_wellDefined (X : Type u) [MetricSpace X] : ∀ x y x' y' : FormalLimit X, FormalLimitRel (X := X) x x' → FormalLimitRel (X := X) y y' → completionViaFormalLimitsDist X (Quotient.mk (FormalLimitSetoid (X := X)) x) (Quotient.mk (FormalLimitSetoid (X := X)) y) = completionViaFormalLimitsDist X (Quotient.mk (FormalLimitSetoid (X := X)) x') (Quotient.mk (FormalLimitSetoid (X := X)) y')

Lean source

Helper for Proposition 1.24: the formal-limit completion carries a metric-space structure via the formal-limit distance.

open Filter universe u noncomputable instance completionViaFormalLimitsMetricSpace (X : Type u) [MetricSpace X] : MetricSpace (CompletionViaFormalLimits X)

Lean source

Helper for Theorem 1.4: choose representatives for a sequence in the quotient.

open Filter universe u lemma helperForTheorem_1_4_chooseRepresentatives (X : Type u) [MetricSpace X] (u : ℕ → CompletionViaFormalLimits X) : ∃ x : ℕ → FormalLimit X, ∀ n, u n = Quotient.mk (FormalLimitSetoid (X := X)) (x n)

Lean source

Helper for Theorem 1.4: reindexing a Cauchy representative stays Cauchy.

open Filter universe u lemma helperForTheorem_1_4_reindex_cauchy (X : Type u) [MetricSpace X] (z : FormalLimit X) {m : ℕ → ℕ} (hm : StrictMono m) : CauchySeq (fun n => z.1 (m n))

Lean source

Helper for Theorem 1.4: a formal limit is equivalent to any strictly monotone reindexing.

open Filter universe u lemma helperForTheorem_1_4_equiv_reindex (X : Type u) [MetricSpace X] (z : FormalLimit X) {m : ℕ → ℕ} (hm : StrictMono m) : FormalLimitRel (X := X) z ⟨fun n => z.1 (m n), helperForTheorem_1_4_reindex_cauchy (X := X) z hm⟩

Lean source

Helper for Theorem 1.4: if the formal-limit distance is below r, then pointwise distances are eventually below r.

open Filter universe u lemma helperForTheorem_1_4_eventually_dist_lt (X : Type u) [MetricSpace X] {x y : FormalLimit X} {r : ℝ} (h : helperForProposition_1_24_formalLimitDist (X := X) x y < r) : ∃ N, ∀ n ≥ N, dist (x.1 n) (y.1 n) < r

Lean source

Helper for Theorem 1.4: powers of 1/2 are eventually below any positive threshold.

open Filter universe u lemma helperForTheorem_1_4_pow_eventually_lt (ε : ℝ) (hε : 0 < ε) : ∃ N, ∀ n ≥ N, (1 / 2 : ℝ) ^ (n + 2) < ε

Lean source

Helper for Theorem 1.4: extract a geometric subsequence of a Cauchy sequence in the completion.

open Filter universe u lemma helperForTheorem_1_4_cauchySeq_subseq_geometric (X : Type u) [MetricSpace X] (u : ℕ → CompletionViaFormalLimits X) (hu : CauchySeq u) : ∃ m : ℕ → ℕ, StrictMono m ∧ ∀ n, dist (u (m n)) (u (m (n + 1))) < (1 / 2 : ℝ) ^ (n + 2)

Lean source

Helper for Theorem 1.4: build a monotone diagonal index with pointwise control.

open Filter universe u lemma helperForTheorem_1_4_diagonal_index (X : Type u) [MetricSpace X] {u : ℕ → CompletionViaFormalLimits X} {m : ℕ → ℕ} {x : ℕ → FormalLimit X} (hx : ∀ n, u (m n) = Quotient.mk (FormalLimitSetoid (X := X)) (x n)) (hsmall : ∀ n, dist (u (m n)) (u (m (n + 1))) < (1 / 2 : ℝ) ^ (n + 2)) : ∃ k : ℕ → ℕ, Monotone k ∧ (∀ n, ∀ j ≥ k n, dist ((x n).1 j) ((x (n + 1)).1 j) < (1 / 2 : ℝ) ^ (n + 2)) ∧ (∀ n, ∀ j ≥ k n, dist ((x (n + 1)).1 (k n)) ((x (n + 1)).1 j) < (1 / 2 : ℝ) ^ (n + 2))

Lean source

Helper for Theorem 1.4: the diagonal sequence is Cauchy.

open Filter universe u lemma helperForTheorem_1_4_diagonal_cauchy (X : Type u) [MetricSpace X] {x : ℕ → FormalLimit X} {k : ℕ → ℕ} (hkmono : Monotone k) (hA : ∀ n, ∀ j ≥ k n, dist ((x n).1 j) ((x (n + 1)).1 j) < (1 / 2 : ℝ) ^ (n + 2)) (hB : ∀ n, ∀ j ≥ k n, dist ((x (n + 1)).1 (k n)) ((x (n + 1)).1 j) < (1 / 2 : ℝ) ^ (n + 2)) : CauchySeq (fun n => (x n).1 (k n))

Lean source

Helper for Theorem 1.4: a Cauchy sequence with a convergent subsequence converges.

open Filter universe u lemma helperForTheorem_1_4_tendsto_of_cauchy_of_subseq {X : Type u} [MetricSpace X] {u : ℕ → X} (hu : CauchySeq u) {m : ℕ → ℕ} (hm : StrictMono m) {a : X} (hsub : Tendsto (fun n => u (m n)) atTop (nhds a)) : Tendsto u atTop (nhds a)

1.4 — Cauchy Sequences and Complete Metric Spaces — Part 2

Lean authors: Zichen Wang, Wanli Ma, Ziyu Wang, Zaiwen Wen.

Source header

Theorem 1.4: Let (X,d) be a metric space. Define Xbar as the set of equivalence classes of Cauchy sequences in X under (x_n) ~ (y_n) iff d(x_n,y_n) -> 0 as n -> infinity. For classes [(x_n)], [(y_n)] define d_{Xbar}([(x_n)],[(y_n)]) := lim_{n -> infinity} d(x_n,y_n), which is well-defined. Then (Xbar, d_{Xbar}) is complete.

open Filter theorem completionViaFormalLimits_completeSpace (X : Type u) [MetricSpace X] : CompleteSpace (CompletionViaFormalLimits X)

Lean source

The constant sequence in a metric space is Cauchy.

open Filter lemma cauchySeq_const' {X : Type u} [MetricSpace X] (x : X) : CauchySeq (fun _ : ℕ => x)

Lean source

The canonical map X → formal-limit completion, sending x to the constant sequence.

open Filter def completionViaFormalLimitsIota (X : Type u) [MetricSpace X] : X → CompletionViaFormalLimits X := fun x => Quotient.mk (FormalLimitSetoid (X := X)) ⟨fun _ : ℕ => x, cauchySeq_const' (X := X) x⟩

Lean source

Proposition 1.25: Let (X,d) be a metric space, let X̄ be the set of equivalence classes of Cauchy sequences in X, and define d_{X̄}(LIM x_n, LIM y_n) := lim_{n→∞} d(x_n,y_n). Define iota : X → X̄ by sending x to the equivalence class of the constant sequence. (i) For all x, y ∈ X, one has x = y iff iota x = iota y. (ii) For all x, y ∈ X, one has d(x,y) = d_{X̄}(iota x, iota y). In particular, iota is an isometric embedding.

open Filter theorem completionViaFormalLimitsIota_props (X : Type u) [MetricSpace X] : (∀ x y : X, x = y ↔ completionViaFormalLimitsIota X x = completionViaFormalLimitsIota X y) ∧ (∀ x y : X, dist x y = completionViaFormalLimitsDist X (completionViaFormalLimitsIota X x) (completionViaFormalLimitsIota X y)) ∧ Isometry (completionViaFormalLimitsIota X)

Lean source

Equality in X is equivalent to equality in the formal completion via iota.

open Filter lemma completionViaFormalLimitsIota_eq_iff {X : Type u} [MetricSpace X] (x y : X) : x = y ↔ completionViaFormalLimitsIota X x = completionViaFormalLimitsIota X y

Lean source

The canonical map into the formal completion preserves distances.

open Filter lemma completionViaFormalLimitsIota_dist {X : Type u} [MetricSpace X] (x y : X) : dist x y = completionViaFormalLimitsDist X (completionViaFormalLimitsIota X x) (completionViaFormalLimitsIota X y)

Lean source

The canonical embedding into the formal completion is an isometry.

open Filter theorem completionViaFormalLimitsIota_isometry {X : Type u} [MetricSpace X] : Isometry (completionViaFormalLimitsIota X)

Lean source

The formal-limit completion is the closure of the canonical image of X.

open Filter theorem completionViaFormalLimits_closure_range (X : Type u) [MetricSpace X] : closure (Set.range (completionViaFormalLimitsIota X)) = (Set.univ : Set (CompletionViaFormalLimits X))

Lean source

Proposition 1.27: Let (X,d) be a metric space. Let (Xbar, d_{Xbar}) be the completion of X constructed via formal limits of Cauchy sequences, and identify X with its canonical image in Xbar. Let (x_n) be a Cauchy sequence in X that converges to x in X. Then the limit of (x_n) in (Xbar, d_{Xbar}) equals the embedded point x in Xbar, i.e. lim_{n -> infinity} x_n = LIM_{n -> infinity} x_n. A convergent Cauchy sequence has formal-limit class equal to the embedded limit.

open Filter theorem completionViaFormalLimits_limit_eq_iota {X : Type u} [MetricSpace X] (x : ℕ → X) {x0 : X} (hx : CauchySeq x) (hlim : Tendsto x atTop (nhds x0)) : Quotient.mk (FormalLimitSetoid (X := X)) ⟨x, hx⟩ = completionViaFormalLimitsIota X x0

Lean source

A complete metric subspace is closed in the ambient space.

open Filter theorem completeSpace_subtype_isClosed {X : Type*} [MetricSpace X] {Y : Set X} : CompleteSpace Y → IsClosed Y

Lean source

A closed subset of a complete metric space is complete as a subspace.

open Filter theorem completeSpace_subtype_of_isClosed {X : Type*} [MetricSpace X] {Y : Set X} : CompleteSpace X → IsClosed Y → CompleteSpace Y

Lean source

Proposition 1.37 (Existence of completion): Let (X,d) be a metric space. There exists a complete metric space (X̄, d̄) and an isometric embedding ι : X → X̄ such that ι(X) is dense in X̄.

open Filter theorem exists_completion_metricSpace (X : Type u) [MetricSpace X] : ∃ (Xbar : Type u) (inst : MetricSpace Xbar), (letI := inst; CompleteSpace Xbar ∧ ∃ iota : X → Xbar, Isometry iota ∧ DenseRange iota)

Lean source

Helper for Theorem 1.4: the chosen subsequence converges to the diagonal class.

open Filter lemma helperForTheorem_1_4_subseq_tendsto (X : Type u) [MetricSpace X] {u : ℕ → CompletionViaFormalLimits X} {m : ℕ → ℕ} {x : ℕ → FormalLimit X} (hx : ∀ n, u (m n) = Quotient.mk (FormalLimitSetoid (X := X)) (x n)) {k : ℕ → ℕ} (hkmono : Monotone k) (hA : ∀ n, ∀ j ≥ k n, dist ((x n).1 j) ((x (n + 1)).1 j) < (1 / 2 : ℝ) ^ (n + 2)) (hB : ∀ n, ∀ j ≥ k n, dist ((x (n + 1)).1 (k n)) ((x (n + 1)).1 j) < (1 / 2 : ℝ) ^ (n + 2)) (hy : CauchySeq (fun n => (x n).1 (k n))) : Tendsto (fun n => u (m n)) atTop (nhds (Quotient.mk (FormalLimitSetoid (X := X)) ⟨fun n => (x n).1 (k n), hy⟩))

Lean source

Helper for Proposition 1.26: each formal limit class lies in the closure of the canonical image of X.

open Filter lemma helperForProposition_1_26_mk_mem_closure_range_iota {X : Type u} [MetricSpace X] (x : FormalLimit X) : Quotient.mk (FormalLimitSetoid (X := X)) x ∈ closure (Set.range (completionViaFormalLimitsIota X))

Lean source

Helper for Proposition 1.26: the canonical map into the completion has dense range.

open Filter theorem helperForProposition_1_26_denseRange_iota (X : Type u) [MetricSpace X] : DenseRange (completionViaFormalLimitsIota X)

Lean source

Helper for Proposition 1.27: convergence implies distances to the limit tend to zero.

open Filter lemma helperForProposition_1_27_tendsto_dist_to_limit {X : Type u} [MetricSpace X] (x : ℕ → X) {x0 : X} (hlim : Tendsto x atTop (nhds x0)) : Tendsto (fun n => dist (x n) x0) atTop (nhds 0)

Lean source

Helper for Proposition 1.27: relate a convergent Cauchy sequence to the constant formal limit.

open Filter lemma helperForProposition_1_27_formalLimitRel_const_of_tendsto {X : Type u} [MetricSpace X] (x : ℕ → X) {x0 : X} (hx : CauchySeq x) (hlim : Tendsto x atTop (nhds x0)) : FormalLimitRel (X := X) ⟨x, hx⟩ ⟨fun _ : ℕ => x0, cauchySeq_const' (X := X) x0⟩

1.5 — Compact Metric Spaces

Lean authors: Zichen Wang, Wanli Ma, Ziyu Wang, Zaiwen Wen.

Source header

Definition 1.21: A subset X ⊆ ℝ is sequentially compact if every sequence in X has a convergent subsequence whose limit belongs to X.

abbrev IsSequentiallyCompact (X : Set ℝ) : Prop := IsSeqCompact X

Lean source

The book's sequential compactness is the same as IsSeqCompact.

lemma isSequentiallyCompact_iff_isSeqCompact (X : Set ℝ) : IsSequentiallyCompact X ↔ IsSeqCompact X

Lean source

Theorem 1.5 (Heine--Borel theorem on ℝ): For X ⊆ ℝ, the following are equivalent: (i) X is closed and bounded. (ii) Every sequence (x_n) in X has a subsequence (x_{n_k}) converging to a limit x ∈ X.

theorem heineBorel_real_iff_isSequentiallyCompact (X : Set ℝ) : (IsClosed X ∧ Bornology.IsBounded X) ↔ IsSequentiallyCompact X

Lean source

Definition 1.22 (Compactness): A metric space (X,d) is compact if every sequence (x_n) in X has a strictly increasing k : ℕ → ℕ and a point x ∈ X with d (x_{k(n)}) x → 0. A subset Y ⊆ X is compact in X if the induced metric on Y is compact.

abbrev IsSequentiallyCompactSpace (X : Type*) [MetricSpace X] : Prop := SeqCompactSpace X

Lean source

Book's compactness of a metric space, expressed as sequential compactness.

abbrev IsCompactSpace (X : Type*) [MetricSpace X] : Prop := IsSequentiallyCompactSpace (X:=X)

Lean source

The book's compactness of a metric space is equivalent to SeqCompactSpace.

lemma isCompactSpace_iff_seqCompactSpace (X : Type*) [MetricSpace X] : IsCompactSpace X ↔ SeqCompactSpace X

Lean source

Book's compactness for a subset of a metric space, expressed as IsSeqCompact.

abbrev IsCompactSubset {X : Type*} [MetricSpace X] (Y : Set X) : Prop := IsSeqCompact Y

Lean source

The book's compact subset notion is equivalent to IsSeqCompact.

lemma isCompactSubset_iff_isSeqCompact {X : Type*} [MetricSpace X] (Y : Set X) : IsCompactSubset (X:=X) Y ↔ IsSeqCompact Y

Lean source

Definition 1.23 (Bounded sets): In a metric space (X,d), a subset Y is bounded if there exist x ∈ X and r ∈ ℝ with 0 ≤ r < ∞ such that Y ⊆ B(x,r) = {y ∈ X : d(x,y) < r}. The metric space (X,d) is bounded if the set X is bounded.

def IsBoundedSubset {X : Type*} [MetricSpace X] (Y : Set X) : Prop := Y = ∅ ∨ ∃ x : X, ∃ r : ℝ, 0 ≤ r ∧ Y ⊆ Metric.ball x r

Lean source

The book's boundedness for subsets agrees with Bornology.IsBounded.

lemma isBoundedSubset_iff_isBounded {X : Type*} [MetricSpace X] (Y : Set X) : IsBoundedSubset (X:=X) Y ↔ Bornology.IsBounded Y

Lean source

A metric space is bounded if it is a BoundedSpace.

abbrev IsBoundedSpace (X : Type*) [MetricSpace X] : Prop := BoundedSpace X

Lean source

The book's boundedness of a metric space matches BoundedSpace.

lemma isBoundedSpace_iff_boundedSpace (X : Type*) [MetricSpace X] : IsBoundedSpace X ↔ BoundedSpace X

Lean source

A metric space is bounded iff its underlying set is bounded in the book's sense.

lemma isBoundedSpace_iff_isBounded_univ (X : Type*) [MetricSpace X] : IsBoundedSpace X ↔ IsBoundedSubset (X:=X) (Set.univ : Set X)

Lean source

Definition 1.24: In a metric space (X,d), a subset K ⊆ X is compact if every open cover of K has a finite subcover; i.e. for every family of open sets (U_i)_{i ∈ I} in X with K ⊆ ⋃ i, U_i, there exist indices i₁, …, iₙ ∈ I such that K ⊆ U_{i₁} ∪ … ∪ U_{iₙ}.

abbrev IsCompactOpenCover {X : Type*} [MetricSpace X] (K : Set X) : Prop := IsCompact K

Lean source

The book's open-cover compactness for subsets agrees with IsCompact.

lemma isCompactOpenCover_iff_isCompact {X : Type*} [MetricSpace X] (K : Set X) : IsCompactOpenCover (X:=X) K ↔ IsCompact K

Lean source

Definition 1.25 (Compactness via open covers): A topological space Y is compact if every open cover of Y has a finite subcover.

abbrev IsCompactOpenCoverSpace (Y : Type*) [TopologicalSpace Y] : Prop := CompactSpace Y

Lean source

The book's open-cover compactness for a space agrees with CompactSpace.

lemma isCompactOpenCoverSpace_iff_compactSpace (Y : Type*) [TopologicalSpace Y] : IsCompactOpenCoverSpace Y ↔ CompactSpace Y

Lean source

Definition 1.26: A metric space (X,d) is totally bounded if for every ε > 0 there exist n ∈ ℕ and points x^(1), …, x^(n) ∈ X such that X = ⋃_{i=1}^n B(x^(i), ε).

abbrev IsTotallyBoundedSpace (X : Type*) [MetricSpace X] : Prop := TotallyBounded (Set.univ : Set X)

Lean source

The book's totally boundedness is equivalent to a finite cover by metric balls.

lemma isTotallyBoundedSpace_iff_ball_cover (X : Type*) [MetricSpace X] : IsTotallyBoundedSpace X ↔ ∀ ε > 0, ∃ t : Set X, t.Finite ∧ (Set.univ : Set X) ⊆ ⋃ x ∈ t, Metric.ball x ε

Lean source

Proposition 1.28: A compact metric space is complete and bounded.

theorem compactSpace_complete_and_bounded_prop (X : Type*) [MetricSpace X] (hX : IsCompactSpace X) : CompleteSpace X ∧ IsBoundedSpace X

Lean source

If a metric space is compact (in the book's sense), then it is complete and bounded.

theorem compactSpace_complete_and_bounded (X : Type*) [MetricSpace X] (hX : IsCompactSpace X) : CompleteSpace X ∧ IsBoundedSpace X

Lean source

Theorem 1.6: (Compact subsets of metric spaces are closed and bounded) Let (X,d) be a metric space and let Y ⊆ X be compact. Then: (i) Y is closed in X. (ii) Y is bounded, i.e. there exist x₀ ∈ X and R > 0 such that Y ⊆ {x ∈ X : d x x₀ ≤ R}.

theorem compactSubset_closed_and_bounded_prop {X : Type*} [MetricSpace X] {Y : Set X} (hY : IsCompactSubset (X := X) Y) : IsClosed Y ∧ IsBoundedSubset (X := X) Y

Lean source

A compact subset of a metric space is closed and bounded.

theorem compactSubset_closed_and_bounded {X : Type*} [MetricSpace X] {Y : Set X} (hY : IsCompactSubset (X := X) Y) : IsClosed Y ∧ IsBoundedSubset (X := X) Y

Lean source

Theorem 1.7 (Heine--Borel theorem): Let n ∈ ℕ, and let d be the Euclidean metric, the taxicab metric, or the sup norm metric on ℝ^n. For a set E ⊆ ℝ^n, the following are equivalent: (i) E is compact (every open cover admits a finite subcover). (ii) E is closed and bounded.

theorem heineBorel_Rn_iff_isClosed_isBounded_prop (n : ℕ) (E : Set (EuclideanSpace ℝ (Fin n))) : IsCompact E ↔ IsClosed E ∧ Bornology.IsBounded E

Lean source

Heine--Borel on ℝ^n: compactness is equivalent to closedness and boundedness.

theorem heineBorel_Rn_iff_isClosed_isBounded (n : ℕ) (E : Set (EuclideanSpace ℝ (Fin n))) : IsCompact E ↔ IsClosed E ∧ Bornology.IsBounded E

Lean source

Theorem 1.8: Let (X,d) be a metric space, let Y ⊆ X be compact, and let (V_α)_{α∈A} be a family of open subsets of X with Y ⊆ ⋃ α, V α. Then there exists a finite F ⊆ A such that Y ⊆ ⋃ α ∈ F, V α.

theorem compactSubset_finite_subcover {X : Type*} [MetricSpace X] {Y : Set X} (hY : IsCompactSubset (X := X) Y) {A : Type*} (V : A → Set X) (hV : ∀ α, IsOpen (V α)) (hcover : Y ⊆ ⋃ α, V α) : ∃ F : Finset A, Y ⊆ ⋃ α ∈ F, V α

Lean source

Theorem 1.9 (Heine--Borel property implies compactness): Let Y be a topological space. If every open cover of Y admits a finite subcover, then Y is compact.

theorem heineBorelProperty_implies_compactSpace (Y : Type u) [TopologicalSpace Y] (hcover : ∀ {ι : Type u} (U : ι → Set Y), (∀ i, IsOpen (U i)) → (Set.univ ⊆ ⋃ i, U i) → ∃ s : Finset ι, Set.univ ⊆ ⋃ i ∈ s, U i) : CompactSpace Y

Lean source

Theorem 1.10: Let (K_n)_{n∈ℕ} be a sequence of nonempty compact subsets of a metric space (X,d) such that K_{n+1} ⊆ K_n for all n. Then ⋂ n, K n is nonempty. Nested nonempty compact sets have nonempty intersection.

theorem nested_compact_inter_nonempty {X : Type*} [MetricSpace X] (K : ℕ → Set X) (hKcompact : ∀ n, IsCompact (K n)) (hKnonempty : ∀ n, (K n).Nonempty) (hmono : ∀ n, K (n + 1) ⊆ K n) : (⋂ n, K n).Nonempty

Lean source

Theorem 1.11: For a metric space (X,d) and a nested sequence of nonempty compact subsets K n with K (n+1) ⊆ K n, the intersection ⋂_{n=1}^∞ K_n is nonempty.

theorem nested_compact_inter_nonempty_from_one_prop {X : Type*} [MetricSpace X] (K : ℕ → Set X) (hKcompact : ∀ n, IsCompact (K n)) (hKnonempty : ∀ n, (K n).Nonempty) (hmono : ∀ n, K (n + 1) ⊆ K n) : (⋂ n, K (n + 1)).Nonempty

Lean source

A nested sequence of nonempty compact subsets has nonempty intersection starting at n = 1.

theorem nested_compact_inter_nonempty_from_one {X : Type*} [MetricSpace X] (K : ℕ → Set X) (hKcompact : ∀ n, IsCompact (K n)) (hKnonempty : ∀ n, (K n).Nonempty) (hmono : ∀ n, K (n + 1) ⊆ K n) : (⋂ n, K (n + 1)).Nonempty

Lean source

Theorem 1.12: Let (X,d) be a metric space. (a) If Y ⊆ X is compact and Z ⊆ Y, then Z is compact iff Z is closed in Y. (b) If Y₁, …, Yₙ ⊆ X are compact, then ⋃ i, Yᵢ is compact. (c) Every finite subset of X (including ∅) is compact.

theorem compact_basic_properties (X : Type*) [MetricSpace X] : (∀ (Y : Set X), IsCompact Y → ∀ (Z : Set Y), IsCompact Z ↔ IsClosed Z) ∧ (∀ {ι : Type*} (s : Finset ι) (Y : ι → Set X), (∀ i ∈ s, IsCompact (Y i)) → IsCompact (⋃ i ∈ s, Y i)) ∧ (∀ {Z : Set X}, Z.Finite → IsCompact Z)

Lean source

Theorem 1.12(a): In a compact subset Y of a metric space, Z ⊆ Y is compact iff it is closed in Y.

theorem compact_subset_iff_closed_in_compact {X : Type*} [MetricSpace X] {Y : Set X} (hY : IsCompact Y) (Z : Set Y) : IsCompact Z ↔ IsClosed Z

Lean source

Theorem 1.12(b): A finite union of compact subsets is compact.

theorem compact_iUnion_finset {X : Type*} [MetricSpace X] {ι : Type*} (s : Finset ι) (Y : ι → Set X) (hY : ∀ i ∈ s, IsCompact (Y i)) : IsCompact (⋃ i ∈ s, Y i)

Lean source

Theorem 1.12(c): Every finite subset of a metric space is compact.

theorem finite_isCompact {X : Type*} [MetricSpace X] {Z : Set X} (hZ : Z.Finite) : IsCompact Z

Lean source

Theorem 1.13 (Equivalence of sequential compactness and open cover compactness): Let (X,d) be a metric space. The following are equivalent: (i) every sequence in X has a convergent subsequence; (ii) every open cover of X has a finite subcover.

theorem sequentiallyCompactSpace_iff_compactOpenCoverSpace_prop (X : Type*) [MetricSpace X] : IsSequentiallyCompactSpace X ↔ IsCompactOpenCoverSpace X

Lean source

In a metric space, sequential compactness is equivalent to open-cover compactness.

theorem sequentiallyCompactSpace_iff_compactOpenCoverSpace (X : Type*) [MetricSpace X] : IsSequentiallyCompactSpace X ↔ IsCompactOpenCoverSpace X

Lean source

local instance : MetricSpace ℤ

Lean source

local instance : Dist ℤ

Lean source

local instance : PseudoMetricSpace ℤ

Lean source

local instance : UniformSpace ℤ

Lean source

local instance : TopologicalSpace ℤ

Lean source

local instance : Bornology ℤ

Lean source

Proposition 1.29: Let (X,d) be a metric space and equip ℤ with the discrete metric d(m,n)=1 when m ≠ n (and 0 otherwise). Then ℤ is complete and bounded, but not compact.

theorem int_discreteMetric_complete_bounded_not_compact : letI : MetricSpace ℤ := intDiscreteMetricSpace CompleteSpace ℤ ∧ BoundedSpace ℤ ∧ ¬ CompactSpace ℤ

Lean source

Proposition 1.36: [Heine-Borel fails for discrete metric on ℤ] In the discrete metric on ℤ, the set ℤ is closed and bounded, but not compact. In the discrete metric on ℤ, the whole space is closed and bounded but not compact.

theorem int_discrete_closed_bounded_not_compact : letI : MetricSpace ℤ := intDiscreteMetricSpace IsClosed (Set.univ : Set ℤ) ∧ IsBoundedSubset (X:=ℤ) (Set.univ) ∧ ¬ IsCompactOpenCover (X:=ℤ) (Set.univ)

Lean source

Helper for Proposition 1.28: sequential compactness of the book gives CompactSpace.

lemma helperForProposition_1_28_compactSpace_of_isCompactSpace (X : Type*) [MetricSpace X] (hX : IsCompactSpace X) : CompactSpace X

Lean source

Helper for Proposition 1.28: compact metric spaces are complete.

lemma helperForProposition_1_28_completeSpace_of_compactSpace (X : Type*) [MetricSpace X] [CompactSpace X] : CompleteSpace X

Lean source

Helper for Proposition 1.28: compact metric spaces are bounded.

lemma helperForProposition_1_28_boundedSpace_of_compactSpace (X : Type*) [MetricSpace X] [CompactSpace X] : BoundedSpace X

Lean source

Helper for Theorem 1.6: a compact subset of a metric space is closed.

lemma helperForTheorem_1_6_isClosed {X : Type*} [MetricSpace X] {Y : Set X} (hY : IsCompactSubset (X := X) Y) : IsClosed Y

Lean source

Helper for Theorem 1.8: sequential compactness of a subset implies compactness.

lemma helperForTheorem_1_8_isCompact {X : Type*} [MetricSpace X] {Y : Set X} (hY : IsCompactSubset (X := X) Y) : IsCompact Y

Lean source

Helper for Theorem 1.9: open-cover finite-subcover property implies compactness of Set.univ.

lemma helperForTheorem_1_9_isCompact_univ_of_openCover (Y : Type u) [TopologicalSpace Y] (hcover : ∀ {ι : Type u} (U : ι → Set Y), (∀ i, IsOpen (U i)) → (Set.univ ⊆ ⋃ i, U i) → ∃ s : Finset ι, Set.univ ⊆ ⋃ i ∈ s, U i) : IsCompact (Set.univ : Set Y)

Lean source

Helper for Theorem 1.12: compactness of univ in the subtype of a compact set.

lemma helperForTheorem_1_12_isCompact_univ_subtype {X : Type*} [MetricSpace X] {Y : Set X} (hY : IsCompact Y) : IsCompact (Set.univ : Set Y)

Lean source

Helper for Proposition 1.29: discrete distance on ℤ, 0 on the diagonal and 1 off it.

def intDiscreteDist (m n : ℤ) : ℝ := if m = n then 0 else 1

Lean source

Helper for Proposition 1.29: the discrete distance on ℤ is zero on the diagonal.

lemma intDiscreteDist_self (m : ℤ) : intDiscreteDist m m = 0

Lean source

Helper for Proposition 1.29: the discrete distance on ℤ is symmetric.

lemma intDiscreteDist_comm (m n : ℤ) : intDiscreteDist m n = intDiscreteDist n m

Lean source

Helper for Proposition 1.29: the discrete distance on ℤ satisfies the triangle inequality.

lemma intDiscreteDist_triangle (m n k : ℤ) : intDiscreteDist m k ≤ intDiscreteDist m n + intDiscreteDist n k

Lean source

Helper for Proposition 1.29: zero discrete distance on ℤ implies equality.

lemma intDiscreteDist_eq_of_dist_eq_zero {m n : ℤ} : intDiscreteDist m n = 0 → m = n

Lean source

Helper for Proposition 1.29: the metric space structure on ℤ induced by intDiscreteDist.

def intDiscreteMetricSpace : MetricSpace ℤ := { dist := intDiscreteDist dist_self := intDiscreteDist_self dist_comm := intDiscreteDist_comm dist_triangle := intDiscreteDist_triangle eq_of_dist_eq_zero := intDiscreteDist_eq_of_dist_eq_zero }

Lean source

Helper for Proposition 1.29: in the discrete metric on ℤ, distance < 1/2 forces equality.

lemma helperForProposition_1_29_eq_of_dist_lt_one_half {m n : ℤ} : intDiscreteDist m n < (1 / 2 : ℝ) → m = n

Lean source

Helper for Proposition 1.29: the discrete metric on ℤ induces the discrete topology.

lemma helperForProposition_1_29_discreteTopology_intDiscrete : letI : MetricSpace ℤ := intDiscreteMetricSpace letI : Dist ℤ := ⟨intDiscreteDist⟩ letI : UniformSpace ℤ := intDiscreteMetricSpace.toPseudoMetricSpace.toUniformSpace letI : TopologicalSpace ℤ := intDiscreteMetricSpace.toPseudoMetricSpace.toUniformSpace.toTopologicalSpace DiscreteTopology ℤ

Lean source

Helper for Proposition 1.29: completeness of the discrete metric on ℤ.

lemma helperForProposition_1_29_completeSpace_intDiscrete : letI : MetricSpace ℤ := intDiscreteMetricSpace letI : Dist ℤ := ⟨intDiscreteDist⟩ letI : UniformSpace ℤ := intDiscreteMetricSpace.toPseudoMetricSpace.toUniformSpace CompleteSpace ℤ

Lean source

Helper for Proposition 1.29: boundedness of the discrete metric on ℤ.

lemma helperForProposition_1_29_boundedSpace_intDiscrete : letI : MetricSpace ℤ := intDiscreteMetricSpace letI : Dist ℤ := ⟨intDiscreteDist⟩ letI : Bornology ℤ := intDiscreteMetricSpace.toPseudoMetricSpace.toBornology BoundedSpace ℤ

Lean source

Helper for Proposition 1.29: ℤ with the discrete metric is not compact.

lemma helperForProposition_1_29_not_compactSpace_intDiscrete : letI : MetricSpace ℤ := intDiscreteMetricSpace letI : Dist ℤ := ⟨intDiscreteDist⟩ letI : UniformSpace ℤ := intDiscreteMetricSpace.toPseudoMetricSpace.toUniformSpace letI : TopologicalSpace ℤ := intDiscreteMetricSpace.toPseudoMetricSpace.toUniformSpace.toTopologicalSpace ¬ CompactSpace ℤ

Lean source

Helper for Proposition 1.36: every integer lies in the ball of radius 2 around 0.

lemma helperForProposition_1_36_mem_ball_zero_two_intDiscrete (z : ℤ) : letI : MetricSpace ℤ := intDiscreteMetricSpace letI : Dist ℤ := ⟨intDiscreteDist⟩ letI : PseudoMetricSpace ℤ := intDiscreteMetricSpace.toPseudoMetricSpace z ∈ Metric.ball (0 : ℤ) 2

Lean source

Helper for Proposition 1.36: univ is bounded for the discrete metric on ℤ.

lemma helperForProposition_1_36_isBoundedSubset_univ_intDiscrete : letI : MetricSpace ℤ := intDiscreteMetricSpace letI : Dist ℤ := ⟨intDiscreteDist⟩ letI : PseudoMetricSpace ℤ := intDiscreteMetricSpace.toPseudoMetricSpace IsBoundedSubset (X:=ℤ) (Set.univ : Set ℤ)

Lean source

Helper for Proposition 1.36: univ is not compact in the discrete metric on ℤ.

lemma helperForProposition_1_36_not_isCompact_univ_intDiscrete : letI : MetricSpace ℤ := intDiscreteMetricSpace letI : Dist ℤ := ⟨intDiscreteDist⟩ letI : UniformSpace ℤ := intDiscreteMetricSpace.toPseudoMetricSpace.toUniformSpace letI : TopologicalSpace ℤ := intDiscreteMetricSpace.toPseudoMetricSpace.toUniformSpace.toTopologicalSpace ¬ IsCompact (Set.univ : Set ℤ)