topology.metric_space.gromov_hausdorff
⟷
Mathlib.Topology.MetricSpace.GromovHausdorff
The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -324,7 +324,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
p.is_compact.bounded q.is_compact.bounded)
rcases this with ⟨y, hy, dy⟩
rcases mem_range.1 hy with ⟨z, hzy⟩
- rw [← hzy] at dy
+ rw [← hzy] at dy
have DΦ : diam (range Φ) = diam (univ : Set X) := Φisom.diam_range
have DΨ : diam (range Ψ) = diam (univ : Set Y) := Ψisom.diam_range
calc
@@ -385,7 +385,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
(Hausdorff_edist_ne_top_of_nonempty_of_bounded p.nonempty q.nonempty p.is_compact.bounded
q.is_compact.bounded) with
⟨z, zq, hz⟩
- have : z ∈ range Ψ := by rwa [← Ψrange] at zq
+ have : z ∈ range Ψ := by rwa [← Ψrange] at zq
rcases mem_range.1 this with ⟨y, hy⟩
calc
(⨅ y, Fb (inl x, inr y)) ≤ Fb (inl x, inr y) :=
@@ -401,7 +401,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
(Hausdorff_edist_ne_top_of_nonempty_of_bounded p.nonempty q.nonempty p.is_compact.bounded
q.is_compact.bounded) with
⟨z, zq, hz⟩
- have : z ∈ range Φ := by rwa [← Φrange] at zq
+ have : z ∈ range Φ := by rwa [← Φrange] at zq
rcases mem_range.1 this with ⟨x, hx⟩
calc
(⨅ x, Fb (inl x, inr y)) ≤ Fb (inl x, inr y) :=
@@ -494,7 +494,7 @@ instance : MetricSpace GHSpace where
is realized by some coupling. In this coupling, the two spaces are at zero Hausdorff distance,
i.e., they coincide. Therefore, the original spaces are isometric. -/
rcases GH_dist_eq_Hausdorff_dist x.rep y.rep with ⟨Φ, Ψ, Φisom, Ψisom, DΦΨ⟩
- rw [← dist_GH_dist, hxy] at DΦΨ
+ rw [← dist_GH_dist, hxy] at DΦΨ
have : range Φ = range Ψ :=
by
have hΦ : IsCompact (range Φ) := isCompact_range Φisom.continuous
@@ -785,7 +785,7 @@ instance : SecondCountableTopology GHSpace :=
let hi := ((E q) ⟨y, ys⟩).is_lt
have ihi_eq : (⟨i, hi⟩ : Fin (N q)) = (E q) ⟨y, ys⟩ := by rw [Fin.ext_iff, Fin.val_mk]
have hiq : i < N q := hi
- have hip : i < N p := by rwa [Npq.symm] at hiq
+ have hip : i < N p := by rwa [Npq.symm] at hiq
let z := (E p).symm ⟨i, hip⟩
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
@@ -804,12 +804,12 @@ instance : SecondCountableTopology GHSpace :=
-- introduce `i`, that codes both `x` and `Φ x` in `fin (N p) = fin (N q)`
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
- have hiq : i < N q := by rwa [Npq] at hip
+ have hiq : i < N q := by rwa [Npq] at hip
have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
- have hjq : j < N q := by rwa [Npq] at hjp
+ have hjq : j < N q := by rwa [Npq] at hjp
have j' : j = ((E q) (Ψ y)).1 := by
simp only [Equiv.apply_symm_apply, Fin.val_eq_coe, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
@@ -835,7 +835,7 @@ instance : SecondCountableTopology GHSpace :=
subst hpq
intros
rfl
- rw [Ap, Aq] at this
+ rw [Ap, Aq] at this
-- deduce that the distances coincide up to `ε`, by a straightforward computation
-- that should be automated
have I :=
@@ -879,7 +879,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
rcases Metric.tendsto_atTop.1 ulim ε εpos with ⟨n, hn⟩
have u_le_ε : u n ≤ ε := by
have := hn n le_rfl
- simp only [Real.dist_eq, add_zero, sub_eq_add_neg, neg_zero] at this
+ simp only [Real.dist_eq, add_zero, sub_eq_add_neg, neg_zero] at this
exact le_of_lt (lt_of_le_of_lt (le_abs_self _) this)
-- construct a finite subset `s p` of `p` which is `ε`-dense and has cardinal `≤ K n`
have :
@@ -893,7 +893,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
use∅, 0, bot_le, choice this
· rcases hcov _ (Set.not_not_mem.1 hp) n with ⟨s, ⟨scard, scover⟩⟩
rcases Cardinal.lt_aleph0.1 (lt_of_le_of_lt scard (Cardinal.nat_lt_aleph0 _)) with ⟨N, hN⟩
- rw [hN, Cardinal.natCast_le] at scard
+ rw [hN, Cardinal.natCast_le] at scard
have : Cardinal.mk s = Cardinal.mk (Fin N) := by rw [hN, Cardinal.mk_fin]
cases' Quotient.exact this with E
use s, N, scard, E
@@ -933,7 +933,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
let hi := ((E q) ⟨y, ys⟩).2
have ihi_eq : (⟨i, hi⟩ : Fin (N q)) = (E q) ⟨y, ys⟩ := by rw [Fin.ext_iff, Fin.val_mk]
have hiq : i < N q := hi
- have hip : i < N p := by rwa [Npq.symm] at hiq
+ have hip : i < N p := by rwa [Npq.symm] at hiq
let z := (E p).symm ⟨i, hip⟩
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
@@ -952,12 +952,12 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
-- introduce `i`, that codes both `x` and `Φ x` in `fin (N p) = fin (N q)`
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
- have hiq : i < N q := by rwa [Npq] at hip
+ have hiq : i < N q := by rwa [Npq] at hip
have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
- have hjq : j < N q := by rwa [Npq] at hjp
+ have hjq : j < N q := by rwa [Npq] at hjp
have j' : j = (E q) (Ψ y) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
have Ap : ((F p).2 ⟨i, hip⟩ ⟨j, hjp⟩).1 = ⌊ε⁻¹ * dist x y⌋₊ :=
@@ -1001,7 +1001,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
rfl
have : ⌊ε⁻¹ * dist x y⌋ = ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋ :=
by
- rw [Ap, Aq] at this
+ rw [Ap, Aq] at this
have D : 0 ≤ ⌊ε⁻¹ * dist x y⌋ :=
floor_nonneg.2 (mul_nonneg (le_of_lt (inv_pos.2 εpos)) dist_nonneg)
have D' : 0 ≤ ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋ :=
@@ -1140,7 +1140,7 @@ instance : CompleteSpace GHSpace :=
rw [← to_inductive_limit_commute I]
simp only [f]
rw [← to_glue_commute]
- rw [range_comp] at X2n
+ rw [range_comp] at X2n
have X2nsucc :
X2 n.succ =
range
@@ -1148,7 +1148,7 @@ instance : CompleteSpace GHSpace :=
Φ n.succ ∘ c n ∘ to_glue_r (Y n).isom (isometry_optimal_GH_injl (X n) (X n.succ))) ∘
optimal_GH_injr (X n) (X n.succ)) :=
by rfl
- rw [range_comp] at X2nsucc
+ rw [range_comp] at X2nsucc
rw [X2n, X2nsucc, Hausdorff_dist_image, Hausdorff_dist_optimal, ← dist_GH_dist]
· exact hu n n n.succ (le_refl n) (le_succ n)
· apply uniform_space.completion.coe_isometry.comp _
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -637,7 +637,7 @@ variable {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty X] {Y : Type v}
[CompactSpace Y] [Nonempty Y]
-- we want to ignore these instances in the following theorem
-attribute [local instance 10] Sum.topologicalSpace Sum.uniformSpace
+attribute [local instance 10] Sum.topologicalSpace Sum.instUniformSpace
#print GromovHausdorff.ghDist_le_of_approx_subsets /-
/-- If there are subsets which are `ε₁`-dense and `ε₃`-dense in two spaces, and
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,11 +3,11 @@ Copyright (c) 2019 Sébastien Gouëzel. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sébastien Gouëzel
-/
-import Mathbin.SetTheory.Cardinal.Basic
-import Mathbin.Topology.MetricSpace.Closeds
-import Mathbin.Topology.MetricSpace.Completion
-import Mathbin.Topology.MetricSpace.GromovHausdorffRealized
-import Mathbin.Topology.MetricSpace.Kuratowski
+import SetTheory.Cardinal.Basic
+import Topology.MetricSpace.Closeds
+import Topology.MetricSpace.Completion
+import Topology.MetricSpace.GromovHausdorffRealized
+import Topology.MetricSpace.Kuratowski
#align_import topology.metric_space.gromov_hausdorff from "leanprover-community/mathlib"@"1a51edf13debfcbe223fa06b1cb353b9ed9751cc"
mathlib commit https://github.com/leanprover-community/mathlib/commit/001ffdc42920050657fd45bd2b8bfbec8eaaeb29
@@ -805,13 +805,13 @@ instance : SecondCountableTopology GHSpace :=
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
have hiq : i < N q := by rwa [Npq] at hip
- have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
+ have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
have hjq : j < N q := by rwa [Npq] at hjp
have j' : j = ((E q) (Ψ y)).1 := by
- simp only [Equiv.apply_symm_apply, Fin.val_eq_coe, Fin.coe_castIso]
+ simp only [Equiv.apply_symm_apply, Fin.val_eq_coe, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
have : (F p).2 ((E p) x) ((E p) y) = floor (ε⁻¹ * dist x y) := by
simp only [F, (E p).symm_apply_apply]
@@ -953,12 +953,12 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
have hiq : i < N q := by rwa [Npq] at hip
- have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
+ have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
have hjq : j < N q := by rwa [Npq] at hjp
- have j' : j = (E q) (Ψ y) := by simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
+ have j' : j = (E q) (Ψ y) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
have Ap : ((F p).2 ⟨i, hip⟩ ⟨j, hjp⟩).1 = ⌊ε⁻¹ * dist x y⌋₊ :=
calc
mathlib commit https://github.com/leanprover-community/mathlib/commit/63721b2c3eba6c325ecf8ae8cca27155a4f6306f
@@ -890,7 +890,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
by_cases hp : p ∉ t
· have : Nonempty (Equiv (∅ : Set p.rep) (Fin 0)) := by rw [← Fintype.card_eq];
simp only [empty_card', Fintype.card_fin]
- use ∅, 0, bot_le, choice this
+ use∅, 0, bot_le, choice this
· rcases hcov _ (Set.not_not_mem.1 hp) n with ⟨s, ⟨scard, scover⟩⟩
rcases Cardinal.lt_aleph0.1 (lt_of_le_of_lt scard (Cardinal.nat_lt_aleph0 _)) with ⟨N, hN⟩
rw [hN, Cardinal.natCast_le] at scard
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,11 +2,6 @@
Copyright (c) 2019 Sébastien Gouëzel. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sébastien Gouëzel
-
-! This file was ported from Lean 3 source module topology.metric_space.gromov_hausdorff
-! leanprover-community/mathlib commit 1a51edf13debfcbe223fa06b1cb353b9ed9751cc
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.SetTheory.Cardinal.Basic
import Mathbin.Topology.MetricSpace.Closeds
@@ -14,6 +9,8 @@ import Mathbin.Topology.MetricSpace.Completion
import Mathbin.Topology.MetricSpace.GromovHausdorffRealized
import Mathbin.Topology.MetricSpace.Kuratowski
+#align_import topology.metric_space.gromov_hausdorff from "leanprover-community/mathlib"@"1a51edf13debfcbe223fa06b1cb353b9ed9751cc"
+
/-!
# Gromov-Hausdorff distance
mathlib commit https://github.com/leanprover-community/mathlib/commit/1a51edf13debfcbe223fa06b1cb353b9ed9751cc
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sébastien Gouëzel
! This file was ported from Lean 3 source module topology.metric_space.gromov_hausdorff
-! leanprover-community/mathlib commit 0c1f285a9f6e608ae2bdffa3f993eafb01eba829
+! leanprover-community/mathlib commit 1a51edf13debfcbe223fa06b1cb353b9ed9751cc
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -17,6 +17,9 @@ import Mathbin.Topology.MetricSpace.Kuratowski
/-!
# Gromov-Hausdorff distance
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
This file defines the Gromov-Hausdorff distance on the space of nonempty compact metric spaces
up to isometry.
mathlib commit https://github.com/leanprover-community/mathlib/commit/5dc6092d09e5e489106865241986f7f2ad28d4c8
@@ -77,30 +77,39 @@ private def isometry_rel : NonemptyCompacts ℓ_infty_ℝ → NonemptyCompacts
private theorem is_equivalence_isometry_rel : Equivalence IsometryRel :=
⟨fun x => ⟨IsometryEquiv.refl _⟩, fun x y ⟨e⟩ => ⟨e.symm⟩, fun x y z ⟨e⟩ ⟨f⟩ => ⟨e.trans f⟩⟩
+#print GromovHausdorff.IsometryRel.setoid /-
/-- setoid instance identifying two isometric nonempty compact subspaces of ℓ^∞(ℝ) -/
instance IsometryRel.setoid : Setoid (NonemptyCompacts ℓ_infty_ℝ) :=
Setoid.mk IsometryRel is_equivalence_isometryRel
#align Gromov_Hausdorff.isometry_rel.setoid GromovHausdorff.IsometryRel.setoid
+-/
+#print GromovHausdorff.GHSpace /-
/-- The Gromov-Hausdorff space -/
def GHSpace : Type :=
Quotient IsometryRel.setoid
#align Gromov_Hausdorff.GH_space GromovHausdorff.GHSpace
+-/
+#print GromovHausdorff.toGHSpace /-
/-- Map any nonempty compact type to `GH_space` -/
def toGHSpace (X : Type u) [MetricSpace X] [CompactSpace X] [Nonempty X] : GHSpace :=
⟦NonemptyCompacts.kuratowskiEmbedding X⟧
#align Gromov_Hausdorff.to_GH_space GromovHausdorff.toGHSpace
+-/
instance : Inhabited GHSpace :=
⟨Quot.mk _ ⟨⟨{0}, isCompact_singleton⟩, singleton_nonempty _⟩⟩
+#print GromovHausdorff.GHSpace.Rep /-
/-- A metric space representative of any abstract point in `GH_space` -/
@[nolint has_nonempty_instance]
def GHSpace.Rep (p : GHSpace) : Type :=
(Quotient.out p : NonemptyCompacts ℓ_infty_ℝ)
#align Gromov_Hausdorff.GH_space.rep GromovHausdorff.GHSpace.Rep
+-/
+#print GromovHausdorff.eq_toGHSpace_iff /-
theorem eq_toGHSpace_iff {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty X]
{p : NonemptyCompacts ℓ_infty_ℝ} :
⟦p⟧ = toGHSpace X ↔ ∃ Ψ : X → ℓ_infty_ℝ, Isometry Ψ ∧ range Ψ = p :=
@@ -121,33 +130,45 @@ theorem eq_toGHSpace_iff {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty
by dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rw [rangeΨ] <;> rfl
exact ⟨cast E f⟩
#align Gromov_Hausdorff.eq_to_GH_space_iff GromovHausdorff.eq_toGHSpace_iff
+-/
+#print GromovHausdorff.eq_toGHSpace /-
theorem eq_toGHSpace {p : NonemptyCompacts ℓ_infty_ℝ} : ⟦p⟧ = toGHSpace p :=
eq_toGHSpace_iff.2 ⟨fun x => x, isometry_subtype_coe, Subtype.range_coe⟩
#align Gromov_Hausdorff.eq_to_GH_space GromovHausdorff.eq_toGHSpace
+-/
section
attribute [local reducible] GH_space.rep
+#print GromovHausdorff.repGHSpaceMetricSpace /-
instance repGHSpaceMetricSpace {p : GHSpace} : MetricSpace p.rep := by infer_instance
#align Gromov_Hausdorff.rep_GH_space_metric_space GromovHausdorff.repGHSpaceMetricSpace
+-/
+#print GromovHausdorff.rep_gHSpace_compactSpace /-
instance rep_gHSpace_compactSpace {p : GHSpace} : CompactSpace p.rep := by infer_instance
#align Gromov_Hausdorff.rep_GH_space_compact_space GromovHausdorff.rep_gHSpace_compactSpace
+-/
+#print GromovHausdorff.rep_gHSpace_nonempty /-
instance rep_gHSpace_nonempty {p : GHSpace} : Nonempty p.rep := by infer_instance
#align Gromov_Hausdorff.rep_GH_space_nonempty GromovHausdorff.rep_gHSpace_nonempty
+-/
end
+#print GromovHausdorff.GHSpace.toGHSpace_rep /-
theorem GHSpace.toGHSpace_rep (p : GHSpace) : toGHSpace p.rep = p :=
by
change to_GH_space (Quot.out p : nonempty_compacts ℓ_infty_ℝ) = p
rw [← eq_to_GH_space]
exact Quot.out_eq p
#align Gromov_Hausdorff.GH_space.to_GH_space_rep GromovHausdorff.GHSpace.toGHSpace_rep
+-/
+#print GromovHausdorff.toGHSpace_eq_toGHSpace_iff_isometryEquiv /-
/-- Two nonempty compact spaces have the same image in `GH_space` if and only if they are
isometric. -/
theorem toGHSpace_eq_toGHSpace_iff_isometryEquiv {X : Type u} [MetricSpace X] [CompactSpace X]
@@ -173,6 +194,7 @@ theorem toGHSpace_eq_toGHSpace_iff_isometryEquiv {X : Type u} [MetricSpace X] [C
by dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rfl
exact ⟨cast I ((f.trans e).trans g)⟩⟩
#align Gromov_Hausdorff.to_GH_space_eq_to_GH_space_iff_isometry_equiv GromovHausdorff.toGHSpace_eq_toGHSpace_iff_isometryEquiv
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
/-- Distance on `GH_space`: the distance between two nonempty compact spaces is the infimum
@@ -185,23 +207,28 @@ instance : Dist GHSpace
hausdorffDist (p.1 : Set ℓ_infty_ℝ) p.2) ''
{a | ⟦a⟧ = x} ×ˢ {b | ⟦b⟧ = y}
+#print GromovHausdorff.ghDist /-
/-- The Gromov-Hausdorff distance between two nonempty compact metric spaces, equal by definition to
the distance of the equivalence classes of these spaces in the Gromov-Hausdorff space. -/
-def gHDist (X : Type u) (Y : Type v) [MetricSpace X] [Nonempty X] [CompactSpace X] [MetricSpace Y]
+def ghDist (X : Type u) (Y : Type v) [MetricSpace X] [Nonempty X] [CompactSpace X] [MetricSpace Y]
[Nonempty Y] [CompactSpace Y] : ℝ :=
dist (toGHSpace X) (toGHSpace Y)
-#align Gromov_Hausdorff.GH_dist GromovHausdorff.gHDist
+#align Gromov_Hausdorff.GH_dist GromovHausdorff.ghDist
+-/
-theorem dist_gHDist (p q : GHSpace) : dist p q = gHDist p.rep q.rep := by
+#print GromovHausdorff.dist_ghDist /-
+theorem dist_ghDist (p q : GHSpace) : dist p q = ghDist p.rep q.rep := by
rw [GH_dist, p.to_GH_space_rep, q.to_GH_space_rep]
-#align Gromov_Hausdorff.dist_GH_dist GromovHausdorff.dist_gHDist
+#align Gromov_Hausdorff.dist_GH_dist GromovHausdorff.dist_ghDist
+-/
+#print GromovHausdorff.ghDist_le_hausdorffDist /-
/-- The Gromov-Hausdorff distance between two spaces is bounded by the Hausdorff distance
of isometric copies of the spaces, in any metric space. -/
-theorem gHDist_le_hausdorffDist {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty X]
+theorem ghDist_le_hausdorffDist {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty X]
{Y : Type v} [MetricSpace Y] [CompactSpace Y] [Nonempty Y] {γ : Type w} [MetricSpace γ]
{Φ : X → γ} {Ψ : Y → γ} (ha : Isometry Φ) (hb : Isometry Ψ) :
- gHDist X Y ≤ hausdorffDist (range Φ) (range Ψ) :=
+ ghDist X Y ≤ hausdorffDist (range Φ) (range Ψ) :=
by
/- For the proof, we want to embed `γ` in `ℓ^∞(ℝ)`, to say that the Hausdorff distance is realized
in `ℓ^∞(ℝ)` and therefore bounded below by the Gromov-Hausdorff-distance. However, `γ` is not
@@ -254,13 +281,15 @@ theorem gHDist_le_hausdorffDist {X : Type u} [MetricSpace X] [CompactSpace X] [N
apply (mem_image _ _ _).2
exists (⟨A, B⟩ : nonempty_compacts ℓ_infty_ℝ × nonempty_compacts ℓ_infty_ℝ)
simp [AX, BY]
-#align Gromov_Hausdorff.GH_dist_le_Hausdorff_dist GromovHausdorff.gHDist_le_hausdorffDist
+#align Gromov_Hausdorff.GH_dist_le_Hausdorff_dist GromovHausdorff.ghDist_le_hausdorffDist
+-/
+#print GromovHausdorff.hausdorffDist_optimal /-
/-- The optimal coupling constructed above realizes exactly the Gromov-Hausdorff distance,
essentially by design. -/
theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty X]
{Y : Type v} [MetricSpace Y] [CompactSpace Y] [Nonempty Y] :
- hausdorffDist (range (optimalGHInjl X Y)) (range (optimalGHInjr X Y)) = gHDist X Y :=
+ hausdorffDist (range (optimalGHInjl X Y)) (range (optimalGHInjr X Y)) = ghDist X Y :=
by
inhabit X; inhabit Y
/- we only need to check the inequality `≤`, as the other one follows from the previous lemma.
@@ -408,14 +437,16 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
exact B p q hp hq
· exact GH_dist_le_Hausdorff_dist (isometry_optimal_GH_injl X Y) (isometry_optimal_GH_injr X Y)
#align Gromov_Hausdorff.Hausdorff_dist_optimal GromovHausdorff.hausdorffDist_optimal
+-/
+#print GromovHausdorff.ghDist_eq_hausdorffDist /-
/-- The Gromov-Hausdorff distance can also be realized by a coupling in `ℓ^∞(ℝ)`, by embedding
the optimal coupling through its Kuratowski embedding. -/
-theorem gHDist_eq_hausdorffDist (X : Type u) [MetricSpace X] [CompactSpace X] [Nonempty X]
+theorem ghDist_eq_hausdorffDist (X : Type u) [MetricSpace X] [CompactSpace X] [Nonempty X]
(Y : Type v) [MetricSpace Y] [CompactSpace Y] [Nonempty Y] :
∃ Φ : X → ℓ_infty_ℝ,
∃ Ψ : Y → ℓ_infty_ℝ,
- Isometry Φ ∧ Isometry Ψ ∧ gHDist X Y = hausdorffDist (range Φ) (range Ψ) :=
+ Isometry Φ ∧ Isometry Ψ ∧ ghDist X Y = hausdorffDist (range Φ) (range Ψ) :=
by
let F := kuratowskiEmbedding (optimal_GH_coupling X Y)
let Φ := F ∘ optimal_GH_injl X Y
@@ -426,7 +457,8 @@ theorem gHDist_eq_hausdorffDist (X : Type u) [MetricSpace X] [CompactSpace X] [N
· rw [← image_univ, ← image_univ, image_comp F, image_univ, image_comp F (optimal_GH_injr X Y),
image_univ, ← Hausdorff_dist_optimal]
exact (Hausdorff_dist_image (kuratowskiEmbedding.isometry _)).symm
-#align Gromov_Hausdorff.GH_dist_eq_Hausdorff_dist GromovHausdorff.gHDist_eq_hausdorffDist
+#align Gromov_Hausdorff.GH_dist_eq_Hausdorff_dist GromovHausdorff.ghDist_eq_hausdorffDist
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
@@ -547,12 +579,14 @@ end GHSpace
--section
end GromovHausdorff
+#print TopologicalSpace.NonemptyCompacts.toGHSpace /-
/-- In particular, nonempty compacts of a metric space map to `GH_space`. We register this
in the topological_space namespace to take advantage of the notation `p.to_GH_space`. -/
def TopologicalSpace.NonemptyCompacts.toGHSpace {X : Type u} [MetricSpace X]
(p : NonemptyCompacts X) : GromovHausdorff.GHSpace :=
GromovHausdorff.toGHSpace p
#align topological_space.nonempty_compacts.to_GH_space TopologicalSpace.NonemptyCompacts.toGHSpace
+-/
open TopologicalSpace
@@ -562,7 +596,8 @@ section NonemptyCompacts
variable {X : Type u} [MetricSpace X]
-theorem GH_dist_le_nonemptyCompacts_dist (p q : NonemptyCompacts X) :
+#print GromovHausdorff.ghDist_le_nonemptyCompacts_dist /-
+theorem ghDist_le_nonemptyCompacts_dist (p q : NonemptyCompacts X) :
dist p.toGHSpace q.toGHSpace ≤ dist p q :=
by
have ha : Isometry (coe : p → X) := isometry_subtype_coe
@@ -572,17 +607,22 @@ theorem GH_dist_le_nonemptyCompacts_dist (p q : NonemptyCompacts X) :
have J : ↑q = range (coe : q → X) := subtype.range_coe_subtype.symm
rw [A, I, J]
exact GH_dist_le_Hausdorff_dist ha hb
-#align Gromov_Hausdorff.GH_dist_le_nonempty_compacts_dist GromovHausdorff.GH_dist_le_nonemptyCompacts_dist
+#align Gromov_Hausdorff.GH_dist_le_nonempty_compacts_dist GromovHausdorff.ghDist_le_nonemptyCompacts_dist
+-/
+#print GromovHausdorff.toGHSpace_lipschitz /-
theorem toGHSpace_lipschitz :
LipschitzWith 1 (NonemptyCompacts.toGHSpace : NonemptyCompacts X → GHSpace) :=
- LipschitzWith.mk_one GH_dist_le_nonemptyCompacts_dist
+ LipschitzWith.mk_one ghDist_le_nonemptyCompacts_dist
#align Gromov_Hausdorff.to_GH_space_lipschitz GromovHausdorff.toGHSpace_lipschitz
+-/
+#print GromovHausdorff.toGHSpace_continuous /-
theorem toGHSpace_continuous :
Continuous (NonemptyCompacts.toGHSpace : NonemptyCompacts X → GHSpace) :=
toGHSpace_lipschitz.Continuous
#align Gromov_Hausdorff.to_GH_space_continuous GromovHausdorff.toGHSpace_continuous
+-/
end NonemptyCompacts
@@ -599,12 +639,13 @@ variable {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty X] {Y : Type v}
-- we want to ignore these instances in the following theorem
attribute [local instance 10] Sum.topologicalSpace Sum.uniformSpace
+#print GromovHausdorff.ghDist_le_of_approx_subsets /-
/-- If there are subsets which are `ε₁`-dense and `ε₃`-dense in two spaces, and
isometric up to `ε₂`, then the Gromov-Hausdorff distance between the spaces is bounded by
`ε₁ + ε₂/2 + ε₃`. -/
-theorem gHDist_le_of_approx_subsets {s : Set X} (Φ : s → Y) {ε₁ ε₂ ε₃ : ℝ}
+theorem ghDist_le_of_approx_subsets {s : Set X} (Φ : s → Y) {ε₁ ε₂ ε₃ : ℝ}
(hs : ∀ x : X, ∃ y ∈ s, dist x y ≤ ε₁) (hs' : ∀ x : Y, ∃ y : s, dist x (Φ y) ≤ ε₃)
- (H : ∀ x y : s, |dist x y - dist (Φ x) (Φ y)| ≤ ε₂) : gHDist X Y ≤ ε₁ + ε₂ / 2 + ε₃ :=
+ (H : ∀ x y : s, |dist x y - dist (Φ x) (Φ y)| ≤ ε₂) : ghDist X Y ≤ ε₁ + ε₂ / 2 + ε₃ :=
by
refine' le_of_forall_pos_le_add fun δ δ0 => _
rcases exists_mem_of_nonempty X with ⟨xX, _⟩
@@ -680,7 +721,8 @@ theorem gHDist_le_of_approx_subsets {s : Set X} (Φ : s → Y) {ε₁ ε₂ ε
rcases hs' x with ⟨y, Dy⟩
exact ⟨Φ y, mem_range_self _, Dy⟩
linarith
-#align Gromov_Hausdorff.GH_dist_le_of_approx_subsets GromovHausdorff.gHDist_le_of_approx_subsets
+#align Gromov_Hausdorff.GH_dist_le_of_approx_subsets GromovHausdorff.ghDist_le_of_approx_subsets
+-/
end
@@ -814,6 +856,7 @@ instance : SecondCountableTopology GHSpace :=
_ ≤ ε + ε / 2 + ε := main
_ = δ := by simp only [ε]; ring
+#print GromovHausdorff.totallyBounded /-
/-- Compactness criterion: a closed set of compact metric spaces is compact if the spaces have
a uniformly bounded diameter, and for all `ε` the number of balls of radius `ε` required
to cover the spaces is uniformly bounded. This is an equivalence, but we only prove the
@@ -986,6 +1029,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
_ = δ / 2 := by simp only [ε, one_div]; ring
_ < δ := half_lt_self δpos
#align Gromov_Hausdorff.totally_bounded GromovHausdorff.totallyBounded
+-/
section Complete
@@ -1005,6 +1049,7 @@ set of nonempty compact subsets), they converge to a limit `L`. This is the none
compact metric space we are looking for. -/
variable (X : ℕ → Type) [∀ n, MetricSpace (X n)] [∀ n, CompactSpace (X n)] [∀ n, Nonempty (X n)]
+#print GromovHausdorff.AuxGluingStruct /-
/-- Auxiliary structure used to glue metric spaces below, recording an isometric embedding
of a type `A` in another metric space. -/
structure AuxGluingStruct (A : Type) [MetricSpace A] : Type 1 where
@@ -1013,6 +1058,7 @@ structure AuxGluingStruct (A : Type) [MetricSpace A] : Type 1 where
embed : A → space
isom : Isometry embed
#align Gromov_Hausdorff.aux_gluing_struct GromovHausdorff.AuxGluingStruct
+-/
attribute [local instance] aux_gluing_struct.metric
@@ -1022,6 +1068,7 @@ instance (A : Type) [MetricSpace A] : Inhabited (AuxGluingStruct A) :=
embed := id
isom := fun x y => rfl }⟩
+#print GromovHausdorff.auxGluing /-
/-- Auxiliary sequence of metric spaces, containing copies of `X 0`, ..., `X n`, where each
`X i` is glued to `X (i+1)` in an optimal way. The space at step `n+1` is obtained from the space
at step `n` by adding `X (n+1)`, glued in an optimal way to the `X n` already sitting there. -/
@@ -1033,6 +1080,7 @@ def auxGluing (n : ℕ) : AuxGluingStruct (X n) :=
toGlueR Y.isom (isometry_optimalGHInjl (X n) (X (n + 1))) ∘ optimalGHInjr (X n) (X (n + 1))
isom := (toGlueR_isometry _ _).comp (isometry_optimalGHInjr (X n) (X (n + 1))) }
#align Gromov_Hausdorff.aux_gluing GromovHausdorff.auxGluing
+-/
/-- The Gromov-Hausdorff space is complete. -/
instance : CompleteSpace GHSpace :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/728ef9dbb281241906f25cbeb30f90d83e0bb451
@@ -721,7 +721,7 @@ instance : SecondCountableTopology GHSpace :=
the fact that `N p = N q`, this constructs `Ψ` between `s p` and `s q`, and then
composing with the canonical inclusion we get `Φ`. -/
have Npq : N p = N q := (Sigma.mk.inj_iff.1 hpq).1
- let Ψ : s p → s q := fun x => (E q).symm (Fin.cast Npq ((E p) x))
+ let Ψ : s p → s q := fun x => (E q).symm (Fin.castIso Npq ((E p) x))
let Φ : s p → q.rep := fun x => Ψ x
-- Use the almost isometry `Φ` to show that `p.rep` and `q.rep`
-- are within controlled Gromov-Hausdorff distance.
@@ -747,7 +747,7 @@ instance : SecondCountableTopology GHSpace :=
let z := (E p).symm ⟨i, hip⟩
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
- have C2 : Fin.cast Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
+ have C2 : Fin.castIso Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ := by rw [ihi_eq]; exact (E q).symm_apply_apply ⟨y, ys⟩
have : Φ z = y := by simp only [Φ, Ψ]; rw [C1, C2, C3]; rfl
rw [this]
@@ -763,13 +763,13 @@ instance : SecondCountableTopology GHSpace :=
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
have hiq : i < N q := by rwa [Npq] at hip
- have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
+ have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
have hjq : j < N q := by rwa [Npq] at hjp
have j' : j = ((E q) (Ψ y)).1 := by
- simp only [Equiv.apply_symm_apply, Fin.val_eq_coe, Fin.coe_cast]
+ simp only [Equiv.apply_symm_apply, Fin.val_eq_coe, Fin.coe_castIso]
-- Express `dist x y` in terms of `F p`
have : (F p).2 ((E p) x) ((E p) y) = floor (ε⁻¹ * dist x y) := by
simp only [F, (E p).symm_apply_apply]
@@ -867,7 +867,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
-- It remains to show that if `F p = F q`, then `p` and `q` are `ε`-close
rintro ⟨p, pt⟩ ⟨q, qt⟩ hpq
have Npq : N p = N q := Fin.ext_iff.1 (Sigma.mk.inj_iff.1 hpq).1
- let Ψ : s p → s q := fun x => (E q).symm (Fin.cast Npq ((E p) x))
+ let Ψ : s p → s q := fun x => (E q).symm (Fin.castIso Npq ((E p) x))
let Φ : s p → q.rep := fun x => Ψ x
have main : GH_dist p.rep q.rep ≤ ε + ε / 2 + ε :=
by
@@ -894,7 +894,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
let z := (E p).symm ⟨i, hip⟩
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
- have C2 : Fin.cast Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
+ have C2 : Fin.castIso Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ := by rw [ihi_eq]; exact (E q).symm_apply_apply ⟨y, ys⟩
have : Φ z = y := by simp only [Φ, Ψ]; rw [C1, C2, C3]; rfl
rw [this]
@@ -910,12 +910,12 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
have hiq : i < N q := by rwa [Npq] at hip
- have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
+ have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
have hjq : j < N q := by rwa [Npq] at hjp
- have j' : j = (E q) (Ψ y) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
+ have j' : j = (E q) (Ψ y) := by simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
-- Express `dist x y` in terms of `F p`
have Ap : ((F p).2 ⟨i, hip⟩ ⟨j, hjp⟩).1 = ⌊ε⁻¹ * dist x y⌋₊ :=
calc
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -49,7 +49,6 @@ noncomputable section
open scoped Classical Topology ENNReal
--- mathport name: exprℓ_infty_ℝ
local notation "ℓ_infty_ℝ" => lp (fun n : ℕ => ℝ) ∞
universe u v w
mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0
@@ -307,7 +307,6 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
diam (univ : Set Y) :=
by rw [DΦ, DΨ]; apply add_le_add (add_le_add le_rfl (le_of_lt dy)) le_rfl
_ = 2 * diam (univ : Set X) + 1 + 2 * diam (univ : Set Y) := by ring
-
let f : Sum X Y → ℓ_infty_ℝ := fun x =>
match x with
| inl y => Φ y
@@ -324,13 +323,11 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
calc
F (inl x, inl y) = dist (Φ x) (Φ y) := rfl
_ = dist x y := Φisom.dist_eq x y
-
·
exact fun x y =>
calc
F (inr x, inr y) = dist (Ψ x) (Ψ y) := rfl
_ = dist x y := Ψisom.dist_eq x y
-
· exact fun x y => dist_comm _ _
· exact fun x y z => dist_triangle _ _ _
·
@@ -348,7 +345,6 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
rw [Φrange, Ψrange]
exact (p ⊔ q).IsCompact.Bounded
_ ≤ 2 * diam (univ : Set X) + 1 + 2 * diam (univ : Set Y) := I
-
let Fb := candidates_b_of_candidates F Fgood
have : Hausdorff_dist (range (optimal_GH_injl X Y)) (range (optimal_GH_injr X Y)) ≤ HD Fb :=
Hausdorff_dist_optimal_le_HD _ _ (candidates_b_of_candidates_mem F Fgood)
@@ -369,7 +365,6 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
_ = dist (Φ x) (Ψ y) := rfl
_ = dist (f (inl x)) z := by rw [hy]
_ ≤ r := le_of_lt hz
-
have I2 : ∀ y : Y, (⨅ x, Fb (inl x, inr y)) ≤ r :=
by
intro y
@@ -386,7 +381,6 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
_ = dist (Φ x) (Ψ y) := rfl
_ = dist z (f (inr y)) := by rw [hx]
_ ≤ r := le_of_lt hz
-
simp only [HD, ciSup_le I1, ciSup_le I2, max_le_iff, and_self_iff]
/- Get the same inequality for any coupling. If the coupling is quite good, the desired
inequality has been proved above. If it is bad, then the inequality is obvious. -/
@@ -408,7 +402,6 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
Hausdorff_dist_optimal_le_HD _ _ candidates_b_dist_mem_candidates_b
_ ≤ diam (univ : Set X) + 1 + diam (univ : Set Y) := HD_candidates_b_dist_le
_ ≤ Hausdorff_dist (p : Set ℓ_infty_ℝ) q := not_lt.1 h
-
refine' le_antisymm _ _
· apply le_csInf
· refine' (Set.Nonempty.prod _ _).image _ <;> exact ⟨_, rfl⟩
@@ -549,7 +542,6 @@ instance : MetricSpace GHSpace where
_ = dist (to_GH_space X) (to_GH_space Y) + dist (to_GH_space Y) (to_GH_space Z) := by
rw [Hausdorff_dist_optimal, Hausdorff_dist_optimal, GH_dist, GH_dist]
_ = dist x y + dist y z := by rw [x.to_GH_space_rep, y.to_GH_space_rep, z.to_GH_space_rep]
-
end GHSpace
@@ -625,7 +617,6 @@ theorem gHDist_le_of_approx_subsets {s : Set X} (Φ : s → Y) {ε₁ ε₂ ε
calc
|dist p q - dist (Φ p) (Φ q)| ≤ ε₂ := H p q
_ ≤ 2 * (ε₂ / 2 + δ) := by linarith
-
-- glue `X` and `Y` along the almost matching subsets
letI : MetricSpace (Sum X Y) :=
glue_metric_approx (fun x : s => (x : X)) (fun x => Φ x) (ε₂ / 2 + δ) (by linarith) this
@@ -812,7 +803,6 @@ instance : SecondCountableTopology GHSpace :=
(abs_mul _ _).symm
_ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| := by congr; ring
_ ≤ 1 := le_of_lt (abs_sub_lt_one_of_floor_eq_floor this)
-
calc
|dist x y - dist (Ψ x) (Ψ y)| = ε * ε⁻¹ * |dist x y - dist (Ψ x) (Ψ y)| := by
rw [mul_inv_cancel (ne_of_gt εpos), one_mul]
@@ -820,12 +810,10 @@ instance : SecondCountableTopology GHSpace :=
rw [abs_of_nonneg (le_of_lt (inv_pos.2 εpos)), mul_assoc]
_ ≤ ε * 1 := (mul_le_mul_of_nonneg_left I (le_of_lt εpos))
_ = ε := mul_one _
-
calc
dist p q = GH_dist p.rep q.rep := dist_GH_dist p q
_ ≤ ε + ε / 2 + ε := main
_ = δ := by simp only [ε]; ring
-
/-- Compactness criterion: a closed set of compact metric spaces is compact if the spaces have
a uniformly bounded diameter, and for all `ε` the number of balls of radius `ε` required
@@ -942,7 +930,6 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
refine'
le_trans (dist_le_diam_of_mem is_compact_univ.bounded (mem_univ _) (mem_univ _)) _
exact hdiam p pt
-
-- Express `dist (Φ x) (Φ y)` in terms of `F q`
have Aq : ((F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩).1 = ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋₊ :=
calc
@@ -957,7 +944,6 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
refine'
le_trans (dist_le_diam_of_mem is_compact_univ.bounded (mem_univ _) (mem_univ _)) _
exact hdiam q qt
-
-- use the equality between `F p` and `F q` to deduce that the distances have equal
-- integer parts
have : ((F p).2 ⟨i, hip⟩ ⟨j, hjp⟩).1 = ((F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩).1 :=
@@ -988,7 +974,6 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
(abs_mul _ _).symm
_ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| := by congr; ring
_ ≤ 1 := le_of_lt (abs_sub_lt_one_of_floor_eq_floor this)
-
calc
|dist x y - dist (Ψ x) (Ψ y)| = ε * ε⁻¹ * |dist x y - dist (Ψ x) (Ψ y)| := by
rw [mul_inv_cancel (ne_of_gt εpos), one_mul]
@@ -996,13 +981,11 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
rw [abs_of_nonneg (le_of_lt (inv_pos.2 εpos)), mul_assoc]
_ ≤ ε * 1 := (mul_le_mul_of_nonneg_left I (le_of_lt εpos))
_ = ε := mul_one _
-
calc
dist p q = GH_dist p.rep q.rep := dist_GH_dist p q
_ ≤ ε + ε / 2 + ε := main
_ = δ / 2 := by simp only [ε, one_div]; ring
_ < δ := half_lt_self δpos
-
#align Gromov_Hausdorff.totally_bounded GromovHausdorff.totallyBounded
section Complete
mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297
@@ -184,7 +184,7 @@ instance : Dist GHSpace
sInf <|
(fun p : NonemptyCompacts ℓ_infty_ℝ × NonemptyCompacts ℓ_infty_ℝ =>
hausdorffDist (p.1 : Set ℓ_infty_ℝ) p.2) ''
- { a | ⟦a⟧ = x } ×ˢ { b | ⟦b⟧ = y }
+ {a | ⟦a⟧ = x} ×ˢ {b | ⟦b⟧ = y}
/-- The Gromov-Hausdorff distance between two nonempty compact metric spaces, equal by definition to
the distance of the equivalence classes of these spaces in the Gromov-Hausdorff space. -/
@@ -457,11 +457,11 @@ instance : MetricSpace GHSpace where
have A :
(fun p : nonempty_compacts ℓ_infty_ℝ × nonempty_compacts ℓ_infty_ℝ =>
Hausdorff_dist (p.1 : Set ℓ_infty_ℝ) p.2) ''
- { a | ⟦a⟧ = x } ×ˢ { b | ⟦b⟧ = y } =
+ {a | ⟦a⟧ = x} ×ˢ {b | ⟦b⟧ = y} =
(fun p : nonempty_compacts ℓ_infty_ℝ × nonempty_compacts ℓ_infty_ℝ =>
Hausdorff_dist (p.1 : Set ℓ_infty_ℝ) p.2) ∘
Prod.swap ''
- { a | ⟦a⟧ = x } ×ˢ { b | ⟦b⟧ = y } :=
+ {a | ⟦a⟧ = x} ×ˢ {b | ⟦b⟧ = y} :=
by congr; funext; simp only [comp_app, Prod.fst_swap, Prod.snd_swap]; rw [Hausdorff_dist_comm]
simp only [dist, A, image_comp, image_swap_prod]
eq_of_dist_eq_zero x y hxy :=
@@ -1145,7 +1145,7 @@ instance : CompleteSpace GHSpace :=
rw [nonempty_compacts.to_GH_space, ← (u n).toGHSpace_rep,
to_GH_space_eq_to_GH_space_iff_isometry_equiv]
constructor
- convert(isom n).isometryEquivOnRange.symm
+ convert (isom n).isometryEquivOnRange.symm
-- Finally, we have proved the convergence of `u n`
exact ⟨L.to_GH_space, by simpa only [this] using M⟩
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -296,7 +296,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
p.is_compact.bounded q.is_compact.bounded)
rcases this with ⟨y, hy, dy⟩
rcases mem_range.1 hy with ⟨z, hzy⟩
- rw [← hzy] at dy
+ rw [← hzy] at dy
have DΦ : diam (range Φ) = diam (univ : Set X) := Φisom.diam_range
have DΨ : diam (range Ψ) = diam (univ : Set Y) := Ψisom.diam_range
calc
@@ -361,7 +361,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
(Hausdorff_edist_ne_top_of_nonempty_of_bounded p.nonempty q.nonempty p.is_compact.bounded
q.is_compact.bounded) with
⟨z, zq, hz⟩
- have : z ∈ range Ψ := by rwa [← Ψrange] at zq
+ have : z ∈ range Ψ := by rwa [← Ψrange] at zq
rcases mem_range.1 this with ⟨y, hy⟩
calc
(⨅ y, Fb (inl x, inr y)) ≤ Fb (inl x, inr y) :=
@@ -378,7 +378,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
(Hausdorff_edist_ne_top_of_nonempty_of_bounded p.nonempty q.nonempty p.is_compact.bounded
q.is_compact.bounded) with
⟨z, zq, hz⟩
- have : z ∈ range Φ := by rwa [← Φrange] at zq
+ have : z ∈ range Φ := by rwa [← Φrange] at zq
rcases mem_range.1 this with ⟨x, hx⟩
calc
(⨅ x, Fb (inl x, inr y)) ≤ Fb (inl x, inr y) :=
@@ -462,8 +462,7 @@ instance : MetricSpace GHSpace where
Hausdorff_dist (p.1 : Set ℓ_infty_ℝ) p.2) ∘
Prod.swap ''
{ a | ⟦a⟧ = x } ×ˢ { b | ⟦b⟧ = y } :=
- by congr ; funext; simp only [comp_app, Prod.fst_swap, Prod.snd_swap];
- rw [Hausdorff_dist_comm]
+ by congr; funext; simp only [comp_app, Prod.fst_swap, Prod.snd_swap]; rw [Hausdorff_dist_comm]
simp only [dist, A, image_comp, image_swap_prod]
eq_of_dist_eq_zero x y hxy :=
by
@@ -471,7 +470,7 @@ instance : MetricSpace GHSpace where
is realized by some coupling. In this coupling, the two spaces are at zero Hausdorff distance,
i.e., they coincide. Therefore, the original spaces are isometric. -/
rcases GH_dist_eq_Hausdorff_dist x.rep y.rep with ⟨Φ, Ψ, Φisom, Ψisom, DΦΨ⟩
- rw [← dist_GH_dist, hxy] at DΦΨ
+ rw [← dist_GH_dist, hxy] at DΦΨ
have : range Φ = range Ψ :=
by
have hΦ : IsCompact (range Φ) := isCompact_range Φisom.continuous
@@ -664,7 +663,7 @@ theorem gHDist_le_of_approx_subsets {s : Set X} (Φ : s → Y) {ε₁ ε₂ ε
have : 0 ≤ ε₁ := le_trans dist_nonneg Dxs
refine'
Hausdorff_dist_le_of_mem_dist this (fun x hx => hs x) fun x hx =>
- ⟨x, mem_univ _, by simpa only [dist_self] ⟩
+ ⟨x, mem_univ _, by simpa only [dist_self]⟩
have : Hausdorff_dist (Fl '' s) (Fr '' range Φ) ≤ ε₂ / 2 + δ :=
by
refine' Hausdorff_dist_le_of_mem_dist (by linarith) _ _
@@ -686,7 +685,7 @@ theorem gHDist_le_of_approx_subsets {s : Set X} (Φ : s → Y) {ε₁ ε₂ ε
rcases hs' xY with ⟨xs', Dxs'⟩
have : 0 ≤ ε₃ := le_trans dist_nonneg Dxs'
refine'
- Hausdorff_dist_le_of_mem_dist this (fun x hx => ⟨x, mem_univ _, by simpa only [dist_self] ⟩)
+ Hausdorff_dist_le_of_mem_dist this (fun x hx => ⟨x, mem_univ _, by simpa only [dist_self]⟩)
fun x _ => _
rcases hs' x with ⟨y, Dy⟩
exact ⟨Φ y, mem_range_self _, Dy⟩
@@ -720,9 +719,9 @@ instance : SecondCountableTopology GHSpace :=
let E := fun p : GH_space => e p (s p) (hs p).1
-- A function `F` associating to `p : GH_space` the data of all distances between points
-- in the `ε`-dense set `s p`.
- let F : GH_space → Σn : ℕ, Fin n → Fin n → ℤ := fun p =>
+ let F : GH_space → Σ n : ℕ, Fin n → Fin n → ℤ := fun p =>
⟨N p, fun a b => ⌊ε⁻¹ * dist ((E p).symm a) ((E p).symm b)⌋⟩
- refine' ⟨Σn, Fin n → Fin n → ℤ, by infer_instance, F, fun p q hpq => _⟩
+ refine' ⟨Σ n, Fin n → Fin n → ℤ, by infer_instance, F, fun p q hpq => _⟩
/- As the target space of F is countable, it suffices to show that two points
`p` and `q` with `F p = F q` are at distance `≤ δ`.
For this, we construct a map `Φ` from `s p ⊆ p.rep` (representing `p`)
@@ -739,7 +738,7 @@ instance : SecondCountableTopology GHSpace :=
have main : GH_dist p.rep q.rep ≤ ε + ε / 2 + ε :=
by
refine' GH_dist_le_of_approx_subsets Φ _ _ _
- show ∀ x : p.rep, ∃ (y : p.rep)(H : y ∈ s p), dist x y ≤ ε
+ show ∀ x : p.rep, ∃ (y : p.rep) (H : y ∈ s p), dist x y ≤ ε
· -- by construction, `s p` is `ε`-dense
intro x
have : x ∈ ⋃ y ∈ s p, ball y ε := (hs p).2 (mem_univ _)
@@ -754,7 +753,7 @@ instance : SecondCountableTopology GHSpace :=
let hi := ((E q) ⟨y, ys⟩).is_lt
have ihi_eq : (⟨i, hi⟩ : Fin (N q)) = (E q) ⟨y, ys⟩ := by rw [Fin.ext_iff, Fin.val_mk]
have hiq : i < N q := hi
- have hip : i < N p := by rwa [Npq.symm] at hiq
+ have hip : i < N p := by rwa [Npq.symm] at hiq
let z := (E p).symm ⟨i, hip⟩
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
@@ -773,12 +772,12 @@ instance : SecondCountableTopology GHSpace :=
-- introduce `i`, that codes both `x` and `Φ x` in `fin (N p) = fin (N q)`
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
- have hiq : i < N q := by rwa [Npq] at hip
+ have hiq : i < N q := by rwa [Npq] at hip
have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
- have hjq : j < N q := by rwa [Npq] at hjp
+ have hjq : j < N q := by rwa [Npq] at hjp
have j' : j = ((E q) (Ψ y)).1 := by
simp only [Equiv.apply_symm_apply, Fin.val_eq_coe, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
@@ -790,7 +789,7 @@ instance : SecondCountableTopology GHSpace :=
have : (F q).2 ((E q) (Ψ x)) ((E q) (Ψ y)) = floor (ε⁻¹ * dist (Ψ x) (Ψ y)) := by
simp only [F, (E q).symm_apply_apply]
have Aq : (F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩ = floor (ε⁻¹ * dist (Ψ x) (Ψ y)) := by rw [← this];
- congr <;> apply Fin.ext_iff.2 <;> [exact i';exact j']
+ congr <;> apply Fin.ext_iff.2 <;> [exact i'; exact j']
-- use the equality between `F p` and `F q` to deduce that the distances have equal
-- integer parts
have : (F p).2 ⟨i, hip⟩ ⟨j, hjp⟩ = (F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩ :=
@@ -800,18 +799,18 @@ instance : SecondCountableTopology GHSpace :=
-- then `subst`
revert hiq hjq
change N q with (F q).1
- generalize F q = f at hpq⊢
+ generalize F q = f at hpq ⊢
subst hpq
intros
rfl
- rw [Ap, Aq] at this
+ rw [Ap, Aq] at this
-- deduce that the distances coincide up to `ε`, by a straightforward computation
-- that should be automated
have I :=
calc
|ε⁻¹| * |dist x y - dist (Ψ x) (Ψ y)| = |ε⁻¹ * (dist x y - dist (Ψ x) (Ψ y))| :=
(abs_mul _ _).symm
- _ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| := by congr ; ring
+ _ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| := by congr; ring
_ ≤ 1 := le_of_lt (abs_sub_lt_one_of_floor_eq_floor this)
calc
@@ -850,7 +849,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
rcases Metric.tendsto_atTop.1 ulim ε εpos with ⟨n, hn⟩
have u_le_ε : u n ≤ ε := by
have := hn n le_rfl
- simp only [Real.dist_eq, add_zero, sub_eq_add_neg, neg_zero] at this
+ simp only [Real.dist_eq, add_zero, sub_eq_add_neg, neg_zero] at this
exact le_of_lt (lt_of_le_of_lt (le_abs_self _) this)
-- construct a finite subset `s p` of `p` which is `ε`-dense and has cardinal `≤ K n`
have :
@@ -864,7 +863,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
use ∅, 0, bot_le, choice this
· rcases hcov _ (Set.not_not_mem.1 hp) n with ⟨s, ⟨scard, scover⟩⟩
rcases Cardinal.lt_aleph0.1 (lt_of_le_of_lt scard (Cardinal.nat_lt_aleph0 _)) with ⟨N, hN⟩
- rw [hN, Cardinal.natCast_le] at scard
+ rw [hN, Cardinal.natCast_le] at scard
have : Cardinal.mk s = Cardinal.mk (Fin N) := by rw [hN, Cardinal.mk_fin]
cases' Quotient.exact this with E
use s, N, scard, E
@@ -873,7 +872,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
-- Define a function `F` taking values in a finite type and associating to `p` enough data
-- to reconstruct it up to `ε`, namely the (discretized) distances between elements of `s p`.
let M := ⌊ε⁻¹ * max C 0⌋₊
- let F : GH_space → Σk : Fin (K n).succ, Fin k → Fin k → Fin M.succ := fun p =>
+ let F : GH_space → Σ k : Fin (K n).succ, Fin k → Fin k → Fin M.succ := fun p =>
⟨⟨N p, lt_of_le_of_lt (hN p) (Nat.lt_succ_self _)⟩, fun a b =>
⟨min M ⌊ε⁻¹ * dist ((E p).symm a) ((E p).symm b)⌋₊,
(min_le_left _ _).trans_lt (Nat.lt_succ_self _)⟩⟩
@@ -889,7 +888,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
-- in `q`, and `s p` and `s q` are almost isometric. Then closeness follows
-- from `GH_dist_le_of_approx_subsets`
refine' GH_dist_le_of_approx_subsets Φ _ _ _
- show ∀ x : p.rep, ∃ (y : p.rep)(H : y ∈ s p), dist x y ≤ ε
+ show ∀ x : p.rep, ∃ (y : p.rep) (H : y ∈ s p), dist x y ≤ ε
· -- by construction, `s p` is `ε`-dense
intro x
have : x ∈ ⋃ y ∈ s p, ball y (u n) := (hs p pt) (mem_univ _)
@@ -904,7 +903,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
let hi := ((E q) ⟨y, ys⟩).2
have ihi_eq : (⟨i, hi⟩ : Fin (N q)) = (E q) ⟨y, ys⟩ := by rw [Fin.ext_iff, Fin.val_mk]
have hiq : i < N q := hi
- have hip : i < N p := by rwa [Npq.symm] at hiq
+ have hip : i < N p := by rwa [Npq.symm] at hiq
let z := (E p).symm ⟨i, hip⟩
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
@@ -923,12 +922,12 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
-- introduce `i`, that codes both `x` and `Φ x` in `fin (N p) = fin (N q)`
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
- have hiq : i < N q := by rwa [Npq] at hip
+ have hiq : i < N q := by rwa [Npq] at hip
have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
- have hjq : j < N q := by rwa [Npq] at hjp
+ have hjq : j < N q := by rwa [Npq] at hjp
have j' : j = (E q) (Ψ y) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
have Ap : ((F p).2 ⟨i, hip⟩ ⟨j, hjp⟩).1 = ⌊ε⁻¹ * dist x y⌋₊ :=
@@ -948,7 +947,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
have Aq : ((F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩).1 = ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋₊ :=
calc
((F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩).1 = ((F q).2 ((E q) (Ψ x)) ((E q) (Ψ y))).1 := by
- congr <;> apply Fin.ext_iff.2 <;> [exact i';exact j']
+ congr <;> apply Fin.ext_iff.2 <;> [exact i'; exact j']
_ = min M ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋₊ := by simp only [F, (E q).symm_apply_apply]
_ = ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋₊ :=
by
@@ -968,13 +967,13 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
-- then `subst`
revert hiq hjq
change N q with (F q).1
- generalize F q = f at hpq⊢
+ generalize F q = f at hpq ⊢
subst hpq
intros
rfl
have : ⌊ε⁻¹ * dist x y⌋ = ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋ :=
by
- rw [Ap, Aq] at this
+ rw [Ap, Aq] at this
have D : 0 ≤ ⌊ε⁻¹ * dist x y⌋ :=
floor_nonneg.2 (mul_nonneg (le_of_lt (inv_pos.2 εpos)) dist_nonneg)
have D' : 0 ≤ ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋ :=
@@ -987,7 +986,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
calc
|ε⁻¹| * |dist x y - dist (Ψ x) (Ψ y)| = |ε⁻¹ * (dist x y - dist (Ψ x) (Ψ y))| :=
(abs_mul _ _).symm
- _ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| := by congr ; ring
+ _ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| := by congr; ring
_ ≤ 1 := le_of_lt (abs_sub_lt_one_of_floor_eq_floor this)
calc
@@ -1111,7 +1110,7 @@ instance : CompleteSpace GHSpace :=
rw [← to_inductive_limit_commute I]
simp only [f]
rw [← to_glue_commute]
- rw [range_comp] at X2n
+ rw [range_comp] at X2n
have X2nsucc :
X2 n.succ =
range
@@ -1119,7 +1118,7 @@ instance : CompleteSpace GHSpace :=
Φ n.succ ∘ c n ∘ to_glue_r (Y n).isom (isometry_optimal_GH_injl (X n) (X n.succ))) ∘
optimal_GH_injr (X n) (X n.succ)) :=
by rfl
- rw [range_comp] at X2nsucc
+ rw [range_comp] at X2nsucc
rw [X2n, X2nsucc, Hausdorff_dist_image, Hausdorff_dist_optimal, ← dist_GH_dist]
· exact hu n n n.succ (le_refl n) (le_succ n)
· apply uniform_space.completion.coe_isometry.comp _
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -780,7 +780,7 @@ instance : SecondCountableTopology GHSpace :=
have hjp : j < N p := ((E p) y).2
have hjq : j < N q := by rwa [Npq] at hjp
have j' : j = ((E q) (Ψ y)).1 := by
- simp only [Equiv.apply_symm_apply, [anonymous], Fin.coe_cast]
+ simp only [Equiv.apply_symm_apply, Fin.val_eq_coe, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
have : (F p).2 ((E p) x) ((E p) y) = floor (ε⁻¹ * dist x y) := by
simp only [F, (E p).symm_apply_apply]
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -47,7 +47,7 @@ i.e., it is complete and second countable. We also prove the Gromov compactness
noncomputable section
-open Classical Topology ENNReal
+open scoped Classical Topology ENNReal
-- mathport name: exprℓ_infty_ℝ
local notation "ℓ_infty_ℝ" => lp (fun n : ℕ => ℝ) ∞
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -119,9 +119,7 @@ theorem eq_toGHSpace_iff {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty
isomΨ.isometry_equiv_on_range).symm
have E :
(range Ψ ≃ᵢ NonemptyCompacts.kuratowskiEmbedding X) = (p ≃ᵢ range (kuratowskiEmbedding X)) :=
- by
- dsimp only [NonemptyCompacts.kuratowskiEmbedding]
- rw [rangeΨ] <;> rfl
+ by dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rw [rangeΨ] <;> rfl
exact ⟨cast E f⟩
#align Gromov_Hausdorff.eq_to_GH_space_iff GromovHausdorff.eq_toGHSpace_iff
@@ -162,9 +160,7 @@ theorem toGHSpace_eq_toGHSpace_iff_isometryEquiv {X : Type u} [MetricSpace X] [C
have I :
(NonemptyCompacts.kuratowskiEmbedding X ≃ᵢ NonemptyCompacts.kuratowskiEmbedding Y) =
(range (kuratowskiEmbedding X) ≃ᵢ range (kuratowskiEmbedding Y)) :=
- by
- dsimp only [NonemptyCompacts.kuratowskiEmbedding]
- rfl
+ by dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rfl
have f := (kuratowskiEmbedding.isometry X).isometryEquivOnRange
have g := (kuratowskiEmbedding.isometry Y).isometryEquivOnRange.symm
exact ⟨f.trans <| (cast I e).trans g⟩, by
@@ -175,9 +171,7 @@ theorem toGHSpace_eq_toGHSpace_iff_isometryEquiv {X : Type u} [MetricSpace X] [C
have I :
(range (kuratowskiEmbedding X) ≃ᵢ range (kuratowskiEmbedding Y)) =
(NonemptyCompacts.kuratowskiEmbedding X ≃ᵢ NonemptyCompacts.kuratowskiEmbedding Y) :=
- by
- dsimp only [NonemptyCompacts.kuratowskiEmbedding]
- rfl
+ by dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rfl
exact ⟨cast I ((f.trans e).trans g)⟩⟩
#align Gromov_Hausdorff.to_GH_space_eq_to_GH_space_iff_isometry_equiv GromovHausdorff.toGHSpace_eq_toGHSpace_iff_isometryEquiv
@@ -224,12 +218,8 @@ theorem gHDist_le_hausdorffDist {X : Type u} [MetricSpace X] [CompactSpace X] [N
letI : MetricSpace (Subtype s) := by infer_instance
haveI : CompactSpace (Subtype s) := ⟨isCompact_iff_isCompact_univ.1 ‹IsCompact s›⟩
haveI : Nonempty (Subtype s) := ⟨Φ' xX⟩
- have ΦΦ' : Φ = Subtype.val ∘ Φ' := by
- funext
- rfl
- have ΨΨ' : Ψ = Subtype.val ∘ Ψ' := by
- funext
- rfl
+ have ΦΦ' : Φ = Subtype.val ∘ Φ' := by funext; rfl
+ have ΨΨ' : Ψ = Subtype.val ∘ Ψ' := by funext; rfl
have : Hausdorff_dist (range Φ) (range Ψ) = Hausdorff_dist (range Φ') (range Ψ') :=
by
rw [ΦΦ', ΨΨ', range_comp, range_comp]
@@ -273,8 +263,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
{Y : Type v} [MetricSpace Y] [CompactSpace Y] [Nonempty Y] :
hausdorffDist (range (optimalGHInjl X Y)) (range (optimalGHInjr X Y)) = gHDist X Y :=
by
- inhabit X
- inhabit Y
+ inhabit X; inhabit Y
/- we only need to check the inequality `≤`, as the other one follows from the previous lemma.
As the Gromov-Hausdorff distance is an infimum, we need to check that the Hausdorff distance
in the optimal coupling is smaller than the Hausdorff distance of any coupling.
@@ -316,9 +305,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
_ ≤
diam (univ : Set X) + (diam (univ : Set X) + 1 + diam (univ : Set Y)) +
diam (univ : Set Y) :=
- by
- rw [DΦ, DΨ]
- apply add_le_add (add_le_add le_rfl (le_of_lt dy)) le_rfl
+ by rw [DΦ, DΨ]; apply add_le_add (add_le_add le_rfl (le_of_lt dy)) le_rfl
_ = 2 * diam (univ : Set X) + 1 + 2 * diam (univ : Set Y) := by ring
let f : Sum X Y → ℓ_infty_ℝ := fun x =>
@@ -355,10 +342,8 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
by
intro z
cases z
- · apply mem_union_left
- apply mem_range_self
- · apply mem_union_right
- apply mem_range_self
+ · apply mem_union_left; apply mem_range_self
+ · apply mem_union_right; apply mem_range_self
refine' dist_le_diam_of_mem _ (A _) (A _)
rw [Φrange, Ψrange]
exact (p ⊔ q).IsCompact.Bounded
@@ -460,18 +445,13 @@ instance : MetricSpace GHSpace where
rcases exists_rep x with ⟨y, hy⟩
refine' le_antisymm _ _
· apply csInf_le
- ·
- exact
- ⟨0, by
- rintro b ⟨⟨u, v⟩, ⟨hu, hv⟩, rfl⟩
- exact Hausdorff_dist_nonneg⟩
+ · exact ⟨0, by rintro b ⟨⟨u, v⟩, ⟨hu, hv⟩, rfl⟩; exact Hausdorff_dist_nonneg⟩
· simp only [mem_image, mem_prod, mem_set_of_eq, Prod.exists]
exists y, y
simpa only [and_self_iff, Hausdorff_dist_self_zero, eq_self_iff_true, and_true_iff]
· apply le_csInf
· exact (nonempty.prod ⟨y, hy⟩ ⟨y, hy⟩).image _
- · rintro b ⟨⟨u, v⟩, ⟨hu, hv⟩, rfl⟩
- exact Hausdorff_dist_nonneg
+ · rintro b ⟨⟨u, v⟩, ⟨hu, hv⟩, rfl⟩; exact Hausdorff_dist_nonneg
dist_comm x y :=
by
have A :
@@ -482,10 +462,7 @@ instance : MetricSpace GHSpace where
Hausdorff_dist (p.1 : Set ℓ_infty_ℝ) p.2) ∘
Prod.swap ''
{ a | ⟦a⟧ = x } ×ˢ { b | ⟦b⟧ = y } :=
- by
- congr
- funext
- simp only [comp_app, Prod.fst_swap, Prod.snd_swap]
+ by congr ; funext; simp only [comp_app, Prod.fst_swap, Prod.snd_swap];
rw [Hausdorff_dist_comm]
simp only [dist, A, image_comp, image_swap_prod]
eq_of_dist_eq_zero x y hxy :=
@@ -782,14 +759,8 @@ instance : SecondCountableTopology GHSpace :=
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
have C2 : Fin.cast Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
- have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ :=
- by
- rw [ihi_eq]
- exact (E q).symm_apply_apply ⟨y, ys⟩
- have : Φ z = y := by
- simp only [Φ, Ψ]
- rw [C1, C2, C3]
- rfl
+ have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ := by rw [ihi_eq]; exact (E q).symm_apply_apply ⟨y, ys⟩
+ have : Φ z = y := by simp only [Φ, Ψ]; rw [C1, C2, C3]; rfl
rw [this]
exact le_of_lt hy
show ∀ x y : s p, |dist x y - dist (Φ x) (Φ y)| ≤ ε
@@ -813,16 +784,12 @@ instance : SecondCountableTopology GHSpace :=
-- Express `dist x y` in terms of `F p`
have : (F p).2 ((E p) x) ((E p) y) = floor (ε⁻¹ * dist x y) := by
simp only [F, (E p).symm_apply_apply]
- have Ap : (F p).2 ⟨i, hip⟩ ⟨j, hjp⟩ = floor (ε⁻¹ * dist x y) :=
- by
- rw [← this]
+ have Ap : (F p).2 ⟨i, hip⟩ ⟨j, hjp⟩ = floor (ε⁻¹ * dist x y) := by rw [← this];
congr <;> apply Fin.ext_iff.2 <;> rfl
-- Express `dist (Φ x) (Φ y)` in terms of `F q`
have : (F q).2 ((E q) (Ψ x)) ((E q) (Ψ y)) = floor (ε⁻¹ * dist (Ψ x) (Ψ y)) := by
simp only [F, (E q).symm_apply_apply]
- have Aq : (F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩ = floor (ε⁻¹ * dist (Ψ x) (Ψ y)) :=
- by
- rw [← this]
+ have Aq : (F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩ = floor (ε⁻¹ * dist (Ψ x) (Ψ y)) := by rw [← this];
congr <;> apply Fin.ext_iff.2 <;> [exact i';exact j']
-- use the equality between `F p` and `F q` to deduce that the distances have equal
-- integer parts
@@ -844,10 +811,7 @@ instance : SecondCountableTopology GHSpace :=
calc
|ε⁻¹| * |dist x y - dist (Ψ x) (Ψ y)| = |ε⁻¹ * (dist x y - dist (Ψ x) (Ψ y))| :=
(abs_mul _ _).symm
- _ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| :=
- by
- congr
- ring
+ _ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| := by congr ; ring
_ ≤ 1 := le_of_lt (abs_sub_lt_one_of_floor_eq_floor this)
calc
@@ -861,9 +825,7 @@ instance : SecondCountableTopology GHSpace :=
calc
dist p q = GH_dist p.rep q.rep := dist_GH_dist p q
_ ≤ ε + ε / 2 + ε := main
- _ = δ := by
- simp only [ε]
- ring
+ _ = δ := by simp only [ε]; ring
/-- Compactness criterion: a closed set of compact metric spaces is compact if the spaces have
@@ -897,9 +859,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
by
intro p
by_cases hp : p ∉ t
- · have : Nonempty (Equiv (∅ : Set p.rep) (Fin 0)) :=
- by
- rw [← Fintype.card_eq]
+ · have : Nonempty (Equiv (∅ : Set p.rep) (Fin 0)) := by rw [← Fintype.card_eq];
simp only [empty_card', Fintype.card_fin]
use ∅, 0, bot_le, choice this
· rcases hcov _ (Set.not_not_mem.1 hp) n with ⟨s, ⟨scard, scover⟩⟩
@@ -917,8 +877,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
⟨⟨N p, lt_of_le_of_lt (hN p) (Nat.lt_succ_self _)⟩, fun a b =>
⟨min M ⌊ε⁻¹ * dist ((E p).symm a) ((E p).symm b)⌋₊,
(min_le_left _ _).trans_lt (Nat.lt_succ_self _)⟩⟩
- refine' ⟨_, _, fun p => F p, _⟩
- infer_instance
+ refine' ⟨_, _, fun p => F p, _⟩; infer_instance
-- It remains to show that if `F p = F q`, then `p` and `q` are `ε`-close
rintro ⟨p, pt⟩ ⟨q, qt⟩ hpq
have Npq : N p = N q := Fin.ext_iff.1 (Sigma.mk.inj_iff.1 hpq).1
@@ -950,14 +909,8 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
have C2 : Fin.cast Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
- have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ :=
- by
- rw [ihi_eq]
- exact (E q).symm_apply_apply ⟨y, ys⟩
- have : Φ z = y := by
- simp only [Φ, Ψ]
- rw [C1, C2, C3]
- rfl
+ have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ := by rw [ihi_eq]; exact (E q).symm_apply_apply ⟨y, ys⟩
+ have : Φ z = y := by simp only [Φ, Ψ]; rw [C1, C2, C3]; rfl
rw [this]
exact le_trans (le_of_lt hy) u_le_ε
show ∀ x y : s p, |dist x y - dist (Φ x) (Φ y)| ≤ ε
@@ -1034,10 +987,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
calc
|ε⁻¹| * |dist x y - dist (Ψ x) (Ψ y)| = |ε⁻¹ * (dist x y - dist (Ψ x) (Ψ y))| :=
(abs_mul _ _).symm
- _ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| :=
- by
- congr
- ring
+ _ = |ε⁻¹ * dist x y - ε⁻¹ * dist (Ψ x) (Ψ y)| := by congr ; ring
_ ≤ 1 := le_of_lt (abs_sub_lt_one_of_floor_eq_floor this)
calc
@@ -1051,9 +1001,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
calc
dist p q = GH_dist p.rep q.rep := dist_GH_dist p q
_ ≤ ε + ε / 2 + ε := main
- _ = δ / 2 := by
- simp only [ε, one_div]
- ring
+ _ = δ / 2 := by simp only [ε, one_div]; ring
_ < δ := half_lt_self δpos
#align Gromov_Hausdorff.totally_bounded GromovHausdorff.totallyBounded
@@ -1108,9 +1056,7 @@ def auxGluing (n : ℕ) : AuxGluingStruct (X n) :=
/-- The Gromov-Hausdorff space is complete. -/
instance : CompleteSpace GHSpace :=
by
- have : ∀ n : ℕ, 0 < ((1 : ℝ) / 2) ^ n := by
- apply pow_pos
- norm_num
+ have : ∀ n : ℕ, 0 < ((1 : ℝ) / 2) ^ n := by apply pow_pos; norm_num
-- start from a sequence of nonempty compact metric spaces within distance `1/2^n` of each other
refine'
Metric.complete_of_convergent_controlled_sequences (fun n => (1 / 2) ^ n) this fun u hu => _
@@ -1122,14 +1068,9 @@ instance : CompleteSpace GHSpace :=
have E :
∀ n : ℕ,
glue_space (Y n).isom (isometry_optimal_GH_injl (X n) (X (n + 1))) = (Y (n + 1)).Space :=
- fun n => by
- dsimp only [Y, aux_gluing]
- rfl
+ fun n => by dsimp only [Y, aux_gluing]; rfl
let c n := cast (E n)
- have ic : ∀ n, Isometry (c n) := fun n x y =>
- by
- dsimp only [Y, aux_gluing]
- exact rfl
+ have ic : ∀ n, Isometry (c n) := fun n x y => by dsimp only [Y, aux_gluing]; exact rfl
-- there is a canonical embedding of `Y n` in `Y (n+1)`, by construction
let f : ∀ n, (Y n).Space → (Y (n + 1)).Space := fun n =>
c n ∘ to_glue_l (Y n).isom (isometry_optimal_GH_injl (X n) (X n.succ))
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -73,12 +73,10 @@ compact type to `GH_space`. -/
/-- Equivalence relation identifying two nonempty compact sets which are isometric -/
private def isometry_rel : NonemptyCompacts ℓ_infty_ℝ → NonemptyCompacts ℓ_infty_ℝ → Prop :=
fun x y => Nonempty (x ≃ᵢ y)
-#align Gromov_Hausdorff.isometry_rel Gromov_Hausdorff.isometry_rel
/-- This is indeed an equivalence relation -/
private theorem is_equivalence_isometry_rel : Equivalence IsometryRel :=
⟨fun x => ⟨IsometryEquiv.refl _⟩, fun x y ⟨e⟩ => ⟨e.symm⟩, fun x y z ⟨e⟩ ⟨f⟩ => ⟨e.trans f⟩⟩
-#align Gromov_Hausdorff.is_equivalence_isometry_rel Gromov_Hausdorff.is_equivalence_isometry_rel
/-- setoid instance identifying two isometric nonempty compact subspaces of ℓ^∞(ℝ) -/
instance IsometryRel.setoid : Setoid (NonemptyCompacts ℓ_infty_ℝ) :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b
@@ -825,7 +825,7 @@ instance : SecondCountableTopology GHSpace :=
have Aq : (F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩ = floor (ε⁻¹ * dist (Ψ x) (Ψ y)) :=
by
rw [← this]
- congr <;> apply Fin.ext_iff.2 <;> [exact i', exact j']
+ congr <;> apply Fin.ext_iff.2 <;> [exact i';exact j']
-- use the equality between `F p` and `F q` to deduce that the distances have equal
-- integer parts
have : (F p).2 ⟨i, hip⟩ ⟨j, hjp⟩ = (F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩ :=
@@ -997,7 +997,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
have Aq : ((F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩).1 = ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋₊ :=
calc
((F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩).1 = ((F q).2 ((E q) (Ψ x)) ((E q) (Ψ y))).1 := by
- congr <;> apply Fin.ext_iff.2 <;> [exact i', exact j']
+ congr <;> apply Fin.ext_iff.2 <;> [exact i';exact j']
_ = min M ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋₊ := by simp only [F, (E q).symm_apply_apply]
_ = ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋₊ :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/e3fb84046afd187b710170887195d50bada934ee
@@ -189,7 +189,7 @@ Hausdorff distance between isometric copies of the two spaces in a metric space.
we only consider embeddings in `ℓ^∞(ℝ)`, but we will prove below that it works for all spaces. -/
instance : Dist GHSpace
where dist x y :=
- infₛ <|
+ sInf <|
(fun p : NonemptyCompacts ℓ_infty_ℝ × NonemptyCompacts ℓ_infty_ℝ =>
hausdorffDist (p.1 : Set ℓ_infty_ℝ) p.2) ''
{ a | ⟦a⟧ = x } ×ˢ { b | ⟦b⟧ = y }
@@ -258,7 +258,7 @@ theorem gHDist_le_hausdorffDist {X : Type u} [MetricSpace X] [CompactSpace X] [N
have BY : ⟦B⟧ = to_GH_space Y := by
rw [eq_to_GH_space_iff]
exact ⟨fun x => F (Ψ' x), (kuratowskiEmbedding.isometry _).comp IΨ', range_comp _ _⟩
- refine' cinfₛ_le ⟨0, _⟩ _
+ refine' csInf_le ⟨0, _⟩ _
· simp only [lowerBounds, mem_image, mem_prod, mem_set_of_eq, Prod.exists, and_imp,
forall_exists_index]
intro t _ _ _ _ ht
@@ -382,7 +382,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
rcases mem_range.1 this with ⟨y, hy⟩
calc
(⨅ y, Fb (inl x, inr y)) ≤ Fb (inl x, inr y) :=
- cinfᵢ_le (by simpa only [add_zero] using HD_below_aux1 0) y
+ ciInf_le (by simpa only [add_zero] using HD_below_aux1 0) y
_ = dist (Φ x) (Ψ y) := rfl
_ = dist (f (inl x)) z := by rw [hy]
_ ≤ r := le_of_lt hz
@@ -399,12 +399,12 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
rcases mem_range.1 this with ⟨x, hx⟩
calc
(⨅ x, Fb (inl x, inr y)) ≤ Fb (inl x, inr y) :=
- cinfᵢ_le (by simpa only [add_zero] using HD_below_aux2 0) x
+ ciInf_le (by simpa only [add_zero] using HD_below_aux2 0) x
_ = dist (Φ x) (Ψ y) := rfl
_ = dist z (f (inr y)) := by rw [hx]
_ ≤ r := le_of_lt hz
- simp only [HD, csupᵢ_le I1, csupᵢ_le I2, max_le_iff, and_self_iff]
+ simp only [HD, ciSup_le I1, ciSup_le I2, max_le_iff, and_self_iff]
/- Get the same inequality for any coupling. If the coupling is quite good, the desired
inequality has been proved above. If it is bad, then the inequality is obvious. -/
have B :
@@ -427,7 +427,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
_ ≤ Hausdorff_dist (p : Set ℓ_infty_ℝ) q := not_lt.1 h
refine' le_antisymm _ _
- · apply le_cinfₛ
+ · apply le_csInf
· refine' (Set.Nonempty.prod _ _).image _ <;> exact ⟨_, rfl⟩
· rintro b ⟨⟨p, q⟩, ⟨hp, hq⟩, rfl⟩
exact B p q hp hq
@@ -461,7 +461,7 @@ instance : MetricSpace GHSpace where
dist_self x := by
rcases exists_rep x with ⟨y, hy⟩
refine' le_antisymm _ _
- · apply cinfₛ_le
+ · apply csInf_le
·
exact
⟨0, by
@@ -470,7 +470,7 @@ instance : MetricSpace GHSpace where
· simp only [mem_image, mem_prod, mem_set_of_eq, Prod.exists]
exists y, y
simpa only [and_self_iff, Hausdorff_dist_self_zero, eq_self_iff_true, and_true_iff]
- · apply le_cinfₛ
+ · apply le_csInf
· exact (nonempty.prod ⟨y, hy⟩ ⟨y, hy⟩).image _
· rintro b ⟨⟨u, v⟩, ⟨hu, hv⟩, rfl⟩
exact Hausdorff_dist_nonneg
mathlib commit https://github.com/leanprover-community/mathlib/commit/09079525fd01b3dda35e96adaa08d2f943e1648c
@@ -632,7 +632,7 @@ variable {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty X] {Y : Type v}
[CompactSpace Y] [Nonempty Y]
-- we want to ignore these instances in the following theorem
-attribute [local instance] Sum.topologicalSpace Sum.uniformSpace
+attribute [local instance 10] Sum.topologicalSpace Sum.uniformSpace
/-- If there are subsets which are `ε₁`-dense and `ε₃`-dense in two spaces, and
isometric up to `ε₂`, then the Gromov-Hausdorff distance between the spaces is bounded by
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce7e9d53d4bbc38065db3b595cd5bd73c323bc1d
@@ -1207,7 +1207,7 @@ instance : CompleteSpace GHSpace :=
rw [nonempty_compacts.to_GH_space, ← (u n).toGHSpace_rep,
to_GH_space_eq_to_GH_space_iff_isometry_equiv]
constructor
- convert (isom n).isometryEquivOnRange.symm
+ convert(isom n).isometryEquivOnRange.symm
-- Finally, we have proved the convergence of `u n`
exact ⟨L.to_GH_space, by simpa only [this] using M⟩
mathlib commit https://github.com/leanprover-community/mathlib/commit/195fcd60ff2bfe392543bceb0ec2adcdb472db4c
@@ -187,7 +187,7 @@ theorem toGHSpace_eq_toGHSpace_iff_isometryEquiv {X : Type u} [MetricSpace X] [C
/-- Distance on `GH_space`: the distance between two nonempty compact spaces is the infimum
Hausdorff distance between isometric copies of the two spaces in a metric space. For the definition,
we only consider embeddings in `ℓ^∞(ℝ)`, but we will prove below that it works for all spaces. -/
-instance : HasDist GHSpace
+instance : Dist GHSpace
where dist x y :=
infₛ <|
(fun p : NonemptyCompacts ℓ_infty_ℝ × NonemptyCompacts ℓ_infty_ℝ =>
mathlib commit https://github.com/leanprover-community/mathlib/commit/4c586d291f189eecb9d00581aeb3dd998ac34442
@@ -538,8 +538,8 @@ instance : MetricSpace GHSpace where
_ ≤
Hausdorff_dist (range (to_glue_l hΦ hΨ ∘ optimal_GH_injl X Y))
(range (to_glue_r hΦ hΨ ∘ optimal_GH_injr Y Z)) :=
- GH_dist_le_Hausdorff_dist ((to_glue_l_isometry hΦ hΨ).comp (isometry_optimal_GH_injl X Y))
- ((to_glue_r_isometry hΦ hΨ).comp (isometry_optimal_GH_injr Y Z))
+ (GH_dist_le_Hausdorff_dist ((to_glue_l_isometry hΦ hΨ).comp (isometry_optimal_GH_injl X Y))
+ ((to_glue_r_isometry hΦ hΨ).comp (isometry_optimal_GH_injr Y Z)))
_ ≤
Hausdorff_dist (range (to_glue_l hΦ hΨ ∘ optimal_GH_injl X Y))
(range (to_glue_l hΦ hΨ ∘ optimal_GH_injr X Y)) +
@@ -857,7 +857,7 @@ instance : SecondCountableTopology GHSpace :=
rw [mul_inv_cancel (ne_of_gt εpos), one_mul]
_ = ε * (|ε⁻¹| * |dist x y - dist (Ψ x) (Ψ y)|) := by
rw [abs_of_nonneg (le_of_lt (inv_pos.2 εpos)), mul_assoc]
- _ ≤ ε * 1 := mul_le_mul_of_nonneg_left I (le_of_lt εpos)
+ _ ≤ ε * 1 := (mul_le_mul_of_nonneg_left I (le_of_lt εpos))
_ = ε := mul_one _
calc
@@ -1047,7 +1047,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
rw [mul_inv_cancel (ne_of_gt εpos), one_mul]
_ = ε * (|ε⁻¹| * |dist x y - dist (Ψ x) (Ψ y)|) := by
rw [abs_of_nonneg (le_of_lt (inv_pos.2 εpos)), mul_assoc]
- _ ≤ ε * 1 := mul_le_mul_of_nonneg_left I (le_of_lt εpos)
+ _ ≤ ε * 1 := (mul_le_mul_of_nonneg_left I (le_of_lt εpos))
_ = ε := mul_one _
calc
mathlib commit https://github.com/leanprover-community/mathlib/commit/9da1b3534b65d9661eb8f42443598a92bbb49211
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sébastien Gouëzel
! This file was ported from Lean 3 source module topology.metric_space.gromov_hausdorff
-! leanprover-community/mathlib commit f2ce6086713c78a7f880485f7917ea547a215982
+! leanprover-community/mathlib commit 0c1f285a9f6e608ae2bdffa3f993eafb01eba829
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -530,7 +530,6 @@ instance : MetricSpace GHSpace where
let Ψ : Y → γ2 := optimal_GH_injl Y Z
have hΨ : Isometry Ψ := isometry_optimal_GH_injl Y Z
let γ := glue_space hΦ hΨ
- letI : MetricSpace γ := Metric.metricSpaceGlueSpace hΦ hΨ
have Comm : to_glue_l hΦ hΨ ∘ optimal_GH_injr X Y = to_glue_r hΦ hΨ ∘ optimal_GH_injl Y Z :=
to_glue_commute hΦ hΨ
calc
@@ -1088,6 +1087,8 @@ structure AuxGluingStruct (A : Type) [MetricSpace A] : Type 1 where
isom : Isometry embed
#align Gromov_Hausdorff.aux_gluing_struct GromovHausdorff.AuxGluingStruct
+attribute [local instance] aux_gluing_struct.metric
+
instance (A : Type) [MetricSpace A] : Inhabited (AuxGluingStruct A) :=
⟨{ Space := A
metric := by infer_instance
@@ -1098,18 +1099,12 @@ instance (A : Type) [MetricSpace A] : Inhabited (AuxGluingStruct A) :=
`X i` is glued to `X (i+1)` in an optimal way. The space at step `n+1` is obtained from the space
at step `n` by adding `X (n+1)`, glued in an optimal way to the `X n` already sitting there. -/
def auxGluing (n : ℕ) : AuxGluingStruct (X n) :=
- Nat.recOn n
- { Space := X 0
- metric := by infer_instance
- embed := id
- isom := fun x y => rfl } fun n Y =>
- letI : MetricSpace Y.space := Y.metric
- { Space := glue_space Y.isom (isometry_optimal_GH_injl (X n) (X (n + 1)))
+ Nat.recOn n default fun n Y =>
+ { Space := GlueSpace Y.isom (isometry_optimalGHInjl (X n) (X (n + 1)))
metric := by infer_instance
embed :=
- to_glue_r Y.isom (isometry_optimal_GH_injl (X n) (X (n + 1))) ∘
- optimal_GH_injr (X n) (X (n + 1))
- isom := (to_glue_r_isometry _ _).comp (isometry_optimal_GH_injr (X n) (X (n + 1))) }
+ toGlueR Y.isom (isometry_optimalGHInjl (X n) (X (n + 1))) ∘ optimalGHInjr (X n) (X (n + 1))
+ isom := (toGlueR_isometry _ _).comp (isometry_optimalGHInjr (X n) (X (n + 1))) }
#align Gromov_Hausdorff.aux_gluing GromovHausdorff.auxGluing
/-- The Gromov-Hausdorff space is complete. -/
@@ -1125,23 +1120,22 @@ instance : CompleteSpace GHSpace :=
let X n := (u n).rep
-- glue them together successively in an optimal way, getting a sequence of metric spaces `Y n`
let Y := aux_gluing X
- letI : ∀ n, MetricSpace (Y n).Space := fun n => (Y n).metric
+ -- this equality is true by definition but Lean unfolds some defs in the wrong order
have E :
- ∀ n : ℕ, glue_space (Y n).isom (isometry_optimal_GH_injl (X n) (X n.succ)) = (Y n.succ).Space :=
+ ∀ n : ℕ,
+ glue_space (Y n).isom (isometry_optimal_GH_injl (X n) (X (n + 1))) = (Y (n + 1)).Space :=
fun n => by
- simp only [Y, aux_gluing]
+ dsimp only [Y, aux_gluing]
rfl
let c n := cast (E n)
- have ic : ∀ n, Isometry (c n) := fun n x y => rfl
+ have ic : ∀ n, Isometry (c n) := fun n x y =>
+ by
+ dsimp only [Y, aux_gluing]
+ exact rfl
-- there is a canonical embedding of `Y n` in `Y (n+1)`, by construction
- let f : ∀ n, (Y n).Space → (Y n.succ).Space := fun n =>
- c n ∘ to_glue_l (aux_gluing X n).isom (isometry_optimal_GH_injl (X n) (X n.succ))
- have I : ∀ n, Isometry (f n) := by
- intro n
- apply Isometry.comp
- · intro x y
- rfl
- · apply to_glue_l_isometry
+ let f : ∀ n, (Y n).Space → (Y (n + 1)).Space := fun n =>
+ c n ∘ to_glue_l (Y n).isom (isometry_optimal_GH_injl (X n) (X n.succ))
+ have I : ∀ n, Isometry (f n) := fun n => (ic n).comp (to_glue_l_isometry _ _)
-- consider the inductive limit `Z0` of the `Y n`, and then its completion `Z`
let Z0 := Metric.InductiveLimit I
let Z := UniformSpace.Completion Z0
mathlib commit https://github.com/leanprover-community/mathlib/commit/eb0cb4511aaef0da2462207b67358a0e1fe1e2ee
@@ -47,7 +47,7 @@ i.e., it is complete and second countable. We also prove the Gromov compactness
noncomputable section
-open Classical Topology Ennreal
+open Classical Topology ENNReal
-- mathport name: exprℓ_infty_ℝ
local notation "ℓ_infty_ℝ" => lp (fun n : ℕ => ℝ) ∞
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
@@ -777,7 +777,7 @@ instance : SecondCountableTopology GHSpace := by
rw [mul_inv_cancel (ne_of_gt εpos), one_mul]
_ = ε * (|ε⁻¹| * |dist x y - dist (Ψ x) (Ψ y)|) := by
rw [abs_of_nonneg (le_of_lt (inv_pos.2 εpos)), mul_assoc]
- _ ≤ ε * 1 := (mul_le_mul_of_nonneg_left I (le_of_lt εpos))
+ _ ≤ ε * 1 := mul_le_mul_of_nonneg_left I (le_of_lt εpos)
_ = ε := mul_one _
calc
dist p q = ghDist p.Rep q.Rep := dist_ghDist p q
@@ -947,7 +947,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
rw [mul_inv_cancel (ne_of_gt εpos), one_mul]
_ = ε * (|ε⁻¹| * |dist x y - dist (Ψ x) (Ψ y)|) := by
rw [abs_of_nonneg (le_of_lt (inv_pos.2 εpos)), mul_assoc]
- _ ≤ ε * 1 := (mul_le_mul_of_nonneg_left I (le_of_lt εpos))
+ _ ≤ ε * 1 := mul_le_mul_of_nonneg_left I (le_of_lt εpos)
_ = ε := mul_one _
calc
dist p q = ghDist p.Rep q.Rep := dist_ghDist p q
@@ -95,7 +95,7 @@ instance : Inhabited GHSpace :=
⟨Quot.mk _ ⟨⟨{0}, isCompact_singleton⟩, singleton_nonempty _⟩⟩
/-- A metric space representative of any abstract point in `GHSpace` -/
--- Porting note: was @[nolint has_nonempty_instance]; why?
+-- Porting note(#5171): linter not yet ported; removed @[nolint has_nonempty_instance]; why?
def GHSpace.Rep (p : GHSpace) : Type :=
(Quotient.out p : NonemptyCompacts ℓ_infty_ℝ)
#align Gromov_Hausdorff.GH_space.rep GromovHausdorff.GHSpace.Rep
All of these changes appear to be oversights to me.
@@ -62,12 +62,12 @@ attribute [local instance] metricSpaceSum
namespace GromovHausdorff
-section GHSpace
-
-/- In this section, we define the Gromov-Hausdorff space, denoted `GHSpace` as the quotient
+/-! In this section, we define the Gromov-Hausdorff space, denoted `GHSpace` as the quotient
of nonempty compact subsets of `ℓ^∞(ℝ)` by identifying isometric sets.
Using the Kuratwoski embedding, we get a canonical map `toGHSpace` mapping any nonempty
compact type to `GHSpace`. -/
+section GHSpace
+
/-- Equivalence relation identifying two nonempty compact sets which are isometric -/
private def IsometryRel (x : NonemptyCompacts ℓ_infty_ℝ) (y : NonemptyCompacts ℓ_infty_ℝ) : Prop :=
Nonempty (x ≃ᵢ y)
@@ -523,7 +523,7 @@ end GHSpace
end GromovHausdorff
/-- In particular, nonempty compacts of a metric space map to `GHSpace`.
- We register this in the topological_space namespace to take advantage
+ We register this in the `TopologicalSpace` namespace to take advantage
of the notation `p.toGHSpace`. -/
def TopologicalSpace.NonemptyCompacts.toGHSpace {X : Type u} [MetricSpace X]
(p : NonemptyCompacts X) : GromovHausdorff.GHSpace :=
@@ -47,7 +47,6 @@ open scoped Classical Topology ENNReal Cardinal
set_option linter.uppercaseLean3 false
--- mathport name: exprℓ_infty_ℝ
local notation "ℓ_infty_ℝ" => lp (fun n : ℕ => ℝ) ∞
universe u v w
I removed some of the tactics that were not used and are hopefully uncontroversial arising from the linter at #11308.
As the commit messages should convey, the removed tactics are, essentially,
push_cast
norm_cast
congr
norm_num
dsimp
funext
intro
infer_instance
@@ -438,7 +438,6 @@ instance : MetricSpace GHSpace where
hausdorffDist (p.1 : Set ℓ_infty_ℝ) p.2) ∘
Prod.swap ''
{ a | ⟦a⟧ = x } ×ˢ { b | ⟦b⟧ = y } := by
- congr
funext
simp only [comp_apply, Prod.fst_swap, Prod.snd_swap]
congr
open Classical
(#11199)
We remove all but one open Classical
s, instead preferring to use open scoped Classical
. The only real side-effect this led to is moving a couple declarations to use Exists.choose
instead of Classical.choose
.
The first few commits are explicitly labelled regex replaces for ease of review.
@@ -52,7 +52,8 @@ local notation "ℓ_infty_ℝ" => lp (fun n : ℕ => ℝ) ∞
universe u v w
-open Classical Set Function TopologicalSpace Filter Metric Quotient Bornology
+open scoped Classical
+open Set Function TopologicalSpace Filter Metric Quotient Bornology
open BoundedContinuousFunction Nat Int kuratowskiEmbedding
@@ -816,7 +817,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
· have : Nonempty (Equiv (∅ : Set p.Rep) (Fin 0)) := by
rw [← Fintype.card_eq];
simp only [empty_card', Fintype.card_fin]
- use ∅, 0, bot_le, choice this
+ use ∅, 0, bot_le, this.some
-- Porting note: unclear why this next line wasn't needed in Lean 3
exact fun hp' => (hp hp').elim
· rcases hcov _ (Set.not_not_mem.1 hp) n with ⟨s, ⟨scard, scover⟩⟩
Homogenises porting notes via capitalisation and addition of whitespace.
It makes the following changes:
@@ -95,7 +95,7 @@ instance : Inhabited GHSpace :=
⟨Quot.mk _ ⟨⟨{0}, isCompact_singleton⟩, singleton_nonempty _⟩⟩
/-- A metric space representative of any abstract point in `GHSpace` -/
--- porting note: was @[nolint has_nonempty_instance]; why?
+-- Porting note: was @[nolint has_nonempty_instance]; why?
def GHSpace.Rep (p : GHSpace) : Type :=
(Quotient.out p : NonemptyCompacts ℓ_infty_ℝ)
#align Gromov_Hausdorff.GH_space.rep GromovHausdorff.GHSpace.Rep
@@ -415,7 +415,7 @@ theorem ghDist_eq_hausdorffDist (X : Type u) [MetricSpace X] [CompactSpace X] [N
/-- The Gromov-Hausdorff distance defines a genuine distance on the Gromov-Hausdorff space. -/
instance : MetricSpace GHSpace where
dist := dist
- -- porting note: why does Lean 4 want this?
+ -- Porting note: why does Lean 4 want this?
edist_dist _ _ := by exact ENNReal.coe_nnreal_eq _
dist_self x := by
rcases exists_rep x with ⟨y, hy⟩
@@ -454,7 +454,7 @@ instance : MetricSpace GHSpace where
i.e., they coincide. Therefore, the original spaces are isometric. -/
rcases ghDist_eq_hausdorffDist x.Rep y.Rep with ⟨Φ, Ψ, Φisom, Ψisom, DΦΨ⟩
rw [← dist_ghDist] at DΦΨ
- simp_rw [hxy] at DΦΨ -- porting note: I have no idea why this needed `simp_rw` versus `rw`
+ simp_rw [hxy] at DΦΨ -- Porting note: I have no idea why this needed `simp_rw` versus `rw`
have : range Φ = range Ψ := by
have hΦ : IsCompact (range Φ) := isCompact_range Φisom.continuous
have hΨ : IsCompact (range Ψ) := isCompact_range Ψisom.continuous
@@ -746,7 +746,7 @@ instance : SecondCountableTopology GHSpace := by
simp only [(E q).symm_apply_apply]
have Aq : (F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩ = ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋ := by
rw [← this]
- -- porting note: `congr` fails to make progress
+ -- Porting note: `congr` fails to make progress
refine congr_arg₂ (F q).2 ?_ ?_ <;> ext1
exacts [i', j']
-- use the equality between `F p` and `F q` to deduce that the distances have equal
@@ -817,7 +817,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
rw [← Fintype.card_eq];
simp only [empty_card', Fintype.card_fin]
use ∅, 0, bot_le, choice this
- -- porting note: unclear why this next line wasn't needed in Lean 3
+ -- Porting note: unclear why this next line wasn't needed in Lean 3
exact fun hp' => (hp hp').elim
· rcases hcov _ (Set.not_not_mem.1 hp) n with ⟨s, ⟨scard, scover⟩⟩
rcases Cardinal.lt_aleph0.1 (lt_of_le_of_lt scard (Cardinal.nat_lt_aleph0 _)) with ⟨N, hN⟩
@@ -918,7 +918,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
have hpq' : HEq (F p).snd (F q).snd := (Sigma.mk.inj_iff.1 hpq).2
rw [Fin.heq_fun₂_iff Npq Npq] at hpq'
rw [← hpq']
- -- porting note: new version above because `subst…` does not work
+ -- Porting note: new version above because `subst…` does not work
-- we want to `subst hpq` where `hpq : F p = F q`, except that `subst` only works
-- with a constant, so replace `F q` (and everything that depends on it) by a constant `f`
-- then `subst`
@@ -990,7 +990,7 @@ instance (A : Type) [MetricSpace A] : Inhabited (AuxGluingStruct A) :=
⟨{ Space := A
metric := by infer_instance
embed := id
- -- porting note: without `by exact` there was an unsolved metavariable
+ -- Porting note: without `by exact` there was an unsolved metavariable
isom := fun x y => by exact rfl }⟩
/-- Auxiliary sequence of metric spaces, containing copies of `X 0`, ..., `X n`, where each
@@ -304,8 +304,8 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
let F : Sum X Y × Sum X Y → ℝ := fun p => dist (f p.1) (f p.2)
-- check that the induced "distance" is a candidate
have Fgood : F ∈ candidates X Y := by
- simp only [candidates, forall_const, and_true_iff, add_comm, eq_self_iff_true, dist_eq_zero,
- and_self_iff, Set.mem_setOf_eq]
+ simp only [F, candidates, forall_const, and_true_iff, add_comm, eq_self_iff_true,
+ dist_eq_zero, and_self_iff, Set.mem_setOf_eq]
repeat' constructor
· exact fun x y =>
calc
@@ -715,7 +715,7 @@ instance : SecondCountableTopology GHSpace := by
have C2 : Fin.cast Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ := by
rw [ihi_eq]; exact (E q).symm_apply_apply ⟨y, ys⟩
- have : Φ z = y := by simp only; rw [C1, C2, C3]
+ have : Φ z = y := by simp only [Φ, Ψ]; rw [C1, C2, C3]
rw [this]
exact le_of_lt hy
show ∀ x y : s p, |dist x y - dist (Φ x) (Φ y)| ≤ ε
@@ -730,13 +730,13 @@ instance : SecondCountableTopology GHSpace := by
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
have hiq : i < N q := by rwa [Npq] at hip
- have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
+ have i' : i = (E q) (Ψ x) := by simp only [Ψ, Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
have hjq : j < N q := by rwa [Npq] at hjp
have j' : j = ((E q) (Ψ y)).1 := by
- simp only [Equiv.apply_symm_apply, Fin.coe_cast]
+ simp only [Ψ, Equiv.apply_symm_apply, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
have : (F p).2 ((E p) x) ((E p) y) = ⌊ε⁻¹ * dist x y⌋ := by
simp only [(E p).symm_apply_apply]
@@ -867,7 +867,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
have C2 : Fin.cast Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ := by
rw [ihi_eq]; exact (E q).symm_apply_apply ⟨y, ys⟩
- have : Φ z = y := by simp only; rw [C1, C2, C3]
+ have : Φ z = y := by simp only [Ψ, Φ]; rw [C1, C2, C3]
rw [this]
exact le_trans (le_of_lt hy) u_le_ε
show ∀ x y : s p, |dist x y - dist (Φ x) (Φ y)| ≤ ε
@@ -881,12 +881,12 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
have hiq : i < N q := by rwa [Npq] at hip
- have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
+ have i' : i = (E q) (Ψ x) := by simp only [Ψ, Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
have hjq : j < N q := by rwa [Npq] at hjp
- have j' : j = (E q) (Ψ y) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
+ have j' : j = (E q) (Ψ y) := by simp only [Ψ, Equiv.apply_symm_apply, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
have Ap : ((F p).2 ⟨i, hip⟩ ⟨j, hjp⟩).1 = ⌊ε⁻¹ * dist x y⌋₊ :=
calc
@@ -953,7 +953,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
calc
dist p q = ghDist p.Rep q.Rep := dist_ghDist p q
_ ≤ ε + ε / 2 + ε := main
- _ = δ / 2 := by simp only [one_div]; ring
+ _ = δ / 2 := by simp only [ε, one_div]; ring
_ < δ := half_lt_self δpos
#align Gromov_Hausdorff.totally_bounded GromovHausdorff.totallyBounded
@@ -1019,9 +1019,9 @@ instance : CompleteSpace GHSpace := by
have E :
∀ n : ℕ,
GlueSpace (Y n).isom (isometry_optimalGHInjl (X n) (X (n + 1))) = (Y (n + 1)).Space :=
- fun n => by dsimp only [auxGluing]; rfl
+ fun n => by dsimp only [Y, auxGluing]; rfl
let c n := cast (E n)
- have ic : ∀ n, Isometry (c n) := fun n x y => by dsimp only [auxGluing]; exact rfl
+ have ic : ∀ n, Isometry (c n) := fun n x y => by dsimp only [Y, auxGluing]; exact rfl
-- there is a canonical embedding of `Y n` in `Y (n+1)`, by construction
let f : ∀ n, (Y n).Space → (Y (n + 1)).Space := fun n =>
c n ∘ toGlueL (Y n).isom (isometry_optimalGHInjl (X n) (X n.succ))
@@ -1046,9 +1046,9 @@ instance : CompleteSpace GHSpace := by
change X2 n = range (coeZ ∘ Φ n.succ ∘ c n ∘
toGlueR (Y n).isom (isometry_optimalGHInjl (X n) (X n.succ)) ∘
optimalGHInjl (X n) (X n.succ))
- simp only --[X2, Φ]
+ simp only [X2, Φ]
rw [← toInductiveLimit_commute I]
- simp only --[f]
+ simp only [f]
rw [← toGlue_commute]
rfl
-- simp_rw [range_comp] at X2n
In this pull request, I have systematically eliminated the leading whitespace preceding the colon (:
) within all unlabelled or unclassified porting notes. This adjustment facilitates a more efficient review process for the remaining notes by ensuring no entries are overlooked due to formatting inconsistencies.
@@ -722,7 +722,7 @@ instance : SecondCountableTopology GHSpace := by
· /- the distance between `x` and `y` is encoded in `F p`, and the distance between
`Φ x` and `Φ y` (two points of `s q`) is encoded in `F q`, all this up to `ε`.
As `F p = F q`, the distances are almost equal. -/
- -- porting note : we have to circumvent the absence of `change … with … `
+ -- Porting note: we have to circumvent the absence of `change … with … `
intro x y
-- have : dist (Φ x) (Φ y) = dist (Ψ x) (Ψ y) := rfl
rw [show dist (Φ x) (Φ y) = dist (Ψ x) (Ψ y) from rfl]
@@ -755,7 +755,7 @@ instance : SecondCountableTopology GHSpace := by
have hpq' : HEq (F p).snd (F q).snd := (Sigma.mk.inj_iff.1 hpq).2
rw [Fin.heq_fun₂_iff Npq Npq] at hpq'
rw [← hpq']
- -- porting note : new version above, because `change … with…` is not implemented
+ -- Porting note: new version above, because `change … with…` is not implemented
-- we want to `subst hpq` where `hpq : F p = F q`, except that `subst` only works
-- with a constant, so replace `F q` (and everything that depends on it) by a constant `f`
-- then `subst`
The FunLike hierarchy is very big and gets scanned through each time we need a coercion (via the CoeFun
instance). It looks like unbundled inheritance suits Lean 4 better here. The only class that still extends FunLike
is EquivLike
, since that has a custom coe_injective'
field that is easier to implement. All other classes should take FunLike
or EquivLike
as a parameter.
Previously, morphism classes would be Type
-valued and extend FunLike
:
/-- `MyHomClass F A B` states that `F` is a type of `MyClass.op`-preserving morphisms.
You should extend this class when you extend `MyHom`. -/
class MyHomClass (F : Type*) (A B : outParam <| Type*) [MyClass A] [MyClass B]
extends FunLike F A B :=
(map_op : ∀ (f : F) (x y : A), f (MyClass.op x y) = MyClass.op (f x) (f y))
After this PR, they should be Prop
-valued and take FunLike
as a parameter:
/-- `MyHomClass F A B` states that `F` is a type of `MyClass.op`-preserving morphisms.
You should extend this class when you extend `MyHom`. -/
class MyHomClass (F : Type*) (A B : outParam <| Type*) [MyClass A] [MyClass B]
[FunLike F A B] : Prop :=
(map_op : ∀ (f : F) (x y : A), f (MyClass.op x y) = MyClass.op (f x) (f y))
(Note that A B
stay marked as outParam
even though they are not purely required to be so due to the FunLike
parameter already filling them in. This is required to see through type synonyms, which is important in the category theory library. Also, I think keeping them as outParam
is slightly faster.)
Similarly, MyEquivClass
should take EquivLike
as a parameter.
As a result, every mention of [MyHomClass F A B]
should become [FunLike F A B] [MyHomClass F A B]
.
While overall this gives some great speedups, there are some cases that are noticeably slower. In particular, a failing application of a lemma such as map_mul
is more expensive. This is due to suboptimal processing of arguments. For example:
variable [FunLike F M N] [Mul M] [Mul N] (f : F) (x : M) (y : M)
theorem map_mul [MulHomClass F M N] : f (x * y) = f x * f y
example [AddHomClass F A B] : f (x * y) = f x * f y := map_mul f _ _
Before this PR, applying map_mul f
gives the goals [Mul ?M] [Mul ?N] [MulHomClass F ?M ?N]
. Since M
and N
are out_param
s, [MulHomClass F ?M ?N]
is synthesized first, supplies values for ?M
and ?N
and then the Mul M
and Mul N
instances can be found.
After this PR, the goals become [FunLike F ?M ?N] [Mul ?M] [Mul ?N] [MulHomClass F ?M ?N]
. Now [FunLike F ?M ?N]
is synthesized first, supplies values for ?M
and ?N
and then the Mul M
and Mul N
instances can be found, before trying MulHomClass F M N
which fails. Since the Mul
hierarchy is very big, this can be slow to fail, especially when there is no such Mul
instance.
A long-term but harder to achieve solution would be to specify the order in which instance goals get solved. For example, we'd like to change the arguments to map_mul
to look like [FunLike F M N] [Mul M] [Mul N] [highPriority <| MulHomClass F M N]
because MulHomClass
fails or succeeds much faster than the others.
As a consequence, the simpNF
linter is much slower since by design it tries and fails to apply many map_
lemmas. The same issue occurs a few times in existing calls to simp [map_mul]
, where map_mul
is tried "too soon" and fails. Thanks to the speedup of leanprover/lean4#2478 the impact is very limited, only in files that already were close to the timeout.
simp
not firing sometimesThis affects map_smulₛₗ
and related definitions. For simp
lemmas Lean apparently uses a slightly different mechanism to find instances, so that rw
can find every argument to map_smulₛₗ
successfully but simp
can't: leanprover/lean4#3701.
Especially in the category theory library, we might sometimes have a type A
which is also accessible as a synonym (Bundled A hA).1
. Instance synthesis doesn't always work if we have f : A →* B
but x * y : (Bundled A hA).1
or vice versa. This seems to be mostly fixed by keeping A B
as outParam
s in MulHomClass F A B
. (Presumably because Lean will do a definitional check A =?= (Bundled A hA).1
instead of using the syntax in the discrimination tree.)
The timeouts can be worked around for now by specifying which map_mul
we mean, either as map_mul f
for some explicit f
, or as e.g. MonoidHomClass.map_mul
.
map_smulₛₗ
not firing as simp
lemma can be worked around by going back to the pre-FunLike situation and making LinearMap.map_smulₛₗ
a simp
lemma instead of the generic map_smulₛₗ
. Writing simp [map_smulₛₗ _]
also works.
Co-authored-by: Matthew Ballard <matt@mrb.email> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Scott Morrison <scott@tqft.net> Co-authored-by: Anne Baanen <Vierkantor@users.noreply.github.com>
@@ -412,7 +412,6 @@ theorem ghDist_eq_hausdorffDist (X : Type u) [MetricSpace X] [CompactSpace X] [N
exact (hausdorffDist_image (kuratowskiEmbedding.isometry _)).symm
#align Gromov_Hausdorff.GH_dist_eq_Hausdorff_dist GromovHausdorff.ghDist_eq_hausdorffDist
-set_option maxHeartbeats 300000 in
/-- The Gromov-Hausdorff distance defines a genuine distance on the Gromov-Hausdorff space. -/
instance : MetricSpace GHSpace where
dist := dist
@@ -442,7 +441,11 @@ instance : MetricSpace GHSpace where
funext
simp only [comp_apply, Prod.fst_swap, Prod.snd_swap]
congr
- simp only [hausdorffDist_comm]
+ -- The next line had `singlePass := true` before #9928,
+ -- then was changed to be `simp only [hausdorffDist_comm]`,
+ -- then `singlePass := true` was readded in #8386 because of timeouts.
+ -- TODO: figure out what causes the slowdown and make it a `simp only` again?
+ simp (config := { singlePass := true }) only [hausdorffDist_comm]
simp only [dist, A, image_comp, image_swap_prod]
eq_of_dist_eq_zero {x} {y} hxy := by
/- To show that two spaces at zero distance are isometric,
Of the 18 uses of singlePass
, in 3 cases we can just use rw
, in 4 cases it isn't needed at all.
In the other 11 cases we are always use it as simp (config := {singlePass := true}) only [X]
(i.e. with just a single simp lemma), and that simp
call would loop forever (usually failing with a maxRecDepth error, sometimes with heartbeats). I've left these as is.
There's also one case where there was a missing only
.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -442,7 +442,7 @@ instance : MetricSpace GHSpace where
funext
simp only [comp_apply, Prod.fst_swap, Prod.snd_swap]
congr
- simp (config := { singlePass := true }) only [hausdorffDist_comm]
+ simp only [hausdorffDist_comm]
simp only [dist, A, image_comp, image_swap_prod]
eq_of_dist_eq_zero {x} {y} hxy := by
/- To show that two spaces at zero distance are isometric,
This is the supremum of
along with some minor fixes from failures on nightly-testing as Mathlib master
is merged into it.
Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.
I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0
branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.
In particular this includes adjustments for the Lean PRs
We can get rid of all the
local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)
macros across Mathlib (and in any projects that want to write natural number powers of reals).
Changes the default behaviour of simp
to (config := {decide := false})
. This makes simp
(and consequentially norm_num
) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp
or norm_num
to decide
or rfl
, or adding (config := {decide := true})
.
This changed the behaviour of simp
so that simp [f]
will only unfold "fully applied" occurrences of f
. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true })
. We may in future add a syntax for this, e.g. simp [!f]
; please provide feedback! In the meantime, we have made the following changes:
(config := { unfoldPartialApp := true })
in some places, to recover the old behaviour@[eqns]
to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp
and Function.flip
.This change in Lean may require further changes down the line (e.g. adding the !f
syntax, and/or upstreaming the special treatment for Function.comp
and Function.flip
, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!
Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>
@@ -1002,8 +1002,6 @@ def auxGluing (n : ℕ) : AuxGluingStruct (X n) :=
isom := (toGlueR_isometry _ _).comp (isometry_optimalGHInjr (X n) (X (n + 1))) }
#align Gromov_Hausdorff.aux_gluing GromovHausdorff.auxGluing
-local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue lean4#2220
-
/-- The Gromov-Hausdorff space is complete. -/
instance : CompleteSpace GHSpace := by
set d := fun n : ℕ ↦ ((1 : ℝ) / 2) ^ n
@@ -113,9 +113,9 @@ theorem eq_toGHSpace_iff {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty
have f :=
((kuratowskiEmbedding.isometry X).isometryEquivOnRange.symm.trans
isomΨ.isometryEquivOnRange).symm
- have E :
- (range Ψ ≃ᵢ NonemptyCompacts.kuratowskiEmbedding X) = (p ≃ᵢ range (kuratowskiEmbedding X)) :=
- by dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rw [rangeΨ]; rfl
+ have E : (range Ψ ≃ᵢ NonemptyCompacts.kuratowskiEmbedding X)
+ = (p ≃ᵢ range (kuratowskiEmbedding X)) := by
+ dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rw [rangeΨ]; rfl
exact ⟨cast E f⟩
#align Gromov_Hausdorff.eq_to_GH_space_iff GromovHausdorff.eq_toGHSpace_iff
@@ -156,8 +156,8 @@ theorem toGHSpace_eq_toGHSpace_iff_isometryEquiv {X : Type u} [MetricSpace X] [C
rintro ⟨e⟩
have I :
(NonemptyCompacts.kuratowskiEmbedding X ≃ᵢ NonemptyCompacts.kuratowskiEmbedding Y) =
- (range (kuratowskiEmbedding X) ≃ᵢ range (kuratowskiEmbedding Y)) :=
- by dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rfl
+ (range (kuratowskiEmbedding X) ≃ᵢ range (kuratowskiEmbedding Y)) := by
+ dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rfl
have f := (kuratowskiEmbedding.isometry X).isometryEquivOnRange
have g := (kuratowskiEmbedding.isometry Y).isometryEquivOnRange.symm
exact ⟨f.trans <| (cast I e).trans g⟩, by
@@ -167,8 +167,8 @@ theorem toGHSpace_eq_toGHSpace_iff_isometryEquiv {X : Type u} [MetricSpace X] [C
have g := (kuratowskiEmbedding.isometry Y).isometryEquivOnRange
have I :
(range (kuratowskiEmbedding X) ≃ᵢ range (kuratowskiEmbedding Y)) =
- (NonemptyCompacts.kuratowskiEmbedding X ≃ᵢ NonemptyCompacts.kuratowskiEmbedding Y) :=
- by dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rfl
+ (NonemptyCompacts.kuratowskiEmbedding X ≃ᵢ NonemptyCompacts.kuratowskiEmbedding Y) := by
+ dsimp only [NonemptyCompacts.kuratowskiEmbedding]; rfl
rw [Quotient.eq]
exact ⟨cast I ((f.trans e).trans g)⟩⟩
#align Gromov_Hausdorff.to_GH_space_eq_to_GH_space_iff_isometry_equiv GromovHausdorff.toGHSpace_eq_toGHSpace_iff_isometryEquiv
rcases
, convert
and congrm
(#7725)
Replace rcases(
with rcases (
. Same thing for convert(
and congrm(
. No other change.
@@ -624,12 +624,12 @@ theorem ghDist_le_of_approx_subsets {s : Set X} (Φ : s → Y) {ε₁ ε₂ ε
have : hausdorffDist (Fl '' s) (Fr '' range Φ) ≤ ε₂ / 2 + δ := by
refine' hausdorffDist_le_of_mem_dist (by linarith) _ _
· intro x' hx'
- rcases(Set.mem_image _ _ _).1 hx' with ⟨x, ⟨x_in_s, xx'⟩⟩
+ rcases (Set.mem_image _ _ _).1 hx' with ⟨x, ⟨x_in_s, xx'⟩⟩
rw [← xx']
use Fr (Φ ⟨x, x_in_s⟩), mem_image_of_mem Fr (mem_range_self _)
exact le_of_eq (glueDist_glued_points (fun x : s => (x : X)) Φ (ε₂ / 2 + δ) ⟨x, x_in_s⟩)
· intro x' hx'
- rcases(Set.mem_image _ _ _).1 hx' with ⟨y, ⟨y_in_s', yx'⟩⟩
+ rcases (Set.mem_image _ _ _).1 hx' with ⟨y, ⟨y_in_s', yx'⟩⟩
rcases mem_range.1 y_in_s' with ⟨x, xy⟩
use Fl x, mem_image_of_mem _ x.2
rw [← yx', ← xy, dist_comm]
@@ -1081,7 +1081,7 @@ instance : CompleteSpace GHSpace := by
rw [Function.comp_apply, NonemptyCompacts.toGHSpace, ← (u n).toGHSpace_rep,
toGHSpace_eq_toGHSpace_iff_isometryEquiv]
constructor
- convert(isom n).isometryEquivOnRange.symm
+ convert (isom n).isometryEquivOnRange.symm
-- the images of `X3 n` in the Gromov-Hausdorff space converge to the image of `L`
-- so the images of `u n` converge to the image of `L` as well
use L.toGHSpace
Metric.Bounded
(#7240)
Use Bornology.IsBounded
instead.
@@ -52,7 +52,7 @@ local notation "ℓ_infty_ℝ" => lp (fun n : ℕ => ℝ) ∞
universe u v w
-open Classical Set Function TopologicalSpace Filter Metric Quotient
+open Classical Set Function TopologicalSpace Filter Metric Quotient Bornology
open BoundedContinuousFunction Nat Int kuratowskiEmbedding
@@ -281,7 +281,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
exact
exists_dist_lt_of_hausdorffDist_lt this bound
(hausdorffEdist_ne_top_of_nonempty_of_bounded p.nonempty q.nonempty
- p.isCompact.bounded q.isCompact.bounded)
+ p.isCompact.isBounded q.isCompact.isBounded)
rcases this with ⟨y, hy, dy⟩
rcases mem_range.1 hy with ⟨z, hzy⟩
rw [← hzy] at dy
@@ -329,7 +329,7 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
· apply mem_union_right; apply mem_range_self
refine' dist_le_diam_of_mem _ (A _) (A _)
rw [Φrange, Ψrange]
- exact (p ⊔ q).isCompact.bounded
+ exact (p ⊔ q).isCompact.isBounded
_ ≤ 2 * diam (univ : Set X) + 1 + 2 * diam (univ : Set Y) := I
let Fb := candidatesBOfCandidates F Fgood
have : hausdorffDist (range (optimalGHInjl X Y)) (range (optimalGHInjr X Y)) ≤ HD Fb :=
@@ -339,8 +339,8 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
intro x
have : f (inl x) ∈ ↑p := Φrange.subst (mem_range_self _)
rcases exists_dist_lt_of_hausdorffDist_lt this hr
- (hausdorffEdist_ne_top_of_nonempty_of_bounded p.nonempty q.nonempty p.isCompact.bounded
- q.isCompact.bounded) with
+ (hausdorffEdist_ne_top_of_nonempty_of_bounded p.nonempty q.nonempty p.isCompact.isBounded
+ q.isCompact.isBounded) with
⟨z, zq, hz⟩
have : z ∈ range Ψ := by rwa [← Ψrange] at zq
rcases mem_range.1 this with ⟨y, hy⟩
@@ -355,8 +355,8 @@ theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Non
intro y
have : f (inr y) ∈ ↑q := Ψrange.subst (mem_range_self _)
rcases exists_dist_lt_of_hausdorffDist_lt' this hr
- (hausdorffEdist_ne_top_of_nonempty_of_bounded p.nonempty q.nonempty p.isCompact.bounded
- q.isCompact.bounded) with
+ (hausdorffEdist_ne_top_of_nonempty_of_bounded p.nonempty q.nonempty p.isCompact.isBounded
+ q.isCompact.isBounded) with
⟨z, zq, hz⟩
have : z ∈ range Φ := by rwa [← Φrange] at zq
rcases mem_range.1 this with ⟨x, hx⟩
@@ -459,7 +459,7 @@ instance : MetricSpace GHSpace where
· exact hΦ.isClosed
· exact hΨ.isClosed
· exact hausdorffEdist_ne_top_of_nonempty_of_bounded (range_nonempty _) (range_nonempty _)
- hΦ.bounded hΨ.bounded
+ hΦ.isBounded hΨ.isBounded
have T : (range Ψ ≃ᵢ y.Rep) = (range Φ ≃ᵢ y.Rep) := by rw [this]
have eΨ := cast T Ψisom.isometryEquivOnRange.symm
have e := Φisom.isometryEquivOnRange.trans eΨ
@@ -498,9 +498,9 @@ instance : MetricSpace GHSpace where
refine' hausdorffDist_triangle <| hausdorffEdist_ne_top_of_nonempty_of_bounded
(range_nonempty _) (range_nonempty _) _ _
· exact (isCompact_range (Isometry.continuous
- ((toGlueL_isometry hΦ hΨ).comp (isometry_optimalGHInjl X Y)))).bounded
+ ((toGlueL_isometry hΦ hΨ).comp (isometry_optimalGHInjl X Y)))).isBounded
· exact (isCompact_range (Isometry.continuous
- ((toGlueL_isometry hΦ hΨ).comp (isometry_optimalGHInjr X Y)))).bounded
+ ((toGlueL_isometry hΦ hΨ).comp (isometry_optimalGHInjr X Y)))).isBounded
_ = hausdorffDist (toGlueL hΦ hΨ '' range (optimalGHInjl X Y))
(toGlueL hΦ hΨ '' range (optimalGHInjr X Y)) +
hausdorffDist (toGlueR hΦ hΨ '' range (optimalGHInjl Y Z))
@@ -605,17 +605,17 @@ theorem ghDist_le_of_approx_subsets {s : Set X} (Φ : s → Y) {ε₁ ε₂ ε
have :
hausdorffDist (range Fl) (range Fr) ≤
hausdorffDist (range Fl) (Fl '' s) + hausdorffDist (Fl '' s) (range Fr) :=
- haveI B : Bounded (range Fl) := (isCompact_range Il.continuous).bounded
+ have B : IsBounded (range Fl) := (isCompact_range Il.continuous).isBounded
hausdorffDist_triangle
(hausdorffEdist_ne_top_of_nonempty_of_bounded (range_nonempty _) (sne.image _) B
- (B.mono (image_subset_range _ _)))
+ (B.subset (image_subset_range _ _)))
have :
hausdorffDist (Fl '' s) (range Fr) ≤
hausdorffDist (Fl '' s) (Fr '' range Φ) + hausdorffDist (Fr '' range Φ) (range Fr) :=
- haveI B : Bounded (range Fr) := (isCompact_range Ir.continuous).bounded
+ have B : IsBounded (range Fr) := (isCompact_range Ir.continuous).isBounded
hausdorffDist_triangle'
(hausdorffEdist_ne_top_of_nonempty_of_bounded ((range_nonempty _).image _) (range_nonempty _)
- (Bounded.mono (image_subset_range _ _) B) B)
+ (B.subset (image_subset_range _ _)) B)
have : hausdorffDist (range Fl) (Fl '' s) ≤ ε₁ := by
rw [← image_univ, hausdorffDist_image Il]
have : 0 ≤ ε₁ := le_trans dist_nonneg Dxs
@@ -894,7 +894,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
refine' min_eq_right (Nat.floor_mono _)
refine' mul_le_mul_of_nonneg_left (le_trans _ (le_max_left _ _)) (inv_pos.2 εpos).le
change dist (x : p.Rep) y ≤ C
- refine' (dist_le_diam_of_mem isCompact_univ.bounded (mem_univ _) (mem_univ _)).trans _
+ refine' (dist_le_diam_of_mem isCompact_univ.isBounded (mem_univ _) (mem_univ _)).trans _
exact hdiam p pt
-- Express `dist (Φ x) (Φ y)` in terms of `F q`
have Aq : ((F q).2 ⟨i, hiq⟩ ⟨j, hjq⟩).1 = ⌊ε⁻¹ * dist (Ψ x) (Ψ y)⌋₊ :=
@@ -907,7 +907,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
refine' min_eq_right (Nat.floor_mono _)
refine' mul_le_mul_of_nonneg_left (le_trans _ (le_max_left _ _)) (inv_pos.2 εpos).le
change dist (Ψ x : q.Rep) (Ψ y) ≤ C
- refine (dist_le_diam_of_mem isCompact_univ.bounded (mem_univ _) (mem_univ _)).trans ?_
+ refine (dist_le_diam_of_mem isCompact_univ.isBounded (mem_univ _) (mem_univ _)).trans ?_
exact hdiam q qt
-- use the equality between `F p` and `F q` to deduce that the distances have equal
-- integer parts
Fin.castIso
and Fin.revPerm
with Fin.cast
and Fin.rev
for the bump of Std (#5847)
Some theorems in Data.Fin.Basic
are copied to Std at the recent commit in Std.
These are written using Fin.cast
and Fin.rev
, so declarations using Fin.castIso
and Fin.revPerm
in Mathlib should be rewritten.
Co-authored-by: Pol'tta / Miyahara Kō <52843868+Komyyy@users.noreply.github.com> Co-authored-by: Johan Commelin <johan@commelin.net>
@@ -684,7 +684,7 @@ instance : SecondCountableTopology GHSpace := by
the fact that `N p = N q`, this constructs `Ψ` between `s p` and `s q`, and then
composing with the canonical inclusion we get `Φ`. -/
have Npq : N p = N q := (Sigma.mk.inj_iff.1 hpq).1
- let Ψ : s p → s q := fun x => (E q).symm (Fin.castIso Npq ((E p) x))
+ let Ψ : s p → s q := fun x => (E q).symm (Fin.cast Npq ((E p) x))
let Φ : s p → q.Rep := fun x => Ψ x
-- Use the almost isometry `Φ` to show that `p.rep` and `q.rep`
-- are within controlled Gromov-Hausdorff distance.
@@ -709,7 +709,7 @@ instance : SecondCountableTopology GHSpace := by
let z := (E p).symm ⟨i, hip⟩
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
- have C2 : Fin.castIso Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
+ have C2 : Fin.cast Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ := by
rw [ihi_eq]; exact (E q).symm_apply_apply ⟨y, ys⟩
have : Φ z = y := by simp only; rw [C1, C2, C3]
@@ -727,13 +727,13 @@ instance : SecondCountableTopology GHSpace := by
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
have hiq : i < N q := by rwa [Npq] at hip
- have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
+ have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
have hjq : j < N q := by rwa [Npq] at hjp
have j' : j = ((E q) (Ψ y)).1 := by
- simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
+ simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
have : (F p).2 ((E p) x) ((E p) y) = ⌊ε⁻¹ * dist x y⌋ := by
simp only [(E p).symm_apply_apply]
@@ -835,7 +835,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
-- It remains to show that if `F p = F q`, then `p` and `q` are `ε`-close
rintro ⟨p, pt⟩ ⟨q, qt⟩ hpq
have Npq : N p = N q := Fin.ext_iff.1 (Sigma.mk.inj_iff.1 hpq).1
- let Ψ : s p → s q := fun x => (E q).symm (Fin.castIso Npq ((E p) x))
+ let Ψ : s p → s q := fun x => (E q).symm (Fin.cast Npq ((E p) x))
let Φ : s p → q.Rep := fun x => Ψ x
have main : ghDist p.Rep q.Rep ≤ ε + ε / 2 + ε := by
-- to prove the main inequality, argue that `s p` is `ε`-dense in `p`, and `s q` is `ε`-dense
@@ -861,7 +861,7 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
let z := (E p).symm ⟨i, hip⟩
use z
have C1 : (E p) z = ⟨i, hip⟩ := (E p).apply_symm_apply ⟨i, hip⟩
- have C2 : Fin.castIso Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
+ have C2 : Fin.cast Npq ⟨i, hip⟩ = ⟨i, hi⟩ := rfl
have C3 : (E q).symm ⟨i, hi⟩ = ⟨y, ys⟩ := by
rw [ihi_eq]; exact (E q).symm_apply_apply ⟨y, ys⟩
have : Φ z = y := by simp only; rw [C1, C2, C3]
@@ -878,12 +878,12 @@ theorem totallyBounded {t : Set GHSpace} {C : ℝ} {u : ℕ → ℝ} {K : ℕ
let i : ℕ := E p x
have hip : i < N p := ((E p) x).2
have hiq : i < N q := by rwa [Npq] at hip
- have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
+ have i' : i = (E q) (Ψ x) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- introduce `j`, that codes both `y` and `Φ y` in `fin (N p) = fin (N q)`
let j : ℕ := E p y
have hjp : j < N p := ((E p) y).2
have hjq : j < N q := by rwa [Npq] at hjp
- have j' : j = (E q) (Ψ y) := by simp only [Equiv.apply_symm_apply, Fin.coe_castIso]
+ have j' : j = (E q) (Ψ y) := by simp only [Equiv.apply_symm_apply, Fin.coe_cast]
-- Express `dist x y` in terms of `F p`
have Ap : ((F p).2 ⟨i, hip⟩ ⟨j, hjp⟩).1 = ⌊ε⁻¹ * dist x y⌋₊ :=
calc
@@ -248,7 +248,7 @@ theorem ghDist_le_hausdorffDist {X : Type u} [MetricSpace X] [CompactSpace X] [N
exists (⟨A, B⟩ : NonemptyCompacts ℓ_infty_ℝ × NonemptyCompacts ℓ_infty_ℝ)
#align Gromov_Hausdorff.GH_dist_le_Hausdorff_dist GromovHausdorff.ghDist_le_hausdorffDist
-set_option maxHeartbeats 500000 in
+set_option maxHeartbeats 400000 in
/-- The optimal coupling constructed above realizes exactly the Gromov-Hausdorff distance,
essentially by design. -/
theorem hausdorffDist_optimal {X : Type u} [MetricSpace X] [CompactSpace X] [Nonempty X]
@@ -1002,8 +1002,7 @@ def auxGluing (n : ℕ) : AuxGluingStruct (X n) :=
isom := (toGlueR_isometry _ _).comp (isometry_optimalGHInjr (X n) (X (n + 1))) }
#align Gromov_Hausdorff.aux_gluing GromovHausdorff.auxGluing
--- porting note: see lean4#2220
-local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y)
+local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue lean4#2220
/-- The Gromov-Hausdorff space is complete. -/
instance : CompleteSpace GHSpace := by
maxHeartbeats
(#6206)
git ls-files '*.lean' | xargs sed -i "s=maxHeartbeats [0-9]*$=& in="
Affected files:
Mathlib/CategoryTheory/Monoidal/Braided.lean:479:set_option maxHeartbeats 400000
Mathlib/FieldTheory/Adjoin.lean:1212:set_option synthInstance.maxHeartbeats 30000
Mathlib/FieldTheory/IsAlgClosed/Basic.lean:302:set_option maxHeartbeats 800000
Mathlib/FieldTheory/IsAlgClosed/Basic.lean:303:set_option synthInstance.maxHeartbeats 400000
Mathlib/RepresentationTheory/GroupCohomology/Basic.lean:202:set_option maxHeartbeats 6400000
Mathlib/RepresentationTheory/GroupCohomology/Resolution.lean:345:set_option maxHeartbeats 800000
Mathlib/Topology/MetricSpace/GromovHausdorff.lean:415:set_option maxHeartbeats 300000
@@ -412,7 +412,7 @@ theorem ghDist_eq_hausdorffDist (X : Type u) [MetricSpace X] [CompactSpace X] [N
exact (hausdorffDist_image (kuratowskiEmbedding.isometry _)).symm
#align Gromov_Hausdorff.GH_dist_eq_Hausdorff_dist GromovHausdorff.ghDist_eq_hausdorffDist
-set_option maxHeartbeats 300000
+set_option maxHeartbeats 300000 in
/-- The Gromov-Hausdorff distance defines a genuine distance on the Gromov-Hausdorff space. -/
instance : MetricSpace GHSpace where
dist := dist
@@ -2,11 +2,6 @@
Copyright (c) 2019 Sébastien Gouëzel. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sébastien Gouëzel
-
-! This file was ported from Lean 3 source module topology.metric_space.gromov_hausdorff
-! leanprover-community/mathlib commit 0c1f285a9f6e608ae2bdffa3f993eafb01eba829
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.SetTheory.Cardinal.Basic
import Mathlib.Topology.MetricSpace.Closeds
@@ -14,6 +9,8 @@ import Mathlib.Topology.MetricSpace.Completion
import Mathlib.Topology.MetricSpace.GromovHausdorffRealized
import Mathlib.Topology.MetricSpace.Kuratowski
+#align_import topology.metric_space.gromov_hausdorff from "leanprover-community/mathlib"@"0c1f285a9f6e608ae2bdffa3f993eafb01eba829"
+
/-!
# Gromov-Hausdorff distance
Co-authored-by: Jireh Loreaux <loreaujy@gmail.com> Co-authored-by: Antoine Chambert-Loir <antoine.chambert-loir@math.univ-paris-diderot.fr> Co-authored-by: Alex J Best <alex.j.best@gmail.com> Co-authored-by: Antoine Chambert-Loir <antoine.chambert-loir@u-paris.fr>
The unported dependencies are
algebra.order.module
init.core
linear_algebra.free_module.finite.rank
algebra.order.monoid.cancel.defs
algebra.abs
algebra.group_power.lemmas
init.data.list.basic
linear_algebra.free_module.rank
algebra.order.monoid.cancel.basic
init.data.list.default
topology.subset_properties
init.logic
The following 1 dependencies have changed in mathlib3 since they were ported, which may complicate porting this file