\[ \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}\]
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)\).
Pushouts in \(\cC\) are coproducts in \(C \comma \cC\).
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.