Smoothing of interval precosheaves and interleavings
Consulted manifestations, attribution and rights: DMP15-v1.
Precosheaves and the target category
A precosheaf on the interval category is a functor F : OpenInterval ⥤ C. The target C is an
arbitrary category, with universe parameters C : Type u and [Category.{v} C]. The
Set-valued pre-cosheaves of de Silva, Munch and Patel are the case C := Type u. Every
statement below specialises to that case without added hypotheses, and no proof uses a property
of Type. The source mentions pre-cosheaves in an arbitrary category in the remark opening its
§3.1 but states smoothing and interleavings for Set; stating them for an arbitrary target is a
choice of the library.
Smoothing
For ε : ℝ≥0, the smoothing endofunctor precomposes with thickening:
(smoothing ε).obj F = thickenFunctor ε ⋙ F
(smoothing ε).map α = Functor.whiskerLeft (thickenFunctor ε) α
Both equations hold by rfl, and smoothing ε is definitionally
(whiskeringLeft _ _ C).obj (thickenFunctor ε). It is reducible and given by components, so
((smoothing ε).obj F).obj I reduces to F.obj (thicken ε I).
The structure maps are:
smoothingUnit ε : 𝟭 ⟶ smoothing ε, whose component atFandIisFapplied toI ⊆ thicken ε I;smoothingMap h : smoothing ε ⟶ smoothing δforh : ε ≤ δ, fromthickenMap h;smoothingZeroIso : smoothing 0 ≅ 𝟭, fromthickenZeroIso;smoothingCompIso ε δ : smoothing δ ⋙ smoothing ε ≅ smoothing (ε + δ), fromthickenCompIso ε δ. Its component atFis(thickenFunctor ε ⋙ thickenFunctor δ) ⋙ F ≅ thickenFunctor (ε + δ) ⋙ F, soS_ε (S_δ F)thickens byεfirst;smoothingCommIso ε δ : smoothing ε ⋙ smoothing δ ≅ smoothing δ ⋙ smoothing ε, built from the two composition isomorphisms andε + δ = δ + ε;smoothingObjBotIso ε F : ((smoothing ε).obj F).obj ⊥ ≅ F.obj ⊥, the image underFofthicken ε ⊥ = ⊥. It is an isomorphism, not an equality, becausethicken ε ⊥is only propositionally equal to⊥.
The coherence laws are equations of natural transformations: smoothingMap preserves
identities and composition, the unit is compatible with enlargement, the zero unit is the
inverse of smoothingZeroIso, both composites F ⟶ S_ε S_δ F ≅ S_(ε+δ) F of two units are the
ε + δ unit, the two composites S_ε S_δ S_γ F ⟶ S_((ε+δ)+γ) F agree (sum associativity), and
smoothingCompIso is unital on both sides.
All of these follow from thinness of the interval category: a functor out of it sends parallel
morphisms to equal maps (map_eq_map_of_interval, map_comp_map_of_interval). The tactic
interval_coherence closes equations between composites of such images. It is a scoped macro,
available after open TDA.Reeb.
Interleavings
An ε-interleaving of F and G is a structure Interleaving ε F G with fields
φ : F ⟶ (smoothing ε).obj G
ψ : G ⟶ (smoothing ε).obj F
φ_ψ : φ ≫ (smoothing ε).map ψ ≫ (smoothingCompIso ε ε).hom.app F = (smoothingUnit (ε + ε)).app F
ψ_φ : ψ ≫ (smoothing ε).map φ ≫ (smoothingCompIso ε ε).hom.app G = (smoothingUnit (ε + ε)).app G
The fields are equations of natural transformations, and 2ε is written ε + ε. The
objectwise triangles ψ_(T_ε I) ∘ φ_I = F[I ⊆ T_ε T_ε I] and their mirror image are
φ_ψ_app and ψ_φ_app, and ofApp builds an interleaving from them. Interleaving ε F G is
data, not a proposition; Nonempty (Interleaving ε F G) is the existence statement.
The proved laws are:
- symmetry (
symm), and identity witnesses at every parameter (refl, given by the units); - enlargement (
mono): anε-interleaving is anε'-interleaving forε ≤ ε'; - composition (
trans): anε-interleaving ofF, Gand aδ-interleaving ofG, Hgive an(ε + δ)-interleaving ofF, H; - zero parameter (
ofIso,toIso,zeroEquivIso):0-interleavings are equivalent to natural isomorphisms,Interleaving 0 F G ≃ (F ≅ G), with both round trips proved; - smoothing (
smooth):S_εcarries aδ-interleaving ofF, Gto aδ-interleaving ofS_ε F, S_ε G; - self-smoothing (
selfSmoothing):Fisε-interleaved withS_ε F, withφthe composite of two units andψthe identity.
In trans the forward map is F(I) → G(T_ε I) → H(T_δ T_ε I). The reverse map is
H(I) → G(T_δ I) → F(T_ε T_δ I), followed by the identification with F(T_(ε+δ) I).
No interleaving distance is defined here. The fixtures show why a zero interleaving parameter
must be kept apart from a zero infimum: I ↦ {0 ∈ I} and I ↦ {0 ∈ closure I} are
ε-interleaved for every ε > 0 but are not 0-interleaved, since they differ on (0, 1).
The point precosheaves at 0 and 1 are 1-interleaved and not 0-interleaved.
Source correspondence
de Silva, Munch and Patel state §4.1–4.2 of Categorified Reeb Graphs for pre-cosheaves
Int → Set on the category Int of open intervals (§3), with the expansion I^ε given for
I = (a, b).
- Definition 4.1 gives an
ε-interleaving as natural familiesφ_I : F(I) → G(I^ε)andψ_I : G(I) → F(I^ε)withψ_(I^ε) ∘ φ_I = F[I ⊆ I^(2ε)]and the mirror equation, and notes that atε = 0this is an isomorphism. Observations 4.10 and 4.12 restate it as natural transformationsφ : F ⇒ GΩ_ε,ψ : G ⇒ FΩ_εwith(ψΩ_ε) ∘ φ = σ^(2ε)_Fand(φΩ_ε) ∘ ψ = σ^(2ε)_G, usingΩ_εΩ_ε = Ω_(2ε)implicitly. The structure fields are this form, with that identification made explicit assmoothingCompIso ε ε. - Observations 4.11 and 4.15 give the unit
σ^ε_F = Fω^ε, which issmoothingUnit. - Definition 4.14 defines
S_εas precomposition withΩ_ε, withS_ε[φ] = φΩ_ε. This issmoothing, withthickenFunctor εasΩ_ε. - Proposition 4.16 states
Ω_(ε₁+ε₂) = Ω_(ε₂)Ω_(ε₁), henceS_(ε₁+ε₂) = S_(ε₁)S_(ε₂). In the library these are isomorphisms (thickenCompIso,smoothingCompIso) in the same order, with their coherence proved. - Proposition 4.5 states that the interleaving distance is an extended pseudometric. Its proof
composes interleavings. The displayed reverse map
ψ³_I = ϕ¹_(I^ε₂) ∘ ψ²_Iis a misprint:ψ²_Ilands inG(I^ε₂), and the map out ofG(I^ε₂)towardsFisψ¹_(I^ε₂), givingψ³_I = ψ¹_(I^ε₂) ∘ ψ²_I.transuses the corrected map.symm,reflandtransare the witness-level content of symmetry,d(F, F) = 0and the triangle inequality. - Proposition 4.17 states that smoothing does not increase interleaving distance. Its proof
takes
φΩ_ε, ψΩ_εas the new witnesses. Their codomain isGΩ_δΩ_ε, whileS_δ(S_ε G) = GΩ_εΩ_δ; the source identifies the two implicitly (both equalΩ_(ε+δ)by Proposition 4.16). In the librarythicken ε (thicken δ I)andthicken δ (thicken ε I)are equal but not definitionally, sosmoothcomposes withsmoothingCommIso.
Admitting ∅, rays and ℝ as intervals, taking ε : ℝ≥0, and stating smoothing and
interleavings for an arbitrary target category are choices of the library. Self-smoothing, the composition and commutation
isomorphisms, and the coherence laws are stated in the source only implicitly or not at all.
Source: de Silva, Munch and Patel, Categorified Reeb Graphs.