\[ \require{mathtools} \let\DeclarePairedDelimiter\DeclarePairedDelimiters % MathJax typo % sup \newcommand{\op}{^\mathrm{op}} \newcommand{\inv}{^{-1}} % rm \newcommand{\Kl}{\mathrm{Kl}} % symbol \newcommand{\xto}{\xrightarrow} \newcommand{\toot}{\rightleftarrows} \newcommand{\comma}{\downarrow} \newcommand{\incl}{\hookrightarrow} \newcommand{\mono}{\rightarrowtail} \newcommand{\epi}{\twoheadrightarrow} \newcommand{\iso}{\cong} \newcommand{\nat}{\Rightarrow} \newcommand{\adj}{\dashv} % delimiter \DeclarePairedDelimiter{\parens}{(}{)} % parentheses ( ) \DeclarePairedDelimiter{\bracks}{[}{]} % brackets [ ] \DeclarePairedDelimiter{\braces}{\{}{\}} % braces { } \DeclarePairedDelimiter{\angles}{\langle}{\rangle} % angles \newcommand{\set}{\braces} % operator \DeclareMathOperator{\Obj}{Obj} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\Eq}{Eq} \DeclareMathOperator{\Coeq}{Coeq} \DeclareMathOperator{\Pull}{Pull} \DeclareMathOperator{\Push}{Push} \DeclareMathOperator{\Lan}{Lan} \DeclareMathOperator{\Ran}{Ran} \DeclareMathOperator{\Lift}{Lift} \DeclareMathOperator{\Rift}{Rift} % \DeclareMathOperator{\id}{id} \DeclareMathOperator{\act}{act} \DeclareMathOperator{\colim}{colim} % exponential \DeclareMathOperator{\partf}{partial} \DeclareMathOperator{\curry}{curry} % natural number \DeclareMathOperator{\zero}{zero} \DeclareMathOperator{\successor}{succ} % list \DeclareMathOperator{\nil}{nil} \DeclareMathOperator{\cons}{cons} \newcommand{\concat}{\mathbin{{+}\mspace{-8mu}{+}}} % fold \DeclareMathOperator{\fold}{fold} \DeclareMathOperator{\map}{map} \DeclareMathOperator{\filter}{filter} % bool \DeclareMathOperator{\cond}{cond} % cd \DeclareMathOperator{\copy}{copy} \DeclareMathOperator{\del}{del} % sets \newcommand{\N}{\mathbb{N}} % natural numbers \newcommand{\Z}{\mathbb{Z}} % integers \newcommand{\Q}{\mathbb{Q}} % rational numbers \newcommand{\R}{\mathbb{R}} % real numbers % category \newcommand{\catf}[1]{{\mathbf{#1}}} \newcommand{\cA}{\catf{A}} \newcommand{\cB}{\catf{B}} \newcommand{\cC}{\catf{C}} \newcommand{\cD}{\catf{D}} \newcommand{\cE}{\catf{E}} \newcommand{\cI}{\catf{I}} \newcommand{\cJ}{\catf{J}} \newcommand{\cS}{\catf{S}} \newcommand{\cT}{\catf{T}} \newcommand{\cV}{\catf{V}} \newcommand{\cZero}{\catf{0}} \newcommand{\cOne}{\catf{1}} \newcommand{\cTwo}{\catf{2}} % \newcommand{\cArr}{\catf{Arr}} % arrow \newcommand{\cPSh}{\catf{PSh}} % presheaf \newcommand{\cCone}{\catf{Cone}} % cone \newcommand{\cCocone}{\catf{Cocone}} % cocone % \newcommand{\cSet}{\catf{Set}} % sets \newcommand{\cFinSet}{\catf{FinSet}} % finite sets \newcommand{\cRel}{\catf{Rel}} % relations \newcommand{\cPos}{\catf{Pos}} % posets \newcommand{\cMon}{\catf{Mon}} % monoids \newcommand{\cGrp}{\catf{Grp}} % groups \newcommand{\cAb}{\catf{Ab}} % Abelian groups \newcommand{\cVect}{\catf{Vect}} % vector spaces \newcommand{\cCat}{\catf{Cat}} % categories % logic \newcommand{\lfal}{\bot} \newcommand{\ltru}{\top} \]

Universal construction defines objects in terms of their relations with other objects.

1 Terminal object & initial object

In a category $\cC$ :

A terminal object is an object $T$ that for every object $A$ there exists a unique morphism $f: A \to T$ to it.
An initial object is an object $I$ that for every object $B$ there exists a unique morphism $g: I \to B$ from it.

\[\begin{aligned} \begin{array}{rlcll} \text{terminal object:} & T & \equiv & \forall A. & \exists! f: A \to T. \\ \text{initial object:} & I & \equiv & \forall B. & \exists! g: I \to B. \end{array} \end{aligned}\]

For an object $A$ in a category $\cC$, a generalized element of $A$ is a morphism $x: X \to A$.

If $\cC$ has a terminal object $1$, a global element of $A$ is a morphism $x: 1 \to A$.

2 Universal morphism

For a $\cC$-object $A$, a $\cD$-object $B$, and functors $F: \cC \toot \cD: G$ :

A universal morphism from $F$ to $B$ is a terminal object $(T, FT \xto{\epsilon} B)$ in the comma category $(F: \cC \to \cD) \comma (B: \cOne \to \cD)$.
A universal morphism from $A$ to $G$ is an initial object $(I, A \xto{\eta} GI)$ in the comma category $(A: \cOne \to \cC) \comma (G: \cD \to \cC)$.

\[\begin{aligned} \begin{array}{rlclll} \text{universal morphism from $F$ to $B$:} & (T, FT \xto{\epsilon} B) & \equiv & \forall f: FA \to B. & \exists! \hat{f}: A \to T. & f = \epsilon \circ F\hat{f}. \\ \text{universal morphism from $A$ to $G$:} & (I, A \xto{\eta} GI) & \equiv & \forall g: A \to GB. & \exists! \hat{g}: I \to B. & g = G\hat{g} \circ \eta. \end{array} \end{aligned}\]

3 Adjoint functor

For functors $F: \cC \toot \cD: G$ and the post-composition functors $F(-): [\cD, \cC] \to [\cD, \cD]$ and $G(-): [\cC, \cD] \to [\cC, \cC]$ :

A right adjoint functor of $F$ is a universal morphism $(G, \epsilon: FG \nat \id_\cD)$ from $F(-)$ to $\id_\cD$.
A left adjoint functor of $G$ is a universal morphism $(F, \eta: \id_\cC \nat GF)$ from $\id_\cC$ to $G(-)$.

For each $\cD$-object $B$ there exists a universal morphism $FGB \xto{\epsilon_B} B$ from $F$ to $B$.
For each $\cC$-object $A$ there exists a universal morphism $A \xto{\eta_A} GFA$ from $A$ to $G$.

4 Adjunction

An adjunction $F \adj G$ between two categories $\cC$ and $\cD$ consists of a pair of adjoint functors $F: \cC \toot \cD: G$ with

counit $\epsilon: FG \nat \id_\cD$
unit $\eta: \id_\cC \nat GF$

such that

$(\epsilon F)(F \eta) = \id_F$
$(G \epsilon)(\eta G) = \id_G$

\[\begin{aligned} \begin{array}{rll} \text{isomorphism:} & \id_\cC = GF & FG = \id_\cD \\ \text{equivalence:} & \id_\cC \iso GF & FG \iso \id_\cD \\ \text{adjunction:} & \id_\cC \nat GF & FG \nat \id_\cD \end{array} \end{aligned}\]

\[\Hom_\cD(FA, B) \iso \Hom_\cC(A, GB)\]

5 Limit & colimit

A diagram of type $\cI$ in a category $\cC$ is a functor

\[\begin{aligned} D: \cI &\to \cC \\ i &\mapsto D_i \\ ij &\mapsto D_{ij} \end{aligned}\]

$\cI$ is called the index category.

Given the diagonal functor $\Delta: \cC \to [\cI, \cC]$ and a diagram $D: \cI \to \cC$ :

A limit is a universal morphism $(\lim D, \epsilon_D: \Delta \lim D \nat D)$ from $\Delta$ to $D$.
A colimit is a universal morphism $(\colim D, \eta_D: D \nat \Delta \colim D)$ from $D$ to $\Delta$.

\[\begin{aligned} \begin{array}{rlclll} \text{limit:} & \epsilon_D: \Delta \lim D \nat D & \equiv & \forall c: \Delta C \nat D. & \exists! \hat{c}: C \to \lim D. & c = \epsilon_D (\Delta \hat{c}). \\ \text{colimit:} & \eta_D: D \nat \Delta \colim D & \equiv & \forall c: D \nat \Delta C. & \exists! \hat{c}: \colim D \to C. & c = (\Delta \hat{c}) \eta_D. \end{array} \end{aligned}\]

Let $\lim, \colim: [\cI, \cC] \to \cC$ be the functors that assign a diagram to its limit/colimit. Then,

\[\colim \adj \Delta \adj \lim\]

A category is finitely (co)complete if it has all finite (co)limits. A category is (co)complete if it has all small (co)limits.

5.1 Cone & cocone

A cone $(C, c)$ over a diagram $D: \cI \to \cC$ consists of

a $\cC$-object $C$
a collection of $\cC$-morphisms from $C$ indexed by $\cI$-objects $c_i: C \to D_i$

such that for all $\cI$-morphisms $ij: i \to j$, $c_j = D_{ij} \circ c_i$.

A cone morphism $f: (C, c) \to (C', c')$ is a $\cC$-morphism $f: C \to C'$ that for all $\cI$-objects $i$, $c_i = c'_i \circ f$.

A cone category $\cCone(D)$ consists of all cones over a diagram $D$ and all cone morphisms.

A limit $\lim D$ of a diagram $D$ is a terminal object in $\cCone(D)$.

A limit is a cone: (a $\cC$-object $\lim D$, a collection of $\cC$-morphisms $\epsilon_i: \lim D \to D_i$)
A limit is a terminal object: for all cones $(C, c)$, there exists a unique cone morphism $f: (C, c) \to (\lim D, \epsilon)$ such that $c_i = \epsilon_i \circ f$.

The concepts of cocone, cocone morphism, cocone category and colimit are defined dually.

cone: $c: \Delta C \nat D$, cocone: $c: D \nat \Delta C$
cone/cocone morphism: $\Delta f: \Delta C \nat \Delta C'$
cone category: $\Delta \comma D$, cocone category: $D \comma \Delta$
limit: $\epsilon_D: \Delta \lim D \nat D$, colimit: $\eta_D: D \nat \Delta \colim D$

5.2 Preservation

For a diagram $D: \cI \to \cC$ and a functor $F: \cC \to \cD$,

$F$ preserves a limit $(\lim D, \epsilon_D)$ in $\cC$ if $(F \lim D, F \epsilon_D)$ is a limit in $\cD$
$F$ preserves a colimit $(\colim D, \eta_D)$ in $\cC$ if $(F \colim D, F \eta_D)$ is a colimit in $\cD$

A functor is finitely (co)continuous if it preserves all finite (co)limits. A functor is (co)continuous if it preserves all small (co)limits.

Hom-functor $\Hom: \cC\op \times \cC \to \cSet$ preserves limits in both arguments.

$\Hom(X, -)$ preserves limits

\[\Hom(A, B \times C) \iso \Hom(A, B) \times \Hom(A, C)\]
$\Hom(-, X)$ sends colimits to limits

\[\Hom(A + B, C) \iso \Hom(A, C) \times \Hom(B, C)\]

6 Limit & colimit examples

6.1 Terminal object & initial object

empty diagram

6.2 Product & coproduct

discrete diagram $\cdot \hphantom{ {}\to{} } \cdot$

The unique morphisms $\angles{f, g}$ and $\bracks{f, g}$ are called the paring and coparing of $f$ and $g$, respectively.

The (co)product is commutative:

\[\begin{aligned} \begin{array}{lcr} \beta_{A, B} := \angles{p_2, p_1} &: A \times B \iso B \times A :& \angles{p_2, p_1} =: \beta_{B, A} \\ \beta_{A, B} := \bracks{i_2, i_1} &: A + B \iso B + A :& \bracks{i_2, i_1} =: \beta_{B, A} \end{array} \end{aligned}\]

For two morphisms $f: A \to C$ and $g: B \to D$, there exist product/coproduct morphisms:

\[\begin{aligned} f \times g &: A \times B \to C \times D := \bracks{f \circ p_1, g \circ p_2} \\ f + g &: A + B \to C + D := \angles{i_1 \circ f, i_2 \circ g} \end{aligned}\]

The (co)product is associative:

\[\begin{aligned} \begin{array}{lcr} \alpha_{A, B, C} := \angles{p_1 \circ p_1, p_2 \times \id_C} &: (A \times B) \times C \iso A \times (B \times C) :& \angles{\id_A \times p_1, p_2 \circ p_2} =: \alpha_{A, B, C}\inv \\ \alpha_{A, B, C} := \bracks{\id_A + i_1, i_2 \circ i_2} &: (A + B) + C \iso A + (B + C) :& \bracks{i_1 \circ i_1, i_2 + \id_C} =: \alpha_{A, B, C}\inv \end{array} \end{aligned}\]

For objects $A$, $B$, and $C$, there exists a distributive morphism of product over coproduct:

\[\delta_{A, B, C}: A \times B + A \times C \to A \times (B + C):= \bracks{\id_A \times i_1, \id_A \times i_2}\]

A category is distributive if all distributive morphisms are isomorphisms.

6.3 Equalizer & coequalizer

free quiver $\cdot \rightrightarrows \cdot$

6.4 Pullback & pushout

cospan $\cdot \rightarrow \cdot \leftarrow \cdot$ / span $\cdot \leftarrow \cdot \rightarrow \cdot$

The fiber of a morphism $f: A \to B$ over a global element $b: 1 \to B$ is the pullback $\Pull(f, b)$.

7 Exponential object

For a category $\cC$ with binary products, an exponential object from $A$ to $B$ is a universal morphism $(B^A, B^A \times A \xto{\epsilon_A} B)$ from $(-) \times A$ to $B$.

\[\begin{array}{rlclll} \text{exponential:} & (B^A, B^A \times A \xto{\epsilon_A} B) & \equiv & \forall f: C \times A \to B. & \exists! \hat{f}: C \to B^A. & f = \epsilon_A \circ (\hat{f} \times \id_A). \end{array}\]

$\epsilon_A: B^A \times A \to B$ is called evaluation
$\hat{f}: C \to B^A$ is called the exponential transpose of $f: C \times A \to B$
$\bar{g}: C \times A \to B := \epsilon_A \circ (g \times \id_A)$ is the exponential transpose of $g: C \to B^A$
transposition of transposition is the identity: $\Hom(C \times A, B) \iso \Hom(C, B^A)$

-- function application
($) :: (a -> b) -> a -> b
-- reverse function application
(&) :: a -> (a -> b) -> b

For a fixed object $A$, let $(-)^A: \cC \to \cC$ be the endofunctor that assigns an object $B$ to the exponential object $B^A$.

\[(-) \times A \adj (-)^A\]

A category is cartesian closed if it has all finite products and exponentials.

The exponential objects of $\cCat$ are functor categories.

7.1 Composition

Precomposition:

\[g^A: B^A \to C^A := g \circ (-)\]

Postcomposition:

\[A^f: C^B \to C^A := (-) \circ f\]

Composition:

\[\circ: C^B \times B^A \to C^A\]

7.2 Currying

Partial application:

\[\partf: C^{A \times B} \times A \to C^B\]

Currying and uncurrying:

\[\curry: C^{A \times B} \iso (C^B)^A: \curry\inv\]

7.3 Product

Product base:

\[\angles{p_1^A, p_2^A}: (B \times C)^A \iso B^A \times C^A\]

\[\Hom(A, B \times C) \iso \Hom(A, B) \times \Hom(A, C)\]

Coproduct exponent:

\[\angles{C^{i_1}, C^{i_2}}: C^{A + B} \iso C^A \times C^B\]

\[\Hom(A + B, C) \iso \Hom(A, C) \times \Hom(B, C)\]

8 High school algebra

$A + B \iso B + A$
$(A + B) + C \iso A + (B + C)$
$A \times 1 \iso A$
$A \times B \iso B \times A$
$(A \times B) \times C \iso A \times (B \times C)$
$A \times B + A \times C \to A \times (B + C)$
$1^A \iso 1$
$A^1 \iso A$
$A^{B + C} \iso A^B \times A^C$
$(A \times B)^C \iso A^C \times B^C$
$(A^B)^C \iso A^{B \times C}$

9 Mono & epi

- monomorphism $f: B \mono C$ :

\[\forall g, h: A \to B. (f \circ g = f \circ h) \to (g = h)\]

$f: B \to C$ is a mono if $\Pull(f, f) = B$

epimorphism $f: B \epi C$ :

\[\forall g, h: C \to D. (g \circ f = h \circ f) \to (g = h)\]

$f: B \to C$ is an epi if $\Push(f, f) = C$

10 Subobject

For a category $\cC$, a subobject of an object $A$ is a mono $s: S \mono A$.

For two subobjects of $A$, a subobject morphism is a morphism in the slice category $\cC \comma A$.

inclusion of two subobjects $s$ and $t$ :

\[s \subseteq t: \exists f: s \to t\]
equivalence of two subobjects $s$ and $t$ :

\[s \equiv t: s \subseteq t \land t \subseteq s\]
local membership of a generalized element $x: X \to A$ :

\[x \in_A s: \exists f: X \to S. x = s \circ f\]

For a category $\cC$ with a terminal object $1$, a subobject classifier is an object $\Omega$ together with a morphism $\ltru: 1 \to \Omega$, such that for each mono $s: S \mono A$, there exists a mono $\chi_s: A \mono \Omega$, called the classifying morphism that forms a pullback.

11 Power object

For a category $\cC$ with binary products, a power object of an object $A$ is an object $PA$ together with a mono $\in_A \mono A \times PA$, such that for each mono $r: R \mono A \times B$, there exists a unique morphism $\chi_r: B \to PA$ that forms a pullback.

12 F-algebra

An initial F-algebra of an endofunctor $F$ is an initial object in the category of F-algebras.

If an endofunctor $F$ has an initial F-algebra $(\mu F, i)$, then $F \mu F \iso \mu F$.

$(F \mu F, Fi)$ is an F-algebra, so there exists a unique F-algebra homomorphism $u: \mu F \to F \mu F$.
$i \circ u: \mu F \to \mu F$ is an F-algebra homomorphism from the initial F-algebra and thus is unique, $i \circ u = \id_{\mu F}$.
$u \circ i = Fi \circ Fu = F(i \circ u) = F \id_{\mu F} = \id_{F \mu F}$.

12.1 Natural numbers object

In a category $\cC$ with a terminal object $1$, a natural numbers object (NNO) $\N$ is an initial F-algebra of the endofunctor $X \mapsto 1 + X$.

\[\begin{aligned} \begin{array}{rccccc} & 1 &+& \N &\to& \N \\ \zero: & * && &\mapsto& 0 \\ \successor: && & n &\mapsto& n+1 \end{array} \end{aligned}\]

$\zero$ maps to zero and $\succ$ is the successor function.

12.2 List object

In a category $\cC$ with a terminal object $1$ and binary products, an $A$-valued list object $[A]$ is an initial F-algebra of the endofunctor $X \mapsto 1 + A \times X$.

\[\begin{aligned} \begin{array}{rccccc} & 1 &+& A \times [A] &\to& [A] \\ \nil: & * && &\mapsto& [] \\ \cons: & && (x, xs) &\mapsto& x:xs \end{array} \end{aligned}\]

$\nil$ maps to the empty list and $\cons$ adds an element to the beginning of a list.

12.3 Group object

In a category $\cC$ with a terminal object $1$ and binary products, a group object $G$ is an F-algebra of the endofunctor $X \mapsto 1 + X + X^2$.

\[\begin{aligned} \begin{array}{rccccc} & 1 &+& G &+& G^2 &\to& G \\ e: & * && && &\mapsto& e \\ i: & && g && &\mapsto& g\inv \\ m: & && && (g_1, g_2) &\mapsto& g_1 \cdot g_2 \end{array} \end{aligned}\]

that satisfies the following associativity, identity, and invertibility axioms:

13 Set

terminal object: singleton $\set{*}$
initial object: empty set $\varnothing$
product: cartesian product $A \times B$
coproduct: disjoint union $A + B$
equalizer: $\Eq(f, g: A \to B) = \set{a \in A \mid f(a) = g(a)}$
coequalizer: $\Coeq(f, g: A \to B) = B / \sim$ where $b_1 \sim b_2$ if $\exists a \in A. f(a) = b_1 \land g(a) = b_2$
pullback: $\Pull(f: A \to C, g: B \to C) = \set{(a, b) \in A \times B \mid f(a) = g(b)}$
pushout: $\Push(f: C \to A, g: C \to B) = (A + B) / \sim$ where $a \sim b$ if $\exists c \in C. f(c) = a \land g(c) = b$
fiber: inverse image $\Pull(f: A \to B, b: 1 \to B) = \set{a \in A \mid f(a) = b}$
exponential object: functions and function evaluation
mono: injective function
epi: surjective function
subobject: subset
subobject classifier: indicator function
power object: power set

14 Kan extension

Given functors $F: \cI \to \cC$, $P: \cJ \to \cI$, and the pre-composition functor $(-)P: [\cJ, \cC] \to [\cI, \cC]$ :

A right Kan extension of $F$ through $P$ is a universal morphism $(\Ran F, \epsilon_F: \Ran F P \nat F)$ from $(-)P$ to $F$.
A left Kan extension of $F$ through $P$ is a universal morphism $(\Lan F, \eta_F: F \nat \Lan F P)$ from $F$ to $(-)P$.

Let $\Lan, \Ran: [\cI, \cC] \to [\cJ, \cC]$ be the functors that assign a functor to its left/right Kan extensions. Then,

\[\Lan \adj (-)P \adj \Ran\]

15 Kan lift

Given functors $F: \cI \to \cC$, $P: \cD \to \cC$, and the post-composition functor $P(-): [\cI, \cD] \to [\cI, \cC]$ :

A right Kan lift of $F$ through $P$ is a universal morphism $(\Rift F, \epsilon_F: P \Rift F \nat F)$ from $P(-)$ to $F$.
A left Kan lift of $F$ through $P$ is a universal morphism $(\Lift F, \eta_F: F \nat P \Lift F)$ from $F$ to $P(-)$.

Let $\Lift, \Rift: [\cI, \cC] \to [\cI, \cD]$ be the functors that assign a functor to its left/right Kan lifts. Then,

\[\Lift \adj P(-) \adj \Rift\]

Universal Construction