module Cat.Instances.Slice where
private variable o β o' β' : Level open Functor open _=>_ open _β£_ module _ {o β} {C : Precategory o β} where private module C = Cat.Reasoning C variable a b c : C.Ob
Slice categoriesπ
When working in there is an evident notion of family indexed by a set: a family of sets is equivalently a functor where we have equipped the set with the discrete category structure. This works essentially because of the discrete category-global sections adjunction, but in general this can not be applied to other categories, like How, then, should we work with βindexed familiesβ in general categories?
The answer is to consider, rather than families themselves, the projections from their total spaces as the primitive objects. A family indexed by then, would consist of an object and a morphism where is considered as the βtotal spaceβ object and assigns gives the βtagβ of each object. By analysing how pulls back along maps we recover a notion of βfibresβ: the collection with index can be recovered as the pullback
Note that, since the discussion in the preceding paragraph made no mention of the category of sets, it applies in any category! More generally, for any category and object we have a category of objects indexed by , the slice category An object of βthe slice over β is given by an object to serve as the domain, and a map
record /-Obj (c : C.Ob) : Type (o β β) where constructor cut field {domain} : C.Ob map : C.Hom domain c
A map between and is given by a map such that the triangle below commutes. Since weβre thinking of and as families indexed by , commutativity of the triangle says that the map βrespects reindexingβ, or less obliquely βpreserves fibresβ.
record /-Hom (a b : /-Obj c) : Type β where no-eta-equality private module a = /-Obj a module b = /-Obj b field map : C.Hom a.domain b.domain commutes : b.map C.β map β‘ a.map
/-Obj-path : β {c} {x y : /-Obj c} β (p : x ./-Obj.domain β‘ y ./-Obj.domain) β PathP (Ξ» i β C.Hom (p i) c) (x ./-Obj.map) (y ./-Obj.map) β x β‘ y /-Obj-path p q i ./-Obj.domain = p i /-Obj-path p q i ./-Obj.map = q i /-Hom-pathp : β {c a a' b b'} (p : a β‘ a') (q : b β‘ b') {x : /-Hom {c = c} a b} {y : /-Hom a' b'} β PathP (Ξ» i β C.Hom (p i ./-Obj.domain) (q i ./-Obj.domain)) (x ./-Hom.map) (y ./-Hom.map) β PathP (Ξ» i β /-Hom (p i) (q i)) x y /-Hom-pathp p q {x} {y} r = path where open /-Hom path : PathP (Ξ» i β /-Hom (p i) (q i)) x y path i .map = r i path i .commutes = is-propβpathp (Ξ» i β C.Hom-set (p i ./-Obj.domain) _ (q i ./-Obj.map C.β r i) (p i ./-Obj.map)) (x .commutes) (y .commutes) i /-Hom-path : β {c a b} {x y : /-Hom {c = c} a b} β x ./-Hom.map β‘ y ./-Hom.map β x β‘ y /-Hom-path = /-Hom-pathp refl refl instance Extensional-/-Hom : β {c a b β} β¦ sa : Extensional (C.Hom (/-Obj.domain a) (/-Obj.domain b)) β β¦ β Extensional (/-Hom {c = c} a b) β Extensional-/-Hom β¦ sa β¦ = injectionβextensional! (/-Hom-pathp refl refl) sa unquoteDecl H-Level-/-Hom = declare-record-hlevel 2 H-Level-/-Hom (quote /-Hom)
The slice category
is given by the /-Obj
and /-Hom
s.
Slice : (C : Precategory o β) β β C β β Precategory _ _ Slice C c = precat where import Cat.Reasoning C as C open Precategory open /-Hom open /-Obj precat : Precategory _ _ precat .Ob = /-Obj {C = C} c precat .Hom = /-Hom precat .Hom-set x y = hlevel 2 precat .id .map = C.id precat .id .commutes = C.idr _
For composition in the slice over note that if the triangle (the commutativity condition for and the rhombus (the commutativity condition for both commute, then so does the larger triangle (the commutativity for
precat ._β_ {x} {y} {z} f g = fog where module f = /-Hom f module g = /-Hom g fog : /-Hom _ _ fog .map = f.map C.β g.map fog .commutes = z .map C.β f.map C.β g.map β‘β¨ C.pulll f.commutes β©β‘ y .map C.β g.map β‘β¨ g.commutes β©β‘ x .map β precat .idr f = ext (C.idr _) precat .idl f = ext (C.idl _) precat .assoc f g h = ext (C.assoc _ _ _)
There is an evident projection functor from to that only remembers the domains.
module _ {o β} {C : Precategory o β} {c} where open /-Hom open /-Obj private module C = Cat.Reasoning C module C/c = Cat.Reasoning (Slice C c)
Forget/ : Functor (Slice C c) C Forget/ .Fβ o = o .domain Forget/ .Fβ f = f .map Forget/ .F-id = refl Forget/ .F-β _ _ = refl
Furthermore, this forgetful functor is easily seen to be faithful and conservative: if is a morphism in whose underlying map has an inverse in then clearly also makes the triangle commute, so that is invertible in
Forget/-is-faithful : is-faithful Forget/ Forget/-is-faithful p = ext p Forget/-is-conservative : is-conservative Forget/ Forget/-is-conservative {f = f} i = C/c.make-invertible fβ»ΒΉ (ext i.invl) (ext i.invr) where module i = C.is-invertible i fβ»ΒΉ : /-Hom _ _ fβ»ΒΉ .map = i.inv fβ»ΒΉ .commutes = C.rswizzle (sym (f .commutes)) i.invl
Finite limitsπ
We discuss the construction of finite limits in the slice of First, every slice category has a terminal object, given by the identity map
module _ {o β} {C : Precategory o β} {c : β C β} where import Cat.Reasoning C as C import Cat.Reasoning (Slice C c) as C/c open /-Hom open /-Obj Slice-terminal-object' : is-terminal (Slice C c) (cut C.id) Slice-terminal-object' obj .centre .map = obj .map Slice-terminal-object' obj .centre .commutes = C.idl _ Slice-terminal-object' obj .paths other = ext (sym (other .commutes) β C.idl _) Slice-terminal-object : Terminal (Slice C c) Slice-terminal-object .Terminal.top = _ Slice-terminal-object .Terminal.hasβ€ = Slice-terminal-object'
module _ {o β} {C : Precategory o β} {c : β C β} where import Cat.Reasoning C as C import Cat.Reasoning (Slice C c) as C/c private variable a b : C.Ob f g Οβ Οβ : C.Hom a b open /-Hom open /-Obj
Products in a slice category are slightly more complicated β but if youβve ever heard a pullback referred to as a βfibre(d) productβ, you already know what weβre up to! Indeed, in defining pullback diagrams, we noted that the pullback of and is exactly the product in the slice over
Suppose we have a pullback diagram like the one below, i.e., a limit of the diagram in the category Weβll show that itβs also a limit of the (discrete) diagram consisting of and but now in the slice category
For starters, we have to define a map to serve as the actual object in the slice. It seems like there are two choices, depending on how you trace out the square. But the square commutes, which by definition means that we donβt really have a choice. We choose i.e.Β following the top face then the right face, for definiteness.
module _ {f g : /-Obj c} {Pb : C.Ob} {Οβ : C.Hom Pb (f .domain)} {Οβ : C.Hom Pb (g .domain)} (pb : is-pullback C {X = f .domain} {Z = c} {Y = g .domain} {P = Pb} Οβ (map {_} {_} {C} {c} f) Οβ (map {_} {_} {C} {c} g)) where private module pb = is-pullback pb
is-pullbackβproduct-over : C/c.Ob is-pullbackβproduct-over = cut (f .map C.β Οβ)
Let us turn to the projection maps. Again by commutativity of the square, the pullback projection maps and extend directly to maps from into and over In the nontrivial case, we have to show that which is exactly what commutativity of the square gets us.
is-pullbackβΟβ : C/c.Hom is-pullbackβproduct-over f is-pullbackβΟβ .map = Οβ is-pullbackβΟβ .commutes = refl is-pullbackβΟβ : C/c.Hom is-pullbackβproduct-over g is-pullbackβΟβ .map = Οβ is-pullbackβΟβ .commutes = sym pb.square open is-product
Now we turn to showing that these projections are universal, in the slice Given a family the data of maps and over is given precisely by evidence that meaning that they fit neatly around our pullback diagram, as shown in the square below.
And, as indicated in the diagram, since this square is a pullback, we can obtain the dashed map which we can calculate satisfies
so that it is indeed a map over as required. Reading out the rest of universal property, we see that is the unique map which satisfies and exactly as required for the pairing of a product in
is-pullbackβis-fibre-product : is-product (Slice C c) is-pullbackβΟβ is-pullbackβΟβ is-pullbackβis-fibre-product .β¨_,_β© {Q} p q = factor where module p = /-Hom p module q = /-Hom q factor : C/c.Hom Q _ factor .map = pb.universal (p.commutes β sym q.commutes) factor .commutes = (f .map C.β Οβ) C.β pb.universal _ β‘β¨ C.pullr pb.pββuniversal β©β‘ f .map C.β p.map β‘β¨ p.commutes β©β‘ Q .map β
is-pullbackβis-fibre-product .Οβββ¨β© = ext pb.pββuniversal is-pullbackβis-fibre-product .Οβββ¨β© = ext pb.pββuniversal is-pullbackβis-fibre-product .unique p q = ext (pb.unique (ap map p) (ap map q)) PullbackβFibre-product : β {f g : /-Obj c} β Pullback C (f .map) (g .map) β Product (Slice C c) f g PullbackβFibre-product pb .Product.apex = _ PullbackβFibre-product pb .Product.Οβ = _ PullbackβFibre-product pb .Product.Οβ = _ PullbackβFibre-product pb .Product.has-is-product = is-pullbackβis-fibre-product (pb .Pullback.has-is-pb)
While products and terminal objects in do not correspond to those in pullbacks (and equalisers) are precisely equivalent. A square is a pullback in precisely if its image in forgetting the maps to is a pullback.
The βifβ direction (what is pullback-aboveβpullback-below
)
in the code is essentially an immediate consequence of the fact that
equality of morphisms in
may be tested in
but we do have to take some care when extending the βuniversalβ morphism
back down to the slice category (see the calculation marked {- * -}
).
module _ {o β} {C : Precategory o β} {X : β C β} {P A B c} {p1 f p2 g} where open Cat.Reasoning C open is-pullback open /-Obj open /-Hom
pullback-aboveβpullback-below : is-pullback C (p1 .map) (f .map) (p2 .map) (g .map) β is-pullback (Slice C X) {P} {A} {B} {c} p1 f p2 g pullback-aboveβpullback-below pb = pb' where pb' : is-pullback (Slice _ _) _ _ _ _ pb' .square = ext (pb .square) pb' .universal p .map = pb .universal (ap map p) pb' .universal {P'} {pβ' = pβ'} p .commutes = (c .map β pb .universal (ap map p)) β‘Λβ¨ pulll (p1 .commutes) β©β‘Λ (P .map β p1 .map β pb .universal (ap map p)) β‘β¨ ap (_ β_) (pb .pββuniversal) β©β‘ (P .map β pβ' .map) β‘β¨ pβ' .commutes β©β‘ P' .map β {- * -} pb' .pββuniversal = ext (pb .pββuniversal) pb' .pββuniversal = ext (pb .pββuniversal) pb' .unique p q = ext (pb .unique (ap map p) (ap map q)) pullback-belowβpullback-above : is-pullback (Slice C X) {P} {A} {B} {c} p1 f p2 g β is-pullback C (p1 .map) (f .map) (p2 .map) (g .map) pullback-belowβpullback-above pb = pb' where pb' : is-pullback _ _ _ _ _ pb' .square = ap map (pb .square) pb' .universal p = pb .universal {pβ' = record { commutes = refl }} {pβ' = record { commutes = sym (pulll (g .commutes)) Β·Β· sym (ap (_ β_) p) Β·Β· pulll (f .commutes) }} (ext p) .map pb' .pββuniversal = ap map $ pb .pββuniversal pb' .pββuniversal = ap map $ pb .pββuniversal pb' .unique p q = ap map $ pb .unique {lim' = record { commutes = sym (pulll (p1 .commutes)) β ap (_ β_) p }} (ext p) (ext q)
It follows that any slice of a category with pullbacks is finitely complete. Note that we could have obtained the products abstractly, since any category with pullbacks and a terminal object has products, but expanding on the definition in components helps clarify both their construction and the role of pullbacks.
module _ {o β} {C : Precategory o β} where open Cat.Reasoning C open Pullback open /-Obj open /-Hom
Slice-pullbacks : β {b} β has-pullbacks C β has-pullbacks (Slice C b) Slice-products : β {b} β has-pullbacks C β has-products (Slice C b) Slice-lex : β {b} β has-pullbacks C β Finitely-complete (Slice C b)
This is one of the rare moments when the sea of theory has already risen
to meet our prose β put another way, the proofs of the statements above
are just putting things together. We leave them in this
<details>
block for the curious reader.
Slice-pullbacks pullbacks {A = A} f g = pb where pb : Pullback (Slice C _) _ _ pb .apex = cut (A .map β pullbacks _ _ .pβ) pb .pβ = record { commutes = refl } pb .pβ = record { commutes = sym (pushl (sym (f .commutes)) Β·Β· apβ _β_ refl (pullbacks _ _ .square) Β·Β· pulll (g .commutes)) } pb .has-is-pb = pullback-aboveβpullback-below $ pullbacks (f .map) (g .map) .has-is-pb Slice-products pullbacks f g = PullbackβFibre-product (pullbacks _ _) Slice-lex pb = with-pullbacks (Slice C _) Slice-terminal-object (Slice-pullbacks pb)
Slices of Setsπ
Having tackled some properties of slice categories in general, we now turn to characterising the slice as the category of families of indexed by , by formalising the aforementioned equivalence Let us trace our route before we depart, and write down an outline of the proof.
A functor is sent to the first projection functorially. Since is the total space of we refer to this as the
Total-space
functor.We define a procedure that, given a morphism over recovers a natural transformation We then calculate that this procedure is an inverse to the action on morphisms of
Total-space
, so that it is fully faithful.Finally, we show that, given the assignment sending an index to the fibre of over it, gives a functor and that over so that
Total-space
is a split essential surjection, hence an equivalence of categories.
Letβs begin. The Total-space
functor gets out of
our way very fast:
Total-space : Functor Cat[ Disc' I , Sets β ] (Slice (Sets β) I) Total-space .Fβ F .domain = el! (Ξ£ _ (β£_β£ β Fβ F)) Total-space .Fβ F .map = fst Total-space .Fβ nt .map (i , x) = i , nt .Ξ· _ x Total-space .Fβ nt .commutes = refl Total-space .F-id = trivial! Total-space .F-β _ _ = trivial!
Since the construction of the functor itself is straightforward, we turn to showing it is fully faithful. The content of a morphism over is a function
which preserves the first projection, i.e.Β we have This means that it corresponds to a dependent function and, since the morphisms in are trivial, this dependent function is automatically a natural transformation.
Total-space-is-ff : is-fully-faithful Total-space Total-space-is-ff {F} {G} = is-isoβis-equiv $ iso from linv (Ξ» x β ext Ξ» _ _ β transport-refl _) where from : /-Hom (Total-space .Fβ F) (Total-space .Fβ G) β F => G from mp = nt where eta : β i β F Κ» i β G Κ» i eta i j = subst (G Κ»_) (mp .commutes # _) (mp .map (i , j) .snd) nt : F => G nt .Ξ· = eta nt .is-natural _ _ = J (Ξ» _ p β eta _ β F .Fβ p β‘ G .Fβ p β eta _) $ eta _ β F .Fβ refl β‘β¨ ap (eta _ β_) (F .F-id) β©β‘ eta _ β‘Λβ¨ ap (_β eta _) (G .F-id) β©β‘Λ G .Fβ refl β eta _ β
linv : is-left-inverse (Fβ Total-space) from linv x = ext Ξ» y s β Ξ£-pathp (sym (x .commutes $β _)) (to-pathpβ» refl)
All that remains is showing that sending a map
to the total space of its family of fibres gets us all the way back
around to
Fortunately, our proof that universes are object classifiers
grappled with many of the same concerns, so we have a reusable
equivalence Total-equiv
which slots right
in. By univalence, we can finish in style: not only is
isomorphic to
in
itβs actually identical to
Total-space-is-eso : is-split-eso Total-space Total-space-is-eso fam = functor , pathβiso path where functor : Functor _ _ functor .Fβ i = el! (fibre (fam .map) i) functor .Fβ p = subst (fibre (fam .map)) p functor .F-id = funext transport-refl functor .F-β f g = funext (subst-β (fibre (fam .map)) _ _) path : Total-space .Fβ functor β‘ fam path = /-Obj-path (n-ua (Total-equiv _ eβ»ΒΉ)) (uaβ Ξ» a β sym (a .snd .snd))
Slices preserve univalenceπ
In passing, we can put together the following result: any slice of a univalent category is univalent again. Thatβs because an identification is given by an identification and a proof that over We already have a characterisation of dependent identifications in a space of morphisms, in terms of composition with the induced isomorphisms, so that this latter condition reduces to showing
module _ {C : Precategory o β} {o : β C β} (isc : is-category C) where private module C = Cat.Reasoning C module C/o = Cat.Reasoning (Slice C o) open /-Obj open /-Hom open C/o._β _ open C._β _
Therefore, if we have an isomorphism over and its component in corresponds to an identification then the commutativity of is exactly the data we need to extend this to an identification
slice-is-category : is-category (Slice C o) slice-is-category .to-path x = /-Obj-path (isc .to-path $ C.make-iso (x .to .map) (x .from .map) (ap map (C/o._β _.invl x)) (ap map (C/o._β _.invr x))) (Univalent.Hom-pathp-refll-iso isc (x .from .commutes)) slice-is-category .to-path-over x = C/o.β -pathp refl _ $ /-Hom-pathp _ _ (Univalent.Hom-pathp-reflr-iso isc (C.idr _))
Constant familiesπ
If is the category of families of indexed by , it stands to reason that we should be able to consider any object as a family over where each fibre of the family is isomorphic to Type-theoretically, this would correspond to taking a closed type and trivially regarding it as living in a context by ignoring the context entirely.
From the perspective of slice categories, the constant families functor, sends an object to the projection morphism
module _ {o β} {C : Precategory o β} {B} (prod : has-products C) where open Binary-products C prod open Cat.Reasoning C constant-family : Functor C (Slice C B) constant-family .Fβ A = cut (Οβ {a = A}) constant-family .Fβ f .map = β¨ f β Οβ , Οβ β© constant-family .Fβ f .commutes = Οβββ¨β© constant-family .F-id = ext (sym (β¨β©-unique id-comm (idr _))) constant-family .F-β f g = ext $ sym $ β¨β©-unique (pulll Οβββ¨β© β extendr Οβββ¨β©) (pulll Οβββ¨β© β Οβββ¨β©)
We can observe that this really is a constant families functor by performing the following little calculation: If we have a map then the fibre of over given by the pullback
is isomorphic to The extra generality makes it a bit harder to see the constancy, but if were a point the fibre over would correspondingly be isomorphic to
constant-family-fibre : (pb : has-pullbacks C) β β {A Y} (h : Hom Y B) β pb (constant-family .Fβ A .map) h .Pullback.apex β (A ββ Y) constant-family-fibre pb {A} h = make-iso β¨ Οβ β pβ , pβ β© (universal {pβ' = β¨ Οβ , h β Οβ β©} {pβ' = Οβ} Οβββ¨β©) (β¨β©β _ β sym (Product.unique (prod _ _) (idr _ β sym (pullr pββuniversal β Οβββ¨β©)) (idr _ β sym pββuniversal))) (Pullback.uniqueβ (pb _ _) {p = Οβββ¨β© β square} (pulll pββuniversal β β¨β©β _ β apβ β¨_,_β© Οβββ¨β© (pullr Οβββ¨β© β sym square)) (pulll pββuniversal β Οβββ¨β©) (idr _ β Product.unique (prod _ _) refl refl) (idr _)) where open Pullback (pb (constant-family .Fβ A .map) h)
The constant families functor is a right adjoint to the
projection
This can be understood in terms of base change: if
has a terminal
object
then the slice
is equivalent to
and the unique map
induces a pullback functor
that is just the constant families functor. On the other hand, the
βdependent sumβ functor sends a map
to the unique composite
it simply Forget/
s the map. Thus the
following adjunction is a special case of the adjunction between
dependent sum and base change.
Forgetβ£constant-family : Forget/ β£ constant-family Forgetβ£constant-family .unit .Ξ· X .map = β¨ id , X .map β© Forgetβ£constant-family .unit .Ξ· X .commutes = Οβββ¨β© Forgetβ£constant-family .unit .is-natural _ _ f = ext (uniqueβ (pulll Οβββ¨β© β id-comm-sym) (pulll Οβββ¨β© β f .commutes) (pulll Οβββ¨β© β pullr Οβββ¨β©) (pulll Οβββ¨β© β Οβββ¨β©)) Forgetβ£constant-family .counit .Ξ· x = Οβ Forgetβ£constant-family .counit .is-natural _ _ f = Οβββ¨β© Forgetβ£constant-family .zig = Οβββ¨β© Forgetβ£constant-family .zag = ext (uniqueβ (pulll Οβββ¨β© β pullr Οβββ¨β©) (pulll Οβββ¨β© β Οβββ¨β©) refl (idr _))