Category Theory

This is a roadmap entry for the field of category theory.

Basics

Definition(category) . A category $\mathcal{C}$ consists of
  1. a family $\operatorname{Ob}(\mathcal{C})$ of objects,
  2. for every pair $(x,y)$ of objects a family $\mathcal{C}(x,y)$ of morphisms from $x$ to $y$,
  3. for every object $x$ a morphism $\text{id}_x \in \mathcal{C}(x,x)$ called the identity morphism.
  4. for every triple $(x,y,z)$ of objects a map $$ \mathcal{C}(x,y)\times\mathcal{C}(y,z)\to \mathcal{C}(x,z): (g,f)\mapsto f\circ g $$ called composition,
such that the following conditions are satisfied:
  1. Unitality. For every morphism $f\in\mathcal{C}(x,y)$, $$ \operatorname{id}_y\circ f = f\circ \operatorname{id}_x = f $$
  2. Associativity. For every triple $h:x\to y, g:y\to z,f:z\to w$, $$ (f\circ g) \circ h = f\circ (g\circ h) $$
Remark. The name "morphism" can be misleading since it tempts one to think of morphisms as maps, while they are really just formal arrows pointing from a source to a target.

For objects the notation $x\in\mathcal{C}$ will be used instead of $x\in\operatorname{Ob}(\mathcal{C})$.

Definition. A morphism $f:x\to y$ in a category $\mathcal{C}$ is an isomorphism if there is a morphism $g:y\to x$ s.t. $f\circ g = \operatorname{id}_y$ and $g\circ f=\operatorname{id}_x$.

There are some issues with the size of the category, where foundational concerns will become important. While there are categorical foundations, here set-theoretic foundations will be used.

Fix an infinite universe $\mathcal{U}$, so when set $X\in \mathcal{U}$ it is a small set, when $X\subset \mathcal{U}$ it is a class, and when $X\not\subset \mathcal{U}$ it is a large set. Here small sets will be simply called sets.

While one can always get rid of the objects by identifying the identity morphism $\operatorname{id}_x$ with $x\in\mathcal{C}$, sometimes distinguishing the two can be handful.

Functor

Definition. A functor $F:\mathcal{C}\to\mathcal{D}$ consists of
  • a map $F:\operatorname{Ob}(\mathcal{C})\to\operatorname{Ob}(\mathcal{D})$,
  • for every pair $(x,y)$ of objects in $\mathcal{C}$, a map $$ F:\mathcal{C}(x,y)\to \mathcal{D}(F(x),F(y)). $$
s.t.
  • For all $x\in \mathcal{C}$, $F(\operatorname{id}_x)=\operatorname{id}_{F(x)}$,
  • For every pair $x\xrightarrow{g}y\xrightarrow{f}z$, $$ F(f\circ g) = F(f) \circ F(g). $$

A good example for a functor is $$ F: BG \to \operatorname{Vect} $$ where $BG$ is the delooping of a group $G$ (i.e. the category with a single object, group elements being morphisms, and the composition being the group multiplication), and $\operatorname{Vect}$ is the category of vector spaces: $F$ is nothing but a representation of $G$. While functors are ubiquitous, those functors $F:\mathcal{C}\to \mathcal{D}$ that ‘realize’ the category $\mathcal{C}$ that is in some sense ‘syntactic’ in a category $\mathcal{D}$ that concretize the syntactic data encoded in $\mathcal{C}$ are of particular significance.

A special class of functors is that of identity functor, i.e. those functors $\operatorname{id}_\mathcal{C}:\mathcal{C}\to\mathcal{C}$ that maps objects and morphisms to itself.

Natural transformation

Definition. A natural transformation $\eta:F\Rightarrow G$ between two functors $F,G:\mathcal{C}\to\mathcal{D}$ consists of a family of morphisms $\{\eta_x:F(x)\to G(x)\}\_x$ in $\mathcal{D}$, such that for every morphism $f:x\to y$ in $\mathcal{C}$, the diagram commutes.

When all the morphisms $\eta_x$ are isomorphisms in $\mathcal{D}$, the natural transformation is a natural isomorphism.

