\[ \require{mathtools} \let\DeclarePairedDelimiter\DeclarePairedDelimiters % MathJax typo %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % symbol %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 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{\cF}{\catf{F}} \newcommand{\cG}{\catf{G}} \newcommand{\cH}{\catf{H}} \newcommand{\cI}{\catf{I}} \newcommand{\cJ}{\catf{J}} \newcommand{\cK}{\catf{K}} \newcommand{\cL}{\catf{L}} \newcommand{\cM}{\catf{M}} \newcommand{\cN}{\catf{N}} \newcommand{\cO}{\catf{O}} \newcommand{\cP}{\catf{P}} \newcommand{\cQ}{\catf{Q}} \newcommand{\cR}{\catf{R}} \newcommand{\cS}{\catf{S}} \newcommand{\cT}{\catf{T}} \newcommand{\cU}{\catf{U}} \newcommand{\cV}{\catf{V}} \newcommand{\cW}{\catf{W}} \newcommand{\cX}{\catf{X}} \newcommand{\cY}{\catf{Y}} \newcommand{\cZ}{\catf{Z}} \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{\cMet}{\catf{Met}} % metric spaces and metric maps \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 % \newcommand{\cBool}{\catf{Bool}} \newcommand{\cCost}{\catf{Cost}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % supscript %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\op}{^\mathrm{op}} \newcommand{\inv}{^{-1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % function %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \DeclareMathOperator{\lcm}{lcm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % arrow %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % morphism \newcommand{\xto}{\xrightarrow} % -> \newcommand{\xot}{\xleftarrow} % <- \newcommand{\toot}{\rightleftarrows} % <=> \newcommand{\iso}{\cong} % ~= \newcommand{\klto}{\rightsquigarrow} % ~> \newcommand{\mono}{\rightarrowtail} % >-> \newcommand{\epi}{\twoheadrightarrow} % ->> \newcommand{\ihom}{\multimap} % -o % category \newcommand{\incl}{\hookrightarrow} \newcommand{\adjto}[2]{\overset{{}\xto[]{#1}{}}{\underset{{}\xot[#2]{}{}}{\bot}}} % functor \newcommand{\nat}{\Rightarrow} % => \newcommand{\xnat}{\xRightarrow} % => \newcommand{\comma}{\downarrow} \newcommand{\adj}{\dashv} % -| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % delimiter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \DeclarePairedDelimiter{\parens}{(}{)} % parentheses ( ) \DeclarePairedDelimiter{\bracks}{[}{]} % brackets [ ] \DeclarePairedDelimiter{\braces}{\{}{\}} % braces { } \DeclarePairedDelimiter{\angles}{\langle}{\rangle} % angles \DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor} \DeclarePairedDelimiter{\ceil}{\lceil}{\rceil} \newcommand{\set}{\braces} \newcommand{\singleton}{{\set{*}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % operator %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\compL}{\mathbin{\circ}} \newcommand{\Kl}{\mathrm{Kl}} \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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % order %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\meet}{\wedge} \newcommand{\join}{\vee} \newcommand{\bigmeet}{\bigwedge} \newcommand{\bigjoin}{\bigvee} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % logic %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\lfal}{\bot} \newcommand{\ltru}{\top} \newcommand{\lcon}{\wedge} \newcommand{\lncon}{\uparrow} \newcommand{\ldis}{\vee} \newcommand{\lndis}{\downarrow} \newcommand{\limp}{\rightarrow} \newcommand{\lnimp}{\nrightarrow} \newcommand{\lcim}{\leftarrow} \newcommand{\lncim}{\nleftarrow} \newcommand{\leqv}{\leftrightarrow} \newcommand{\lneqv}{\nleftrightarrow} \newcommand{\lproves}{\vdash} % |- \newcommand{\lmodels}{\vDash} % |= \newcommand{\lnproves}{\nvdash} % |/- \newcommand{\lnmodels}{\nvDash} % |/= \]
Universal construction defines objects in terms of their relations with other objects.
1 Terminal object & initial object
- 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}\]
A generalized element of \(A\) is a morphism \(x: X \to A\).
A global element of \(A\) is a morphism \(x: 1 \to A\).
A zero object is both a terminal object and an initial object.
A pointed category has a zero object.
2 Universal morphism
\[\begin{aligned} \begin{array}{ccccc} F: & \cC & \toot & \cD & :G \\ & A && B & \\ & f && g & \end{array} \end{aligned}\]
- 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 g: FA \to B. & \exists! \hat{g}: A \to T. & g = \epsilon \compL F\hat{g}. \\ \text{universal morphism from $A$ to $G$:} & (I, A \xto{\eta} GI) & \equiv & \forall f: A \to GB. & \exists! \hat{f}: I \to B. & f = G\hat{f} \compL \eta. \end{array} \end{aligned}\]
3 Adjunction
3.1 Adjoint functor
- A right adjoint functor of \(F\) is a universal morphism \((G, \epsilon: FG \nat \id_\cD)\) from \(F^\cD: \cC^\cD \to \cD^\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: \cD^\cC \to \cC^\cC\).
- For each \(\cD\)-object \(B\), there exists a universal morphism \((GB, \epsilon_B: FGB \to B)\) from \(F\) to \(B\).
- For each \(\cC\)-object \(A\), there exists a universal morphism \((FA, \eta_A: A \to GFA)\) from \(A\) to \(G\).
\[G(B \xto{g} B') := \widehat{g \compL \epsilon_B}\]
\[F(A \xto{f} A') := \widehat{\eta_A' \compL f}\]
3.2 Hom-set isomorphism
\[\alpha: \Hom_\cD(FA, B) \iso \Hom_\cC(A, GB) :\alpha\inv\]
\[\begin{aligned} \begin{array}{cccc} \alpha\inv_{GB, B}: & \Hom_\cC(GB, GB) & \iso & \Hom_\cD(FGB, B) \\ & \id_{GB} & \mapsto & \epsilon_B \\ \alpha_{A, FA}: & \Hom_\cD(FA, FA) & \iso & \Hom_\cC(A, GFA) \\ & \id_{FA} & \mapsto & \eta_A \end{array} \end{aligned}\]
3.3 Counit-unit adjunction
\[\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}\]
\[\cC \adjto{F}{G} \cD\]
An adjunction \(F \adj G\) 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) \compL (F \eta) = \id_F\)
- \((G \epsilon) \compL (\eta G) = \id_G\)
3.4 Galois connection
\[F: (A, \leq_A) \adj (B, \leq_B) :G\]
\[\begin{aligned} Fa := \min \set{b \in B \mid a \leq_A Gb} \\ Gb := \max \set{a \in A \mid Fa \leq_B b} \end{aligned}\]
3.4.1 Multiplication and division
\[(\R, \leq) \adjto{- / c}{- \times c} (\R, \leq)\]
\[a / c \leq b \equiv a \leq b \times c\]
- \(\eta_a: a \leq a / c * c = \id_a\)
- \(\epsilon_a: a * c / c \leq a = \id_a\)
3.4.2 Union and intersection
\[(PA, \subseteq) \adjto{- \cap X}{\overline{X} \cup -} (PA, \subseteq)\]
\[Z \cap X \subseteq Y \equiv Z \subseteq \overline{X} \cup Y\]
- \(\eta_A: A \subseteq \overline{X} \cup (A \cap X)\)
- \(\epsilon_A: (\overline{X} \cup A) \cap X \subseteq A\)
3.4.3 Floor and ceiling
\[(\R, \leq) \adjto{\ceil{-}}{} (\Z, \leq) \adjto{}{\floor{-}} (\R, \leq)\]
\[\ceil{x} \leq_\Z n \equiv x \leq_\R n\]
\[n \leq_\R x \equiv n \leq_\Z \floor{x}\]
- \(\eta_x: x \leq_\R \ceil{x}\)
- \(\epsilon_n: \ceil{n} \leq_\Z n = \id_n\)
- \(\eta_n: n \leq_\Z \floor{n} = \id_n\)
- \(\epsilon_x: \floor{x} \leq_\R x\)
3.4.4 Maximum and minimum
\[\cOne \adjto{\min A}{} (A, \leq) \adjto{}{\max A} \cOne\]
- \(\eta_* = \id_*\)
- \(\epsilon_a: \min A \leq a\)
- \(\eta_a: a \leq \max A\)
- \(\epsilon_* = \id_*\)
\[(PA, \subseteq) \adjto{\max}{A_{\leq -}} (A, \leq) \adjto{A_{\geq -}}{\min} (PA, \supseteq)\]
\[\max A \leq b \equiv A \subseteq A_{\leq b}\]
\[A_{\geq a} \supseteq B \equiv a \leq \min B\]
- \(\eta_A: A \subseteq A_{\leq \max A}\)
- \(\epsilon_b: \max A_{\leq b} \leq b = \id_b\)
- \(\eta_a: a \leq \min A_{\geq a} = \id_a\)
- \(\epsilon_B: A_{\geq \min B} \supseteq B\)
\[(PA, \subseteq) \adjto{\min}{A_{\geq -}} (A, \geq) \adjto{A_{\leq -}}{\max} (PA, \supseteq)\]
\[\min A \geq b \equiv A \subseteq A_{\geq b}\]
\[A_{\leq a} \supseteq B \equiv a \geq \max B\]
- \(\eta_A: A \subseteq A_{\geq \min A}\)
- \(\epsilon_b: \min A_{\geq b} \geq b = \id_b\)
- \(\eta_a: a \geq \max A_{\leq a} = \id_a\)
- \(\epsilon_B: A_{\leq \max B} \supseteq B\)
3.5 Free-forgetful adjunction
\[\cC \adjto{F\text{ree}}{U\text{nderlying}} \cD\]
4 Kan
- \(F: \cA \to \cC\)
- \(G: \cA \to \cB\)
- \(H: \cB \to \cC\)
- \(\cC^G: \cC^\cB \to \cC^\cA\) precomposition
- \(H^\cA: \cB^\cA \to \cC^\cA\) postcomposition
- \(\Lan_G, \Ran_G: \cC^\cA \to \cC^\cB\) Kan extension
- \(\Lift_H, \Rift_H: \cC^\cA \to \cB^\cA\) Kan lift
4.1 Kan extension
- A right Kan extension of \(F\) through \(G\) is a universal morphism \((\Ran_G F: \cB \to \cC, \epsilon_F: \Ran_G F G \nat F)\) from \(\cC^G\) to \(F\).
- A left Kan extension of \(F\) through \(G\) is a universal morphism \((\Lan_G F: \cB \to \cC, \eta_F: F \nat \Lan_G F G)\) from \(F\) to \(\cC^G\).
\[\Lan_G \adj \cC^G \adj \Ran_G\]
4.2 Kan lift
- A right Kan lift of \(F\) through \(H\) is a universal morphism \((\Rift_H F: \cA \to \cB, \epsilon_F: H \Rift_H F \nat F)\) from \(H^\cA\) to \(F\).
- A left Kan lift of \(F\) through \(H\) is a universal morphism \((\Lift_H F: \cA \to \cB, \eta_F: F \nat H \Lift_H F)\) from \(F\) to \(H^\cA\).
\[\Lift_H \adj H^\cA \adj \Rift_H\]
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 \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}\]
\[\colim \adj \Delta \adj \lim\]
- A (finitely) (co)complete category has all (finite) (co)limits.
- A (finitely) bicomplete category is (finitely) complete and (finitely) cocomplete.
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} \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\)
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 (finitely) (co)continuous functor preserves all (finite) (co)limits.
\(\Hom(A, -)\) preserves limits
\[\Hom(A, B \times C) \iso \Hom(A, B) \times \Hom(A, C)\]
\(\Hom(-, C)\) sends colimits to limits
\[\Hom(A + B, C) \iso \Hom(A, C) \times \Hom(B, C)\]
\(F\) is a left adjoint functor \(\equiv\) \(F\) preserves colimits. \(G\) is a right adjoint functor \(\equiv\) \(G\) preserves limits.
6 Product & coproduct
A (co)product is the (co)limit of the 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.
finite products \(\equiv\) binary products and a terminal object
finite coproducts \(\equiv\) binary coproducts and an initial object
- A (finitely) (co)cartesian category has all (finite) (co)products.
- A (finitely) bicartesian category is (finitely) cartesian and (finitely) cocartesian.
6.1 Properties
6.1.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.
6.1.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}\]
6.1.3 Unitality
- 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\).
6.1.4 Associativity
\[\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}\]
6.1.5 Commutativity
\[\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}\]
6.1.6 Distributivity
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 distributive category is a category where all distributive morphisms are isomorphisms.
6.2 Tensor product
The category \(\cVect\) of vector spaces and linear maps has products, given by the direct product \(\times\) of vector spaces.
In the product \(U \times V\):
\[\begin{aligned} (u_1, v_1) + (u_2, v_2) &:= (u_1 + v_2, u_1 + v_2)\\ \lambda (u, v) &:= (\lambda u, \lambda v)\\ \end{aligned}\]
The tensor product of two vector spaces \(U\) and \(V\) is the initial object in the category of bilinear maps out of the product \(U \times V\).
In the tensor product \(U \otimes V\):
\[\begin{aligned} (u_1 + u_2) \otimes v &= u_1 \otimes v + u_2 \otimes v\\ u \otimes (v_1 + v_2) &= u \otimes v_1 + u \otimes v_2\\ \lambda (u \otimes v) &= \lambda u \otimes v = u \otimes \lambda v\\ \end{aligned}\]
The internal hom \([V, W]\) is the space of linear maps from \(V\) to \(W\).
\[\text{bilinear } U \times V \to W \iso \text{linear } U \otimes V \to W \iso \text{linear } U \to [V, W]\]
7 Equalizer & coequalizer
A (co)equalizer is the (co)limit of the free quiver \(\cdot \rightrightarrows \cdot\).
finite limits \(\equiv\) finite products and equalizers
\(\Eq(f, f) \iso A\), \(B \iso \Coeq(f, f)\).
7.1 Regular mono & epi
Regular monomorphism \(f: A \mono B\):
\[\exists g, h: B \to C. f: \Eq(g, h) \mono B\]
Regular epimorphism \(f: A \epi B\):
\[\exists g, h: C \to A. f: A \epi \Coeq(g, h)\]
7.2 Split mono & epi
Split monomorphism \(f: A \mono B\):
\[\exists r: B \to A. r \compL f = \id_A\]
\(r\) is a retraction of \(f\).
\(f: \Eq(f \compL r, \id_B) \mono B\).
Split epimorphism \(f: A \epi B\):
\[\exists s: B \to A. f \compL s = \id_B\]
\(s\) is a section of \(f\).
\(f: A \epi \Coeq(s \compL f, \id_A)\).
If \(f: A \to B\) is a split mono in a category \(\cC\) and has a retraction \(g\) (\(g \compL f = \id_A\)) but is not an iso (\(f \compL g \neq \id_B\)), then \((f, \id_B): f \to \id_B\) is a pointwise retraction in the arrow category \([\cTwo, \cC]\) but is not a natural retraction.
8 Pullback & pushout
A pullback is the limit of the cospan \(\cdot \rightarrow \cdot \leftarrow \cdot\), and a pushout is the colimit of the span \(\cdot \leftarrow \cdot \rightarrow \cdot\).
- Pullbacks \(\Pull(f: A \to C, g: B \to C)\) in \(\cC\) are products \(A \times_C B\) in \(\cC \comma C\).
- Pushouts \(\Push(f: C \to A, g: C \to B)\) in \(\cC\) are coproducts \(A +_C B\) in \(C \comma \cC\).
The fiber of a morphism \(f: A \to B\) over a global element \(b: 1 \to B\) is the pullback \(\Pull(f, b)\).
binary products and pullbacks \(\limp\) equalizers
finite limits \(\equiv\) pullbacks and a terminal object
8.1 Mono & epi
Monomorphism \(f: A \mono B\):
\[\forall g, h: C \to A. (f \compL g = f \compL h) \to (g = h)\]
\(\Pull(f, f) = A\).
Epimorphism \(f: A \epi B\):
\[\forall g, h: B \to C. (g \compL f = h \compL f) \to (g = h)\]
\(\Push(f, f) = B\).
Every iso is an epi and a mono, but not vice versa.
split mono/epi \(\limp\) regular mono/epi \(\limp\) mono/epi
8.2 Base change
A morphism \(f: A \to B\) induces a base change functor \(f^*: \cC \comma B \to \cC \comma A\) between slice categories:
\[\begin{aligned} \begin{array}{cccc} f^*: & \cC \comma B & \to & \cC \comma A \\ & C \xto{o} B & \mapsto & \Pull(f, o) \xto{o^*} A \\ & C_1 \xto{m} C_2 & \mapsto & \Pull(f, o_1) \xto{m^*} \Pull(f, o_2) \end{array} \end{aligned}\]
\[\id_A \times_B m: A \times_B C_1 \to A \times_B C_2\]
8.3 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.
8.4 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.
9 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\)
\[(-) \times A \adj (-)^A\]
\[\Hom(C \times A, B) \iso \Hom(C, B^A)\]
-- function application
($) :: (a -> b) -> a -> b
-- reverse function application
(&) :: a -> (a -> b) -> bA cartesian closed category has all finite products and exponentials.
In a cartesian closed category, the functor \((-) \times A\) is a left adjoint, which necessarily preserves all colimits, including all coproducts.
9.1 Composition
\[A \xto{f} B \xto{g} C \xto{h} D\]
9.1.1 Composition
\[\compL: C^B \times B^A \to C^A\]
-- function composition
(.) :: (b -> c) -> (a -> b) -> (a -> c)9.1.2 Postcomposition
\[h^B: C^B \to D^B := h \compL (-)\]
\[\begin{aligned} \begin{array}{cccc} (-)^B: & \cC & \to & \cC \\ & C & \mapsto & C^B \\ & C \xto{h} D & \mapsto & C^B \xto{h^B} D^B \end{array} \end{aligned}\]
9.1.3 Precomposition
\[C^f: C^B \to C^A := (-) \compL f\]
\[\begin{aligned} \begin{array}{cccc} C^{(-)}: & \cC\op & \to & \cC \\ & B & \mapsto & C^B \\ & B \xto{f\op} A & \mapsto & C^B \xto{C^f} C^A \end{array} \end{aligned}\]
9.2 Currying
9.2.1 Partial application
\[\partf: C^{A \times B} \times A \to C^B\]
9.2.2 Currying and uncurrying
\[\curry: C^{A \times B} \iso (C^B)^A :\curry\inv\]
\[\Hom(A \times B, C) \iso \Hom(A, C^B)\]
curry :: ((a, b) -> c) -> a -> b -> c
uncurry :: (a -> b -> c) -> (a, b) -> c 9.3 Product
9.3.1 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)\]
9.3.2 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)\]
9.4 Tarski’s high school algebra
Bicartesian closed category:
- \(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 \iso 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}\)
10 Examples
10.1 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}\) |
| mono | injective function |
| epi | surjective function |
| subobject | subset |
| subobject classifier | indicator function |
| power object | power set |
| exponential object | the set of functions and function evaluation |
10.2 Cat
| terminal object | \(\cOne\) |
| initial object | \(\cZero\) |
| product | product category \(\cC \times \cD\) |
| exponential object | functor category \([\cC, \cD]\) |
10.3 Poset
\((A, \leq)\)
| terminal object | greatest element / top \(\top\) |
| initial object | least element / bottom \(\bot\) |
| product | greatest lower bound / meet \(a \meet b\) |
| coproduct | least upper bound / join \(a \join b\) |
| equalizer | \(\id_a: a \leq a\) |
| coequalizer | \(\id_b: b \leq b\) |
| pullback | \(p_1: a \meet b \leq a\), \(p_2: a \meet b \leq b\) |
| pushout | \(i_1: a \leq a \join b\), \(i_2: a \leq a \join b\) |
| exponential object | \(a \ihom b := \bigjoin\set{c \mid c \lcon a \leq b}\) (\(c \lcon a \leq b \equiv c \leq a \ihom b\)) |
A bounded poset has a terminal object \(\top\) and/or an initial object \(\bot\).
- A meet-semilattice is a poset with all binary meets \(a \meet b\).
- A join-semilattice is a poset with all binary joins \(a \join b\).
- A lattice is a meet-semilattice and a join-semilattice.
- A bounded meet-semilattice is a finitely cartesian poset.
- A bounded join-semilattice is a finitely cocartesian poset.
- A bounded lattice is a finitely bicartesian poset.
Because all (co)equalizers exist in a poset, finitely (co)cartesian = finitely (co)complete in a poset.
- A Heyting algebra is a bounded closed lattice.
- A Boolean algebra is a Heyting algebra satisfying the law of excluded middle.
A Heyting algebra is finitely distributive because it is finitely bicartesian and closed.
- A inflattice is a cartesian poset.
- A suplattice is a cocartesian poset.
- A complete lattice is a bicartesian poset.
By the adjoint functor theorem for posets, all joins \(\equiv\) all meets, i.e., inflattice = suplattice = complete lattice.
A inflattice/suplattice homomorphism is a monotone preserving meets/joins.
10.3.1 \((\N, \leq)\)
| terminal object | \(-\) | |
| initial object | \(0\) | \(0 \leq a\) |
| product | \(\min\) | \(c \leq a, c \leq b \equiv c \leq \min(a, b)\) |
| coproduct | \(\max\) | \(a \leq c, b \leq c \equiv \max(a, b) \leq c\) |
| exponential object | \(-\) |
10.3.2 \((\N, \mid)\)
| terminal object | \(0\) | \(a \mid 0\) |
| initial object | \(1\) | \(1 \mid a\) |
| product | \(\gcd\) | \(c \mid a, c \mid b \equiv c \mid \gcd(a, b)\) |
| copoduct | \(\lcm\) | \(a \mid c, b \mid c \equiv \lcm(a, b) \mid c\) |
| exponential object | \(-\) |
10.3.3 \((\set{\lfal, \ltru}, \lfal \lproves \ltru)\)
| terminal object | \(\ltru\) | |
| initial object | \(\lfal\) | |
| product | \(\lcon\) | \(C \lproves A, C \lproves B \equiv C \lproves A \lcon B\) |
| copoduct | \(\ldis\) | \(A \lproves C, B \lproves C \equiv A \ldis B \lproves C\) |
| exponential object | \(\limp\) | \(C \lcon A \lproves B \equiv C \lproves (A \limp B)\) |
10.3.4 \(([0, \infty], \geq)\)
| terminal object | \(0\) | \(a \geq 0\) |
| initial object | \(\infty\) | \(\infty \geq a\) |
| product | \(\max\) | \(c \geq a, c \geq b \equiv c \geq \max(a, b)\) |
| copoduct | \(\min\) | \(a \geq c, b \geq c \equiv \min(a, b) \geq c\) |
| exponential object | \(\begin{cases}0 & a \geq b \\ b & \text{otherwise}\end{cases}\) | \(\max(c, a) \geq b \equiv c \geq \begin{cases}0 & a \geq b \\ b & \text{otherwise}\end{cases}\) |
10.4 Met
metric spaces \((A, d_A: A \times A \to [0, \infty])\) and metric maps \(d_A(a, a') \geq d_B(f(a), f(a'))\).
| terminal object | singleton \((\set{*}, d)\) |
| initial object | empty set \((\varnothing, d)\) |
| product | product metric \(d_{A \times B}((a, b), (a', b')) := \max(d_A(a, a'), d_B(b, b'))\) |
| coproduct | disjoint metric \(d_{A + B}(a, a') := d_A(a, a')\), \(d_{A + B}(b, b') := d_B(b, b')\), \(d_{A + B}(a, b) = d_{A + B}(b, a) := \infty\) |