module Cat.Displayed.Instances.Simple
  {o β„“} (B : Precategory o β„“)
  (has-prods : βˆ€ X Y β†’ Product B X Y)
  where

open Cat.Reasoning B
open Binary-products B has-prods

Simple fibrationsπŸ”—

One reason to be interested in fibrations is that they provide an excellent setting to study logical and type-theoretical phenomena. When constructing models of type theories, the general pattern is to construct a category of contexts and substitutions, and then to study types and terms as structures over this category. The language of displayed categories allows us to capture this situation quite succinctly by considering these extra pieces of equipment as being fibred over our category of contexts.

Focusing in, the language of simple fibrations provides us with enough structure to study simply-typed languages that have enough structure to represent contexts internally (i.e.: product types).

To start, we fix some base category with binary products. Intuitvely, this will be some sort of category of contexts, and context extension endows this category with products. We interpret a type in a context to be an object

Maps between types in contexts are then given by a map between contexts, and a map which is meant to denote a derivation of from

To encode this as a displayed category, we define the space of objects over some to be simply an object of This may seem odd, but recall that we are modeling a type theory with enough structure to consider contexts as types: if this is not the situation (IE: STLC without products), then we need to consider a more refined notion.

For the maps, we already have the map as the base morphism, so the displayed portion of the map will be the map between derivations. The identity morphism ignores the context, and derives by using the we already had, and is thus represented by the second projection

Composition of morphisms is somewhat more involved, but can be derived by playing type-tetris, as it’s all a matter of golfing the types and contexts into the correct place. The category laws are then a matter of bashing through a bunch of nested pairings and projections, and can be entirely automated.

Simple : Displayed B o β„“
Simple .Displayed.Ob[_] Ξ“ = Ob
Simple .Displayed.Hom[_] {Ξ“} {Ξ”} u X Y = Hom (Ξ“ βŠ—β‚€ X) Y
Simple .Displayed.Hom[_]-set _ _ _ = Hom-set (_ βŠ—β‚€ _) _
Simple .Displayed.id' = Ο€β‚‚
Simple .Displayed._∘'_ {f = u} {g = v} f g = f ∘ ⟨ v ∘ π₁ , g ⟩
Simple .Displayed.idr' f =
  f ∘ ⟨ (id ∘ π₁) , Ο€β‚‚ ⟩ β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
  f                      ∎
Simple .Displayed.idl' {f = u} f =
  Ο€β‚‚ ∘ ⟨ u ∘ π₁ , f ⟩ β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
  f                   ∎
Simple .Displayed.assoc' {f = u} {g = v} {h = w} f g h =
  f ∘ ⟨ (v ∘ w) ∘ π₁ , g ∘ ⟨ w ∘ π₁ , h ⟩ ⟩ β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
  (f ∘ ⟨ v ∘ π₁ , g ⟩) ∘ ⟨ w ∘ π₁ , h ⟩     ∎

Cartesian morphismsπŸ”—

A morphism in the simple fibration is cartesian if and only if the morphism is invertible. This means that the cartesian morphisms are the isomorphisms of types, as we are interpreting morphisms in the simple fibration as derivations.

We begin with the reverse direction, as it is slightly simpler to show.

