\[ \require{mathtools} \let\DeclarePairedDelimiter\DeclarePairedDelimiters % MathJax typo % sup \newcommand{\op}{^\mathrm{op}} \newcommand{\inv}{^{-1}} % rm \newcommand{\compL}{\mathbin{\circ}} \newcommand{\Kl}{\mathrm{Kl}} % arrow \newcommand{\xto}{\xrightarrow} \newcommand{\xot}{\xleftarrow} \newcommand{\toot}{\rightleftarrows} \newcommand{\klto}{\rightsquigarrow} \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{\cFin}{\catf{Fin}} % finite prefix \newcommand{\cSet}{\catf{Set}} % functions \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{\cCat}{\catf{Cat}} % categories \newcommand{\cGrpd}{\catf{Grpd}} % groupoids \newcommand{\cVect}{\catf{Vect}} % vector spaces \newcommand{\cMeas}{\catf{Meas}} % measurable spaces and measurable functions \newcommand{\cStoch}{\catf{Stoch}} %measurable spaces and stochastic maps \newcommand{\cProb}{\catf{Prob}} % probability measures and measure-preserving functions % 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 \compL 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} \compL \eta. \end{array} \end{aligned}\]

3 Adjoint functor

For functors $F: \cC \toot \cD: G$ and the postcomposition functors $F^\cD: \cC^\cD \to \cD^\cD$ and $G^\cC: \cD^\cC \to \cC^\cC$:

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

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 Kan extension

Given functors $F: \cI \to \cC$, $P: \cI \to \cJ$, and the precomposition functor $\cC^P: \cC^\cJ \to \cC^\cI$:

A right Kan extension of $F$ through $P$ is a universal morphism $(\Ran F, \epsilon_F: \Ran F P \nat F)$ from $\cC^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 $\cC^P$.

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

\[\Lan \adj \cC^P \adj \Ran\]

6 Kan lift

Given functors $F: \cI \to \cC$, $P: \cD \to \cC$, and the postcomposition functor $P^\cI: \cD^\cI \to \cC^\cI$:

A right Kan lift of $F$ through $P$ is a universal morphism $(\Rift F, \epsilon_F: P \Rift F \nat F)$ from $P^\cI$ 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^\cI$.

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

\[\Lift \adj P^\cI \adj \Rift\]

7 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 \cC^\cI$ 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: \cC^\cI \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.

7.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} \compL 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 \compL 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 \compL 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$

7.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(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)\]

8 Product & coproduct

limit and colimit of 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 products of $\cCat$ are product categories.

8.1 Bifunctor

For two morphisms $f: A \to C$ and $g: B \to D$, the (co)product morphism is defined as

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

which makes $\times: \cC \times \cC \to \cC$ and $+: \cC \times \cC \to \cC$ bifunctors.

8.2 Diagonal & codiagonal

For an object $A$, the (co)diagonal morphism is defined as

\[\begin{aligned} \Delta_A &: A \to A \times A := \angles{\id_A, \id_A} \\ \nabla_A &: A + A \to A := \bracks{\id_A, \id_A} \end{aligned}\]

8.3 Associativity, unitality, commutativity, and distributivity

The (co)product is associative:

\[\begin{aligned} \begin{array}{lcr} \alpha_{A, B, C} := \angles{p_1 \compL 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 \compL p_2} =: \alpha_{A, B, C}\inv \\ \alpha_{A, B, C} := \bracks{\id_A + i_1, i_2 \compL i_2} &: (A + B) + C \iso A + (B + C) :& \bracks{i_1 \compL i_1, i_2 + \id_C} =: \alpha_{A, B, C}\inv \end{array} \end{aligned}\]
The terminal object $1$ is the unit of the product: $1 \times A \iso A \iso A \times 1$.

The initial object $0$ is the unit of the coproduct: $0 + A \iso A \iso A + 0$.
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 objects $A$, $B$, and $C$, there exists a distributive morphism of the product over the 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.

9 Equalizer & coequalizer

limit and colimit of free quiver $\cdot \rightrightarrows \cdot$

10 Pullback & pushout

limit of cospan $\cdot \rightarrow \cdot \leftarrow \cdot$ and colimit of 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)$.

Pullbacks in $\cC$ are products in $\cC \comma C$.
Pushouts in $\cC$ are coproducts in $C \comma \cC$.

All finite limits exist in a category with binary products and equalizers.
All finite limits exist in a category with terminal object and pullbacks.

11 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 \compL (\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 \compL (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

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

11.1 Composition

Precomposition:

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

Postcomposition:

\[h^B: C^B \to D^B := h \compL (-)\]

Composition:

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

Let $(-)^A: \cC \to \cC$ be the endofunctor that sends $B$ to $B^A$ and $f$ to $f^A$. Then,

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

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

11.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\]

11.3 Product

Product codomain:

\[\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 domain:

\[\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)\]

12 Tarski’s 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}$

13 Mono & epi

monomorphism $f: B \mono C$:

\[\forall g, h. (f \compL g = f \compL h) \to (g = h)\]

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

epimorphism $f: B \epi C$:

\[\forall g, h. (g \compL f = h \compL f) \to (g = h)\]

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

14 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 \compL 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.

15 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.

16 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

17 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 \compL u: \mu F \to \mu F$ is an F-algebra homomorphism from the initial F-algebra and thus is unique, $i \compL u = \id_{\mu F}$.
$u \compL i = Fi \compL Fu = F(i \compL u) = F \id_{\mu F} = \id_{F \mu F}$.

17.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 $\successor$ is the successor function.

17.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.

Universal Construction