\[ \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} \DeclareMathOperator{\partf}{partial} \DeclareMathOperator{\curry}{curry} \DeclareMathOperator{\zero}{zero} \DeclareMathOperator{\succ}{succ} \DeclareMathOperator{\nil}{nil} \DeclareMathOperator{\cons}{cons} \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.
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 \(B\) to \(C\) is a universal morphism \((C^B, C^B \times B \xto{\epsilon_B} C)\) from \((-) \times B\) to \(C\).
\[\begin{array}{rlclll} \text{exponential:} & (C^B, C^B \times B \xto{\epsilon_B} C) & \equiv & \forall f: A \times B \to C. & \exists! \hat{f}: A \to C^B. & f = \epsilon_B \circ (\hat{f} \times \id_B). \end{array}\]
- \(\epsilon_B: C^B \times B \to C\) is called evaluation
- \(\hat{f}: A \to C^B\) is called the exponential transpose of \(f: A \times B \to C\)
- for a morphism \(g: A \to C^B\), \(\bar{g} := \epsilon_B \circ (g \times \id_B): A \times B \to C\) is the transpose of \(g\)
- transposition of transposition is the identity: \(\bar{\hat{f}} = f\), \(\hat{\bar{g}} = g\)
\[\Hom(A \times B, C) \iso \Hom(A, C^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\). Then,
\[(-) \times B \adj (-)^B\]
A category is cartesian closed if it has all finite products and exponentials.
For morphisms \(A \xto{f} B \xto{g} C\), there exist exponential morphisms:
\[g^A: B^A \to C^A := g \circ (-)\]
\[A^f: C^B \to C^A := (-) \circ f\]
Product base:
\[\angles{p_1^C, p_2^C}: (A \times B)^C \iso A^C \times B^C\]
Coproduct exponent:
\[\angles{A^{i_1}, A^{i_2}}: A^{B + C} \iso A^B \times A^C\]
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\]
The exponential objects of \(\cCat\) are functor categories.
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 \\ \succ & & & 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 Binary trees object
In a category \(\cC\) with a terminal object \(1\) and binary products, a binary trees object is an initial F-algebra of the endofunctor \(X \mapsto 1 + X^2\).
12.4 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\]