Some words about composition of natural transformations.

Natural transformations can be composed vertically and horizontally,

Created by potrace 1.16, written by Peter Selinger 2001-2019

Natural transformations can also be composed with functors. A natural transformation $\eta:F\Rightarrow G$ between $F,G:\mathcal{C}\to \mathcal{D}$ is actually a collection of morphisms $\eta_x: F(x) \to G(x)$ in the target category $\mathcal{D}$ ‘parametrized’ by objects in the source category $x\in\mathcal{C}$.

  1. If there is a functor $A:\mathcal{B}\to \mathcal{C}$, the natural transformation $\eta$ can be “pulled-back” to $\mathcal{C}$, so the parametrization can actually be done by objects $b\in\mathcal{B}$. This is done by ‘composing’ natural transformations with functors: $$ \eta\circ A:= \{\eta_{A(b)}\}_{b\in \mathcal{B}}. $$
  2. The morphisms $\eta_x\in \text{Mor}(\mathcal{D})$ can, of course, be put into the slot of a functor and be ‘pushed’ to another category. Given a functor $K:\mathcal{D}\to\mathcal{E}$, there is another composition of natural transformations with functors: $$ K\circ \eta = \{K(\eta_x)\}_{x\in \mathcal{C}} $$

Equivalences and adjunctions

Recall that within a fixed category $\mathcal{C}$ the notion of equivalence is that of an isomorphism: A morphism $f:x\to y$ in a category $\mathcal{C}$ is an isomorphism if there is a morphism $g:y\to x$ s.t. $f\circ g = \operatorname{id}_y$ and $g\circ f=\operatorname{id}_x$. However, for categories an isomorphism will be far too strict. For categories, or in the category $\mathsf{Cat}$, the notion of equivalence is that of an equivalence of categories:

Definition. A functor $F:\mathcal{C}\to\mathcal{D}$ is an equivalence of categories if there is a functor $G:\mathcal{D}\to\mathcal{C}$, together with natural isomorphisms $F\circ G \Rightarrow \operatorname{id}_{\mathcal{D}}$ and $G\circ \Rightarrow \operatorname{id}_{\mathcal{C}}$.

A particularly useful theorem is

Theorem(Equivalence of categories) . A functor is an equivalence of categories, if it is fully faithful and essentially surjective.

An equivalence of categories $F:\mathcal{C}\to\mathcal{D}$ can be seen as a part of a particularly good adjunction between $\mathcal{C}$ and $\mathcal{D}$.

Definition. An adjunction between categories $\mathcal{C}$ and $\mathcal{D}$ is a tuple $(F,G;\eta,\epsilon)$, where
  • the functor $F:\mathcal{C}\to\mathcal{D}$ is called the left adjoint,
  • the functor $G:\mathcal{D}\to\mathcal{C}$ is called the right adjoint,
  • the natural transformation $\eta:F\circ G \Rightarrow \operatorname{id}_{\mathcal{D}}$ is called the counit,
  • the natural transformation $\epsilon:\operatorname{id}_\mathcal{C} \Rightarrow G\circ F$ is called the unit,
such that the composites $$ F\overset{F\circ\epsilon}{\Rightarrow} F\circ G \circ F \overset{\eta\circ F}{\Rightarrow} F, \quad F\overset{\epsilon\circ G}{\Rightarrow} G\circ F \circ G \overset{G\circ \eta}{\Rightarrow} G $$ are identities $\operatorname{id}_F$ and $\operatorname{id}_G$.

So when an adjunction has unit and counit being natural isomorphisms, then the functors are equivalences of categories. In fact, all equivalence of categories arise in this way, i.e., an equivalence of categories is a part of a adjunction where unit and counit are natural isomorphisms.

There is an equivalent definition for adjunction.

Definition. An adjunction between categories $\mathcal{C},\mathcal{D}$ is a triple $(F,G,\phi)$, where $F:\mathcal{C}\Rightarrow\mathcal{D},G:\mathcal{D}\Rightarrow\mathcal{C}$, and $\phi = \{\phi_{x,y}\}_{x\in\mathcal{C},y\in\mathcal{D}}$ is a family of bijections $$ \phi_{x,y}:\mathcal{D}(Fx,y)\to \mathcal{C}(x,Gy). $$