⟨⟩-invertibleβ†’cartesian
  : βˆ€ {Ξ“ Ξ” x y} {f : Hom Ξ“ Ξ”} {f' : Hom (Ξ“ βŠ—β‚€ x) y}
  β†’ is-invertible ⟨ π₁ , f' ⟩
  β†’ is-cartesian Simple f f'
⟨⟩-invertibleβ†’cartesian {Ξ“} {Ξ”} {x} {y} {f} {f'} ⟨⟩-inv = cart where
  module ⟨⟩-inv = is-invertible ⟨⟩-inv
  open is-cartesian

Let and be a pair of morphisms; we need to construct some that factorizes through

We begin by constructing the map which we can then pre-compose with the inverse to to obtain a map Finally, we can compose these two maps with the second projection, yielding the required map.

  cart : is-cartesian Simple f f'
  cart .universal m h' = Ο€β‚‚ ∘ ⟨⟩-inv.inv ∘ ⟨ m ∘ π₁ , h' ⟩

Showing that this map uniquely factorises boils down to pushing around products and using that fact that the inverse to is, in fact, an inverse.

  cart .commutes m h' =
    f' ∘ ⟨ m ∘ π₁ , Ο€β‚‚ ∘ ⟨⟩-inv.inv ∘ ⟨ m ∘ π₁ , h' ⟩ ⟩ β‰‘Λ˜βŸ¨ apβ‚‚ _∘_ refl (⟨⟩-unique (pulll (π₁-inv ⟨⟩-inv) βˆ™ Ο€β‚βˆ˜βŸ¨βŸ©) refl) βŸ©β‰‘Λ˜
    f' ∘ ⟨⟩-inv.inv ∘ ⟨ m ∘ π₁ , h' ⟩                   β‰‘βŸ¨ pulll (Ο€β‚‚-inv ⟨⟩-inv) βŸ©β‰‘
    Ο€β‚‚ ∘ ⟨ m ∘ π₁ , h' ⟩                                β‰‘βŸ¨ Ο€β‚‚βˆ˜βŸ¨βŸ© βŸ©β‰‘
    h'                                                  ∎
  cart .unique {m = m} {h' = h'} m' p =
    m'                                                      β‰‘Λ˜βŸ¨ Ο€β‚‚βˆ˜βŸ¨βŸ© βŸ©β‰‘Λ˜
    Ο€β‚‚ ∘ ⟨ m ∘ π₁ , m' ⟩                                    β‰‘βŸ¨ apβ‚‚ _∘_ refl (introl ⟨⟩-inv.invr) βŸ©β‰‘
    Ο€β‚‚ ∘ (⟨⟩-inv.inv ∘ ⟨ π₁ , f' ⟩) ∘ ⟨ m ∘ π₁ , m' ⟩       β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
    Ο€β‚‚ ∘ ⟨⟩-inv.inv ∘ ⟨ m ∘ π₁ , ⌜ f' ∘ ⟨ m ∘ π₁ , m' ⟩ ⌝ ⟩ β‰‘βŸ¨ ap! p βŸ©β‰‘
    Ο€β‚‚ ∘ ⟨⟩-inv.inv ∘ ⟨ m ∘ π₁ , h' ⟩ ∎

On to the forward direction! Let and form a cartesian map in the simple fibration. We can construct an inverse to by factorizing the map as in the following diagram:

cartesianβ†’βŸ¨βŸ©-invertible
  : βˆ€ {Ξ“ Ξ” x y} {f : Hom Ξ“ Ξ”} {f' : Hom (Ξ“ βŠ—β‚€ x) y}
  β†’ is-cartesian Simple f f'
  β†’ is-invertible ⟨ π₁ , f' ⟩
cartesianβ†’βŸ¨βŸ©-invertible {Ξ“} {Ξ”} {x} {y} {f} {f'} cart =
  make-invertible ⟨ π₁ , universal id Ο€β‚‚ ⟩
    left-inv
    right-inv
    where
      open is-cartesian cart

Showing that this map is a left inverse can be seen by a short computation.

      left-inv : ⟨ π₁ , f' ⟩ ∘ ⟨ π₁ , universal id Ο€β‚‚ ⟩ ≑ id
      left-inv =
        ⟨ π₁ , f' ⟩ ∘ ⟨ π₁ , universal id Ο€β‚‚ ⟩           β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
        ⟨ π₁ , ⌜ f' ∘ ⟨ id ∘ π₁ ,  universal id Ο€β‚‚ ⟩ ⌝ ⟩ β‰‘βŸ¨ ap! (commutes id Ο€β‚‚) βŸ©β‰‘
        ⟨ π₁ , Ο€β‚‚ ⟩                                      β‰‘βŸ¨ ⟨⟩-Ξ· βŸ©β‰‘
        id                                               ∎

Showing that the constructed map is a right inverse is somewhat more involved. The key lemma is that is equal to To see this, consider the following diagram

Note that factorizes so it must be equal to the universal factorisation of as is cartesian. Furthermore, also factorizes which lets us see that

      universal-Ο€β‚‚-unique : f' ∘ ⟨ id ∘ π₁ , universal id Ο€β‚‚ ∘ ⟨ π₁ , f' ⟩ ⟩ ≑ f'
      universal-Ο€β‚‚-unique =
        f' ∘ ⟨ id ∘ π₁ , universal id Ο€β‚‚ ∘ ⟨ π₁ , f' ⟩ ⟩ β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
        f' ∘ ⟨ id ∘ π₁ , universal id Ο€β‚‚ ⟩ ∘ ⟨ π₁ , f' ⟩ β‰‘βŸ¨ pulll (commutes id Ο€β‚‚) βŸ©β‰‘
        Ο€β‚‚ ∘ ⟨ π₁ , f' ⟩                                 β‰‘βŸ¨ Ο€β‚‚βˆ˜βŸ¨βŸ© βŸ©β‰‘
        f'                                               ∎

      universal-Ο€β‚‚βˆ˜f' : universal id Ο€β‚‚ ∘ ⟨ π₁ , f' ⟩ ≑ Ο€β‚‚
      universal-Ο€β‚‚βˆ˜f' =
        universal id Ο€β‚‚ ∘ ⟨ π₁ , f' ⟩ β‰‘βŸ¨ unique _ universal-Ο€β‚‚-unique βŸ©β‰‘
        universal id f'               β‰‘Λ˜βŸ¨ unique _ (elimr (apβ‚‚ ⟨_,_⟩ (idl _) refl βˆ™ ⟨⟩-Ξ·)) βŸ©β‰‘Λ˜
        Ο€β‚‚                            ∎

We can then apply this lemma to see that forms a right inverse.

      right-inv : ⟨ π₁ ,  universal id Ο€β‚‚ ⟩ ∘ ⟨ π₁ , f' ⟩ ≑ id
      right-inv =
        ⟨ π₁ , universal id Ο€β‚‚ ⟩ ∘ ⟨ π₁ , f' ⟩ β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
        ⟨ π₁ , universal id Ο€β‚‚ ∘ ⟨ π₁ , f' ⟩ ⟩ β‰‘βŸ¨ apβ‚‚ ⟨_,_⟩ refl universal-Ο€β‚‚βˆ˜f' βŸ©β‰‘
        ⟨ π₁ , Ο€β‚‚ ⟩                            β‰‘βŸ¨ ⟨⟩-Ξ· βŸ©β‰‘
        id                                     ∎

Fibration structureπŸ”—

As suggested by it’s name, the simple fibration is a fibration. given a map in the base, and a upstairs, we can construct a lift by selecting as the corner of the lift, and then using the second projection as the lift itself. Intuitively, this encodes a substitution of contexts: because we are working with a simple type theory, the substitutions don’t need to touch the types, as there are no possible dependencies!

Simple-fibration : Cartesian-fibration Simple
Simple-fibration .has-lift f Y .x' = Y
Simple-fibration .has-lift f Y .lifting = Ο€β‚‚
Simple-fibration .has-lift f Y .cartesian .universal _ h = h
Simple-fibration .has-lift f Y .cartesian .commutes g h = Ο€β‚‚βˆ˜βŸ¨βŸ©
Simple-fibration .has-lift f Y .cartesian .unique {m = g} {h' = h} h' p =
  h'                   β‰‘Λ˜βŸ¨ Ο€β‚‚βˆ˜βŸ¨βŸ© βŸ©β‰‘Λ˜
  Ο€β‚‚ ∘ ⟨ g ∘ π₁ , h' ⟩ β‰‘βŸ¨ p βŸ©β‰‘
  h ∎

Comprehension structureπŸ”—

The simple fibration admits a fibred functor into the codomain fibration that maps an object over to the projection

Simple→Slices
  : Vertical-functor Simple (Slices B)
Simple→Slices = func where
  open Vertical-functor
  open /-Obj
  open Slice-hom

  func : Vertical-functor _ _
  func .Fβ‚€' {x} x' = cut {domain = x βŠ—β‚€ x'} π₁
  func .F₁' {f = f} f' = slice-hom ⟨ f ∘ π₁ , f' ⟩ (sym Ο€β‚βˆ˜βŸ¨βŸ©)
  func .F-id' =
    Slice-path B $
    ⟨ id ∘ π₁ , Ο€β‚‚ ⟩ β‰‘βŸ¨ apβ‚‚ ⟨_,_⟩ (idl _) refl βˆ™ ⟨⟩-Ξ· βŸ©β‰‘
    id               ∎
  func .F-∘' {f = f} {g = g} {f' = f'} {g' = g'} =
    Slice-path B $
    ⟨ (f ∘ g) ∘ π₁ , f' ∘ ⟨ g ∘ π₁ , g' ⟩ ⟩ β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
    ⟨ f ∘ π₁ , f' ⟩ ∘ ⟨ g ∘ π₁ , g' ⟩       ∎

Furthermore, this functor is fibred. The general sketch is that cartesian morphisms in the codomain fibration are given by pullbacks, and cartesian maps in the simple fibration are given by inverses to and we can use this inverse to construct the universal map for the pullback.

Simple→Slices-fibred
  : is-vertical-fibred Simple→Slices
Simple→Slices-fibred {f = f} f' cart =
  pullback→cartesian B pb
  where
    open is-pullback

    ⟨⟩-inv : is-invertible ⟨ π₁ , f' ⟩
    ⟨⟩-inv = cartesianβ†’βŸ¨βŸ©-invertible cart

    module ⟨⟩-inv = is-invertible ⟨⟩-inv

    pb : is-pullback B π₁ f ⟨ f ∘ π₁ , f' ⟩ π₁
    pb .square = sym Ο€β‚βˆ˜βŸ¨βŸ©
    pb .universal {P'} {p₁'} {pβ‚‚'} p =
      ⟨⟩-inv.inv ∘ ⟨ p₁' , Ο€β‚‚ ∘ pβ‚‚' ⟩
Showing that this map is universal involves a series of somewhat tedious calculations, so we omit them.
    pb .pβ‚βˆ˜universal {P} {p₁'} {pβ‚‚'} {p} =
      π₁ ∘ ⟨⟩-inv.inv ∘ ⟨ p₁' , Ο€β‚‚ ∘ pβ‚‚' ⟩ β‰‘βŸ¨ pulll (π₁-inv ⟨⟩-inv) βŸ©β‰‘
      π₁ ∘ ⟨ p₁' , Ο€β‚‚ ∘ pβ‚‚' ⟩              β‰‘βŸ¨ Ο€β‚βˆ˜βŸ¨βŸ© βŸ©β‰‘
      p₁' ∎
    pb .pβ‚‚βˆ˜universal {P} {p₁'} {pβ‚‚'} {p} =
      ⟨ f ∘ π₁ , f' ⟩ ∘ ⟨⟩-inv.inv ∘ ⟨ p₁' , Ο€β‚‚ ∘ pβ‚‚' ⟩                β‰‘βŸ¨ pulll (⟨⟩∘ _) βŸ©β‰‘
      ⟨ (f ∘ π₁) ∘ ⟨⟩-inv.inv , f' ∘ ⟨⟩-inv.inv ⟩ ∘ ⟨ p₁' , Ο€β‚‚ ∘ pβ‚‚' ⟩ β‰‘βŸ¨ apβ‚‚ _∘_ (apβ‚‚ ⟨_,_⟩ (pullr (π₁-inv ⟨⟩-inv)) (Ο€β‚‚-inv ⟨⟩-inv)) refl βŸ©β‰‘
      ⟨ f ∘ π₁ , Ο€β‚‚ ⟩ ∘ ⟨ p₁' , Ο€β‚‚ ∘ pβ‚‚' ⟩                             β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
      ⟨ f ∘ p₁' , Ο€β‚‚ ∘ pβ‚‚' ⟩                                           β‰‘βŸ¨ apβ‚‚ ⟨_,_⟩ p refl βŸ©β‰‘
      ⟨ π₁ ∘ pβ‚‚' , Ο€β‚‚ ∘ pβ‚‚' ⟩                                          β‰‘βŸ¨ products! B has-prods βŸ©β‰‘
      pβ‚‚' ∎
    pb .unique {P} {p₁'} {pβ‚‚'} {p} {h'} q r =
      h'                                                   β‰‘βŸ¨ insertl ⟨⟩-inv.invr βŸ©β‰‘
      ⟨⟩-inv.inv ∘ ⟨ π₁ , f' ⟩ ∘ h'                        β‰‘βŸ¨ apβ‚‚ _∘_ refl (⟨⟩∘ h') βŸ©β‰‘
      ⟨⟩-inv.inv ∘ ⟨ ⌜ π₁ ∘ h' ⌝ , f' ∘ h' ⟩               β‰‘βŸ¨ ap! q βŸ©β‰‘
      ⟨⟩-inv.inv ∘ ⟨ p₁' , ⌜ f' ∘ h' ⌝ ⟩                   β‰‘βŸ¨ ap! (pushl (sym Ο€β‚‚βˆ˜βŸ¨βŸ©)) βŸ©β‰‘
      ⟨⟩-inv.inv ∘ ⟨ p₁' , Ο€β‚‚ ∘ ⌜ ⟨ f ∘ π₁ , f' ⟩ ∘ h' ⌝ ⟩ β‰‘βŸ¨ ap! r βŸ©β‰‘
      ⟨⟩-inv.inv ∘ ⟨ p₁' , Ο€β‚‚ ∘ pβ‚‚' ⟩                      ∎

This yields a comprehension structure on the simple fibration, which encodes the structure of a non-dependent type theory.

Simple-comprehension : Comprehension Simple
Simple-comprehension .Vertical-fibred-functor.vert = Simple→Slices
Simple-comprehension .Vertical-fibred-functor.F-cartesian = Simple→Slices-fibred