open import 1Lab.Path.IdentitySystem
open import 1Lab.Reflection.Record
open import 1Lab.HLevel.Retracts
open import 1Lab.HLevel.Universe
open import 1Lab.Extensionality
open import 1Lab.Rewrite
open import 1Lab.HLevel
open import 1Lab.Equiv
open import 1Lab.Path
open import 1Lab.Type hiding (id ; _β_)

module Cat.Base where


# Precategoriesπ

In univalent mathematics, it makes sense to distinguish two stages in the construction of categories: A precategory is the object that directly corresponds to the definition of precategory as it is traditionally formalised, whereas a category (or univalent category) has an extra condition: Isomorphic objects must be identified.

record Precategory (o h : Level) : Type (lsuc (o β h)) where
no-eta-equality


A precategory is a βproof-relevant preorderβ. In a preordered set $(A, \le)$, the inhabitants of a set $A$ are related by a proposition $a \le b$, which is

• reflexive: $a \le a$
• transitive: $a \le b \land b \le c \to a \le c$

In a precategory, the condition that $a \le b$ be a proposition is relaxed: A precategory has a type of objects and, between each $x, y$, a set $\mathbf{Hom}(x, y)$ of relations (or maps). The name β$\mathbf{Hom}$β is historical and it betrays the original context in which categories where employed: algebra(ic topology), where the maps in question are homomorphisms.

  field
Ob  : Type o
Hom : Ob β Ob β Type h


Whereas reading a classical definition into a type theory where equality is a proposition, the word set may be read to mean inhabitant of a universe. But in HoTT, if we want categories to be well-behaved, we do actually mean set: A type of h-level 2

  field
Hom-set : (x y : Ob) β is-set (Hom x y)


If you are already familiar with the definition of precategory there are two things to note here:

First is that our formalization has a family of Hom-sets rather than a single Hom-set and source/target maps. This formulation is not unique to precategory theory done internally to type theory, but it is the most reasonable way to formulate things in this context.

Second is that the word βsetβ in the definition of Hom-set has nothing to do with βsizeβ. Indeed, the βsetβ/βnot a setβ (alternatively βsmallβ/βlargeβ) distinction makes no sense in type theory (some may argue it makes no sense in general).

Instead, the Precategory record is parametrised by two levels: o, and h. The type of objects has to fit in the universe Type o, and the family of Hom-sets is Type h valued. As an example, the thin precategory corresponding to the natural numbers with their usual ordering would live in Precategory lzero lzero.

This means, for instance, that there is no single βcategory of setsβ - there is a family of categories of sets, parametrised by the level in which its objects live.

  field
id  : β {x}     β Hom x x
_β_ : β {x y z} β Hom y z β Hom x y β Hom x z

infixr 40 _β_


The βproof-relevantβ version of the reflexivity and transitivity laws are, respectively, the identity morphisms and composition of morphisms. Unlike in the proof-irrelevant case, in which an inhabitant of $x \le y$ merely witnesses that two things are related, these operations matter, and thus must satisfy laws:

  field
idr : β {x y} (f : Hom x y) β f β id β‘ f
idl : β {x y} (f : Hom x y) β id β f β‘ f


The two identity laws say that the identity morphisms serve as neutral elements for the composition operation, both on the left and on the right. The βtwoβ associativity laws (below) say that both ways of writing parentheses around a composition of three morphisms is equal: $(f \circ g) \circ h = f \circ (g \circ h)$.

    assoc : β {w x y z} (f : Hom y z) (g : Hom x y) (h : Hom w x)
β f β (g β h) β‘ (f β g) β h


We can define the type of all morphisms in a precategory as the total space of Hom:

  Mor : Type (o β h)
Mor = Ξ£[ a β Ob ] Ξ£[ b β Ob ] Hom a b

  HomβMor : {a b : Ob} β Hom a b β Mor
HomβMor f = _ , _ , f

Mor-path : {a b : Mor}
β (p : a .fst β‘ b .fst)
β (q : a .snd .fst β‘ b .snd .fst)
β PathP (Ξ» i β Hom (p i) (q i)) (a .snd .snd) (b .snd .snd)
β a β‘ b
Mor-path p q r i = p i , q i , r i

  module HLevel-instance where
