Hausdorff bounds, reachable sets, and metric properties for the strong converse
DefinitionNadlerCLS_Supplement_HausdorffBoundFor a nonnegative distance function and subsets of a common space, the relation
is represented by the two directed conditions that every point of is within of some point of , and every point of is within of some point of . For a correspondence , is the set of all states reachable after exactly admissible updates from .
The module also gives direct predicates for Hausdorff continuity, robust global convergence, local uniform convergence, a real-valued metric, equality of the induced topology with a reference topology, compactness, and completeness. These are the notions appearing in Theorem 4.1.
Formalization Note Hausdorff bounds are unfolded rather than installing a second metric-space instance. For nonempty compact sets this is equivalent to the usual Hausdorff-distance inequality. Compactness is stated by finite subcovers and completeness by convergence of Cauchy sequences.
import Mathlib
set_option autoImplicit false
namespace NadlerCLS
namespace Supplement
/-- A pointwise formulation of the assertion that the Hausdorff distance between `A` and `B`
is at most `r`, for an arbitrary candidate distance `rho`. This avoids installing a second
metric-space instance when Theorem 4.1 compares the original metric with the constructed one.
(Xiong–Vlatakis-Gkaragkounis, *On the Complexity of Finding Fixed Points for Set-Valued
Contractions*, arXiv:2609.14101, held version of 2026-11-03, sha256
1fcc5a02…6dc485, Section 4 and Theorem 4.1, p.12.) -/
def HausdorffBound {X : Type*} (rho : X → X → ℝ) (A B : Set X) (r : ℝ) : Prop :=
(∀ a ∈ A, ∃ b ∈ B, rho a b ≤ r) ∧ (∀ b ∈ B, ∃ a ∈ A, rho a b ≤ r)
/-- The set `F^[t](x)` of all states reachable after exactly `t` admissible updates from `x`
(Section 4, equation (4.1), p.12). -/
def reachable {X : Type*} (F : X → Set X) : ℕ → X → Set X
| 0, x => {x}
| t + 1, x => ⋃ y ∈ reachable F t x, F y
/-- Hausdorff continuity of a compact-valued correspondence, written directly in
epsilon–delta form using `HausdorffBound`. -/
def HausdorffContinuous {X : Type*} [MetricSpace X] (F : X → Set X) : Prop :=
∀ (x : X) (η : ℝ), 0 < η → ∃ δ : ℝ, 0 < δ ∧
∀ y, dist x y < δ → HausdorffBound dist (F x) (F y) η
/-- Robust global convergence (4.1): all states reachable after exactly `t` updates converge
to the endpoint, for each initial state. -/
def RobustlyGloballyConverges {X : Type*} [MetricSpace X] (F : X → Set X)
(xstar : X) : Prop :=
∀ (x : X) (η : ℝ), 0 < η → ∃ N : ℕ, ∀ t ≥ N,
HausdorffBound dist (reachable F t x) {xstar} η
/-- Local uniformity (4.2): convergence of the full reachable sets is uniform on some open
neighborhood of the endpoint. -/
def LocallyUniformlyConverges {X : Type*} [MetricSpace X] (F : X → Set X)
(xstar : X) : Prop :=
∃ U : Set X, IsOpen U ∧ xstar ∈ U ∧
∀ η : ℝ, 0 < η → ∃ N : ℕ, ∀ t ≥ N, ∀ x ∈ U,
HausdorffBound dist (reachable F t x) {xstar} η
/-- The ordinary metric axioms for a real-valued distance function. -/
def IsMetricFunction {X : Type*} (D : X → X → ℝ) : Prop :=
(∀ x y, 0 ≤ D x y) ∧
(∀ x y, D x y = 0 ↔ x = y) ∧
(∀ x y, D x y = D y x) ∧
(∀ x y z, D x z ≤ D x y + D y z)
/-- Openness for the topology generated by a metric function `D`. -/
def IsOpenFor {X : Type*} (D : X → X → ℝ) (s : Set X) : Prop :=
∀ x ∈ s, ∃ r : ℝ, 0 < r ∧ ∀ y, D x y < r → y ∈ s
/-- The metric function `D` generates the already installed topology. -/
def GeneratesSameTopology {X : Type*} [TopologicalSpace X] (D : X → X → ℝ) : Prop :=
∀ s : Set X, IsOpen s ↔ IsOpenFor D s
/-- Compactness for the topology generated by `D`, expressed by finite subcovers. -/
def CompactFor {X : Type*} (D : X → X → ℝ) : Prop :=
∀ (ι : Type) (U : ι → Set X),
(∀ i, IsOpenFor D (U i)) →
(∀ x, ∃ i, x ∈ U i) →
∃ J : Set ι, J.Finite ∧ ∀ x, ∃ i ∈ J, x ∈ U i
/-- Sequential completeness for the metric function `D`. -/
def CompleteFor {X : Type*} (D : X → X → ℝ) : Prop :=
∀ u : ℕ → X,
(∀ η : ℝ, 0 < η → ∃ N : ℕ, ∀ m ≥ N, ∀ n ≥ N, D (u m) (u n) < η) →
∃ x : X, ∀ η : ℝ, 0 < η → ∃ N : ℕ, ∀ n ≥ N, D (u n) x < η
end Supplement
end NadlerCLS