module Cat.Allegory.Maps where

# Maps in allegoriesπ

Suppose we have an allegory
$A$
β for definiteness you could consider the archetypal allegory
$Rel$
β 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
$Rel!$

If you have a relation $RβͺAΓB,$ when does it correspond to a function $AβB?$ Well, it must definitely be functional: if we want $R(x,y)$ to represent β$f(x)=y$β, then surely if $R(x,y)β§R(x,z),$ we must have $y=z.$ In allegorical language, we would say $RR_{o}β€id,$ which we can calculate to mean (in $Rel)$ that, for all $x,y,$

$(βz,R(z,x)β§R(z,y))β(x=y).$It must also be an entire relation:
Every
$x$
must at least one
$y$
it is related to, and by functionality, *exactly* one
$y$
it is related to. This is the βvalue ofβ the function at
$y.$

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 $a$ in the domain) the space of βpoints in the codomain related to $a$β 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 $A,$ we can form a category $Map(A)$ with the same objects as $A,$ 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 $fβ£f_{o},$ 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 _ _ _)