module Cat.Univalent.Rezk.Universal where

Universal property of the Rezk completion🔗

With the Rezk completion, we defined, for any precategory a univalent category together with a weak equivalence functor We also stated, but did not in that module prove, the universal property of the Rezk completion: The functor is the universal map from to categories. This module actually proves it, but be warned: the proof is very technical, and is mostly a calculation.

In generic terms, universality of the Rezk completion follows from univalent categories being the class of local objects for the weak equivalences1: A category is univalent precisely if any weak equivalence induces2 a proper equivalence of categories

The high-level overview of the proof is as follows:

  • For any eso functor and for any all precategories, the functor is faithful. This is the least technical part of the proof, so we do it first.

  • If is additionally full, then is fully faithful.

  • If is a weak equivalence, and is univalent, then is essentially surjective. By the principle of unique choice, it is an equivalence, and thus3 an isomorphism.

Faithfulness🔗

The argument here is almost elementary: We’re given a witness that so all we have to do is manipulate the expression to something which has a subexpression. Since is eso, given we can find and an iso from which we can calculate:

eso→pre-faithful
  : (H : Functor A B) {F G : Functor B C}
  → is-eso H → (γ δ : F => G)
  → (∀ b → γ .η (H .F₀ b) ≡ δ .η (H .F₀ b)) → γ ≡ δ