instance
H-Level-Hom : β {x y} {k} β H-Level (Hom x y) (2 + k)
H-Level-Hom = basic-instance 2 (Hom-set _ _)


## Oppositesπ

A common theme throughout precategory theory is that of duality: The dual of a categorical concept is same concept, with βall the arrows invertedβ. To make this formal, we introduce the idea of opposite categories: The opposite of $C$, written $C^{\mathrm{op}}$, has the same objects, but with $\mathbf{Hom}_{C^{\mathrm{op}}}(x, y) = \mathbf{Hom}_{C}(y, x)$.

infixl 60 _^op
_^op : β {oβ hβ} β Precategory oβ hβ β Precategory oβ hβ
(C ^op) .Precategory.Ob = Precategory.Ob C
(C ^op) .Precategory.Hom x y = Precategory.Hom C y x
(C ^op) .Precategory.Hom-set x y = Precategory.Hom-set C y x
(C ^op) .Precategory.id = Precategory.id C
(C ^op) .Precategory._β_ f g = Precategory._β_ C g f


Composition in the opposite precategory $C^{\mathrm{op}}$ is βbackwardsβ with respect to $C$: $f \circ_{op} g = g \circ f$. This inversion, applied twice, ends up equal to what we started with by the nature of computation - An equality that arises like this, automatically from what Agda computes, is called definitional.

(C ^op) .Precategory.idl x = C .Precategory.idr x
(C ^op) .Precategory.idr x = C .Precategory.idl x


The left and right identity laws are swapped for the construction of the opposite precategory: For idr one has to show $f \circ_{op} \operatorname{id}_{} = f$, which computes into having to show that $\operatorname{id}_{} \circ_{op}{f} = f$. The case for idl is symmetric.

(C ^op) .Precategory.assoc f g h i = Precategory.assoc C h g f (~ i)


For associativity, consider the case of assoc for the opposite precategory $C^{\mathrm{op}}$. What we have to show is - by the type of assocβ - $f \circ_{op} (g \circ_{op} h) = (f \circ_{op} g) \circ_{op} h$. This computes into $(h \circ g) \circ f = h \circ (g \circ f)$ - which is exactly what sym (assoc C h g f) shows!

C^op^opβ‘C : β {o β} {C : Precategory o β} β C ^op ^op β‘ C
C^op^opβ‘C {C = C} i = precat i where
open Precategory
precat : C ^op ^op β‘ C
precat i .Ob = C .Ob
precat i .Hom = C .Hom
precat i .Hom-set = C .Hom-set
precat i .id = C .id
precat i ._β_ = C ._β_
precat i .idr = C .idr
precat i .idl = C .idl
precat i .assoc = C .assoc

