open import Cat.Allegory.Base
open import Cat.Prelude

import Cat.Allegory.Morphism

module Cat.Allegory.Maps where


# Maps in allegoriesπ

Suppose we have an allegory β for definiteness you could consider the archetypal allegory β but what we really wanted was to get our hands on an ordinary category. That is: we want, given some category of βsets and relationsβ, to recover the associated category of βsets and functionsβ. So, letβs start by thinking about

If you have a relation when does it correspond to a function Well, it must definitely be functional: if we want to represent ββ, then surely if we must have In allegorical language, we would say which we can calculate to mean (in that, for all

It must also be an entire relation: Every must at least one it is related to, and by functionality, exactly one it is related to. This is the βvalue ofβ the function at

module _ {o β h} (A : Allegory o β h) where
open Cat.Allegory.Morphism A
record is-map x y (f : Hom x y) : Type h where
constructor mapping
field
functional : is-functional f
entire     : is-entire f

module _ {o β h} {A : Allegory o β h} where
open Allegory A
open is-map
instance
H-Level-is-map : β {x y} {f : Hom x y} {n} β H-Level (is-map A x y f) (suc n)
H-Level-is-map = prop-instance {T = is-map A _ _ _} Ξ» where
x y i .functional β β€-thin (x .functional) (y .functional) i
x y i .entire     β β€-thin (x .entire) (y .entire) i


We can calculate that a functional entire relation is precisely a function between sets: Functionality ensures that (fixing a point in the domain) the space of βpoints in the codomain related to β is a subsingleton, and entireness ensures that it is inhabited; By unique choice, we can project the value of the function.

Rel-mapβfunction
: β {β} {x y : Set β} {f : Allegory.Hom (Rel β) x y}
β is-map (Rel β) x y f
β β£ x β£ β β£ y β£
Rel-mapβfunction {x = x} {y} {rel} map elt =
β₯-β₯-rec {P = Ξ£ β£ y β£ Ξ» b β β£ rel elt b β£}
(Ξ» { (x , p) (y , q) β Ξ£-prop-path! (functional' p q) })
(Ξ» x β x)
(entire' elt) .fst
where
module map = is-map map
functional' : β {a b c} β β£ rel a b β£ β β£ rel a c β£ β b β‘ c
functional' r1 r2 = β‘-out! (map.functional _ _ (inc (_ , r1 , r2)))

entire' : β a β β β£ y β£ Ξ» b β β£ rel a b β£
entire' a = case map.entire a a (inc refl) of Ξ» x _ a~x β inc (x , a~x)


## The category of mapsπ

Given an allegory we can form a category with the same objects as but considering only the maps (rather than arbitrary relations).

module _ {o β h} (A : Allegory o β h) where
private module A = Cat.Allegory.Morphism A
open is-map
open Precategory hiding (_β_ ; id)
open A using (_β  ; _β_ ; id ; _β_ ; _βΆ_)

Maps[_] : Precategory _ _
Maps[_] .Ob  = A.Ob
Maps[_] .Hom x y = Ξ£ (A.Hom x y) (is-map A x y)
Maps[_] .Hom-set x y = hlevel 2


Proving that maps compose is a bit annoying, but it follows from the properties of the duality involution. By the way: This is essentially the proof that adjunctions compose! This is because, sneakily, the property βbeing a mapβ is defined to be but without using those words.

  Maps[_] .Precategory.id = A.id , mapping
A.functional-id
A.entire-id
Maps[_] .Precategory._β_ (f , m) (g , m') =
f A.β g , mapping
(A.functional-β (m .functional) (m' .functional))
(A.entire-β (m .entire) (m' .entire))
Maps[_] .idr f = Ξ£-prop-path! (A.idr _)
Maps[_] .idl f = Ξ£-prop-path! (A.idl _)
Maps[_] .assoc f g h = Ξ£-prop-path! (A.assoc _ _ _)