module Cat.Functor.Kan.Unique where

Uniqueness of Kan extensions🔗

Kan extensions (both left and right) are universal constructions, so they are unique when they exist. To get a theorem out of this intuition, we must be careful about how the structure and the properties are separated: Informally, we refer to the functor as “the Kan extension”, but in reality, the data associated with “the Kan extension of $F$ along $p$ ” also includes the natural transformation. For accuracy, using the setup from the diagram below, we should say “ $(G, η)$ is the Kan extension of $F$ along $p$ ”.

To show uniqueness, suppose that $(G_{1}, η_{1})$ and $(G_{2}, η_{2})$ and both left extensions of $F$ along $p .$ Diagramming this with both natural transformations shown is a bit of a nightmare: the option which doesn’t result in awful crossed arrows is to duplicate the span $C^{'} \leftarrow C \to D .$ So, to be clear: The upper triangle and the lower triangle are the same.

Recall that $(G_{1}, η_{1})$ being a left extension means we can (uniquely) factor natural transformations $F \to Mp$ through transformations $G_{1} \to M .$ We want a map $G_{1} \to G_{2},$ for which it will suffice to find a map $F \to G_{2} p$ — but $η_{2}$ is right there! In the other direction, we can factor $η_{1}$ to get a map $G_{2} \to G_{1} .$ Since these factorisations are unique, we have a natural isomorphism.

  σ-inversesp
    : ∀ {α : G₁ => G₂} {β : G₂ => G₁}
    → (α ◂ p) ∘nt η₁ ≡ η₂
    → (β ◂ p) ∘nt η₂ ≡ η₁
    → Inversesⁿ α β
  σ-inversesp α-factor β-factor = C'D.make-inverses
    (l₂.σ-uniq₂ η₂
      (ext λ j → sym (D.pullr (β-factor ηₚ j) ∙ α-factor ηₚ j))
      (ext λ j → sym (D.idl _)))
    (l₁.σ-uniq₂ η₁
      (ext λ j → sym (D.pullr (α-factor ηₚ j) ∙ β-factor ηₚ j))
      (ext λ j → sym (D.idl _)))

It’s immediate from the construction that this isomorphism “sends $η_{1}$ to $η_{2}$ ”.

  unit : (l₁.σ η₂ ◂ p) ∘nt η₁ ≡ η₂
  unit = l₁.σ-comm

Another uniqueness-like result we can state for left extensions is the following: Given any functor $G^{'} : C^{'} \to D$ and candidate “unit” transformation $η^{'} : F \to G^{'} p,$ if a left extension $Lan_{p} (F)$ sends $η^{'}$ to a natural isomorphism, then $(G^{'}, η^{'})$ is also a left extension of $F$ along $p .$

  is-invertible→is-lan
    : ∀ {G' : Functor C' D} {eta' : F => G' F∘ p}
    → is-invertibleⁿ (lan.σ eta')
    → is-lan p F G' eta'
  is-invertible→is-lan {G' = G'} {eta'} invert = lan' where
    open is-lan
    open C'D.is-invertible invert

    lan' : is-lan p F G' eta'
    lan' .σ α = lan.σ α ∘nt inv
    lan' .σ-comm {M} {α} = ext λ j →
      (lan.σ α .η _ D.∘ inv .η _) D.∘ eta' .η j                      ≡˘⟨ D.refl⟩∘⟨ (lan.σ-comm ηₚ _) ⟩
      (lan.σ α .η _ D.∘ inv .η _) D.∘ (lan.σ eta' .η _ D.∘ eta .η j) ≡⟨ D.cancel-inner (invr ηₚ _) ⟩
      lan.σ α .η _ D.∘ eta .η j                                      ≡⟨ lan.σ-comm ηₚ _ ⟩
      α .η j                                                         ∎
    lan' .σ-uniq {M} {α} {σ'} p = ext λ j →
      lan.σ α .η j D.∘ inv .η j                  ≡⟨ (lan.σ-uniq {σ' = σ' ∘nt lan.σ eta'} (ext λ j → p ηₚ j ∙ D.pushr (sym (lan.σ-comm ηₚ j))) ηₚ j) D.⟩∘⟨refl ⟩
      (σ' .η j D.∘ lan.σ eta' .η j) D.∘ inv .η _ ≡⟨ D.cancelr (invl ηₚ _) ⟩
      σ' .η j                                    ∎

Left Kan extensions are also invariant under arbitrary natural isomorphisms. To get better definitional control, we allow “adjusting” the resulting construction to talk about any natural transformation which is propositionally equal to the whiskering:

  natural-isos→is-lan
    : (p-iso : p ≅ⁿ p')
    → (F-iso : F ≅ⁿ F')
    → (G-iso : G ≅ⁿ G')
    → (Isoⁿ.to G-iso ◆ Isoⁿ.to p-iso) ∘nt eps ∘nt Isoⁿ.from F-iso ≡ eps'
    → is-lan p F G eps
    → is-lan p' F' G' eps'

As a consequence of uniqueness, if a functor preserves a given Kan extension, then it preserves all extensions for the same diagram.

preserves-lan→preserves-all
  : ∀ (H : Functor D E) {p : Functor C C'} {F : Functor C D}
  → ∀ {G} {eta : F => G F∘ p} (lan : is-lan p F G eta)
  → preserves-lan H lan
  → ∀ {G'} {eta' : F => G' F∘ p} (lan' : is-lan p F G' eta')
  → preserves-lan H lan'
preserves-lan→preserves-all {E = E} {C' = C'} H lan pres {G'} lan' =
  natural-isos→is-lan idni idni
    (F∘-iso-r One.unique)
    (ext λ c →
      (H.₁ (G'.₁ C'.id) E.∘ H.₁ _) E.∘ H.₁ _ E.∘ E.id ≡⟨ E.pullr (H.pulll (One.unit ηₚ c)) ⟩
      H.₁ (G'.₁ C'.id) E.∘ H.₁ _ E.∘ E.id             ≡⟨ H.eliml G'.F-id ∙ E.idr _ ⟩
      H.₁ _                                           ∎)
    pres
  where
    module C' = Cat.Reasoning C'
    module E = Cat.Reasoning E
    module H = Cat.Functor.Reasoning H
    module G' = Cat.Functor.Reasoning G'
    module One = Lan-unique lan lan'

Into univalent categories🔗

As traditional with universal constructions, if $F : C \to D$ takes values in a univalent category, we can sharpen our result: the type of left extensions of $F$ along $p$ is a proposition.

Lan-is-prop
  : ∀ {p : Functor C C'} {F : Functor C D} → is-category D → is-prop (Lan p F)
Lan-is-prop {C = C} {C' = C'} {D = D} {p = p} {F = F} d-cat L₁ L₂ = path where

That’s because if $D$ is univalent, then so is $[C^{'}, D]$ , so our natural isomorphism $i : G_{1} ≅ G_{2}$ is equivalent to an identification $i^{'} : G_{1} \equiv G_{2} .$ Then, our tiny lemma stating that this isomorphism “sends $η_{1}$ to $η_{2}$ ” is precisely the data of a dependent identification $η_{1} \equiv η_{2}$ over $i^{'} .$

  functor-path : L₁.Ext ≡ L₂.Ext
  functor-path = c'd-cat .to-path Lu.unique

  eta-path : PathP (λ i → F => functor-path i F∘ p) L₁.eta L₂.eta
  eta-path = Nat-pathp _ _ λ x →
    Univalent.Hom-pathp-reflr-iso d-cat (Lu.unit ηₚ _)

Since being a left extension is always a proposition when applied to $(G, η),$ even when the categories are not univalent, we can finish our proof.

  path : L₁ ≡ L₂
  path i .Ext = functor-path i
  path i .eta = eta-path i
  path i .has-lan =
    is-prop→pathp (λ i → is-lan-is-prop {p = p} {F} {functor-path i} {eta-path i})
      L₁.has-lan L₂.has-lan i