Adjoint functors are strongly related. When two functors $G,G’$ are right adjoints to a single functor $F$ (i.e. there are adunctions $(F,G,\phi)$, $(F,G’,\phi’)$), they are naturally isomorphic.

Limits

Let $I$ and $\mathcal{I}$ be categories, the category of $I$-diagrams in $\mathcal{C}$ is the functor category $$ \mathcal{C}^I := \operatorname{Func}(I,\mathcal{C}) $$ where the objects are functors from $I$ to $\mathcal{C}$, and morphisms are natural transformations. The diagonal functor $\Delta:\mathcal{C}\to \mathcal{C}^I$ is the functor that sends $x \in \mathcal{C}$ to $\Delta(x) = \operatorname{const}_x$, the constant functor that sends all $i\in I$ to $x$, and all morphisms in $I$ to $\operatorname{id}_{x}$.

A cone over an $I$-diagram $F\in \mathcal{C}^I$ is a pair $(x\in\mathcal{C},\eta:\Delta(x)\Rightarrow F)$. Then a morphism of cones over $F$ can be defined in an obvious manner.

Definition(Limit cone) . A limit cone $(x,\eta)$ over $F\in \mathcal{C}^I$ is a cone s.t. every cone $(x',\eta')$ over $F$ factors uniquely through $(x,\eta)$. Given a limit cone $(x,\eta)$, $x$ is called a limit of the diagram $F$.

The dual notion of colimit cone and colimit are formed by taking the opposite functor $F^{\text{op}}:I^{\text{op}}\to\mathcal{C}^{\text{op}}$ and repeating the definition.

A good example again arise from a functor from the delooping of a group $G$. Consider a functor $F:BG\to \mathsf{Set}$. Such a functor consists of a set $X = F(\ast)$ together with a $G$-action $\rho$ on $X$. A cone over $F$ will consist of $(Z,f)$ where $Z$ is a set with trivial $G$ action and $f:Z\to X$ is a $G$-equivariant map to $X$. The limit of $F$ is then the set $X^G$ of $G$-fixed points of $X$. The colimit is the set $X/G$ of $G$-orbits in $X$.

Kan extensions

The apperance of the diagonal functor $\Delta:\mathcal{C}\to \mathcal{C}^I$ in the definition of a cone over a functor $F\in \mathcal{C}^I$ looks quite special. Notice that given a functor $\phi: I\to J$, there is a functor $\phi^\ast: \mathcal{C}^J \to \mathcal{C}^I: F\mapsto F\circ\phi$, when $J=\ast$ this becomes $\Delta$.

Definition(Right extension) . Let $F\in\mathcal{C}^I$. A right extension of $F$ along $\phi$ is a pair $(G,\eta)$, where $G\in\mathcal{C}^J$, and $\eta$ is a natural transformation $\eta:\phi^\ast G\Rightarrow F$.

If every right extension $(G’,\eta’)$ of $F$ along $\phi$ factors through the right extension $(G,\eta)$, the right extension $(G,\eta)$ is called a right Kan extension. Reversing the direction of the natural transformations, the extensions and the corresponding Kan extensions are left etc.

Theorem(Adjunction of a right Kan extension) . Let $\phi:I\to J$ be a functor and $\mathcal{C}$ be a category. If every $F\in \mathcal{C}^I$ has a right Kan extension along $\phi$, then there is an adjunction between the functors $(\phi^\ast,\phi_\ast)$ where $\phi_*:\mathcal{C}^I\to \mathcal{C}^J$ assocaites to each diagram $F\in\mathcal{C}^I$ a right Kan extension $G\in\mathcal{C}^J$ along $\phi$.

This for $J=\ast$ specialize to limits, which says that if every $F\in\mathcal{C}^I$ has a limit, then there is a functor $\operatorname{lim}$ that associates the limit $\operatorname{lim}(F)$ to each diagram $F$.