private
precategory-double-dual : β {o β} {C : Precategory o β} β C ^op ^op β‘rw C
precategory-double-dual = make-rewrite C^op^opβ‘C
{-# REWRITE precategory-double-dual #-}


## The precategory of Setsπ

Given a universe level, we can consider the collection of all sets of that level. This assembles into a precategory quite nicely, since taking function types is an operation that preserves h-level.

module _ where
open Precategory

Sets : (o : _) β Precategory (lsuc o) o
Sets o .Ob = Set o
Sets o .Hom A B = β£ A β£ β β£ B β£
Sets o .Hom-set _ B f g p q i j a =
B .is-tr (f a) (g a) (happly p a) (happly q a) i j
Sets o .id x = x
Sets o ._β_ f g x = f (g x)
Sets o .idl f = refl
Sets o .idr f = refl
Sets o .assoc f g h = refl


# Functorsπ

record
Functor
{oβ hβ oβ hβ}
(C : Precategory oβ hβ)
(D : Precategory oβ hβ)
: Type (oβ β hβ β oβ β hβ)
where
no-eta-equality

private
module C = Precategory C
module D = Precategory D


Since a category is an algebraic structure, there is a natural definition of homomorphism of categories defined in the same fashion as, for instance, a homomorphism of groups. Since this kind of morphism is ubiquitous, it gets a shorter name: Functor.

Alternatively, functors can be characterised as the βproof-relevant versionβ of a monotone map: A monotone map is a map $F : C \to D$ which preserves the ordering relation, $x \le y \to F(x) \le F(y)$. Categorifying, βpreserves the ordering relationβ becomes a function between Hom-sets.

  field
Fβ : C.Ob β D.Ob
Fβ : β {x y} β C.Hom x y β D.Hom (Fβ x) (Fβ y)


A Functor $F : C \to D$ consists of a function between the object sets - $F_0 : \mathrm{Ob}(C) \to \mathrm{Ob}(D)$, and a function between Hom-sets - which takes $f : x \to y \in C$ to $F_1(f) : F_0(x) \to F_0(y) \in D$.

  field
F-id : β {x} β Fβ (C.id {x}) β‘ D.id
F-β : β {x y z} (f : C.Hom y z) (g : C.Hom x y)
β Fβ (f C.β g) β‘ Fβ f D.β Fβ g


Furthermore, the morphism mapping $F_1$ must be homomorphic: Identity morphisms are taken to identity morphisms (F-id) and compositions are taken to compositions (F-β).

  -- Alias for Fβ for use in Functor record modules.
β : C.Ob β D.Ob
β = Fβ

-- Alias for Fβ for use in Functor record modules.
β : β {x y} β C.Hom x y β D.Hom (Fβ x) (Fβ y)
β = Fβ


Functors also have duals: The opposite of $F : C \to D$ is $F^{\mathrm{op}} : C^{\mathrm{op}} \to D^{\mathrm{op}}$.

  op : Functor (C ^op) (D ^op)
Fβ op      = Fβ
Fβ op      = Fβ
F-id op    = F-id
F-β op f g = F-β g f

F^op^opβ‘F : β {o β o' β'} {C : Precategory o β} {D : Precategory o' β'} {F : Functor C D}
β Functor.op (Functor.op F) β‘ F
F^op^opβ‘F {F = F} i .Functor.Fβ = F .Functor.Fβ
F^op^opβ‘F {F = F} i .Functor.Fβ = F .Functor.Fβ
F^op^opβ‘F {F = F} i .Functor.F-id = F .Functor.F-id
F^op^opβ‘F {F = F} i .Functor.F-β = F .Functor.F-β

private
functor-double-dual
: β {o β o' β'} {C : Precategory o β} {D : Precategory o' β'} {F : Functor C D}
β Functor.op (Functor.op F) β‘rw F
functor-double-dual = make-rewrite F^op^opβ‘F
{-# REWRITE functor-double-dual #-}


## Compositionπ

_Fβ_ : β {oβ hβ oβ hβ oβ hβ}
{C : Precategory oβ hβ} {D : Precategory oβ hβ} {E : Precategory oβ hβ}
β Functor D E β Functor C D β Functor C E
_Fβ_ {C = C} {D} {E} F G = comps


Functors, being made up of functions, can themselves be composed. The object mapping of $(F \circ G)$ is given by $F_0 \circ G_0$, and similarly for the morphism mapping. Alternatively, composition of functors is a categorification of the fact that monotone maps compose.

  module Fβ where
module C = Precategory C
module D = Precategory D
module E = Precategory E

module F = Functor F
module G = Functor G

    Fβ : C.Ob β E.Ob
Fβ x = F.Fβ (G.Fβ x)

Fβ : {x y : C.Ob} β C.Hom x y β E.Hom (Fβ x) (Fβ y)
Fβ f = F.Fβ (G.Fβ f)


To verify that the result is functorial, equational reasoning is employed, using the witnesses that $F$ and $G$ are functorial.

    abstract
F-id : {x : C.Ob} β Fβ (C.id {x}) β‘ E.id {Fβ x}
F-id {x} =
F.Fβ (G.Fβ C.id) β‘β¨ ap F.Fβ G.F-id β©β‘
F.Fβ D.id        β‘β¨ F.F-id β©β‘
E.id             β

F-β : {x y z : C.Ob} (f : C.Hom y z) (g : C.Hom x y)
β Fβ (f C.β g) β‘ (Fβ f E.β Fβ g)
F-β f g =
F.Fβ (G.Fβ (f C.β g))     β‘β¨ ap F.Fβ (G.F-β f g) β©β‘
F.Fβ (G.Fβ f D.β G.Fβ g)  β‘β¨ F.F-β _ _ β©β‘
Fβ f E.β Fβ g             β

comps : Functor _ _
comps .Functor.Fβ = Fβ
comps .Functor.Fβ = Fβ
comps .Functor.F-id = F-id
comps .Functor.F-β = F-β

{-# DISPLAY Fβ.comps F G = F Fβ G #-}


The identity functor can be defined using the identity funct_ion_ for both its object and morphism mappings. That functors have an identity and compose would seem to imply that categories form a category: However, since there is no upper bound on the h-level of Ob, we can not form a βcategory of categoriesβ. If we do impose a bound, however, we can obtain a category of strict categories, those which have a set of objects.

Id : β {oβ hβ} {C : Precategory oβ hβ} β Functor C C
Functor.Fβ Id x = x
Functor.Fβ Id f = f
Functor.F-id Id = refl
Functor.F-β Id f g = refl


# Natural transformationsπ

Another common theme in category theory is that roughly every concept can be considered the objects of a category. This is the case for functors, as well! The functors between $C$ and $D$ assemble into a category, notated $[C, D]$ - the functor category between $C$ and $D$.

record _=>_ {oβ hβ oβ hβ}
{C : Precategory oβ hβ}
{D : Precategory oβ hβ}
(F G : Functor C D)
: Type (oβ β hβ β hβ)
where
no-eta-equality
constructor NT


The morphisms between functors are called natural transformations. A natural transformation $F \Rightarrow G$ can be thought of as a way of turning $F(x)$s into $G(x)$s that doesnβt involve any βarbitrary choicesβ.

  private
module F = Functor F
module G = Functor G
module D = Precategory D
module C = Precategory C

field
Ξ· : (x : _) β D.Hom (F.β x) (G.β x)


The transformation itself is given by Ξ·, the family of components, where the component at $x$ is a map $F(x) \to G(x)$. The βwithout arbitrary choicesβ part is encoded in the field is-natural, which encodes commutativity of the square below:

    is-natural : (x y : _) (f : C.Hom x y)
β Ξ· y D.β F.β f β‘ G.β f D.β Ξ· x


Natural transformations also dualize. The opposite of $\eta : F \Rightarrow G$ is $\eta^{\mathrm{op}} : G^{\mathrm{op}} \Rightarrow F^{\mathrm{op}}$.

  op : Functor.op G => Functor.op F
op = record
{ Ξ· = Ξ·
; is-natural = Ξ» x y f β sym (is-natural _ _ f)
}

{-# INLINE NT #-}

is-natural-transformation
: β {o β o' β'} {C : Precategory o β} {D : Precategory o' β'}
β (F G : Functor C D)
β (Ξ· : β x β D .Precategory.Hom (F .Functor.Fβ x) (G .Functor.Fβ x))
β Type _
is-natural-transformation {C = C} {D = D} F G Ξ· =
β x y (f : C .Precategory.Hom x y) β Ξ· y D.β F .Fβ f β‘ G .Fβ f D.β Ξ· x
where module D = Precategory D
open Functor

module _ where
open Precategory
open Functor

Const : β {o β o' β'} {C : Precategory o β} {D : Precategory o' β'}
β Ob D β Functor C D
Const {D = D} x .Fβ _ = x
Const {D = D} x .Fβ _ = id D
Const {D = D} x .F-id = refl
Const {D = D} x .F-β _ _ = sym (idr D _)

const-nt : β {o β o' β'} {C : Precategory o β} {D : Precategory o' β'}
β {x y : Ob D} β Hom D x y
β Const {C = C} {D = D} x => Const {C = C} {D = D} y
const-nt f ._=>_.Ξ· _ = f
const-nt {D = D} f ._=>_.is-natural _ _ _ = idr D _ β sym (idl D _)

infixr 30 _Fβ_
infix 20 _=>_

module _ {oβ hβ oβ hβ}
{C : Precategory oβ hβ}
{D : Precategory oβ hβ}
{F G : Functor C D} where
private
module F = Functor F
module G = Functor G
module D = Precategory D
module C = Precategory C

open Functor
open _=>_


Since the type of natural transformations is defined as a record, we can not a priori reason about its h-level in a convenient way. However, using Agdaβs metaprogramming facilities (both reflection and instance search), we can automatically derive an equivalence between the type of natural transformations and a certain $\Sigma$ type; This type can then be shown to be a set using the standard hlevel machinery.

  private unquoteDecl eqv = declare-record-iso eqv (quote _=>_)
Nat-is-set : is-set (F => G)
Nat-is-set = Isoβis-hlevel 2 eqv (hlevel 2) where
open C.HLevel-instance
open D.HLevel-instance


Another fundamental lemma is that equality of natural transformations depends only on equality of the family of morphisms, since being natural is a proposition:

  Nat-pathp : {F' G' : Functor C D}
β (p : F β‘ F') (q : G β‘ G')
β {a : F => G} {b : F' => G'}
β (β x β PathP _ (a .Ξ· x) (b .Ξ· x))
β PathP (Ξ» i β p i => q i) a b
Nat-pathp p q path i .Ξ· x = path x i
Nat-pathp p q {a} {b} path i .is-natural x y f =
is-propβpathp
(Ξ» i β D.Hom-set _ _
(path y i D.β Functor.Fβ (p i) f) (Functor.Fβ (q i) f D.β path x i))
(a .is-natural x y f)
(b .is-natural x y f) i

Nat-path : {a b : F => G}
β ((x : _) β a .Ξ· x β‘ b .Ξ· x)
β a β‘ b
Nat-path = Nat-pathp refl refl

_Ξ·β_ : β {a b : F => G} β a β‘ b β β x β a .Ξ· x β‘ b .Ξ· x
p Ξ·β x = ap (Ξ» e β e .Ξ· x) p

_Ξ·α΅_ : β {F' G' : Functor C D} {p : F β‘ F'} {q : G β‘ G'}
β {a : F => G} {b : F' => G'}
β PathP (Ξ» i β p i => q i) a b
β β x β PathP (Ξ» i β D.Hom (p i .Fβ x) (q i .Fβ x)) (a .Ξ· x) (b .Ξ· x)
p Ξ·α΅ x = apd (Ξ» i e β e .Ξ· x) p

infixl 45 _Ξ·β_

open Precategory
open _=>_

{-
Set-up for using natural transformations with the extensionality tactic;
See the docs in 1Lab.Extensionality for a more detailed explanation of
how it works.

This function is the actual worker which computes the preferred
identity system for natural transformations. Its type asks for

β x β Extensional (D.Hom (F # x) (G # x))

instead of the more generic β x y β Extensional (D.Hom x y) so that
any specific *instances* for D.Hom involving the object parts of F and G
have a chance to fire. E.g. if G is the product functor on Sets then
(x β y) will only match the funext instance but (x β G # y) will
match funext *and* product extensionality.
-}
Extensional-natural-transformation
: β {o β o' β' βr} {C : Precategory o β} {D : Precategory o' β'}
β {F G : Functor C D}
β {@(tactic extensionalαΆ  {A = Precategory.Ob C β Type _}
(Ξ» x β D .Hom (F .Functor.Fβ x) (G .Functor.Fβ x)))
sa : β x β Extensional (D .Hom (F .Functor.Fβ x) (G .Functor.Fβ x)) βr}
β Extensional (F => G) (o β βr)
Extensional-natural-transformation {sa = sa} .Pathα΅ f g = β i β Pathα΅ (sa i) (f .Ξ· i) (g .Ξ· i)
Extensional-natural-transformation {sa = sa} .reflα΅ x i = reflα΅ (sa i) (x .Ξ· i)
Extensional-natural-transformation {sa = sa} .idsα΅ .to-path x = Nat-path Ξ» i β
sa _ .idsα΅ .to-path (x i)
Extensional-natural-transformation {D = D} {sa = sa} .idsα΅ .to-path-over h =
is-propβpathp
(Ξ» i β Ξ -is-hlevel 1
(Ξ» _ β is-hlevelβ 1 (identity-system-gives-path (sa _ .idsα΅)) (D .Hom-set _ _ _ _)))
_ _

-- Actually define the loop-breaker instance which tells the
-- extensionality tactic what lemma to use for a type of natural
-- transformations.

instance
extensionality-natural-transformation
: β {o β o' β'} {C : Precategory o β} {D : Precategory o' β'}
{F G : Functor C D}
β Extensionality (F => G)
extensionality-natural-transformation = record
{ lemma = quote Extensional-natural-transformation }