eso→pre-faithful {A = A} {B = B} {C = C} H {F} {G} h-eso γ δ p = ext λ b →
  ∥-∥-proj (C.Hom-set _ _ _ _) do
  (b' , m) ← h-eso b
  ∥_∥.inc $
    γ .η b                                      ≡⟨ C.intror (F-map-iso F m .invl) ⟩≡
    γ .η b C.∘ F.₁ (m .to) C.∘ F.₁ (m .from)    ≡⟨ C.extendl (γ .is-natural _ _ _) ⟩≡
    G.₁ (m .to) C.∘ γ .η _ C.∘ F.₁ (m .from)    ≡⟨ ap₂ C._∘_ refl (ap₂ C._∘_ (p b') refl) ⟩≡
    G.₁ (m .to) C.∘ δ .η _ C.∘ F.₁ (m .from)    ≡⟨ C.extendl (sym (δ .is-natural _ _ _)) ⟩≡
    δ .η b C.∘ F.₁ (m .to) C.∘ F.₁ (m .from)    ≡⟨ C.elimr (F-map-iso F m .invl) ⟩≡
    δ .η b                                      ∎
  where module C = Cat.Reasoning C
        module F = Functor F
        module G = Functor G

The above is, unfortunately, the simplest result in this module. The next two proofs are both quite technical: that’s because we’re given some mere4 data, from the assumption that is a weak equivalence, so to use it as proper data, we need to show that whatever we want lives in a contractible space, after which we are free to project only the data we are interested in, and forget about the coherences.

It will turn out, however, that the coherence data necessary to make these types contractible is exactly the coherence data we need to show that we are indeed building functors, natural transformations, etc. So, not only do we need it to use unique choice, we also need it to show we’re doing category theory.

Full-faithfulness🔗

Let and be as before, except now assume that is full (in addition to eso).

eso-full→pre-ff
  : (H : Functor A B)
  → is-eso H → is-full H
  → is-fully-faithful {C = Cat[ B , C ]} (precompose H)
eso-full→pre-ff {A = A} {B = B} {C = C} H H-eso H-full = res where

We will show that, for every natural transformation and each there is a contractible type of “component data” over These data consist of morphisms each equipped with a witness that acts naturally when faced with isomorphisms

In more detail, if we’re given an essential fibre of over we can use to “match up” our component with the components of the natural transformation since we’ve claimed to have a and someone has just handed us a then it darn well better be the case that is

    T : B.Ob → Type _
    T b = Σ (C.Hom (F.₀ b) (G.₀ b)) λ g →
      (a : A.Ob) (f : H.₀ a B.≅ b) →
      γ.η a ≡ G.₁ (f .from) C.∘ g C.∘ F.₁ (f .to)

We’ll first show that components exist at all. Assume that we have some and an essential fibre of over it5. In this situation, guided by the compatibility condition (and isomorphisms being just the best), we can actually define the component to be “whatever satisfies compatibility at ” and a short calculation establishes that defining

      g = G.₁ h.to C.∘ γ.η a₀ C.∘ F.₁ h.from

is indeed a possible choice. We present the formalisation below, but do not comment on the calculation, leaving it to the curious reader to load this file in Agda and poke around the proof.

      lemma : (a : A.Ob) (f : H.₀ a B.≅ b)
            → γ.η a ≡ G.₁ (f .from) C.∘ g C.∘ F.₁ (f .to)
      lemma a f = ∥-∥-proj (C.Hom-set _ _ _ _) do
        (k , p)   ← H-full (h.from B.∘ B.to f)
        (k⁻¹ , q) ← H-full (B.from f B.∘ h.to)
        ∥_∥.inc $
             C.intror (F.annihilate
               (ap₂ B._∘_ q p ·· B.cancel-inner h.invl ·· f .invr))
          ·· C.extendl (γ.is-natural _ _ _)
          ·· ap₂ (λ e e' → G.₁ e C.∘ γ.η a₀ C.∘ F.₁ e') q p
          ·· ap₂ (λ e e' → e C.∘ γ.η a₀ C.∘ e') (G.F-∘ _ _) (F.F-∘ _ _)
          ·· C.pullr (ap (G.₁ h.to C.∘_) (C.pulll refl) ∙ C.pulll refl)

Anyway, because of how we’ve phrased the coherence condition, if both satisfy it, then we have equal to both and 6 Since isomorphisms are both monic and epic, we can cancel and from these equations to conclude Since the coherence condition is a proposition, the type of component data over is a proposition.

    T-prop : ∀ b → is-prop (T b)
    T-prop b (g , coh) (g' , coh') = Σ-prop-path (λ x → hlevel 1) $ ∥-∥-proj (hlevel 1) do
      (a₀ , h) ← H-eso b
      pure $ C.iso→epic (F-map-iso F h) _ _
        (C.iso→monic (F-map-iso G (h B.Iso⁻¹)) _ _
          (sym (coh a₀ h) ∙ coh' a₀ h))

Given any being eso means that we merely have an essential fibre of over But since the type of components over is a proposition, if we’re going to use it to construct a component over then we are granted the honour of actually getting hold of an pair.

    mkT' : ∀ b → ∥ Essential-fibre H b ∥ → ∥ T b ∥
    mkT' b he = do
      (a₀ , h) ← he
      ∥_∥.inc (Mk.g b a₀ h , Mk.lemma b a₀ h)

    mkT : ∀ b → T b
    mkT b = ∥-∥-proj (T-prop b) (mkT' b (H-eso b))

Another calculation shows that, since is full, given any pair of essential fibres over and over with a mediating map we can choose a map satisfying and since both the components at and “come from ” (which is natural), we get a naturality result for the transformation we’re defining, too.

That computation is a bit weirder, so it’s hidden in this <details> tag.
    module
      _ {b b'} (f : B.Hom b b') (a a' : A.Ob)
        (h : H.₀ a B.≅ b) (h' : H.₀ a' B.≅ b')
      where
      private
        module h' = B._≅_ h'
        module h = B._≅_ h

      naturality : _
      naturality = ∥-∥-proj (C.Hom-set _ _ _ _) do
        (k , p) ← H-full (h'.from B.∘ f B.∘ h.to)
        pure $ C.pullr (C.pullr (F.weave (sym
                  (B.pushl p ∙ ap₂ B._∘_ refl (B.cancelr h.invl)))))
            ·· ap₂ C._∘_ refl (C.extendl (γ.is-natural _ _ _))
            ·· C.extendl (G.weave (B.lswizzle p h'.invl))

Because of this naturality result, all the components we’ve chosen piece together into a natural transformation. And since we defined parametrically over the choice of essential fibre, if we’re looking at some then we can choose the identity isomorphism, from which it falls out that Since we had already established that is faithful, and now we’ve shown it is full, it is fully faithful.

    δ : F => G
    δ .η b = mkT b .fst
    δ .is-natural b b' f = ∥-∥-elim₂
      {P = λ α β → ∥-∥-proj (T-prop b') (mkT' b' α) .fst C.∘ F.₁ f
                 ≡ G.₁ f C.∘ ∥-∥-proj (T-prop b) (mkT' b β) .fst}
      (λ _ _ → C.Hom-set _ _ _ _)
      (λ (a' , h') (a , h) → naturality f a a' h h') (H-eso b') (H-eso b)

  full : is-full (precompose H)
  full {x = x} {y = y} γ = pure (δ _ _ γ , ext p) where
    p : ∀ b → δ _ _ γ .η (H.₀ b) ≡ γ .η b
    p b = subst
      (λ e → ∥-∥-proj (T-prop _ _ γ (H.₀ b)) (mkT' _ _ γ (H.₀ b) e) .fst
           ≡ γ .η b)
      (squash (inc (b , B.id-iso)) (H-eso (H.₀ b)))
      (C.eliml (y .F-id) ∙ C.elimr (x .F-id))

  res : is-fully-faithful (precompose H)
  res = full+faithful→ff (precompose H) full λ {F} {G} {γ} {δ} p →
    eso→pre-faithful H H-eso γ δ λ b → p ηₚ b

Essential surjectivity🔗

The rest of the proof proceeds in this same way: Define a type which characterises, up to a compatible space of choices, first the action on morphisms of a functor which inverts and in terms of this type, the action on morphisms. It’s mostly the same trick as above, but a lot wilder. We do not comment on it too extensively: the curious reader, again, can load this file in Agda and play around.

The type of object-candidates Obs is indexed by a and any object candidate must come with a family of isomorphisms giving, for every way of expressing as coming from a way of coming from To show this type is a proposition, we additionally require a naturality condition for these isomorphisms.

  private module _ (F : Functor A C) where
    private module F = FR F

    Obs : B.Ob → Type _
    Obs b =
      Σ C.Ob λ c →
      Σ ((a : A.Ob) (h : H.₀ a B.≅ b) → F.₀ a C.≅ c) λ k →
      ((a , h) (a' , h') : Essential-fibre H b) (f : A.Hom a a') →
      h' .to B.∘ H.₁ f ≡ h .to →
      k a' h' .to C.∘ F.₁ f ≡ k a h .to

Note that we can derive an object candidate over from a fibre of over Moreover, this choice is a center of contraction, so we can once more apply unique choice and the assumption that is eso to conclude that every has an object candidate over it.

    obj' : ∀ {b} → Essential-fibre H b → Obs b
    obj' (a₀ , h₀) .fst = F.₀ a₀
    obj' (a₀ , h₀) .snd .fst a h = F-map-iso F (H.iso.from (h B.∘Iso (h₀ B.Iso⁻¹)))
    obj' (a₀ , h₀) .snd .snd (a , h) (a' , h') f p = F.collapse (H.ipushr p)

    Obs-is-prop : ∀ {b} (f : Essential-fibre H b) (c : Obs b) → obj' f ≡ c
    Obs-is-prop (a₀ , h₀) (c' , k' , β) =
      Σ-pathp (Univalent.iso→path c-cat c≅c') $
      Σ-prop-pathp
        (λ i x → Π-is-hlevel³ 1 λ _ _ _ → Π-is-hlevel 1 λ _ → C.Hom-set _ _ _ _) $
        funextP λ a → funextP λ h → C.≅-pathp _ _ $
          Univalent.Hom-pathp-reflr-iso c-cat {q = c≅c'}
            ( C.pullr (F.eliml (H.from-id (h₀ .invr)))
            ∙ β _ _ _ (H.ε-lswizzle (h₀ .invl)))
      where
        ckα = obj' (a₀ , h₀)
        c = ckα .fst
        k = ckα .snd .fst
        α = ckα .snd .snd
        c≅c' = (k a₀ h₀ C.Iso⁻¹) C.∘Iso k' a₀ h₀

We will write G₀ for the canonical choice of object candidate, and k for the associated family of isomorphisms. The type of morphism candidates over consists of maps which are compatible with the reindexing isomorphisms for any essential fibre over over and map satisfying

    compat : ∀ {b b'} (f : B.Hom b b') → C.Hom (G₀ b) (G₀ b') → Type _
    compat {b} {b'} f g =
      ∀ a (h : H.₀ a B.≅ b) a' (h' : H.₀ a' B.≅ b') (l : A.Hom a a')
      → h' .to B.∘ H.₁ l ≡ f B.∘ h .to
      → k a' h' .to C.∘ F.₁ l ≡ g C.∘ k a h .to

    Homs : ∀ {b b'} (f : B.Hom b b') → Type _
    Homs {b = b} {b'} f = Σ (C.Hom (G₀ b) (G₀ b')) (compat f)
It will again turn out that any initial choice of fibre over and gives a morphism candidate over and the compatibility data is exactly what we need to show the type of morphism candidates is a proposition.

This proof really isn’t commented. I’m sorry.

    module _ {b b'} (f : B.Hom b b')
             a₀ (h₀ : H.₀ a₀ B.≅ b)
             a₀' (h₀' : H.₀ a₀' B.≅ b') where
      l₀ : A.Hom a₀ a₀'
      l₀ = H.from (h₀' .from B.∘ f B.∘ h₀ .to)

      p : h₀' .to B.∘ H.₁ l₀ ≡ (f B.∘ h₀ .to)
      p = H.ε-lswizzle (h₀' .invl)

      g₀ : C.Hom (G₀ b) (G₀ b')
      g₀ = k a₀' h₀' .to C.∘ F.₁ l₀ C.∘ k a₀ h₀ .from

      module _ a (h : H.₀ a B.≅ b) a' (h' : H.₀ a' B.≅ b')
                (l : A.Hom a a') (w : h' .to B.∘ H.₁ l ≡ f B.∘ h .to) where
        m : a₀ A.≅ a
        m = H.iso.from (h₀ B.∘Iso (h B.Iso⁻¹))

        m' : a₀' A.≅ a'
        m' = H.iso.from (h₀' B.∘Iso (h' B.Iso⁻¹))

        α : k a₀ h₀ .from ≡ F.₁ (m .from) C.∘ k a h .from
        α = C.inverse-unique _ _ {f = k a₀ h₀} {g = F-map-iso F m C.∘Iso k a h} $
          sym (kcomm _ _ _ (H.ε-lswizzle (h .invl)))

        γ : H.₁ (m' .to) B.∘ H.₁ l₀ ≡ H.₁ l B.∘ H.₁ (m .to)
        γ =  B.pushl (H.ε _)
          ·· ap₂ B._∘_ refl (p ∙
              B.pushl (B.insertr (h .invl) ∙ ap₂ B._∘_ (sym w) refl))
          ·· B.deletel (h' .invr)
          ∙ ap₂ B._∘_ refl (sym (H.ε _))

        γ' : l₀ A.∘ m .from ≡ m' .from A.∘ l
        γ' = A.iso→monic m' _ _ $ A.extendl (H.injective (H.swap γ))
                               ·· A.elimr (m .invl)
                               ·· A.insertl (m' .invl)

        δ : g₀ C.∘ k a h .to ≡ k a' h' .to C.∘ F.₁ l
        δ = C.pullr ( C.pullr refl ·· ap₂ C._∘_ refl (C.pushl α)
                   ·· C.pulll refl ∙ C.elimr (k a h .invr))
          ·· ap₂ C._∘_ refl (F.weave γ')
          ·· C.pulll (C.pushl (sym (kcomm _ _ _ (H.ε-lswizzle (h' .invl))))
              ∙ C.elimr (F.annihilate (m' .invl)))

      Homs-pt : Homs f
      Homs-pt = g₀ , λ a h a' h' l w → sym (δ a h a' h' l w)

      Homs-prop' : (h' : Homs f) → h' .fst ≡ g₀
      Homs-prop' (g₁ , w) = C.iso→epic (k a₀ h₀) _ _
        (sym (δ a₀ h₀ a₀' h₀' l₀ p ∙ w a₀ h₀ a₀' h₀' l₀ p))

    Homs-contr' : ∀ {b b'} (f : B.Hom b b') → ∥ is-contr (Homs f) ∥
    Homs-contr' {b = b} {b'} f = do
      (a₀ , h)   ← H-eso b
      (a₀' , h') ← H-eso b'
      inc (contr (Homs-pt f a₀ h a₀' h') λ h' → Σ-prop-path
        (λ _ → compat-prop f) (sym (Homs-prop' f _ _ _ _ h')))

    Homs-contr : ∀ {b b'} (f : B.Hom b b') → is-contr (Homs f)
    Homs-contr f = ∥-∥-proj! (Homs-contr' f)

    G₁ : ∀ {b b'} → B.Hom b b' → C.Hom (G₀ b) (G₀ b')
    G₁ f = Homs-contr f .centre .fst
Using the compatibility condition, and choices of we can show that the assignment of morphism candidates does assemble into a functor.
    module G∘ {x y z} (f : B.Hom y z) (g : B.Hom x y)
              {ax ay az} (hx : H.₀ ax B.≅ x) (hy : H.₀ ay B.≅ y)
              (hz : H.₀ az B.≅ z) where

      af : A.Hom ay az
      af = H.from (hz .from B.∘ f B.∘ hy .to)

      ag : A.Hom ax ay
      ag = H.from (hy .from B.∘ g B.∘ hx .to)

      h' : H.₁ (af A.∘ ag) ≡ hz .from B.∘ f B.∘ g B.∘ hx .to
      h' = H.ε-expand refl ∙ B.pullr (B.cancel-inner (hy .invl))

      commutes : G₁ (f B.∘ g) ≡ G₁ f C.∘ G₁ g
      commutes = C.iso→epic (k ax hx) _ _ $
          sym (Homs-contr (f B.∘ g) .centre .snd ax hx az hz (af A.∘ ag)
                (ap₂ B._∘_ refl h' ·· B.cancell (hz .invl) ·· B.pulll refl))
        ∙ sym ( C.pullr (sym (Homs-contr g .centre .snd ax hx ay hy ag
                  (H.ε-lswizzle (hy .invl))))
              ∙ C.pulll (sym (Homs-contr f .centre .snd ay hy az hz af
                  (H.ε-lswizzle (hz .invl))))
              ∙ F.pullr refl)

In this manner, the assignment of object candidates and morphism candidates fits together into a functor After finishing this, we have to show that But the compatibility data which we have used to uniquely characterise uniquely characterises after all, and it does so as composing with to give .

    G : Functor B C
    G .F₀ b = G₀ b
    G .F₁ f = G₁ f

    G .F-id = ap fst $ Homs-contr B.id .paths $ C.id , λ a h a' h' l w →
      sym (C.idl _ ∙ sym (kcomm (a , h) (a' , h') l (w ∙ B.idl _)))

Note that we proved7 that is functorial given choices of essential fibres of all three objects involved in the composition. Since we’re showing an equality in a set — a proposition — these choices don’t matter, so we can use essential surjectivity of

    G .F-∘ {x} {y} {z} f g = ∥-∥-proj! do
      (ax , hx) ← H-eso x
      (ay , hy) ← H-eso y
      (az , hz) ← H-eso z
      inc (G∘.commutes f g hx hy hz)

To use the unique charactersation of as “the functor satisfying ”, observe: for any the object can be made into an object candidate over and since the type of object candidates is a proposition, our candidate is identical to the value of That’s half of established right off the bat!

    module _ (x : A.Ob) where
      hf-obs : Obs (H.₀ x)
      hf-obs .fst = F.F₀ x
      hf-obs .snd .fst a h = F-map-iso F (H.iso.from h)
      hf-obs .snd .snd (a , h) (a' , h') f α = F.collapse (H.inv∘l α)

      abstract
        objp : G₀ (H.₀ x) ≡ F.₀ x
        objp = ap fst $ summon {H.₀ x} (H-eso _) .paths hf-obs

Over that identification, we can show that, for any in the value is also a candidate for the morphism so these are also identical. This proof is a bit hairier, because only has the right type if we adjust it by the proof that we have to transport and then as punishment for our hubris, invoke a lot of technical lemmas about the characterisation of PathP in the morphism spaces of (pre)categories.

    module _ {x y} (f : A.Hom x y) where
      hom' : Homs (H.₁ f)
      hom' .fst = transport (λ i → C.Hom (objp x (~ i)) (objp y (~ i))) (F.₁ f)
      hom' .snd a h a' h' l w = sym $
        C.pushl (Hom-transport C (sym (objp x)) (sym (objp y)) (F.₁ f))
        ·· ap₂ C._∘_ refl
          ( C.pullr (from-pathp-from C (objp x) (λ i → kp x a h i .to))
          ∙ F.weave (H.ε-twist (sym w)))
        ·· C.pulll (from-pathp-to C (sym (objp y)) λ i → kp y a' h' (~ i) .to)

      homp : transport (λ i → C.Hom (objp x (~ i)) (objp y (~ i))) (F.₁ f)
           ≡ Homs-contr (H.₁ f) .centre .fst
      homp = ap fst $ sym $ Homs-contr (H.₁ f) .paths hom'

    correct : G F∘ H ≡ F
    correct = Functor-path objp λ {x} {y} f → symP
      {A = λ i → C.Hom (objp x (~ i)) (objp y (~ i))} $
      to-pathp (homp f)

Since we’ve shown that so in particular we’ve now put together proofs that is fully faithful and, since the construction above works for any essentially surjective. Even better, since we’ve actually constructed a functor we’ve shown that is split essentially surjective! Since is univalent whenever is, the splitting would be automatic, but this is a nice strengthening.

  weak-equiv→pre-equiv : is-equivalence {C = Cat[ B , C ]} (precompose H)
  weak-equiv→pre-equiv = ff+split-eso→is-equivalence {F = precompose H}
    (eso-full→pre-ff H H-eso λ g → inc (H.from g , H.ε g))
    λ F → G F , path→iso (correct F)

And since a functor is an equivalence of categories iff. it is an isomorphism of categories, we also have that the rule sending to its is an equivalence of types.

  weak-equiv→pre-iso : is-precat-iso {C = Cat[ B , C ]} (precompose H)
  weak-equiv→pre-iso = is-equivalence→is-precat-iso (precompose H) weak-equiv→pre-equiv
    (Functor-is-category c-cat)
    (Functor-is-category c-cat)

Restating the result that acts on objects as an equivalence of types, we have the following result: If is a weak equivalence (a fully faithful and essentially surjective functor), then for any category and functor there is a contractible space(!) of extensions which factor through

weak-equiv→reflection
  : (F : Functor C C⁺) → is-eso F → is-fully-faithful F
  → {D : Precategory o ℓ} → is-category D
  → (G : Functor C D)
  → is-contr (Σ (Functor C⁺ D) λ H → H F∘ F ≡ G)
weak-equiv→reflection F F-eso F-ff D-cat G =
  weak-equiv→pre-iso F F-eso F-ff D-cat
    .is-precat-iso.has-is-iso .is-eqv G

Note that this is only half of the point of the Rezk completion: we would also like for to be univalent, but that is not necessary for to think that precomposition with is an isomorphism.


  1. a weak equivalence is a fully faithful, essentially surjective functor↩︎

  2. by precomposition↩︎

  3. since both its domain and codomain are univalent↩︎

  4. truncated↩︎

  5. Don’t worry about actually getting your hands on an ↩︎

  6. I’ve implicitly used that is eso to cough up an over since we’re proving a proposition↩︎

  7. in the second <details> tag above↩︎