\[ \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 \newcommand{\C}{\mathbb{C}} % complex 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{\cCMon}{\catf{CMon}} % commutative 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{\cMat}{\catf{Mat}} % matrices \newcommand{\cTop}{\catf{Top}} % topological spaces and continuous maps \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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % supscript %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\op}{^\mathrm{op}} \newcommand{\inv}{^{-1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % function %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\logsumexp}{log-sum-exp} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % arrow %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % morphism \newcommand{\xto}{\xrightarrow} % -> \newcommand{\xot}{\xleftarrow} % <- \newcommand{\toot}{\rightleftarrows} % <=> \newcommand{\xtoot}[2]{\xrightleftharpoons[#2]{#1}} \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{\compR}{\mathbin{;}} \newcommand{\Kl}{\mathrm{Kl}} \DeclareMathOperator{\Obj}{Obj} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\Sub}{Sub} \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} % |/= \]
1 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.
- \(\angles{f, g} \compL h = \angles{f \compL h, g \compL h}\)
- \(h \compL \bracks{f, g} = \bracks{h \compL f, h \compL g}\)
- A (finitely) (co)cartesian category has all (finite) (co)products.
- A (finitely) bicartesian category is (finitely) cartesian and (finitely) cocartesian.
finite products \(\equiv\) binary products and a terminal object
finite coproducts \(\equiv\) binary coproducts and an initial object
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.
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}\]
- \((f_1 \times f_2) \compL \Delta_A = \angles{f_1, f_2}\)
- \(\nabla_B \compL (f_1 + f_2) = \bracks{f_1, f_2}\)
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\).
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}\]
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}\]
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.
1.7 Tensor product
The product in the category \(\cVect\) of vector spaces and linear functions is 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}\]
A bilinear function \(m: U \times V \to W\) is a binary function that is linear in each argument:
\[m(u_1 + u_2, v) = m(u_1, v) + m(u_2, v)\]
\[m(u, v_1 + v_2) = m(u, v_1) + m(u, v_2)\]
\[m(\lambda u, v) = m(u, \lambda v) = \lambda m(u, v)\]
Examples: matrix multiplication, inner product
The tensor product of two vector spaces \(U\) and \(V\) is the initial object in the category of bilinear functions out of the product \(U \times V\).
\[\begin{aligned} \begin{array}{rccc} \alpha: & U \times V & \to & U \otimes V \\ & (u, v) & \mapsto & u \otimes v \end{array} \end{aligned}\]
In the tensor product \(U \otimes V\):
\[(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 = u \otimes \lambda v = \lambda (u \otimes v)\]
The tensor product of two linear functions \(f: U_1 \to U_2\) and \(g: V_1 \to V_2\) is the unique linear function \(f \otimes g: U_1 \otimes V_1 \to U_2 \otimes V_2\) such that
\[(f \otimes g)(u \otimes v) = f(u) \otimes g(v)\]
which makes \(\otimes: \cVect \times \cVect \to \cVect\) a bifunctor.
The tensor product of representations is the composition \(F_1 \otimes F_2: \cC \xto{\angles{F_1, F_2}} \cVect \times \cVect \xto{\otimes} \cVect\).
The internal hom \([V, W]\) in the category \(\cVect\) is the vector space of linear functions from \(V\) to \(W\):
\[(f + g)(x) := f(x) + g(x)\]
\[(\lambda f)(x) := \lambda f(x)\]
\[\text{bilinear } U \times V \to W \iso \text{linear } U \otimes V \to W \iso \text{linear } U \to [V, W]\]
2 Equalizer & coequalizer
A (co)equalizer is the (co)limit of the free quiver \(\cdot \rightrightarrows \cdot\).
finite products and equalizers \(\limp\) finite limits
\(\Eq(f, f) \iso A\), \(B \iso \Coeq(f, f)\).
2.1 Regular mono & epi
Regular monomorphism \(f: A \mono B\):
- \(\exists g, h: B \to C. f: \Eq(g, h) \to B\).
Regular epimorphism \(f: A \epi B\):
- \(\exists g, h: C \to A. f: A \to \Coeq(g, h)\).
2.2 Split mono & epi
Split monomorphism \(f: A \mono B\):
- \(\exists r: B \to A. r \compL f = \id_A\).
- \(\exists r: B \to A. f: \Eq(f \compL r, \id_B) \to B\).
- \(r\) is called a retraction of \(f\).
Split epimorphism \(f: A \epi B\):
- \(\exists s: B \to A. f \compL s = \id_B\).
- \(\exists s: B \to A. f: A \to \Coeq(s \compL f, \id_A)\).
- \(s\) is called a section of \(f\).
If \(f: A \to B\) is a split monomorphism in a category \(\cC\) and has a retraction \(g\) (\(g \compL f = \id_A\)) but is not an isomorphism (\(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.
3 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)\).
pullbacks and a terminal object \(\limp\) products: \(A \times_1 B \iso A \times B\)
pullbacks and products \(\limp\) equalizers: \(\Pull(\angles{f, g}, \Delta_B) \iso \Eq(f, g)\)
Pullbacks commute with products.
\[\Pull(f_1 \times f_2, g_1 \times g_2) \iso \Pull(f_1, g_1) \times \Pull(f_2, g_2)\]
This is a special case of limits commuting with limits, which is a result of the adjoint functor theorem.
For every pair of morphisms \(q_A: Q \to A\) and \(q_B: Q \to B\) such that \((f_1 \times f_2) \compL q_A = (g_1 \times g_2) \compL q_B\), we have \(f_1 \compL p_1 \compL q_A = g_1 \compL p_1 \compL q_B\) and \(f_2 \compL p_2 \compL q_A = g_2 \compL p_2 \compL q_B\), so there exist unique morphisms \(q_1: Q \to \Pull(f_1, g_1)\) and \(q_2: Q \to \Pull(f_2, g_2)\) such that \(q_A = \angles{{f_1}^*g_1 \compL q_1, {f_2}^*g_2 \compL q_2}\) and \(q_B = \angles{{g_1}^*f_1 \compL q_1, {g_2}^*f_2 \compL q_2}\). Therefore, \(\angles{q_1, q_2}: Q \to \Pull(f_1, g_1) \times \Pull(f_2, g_2)\) is the unique morphism such that \(q_A = \pi_1 \compL \angles{q_1, q_2}\) and \(q_B = \pi_2 \compL \angles{q_1, q_2}\), where \(\pi_1 = (f_1 \times f_2)^*(g_1 \times g_2) = {f_1}^*g_1 \times {f_2}^*g_2\) and \(\pi_2 = (g_1 \times g_2)^*(f_1 \times f_2) = {g_1}^*f_1 \times {g_2}^*f_2\).
3.1 Mono & epi
Monomorphism \(f: A \mono B\):
- \(\forall g, h: C \to A. (f \compL g = f \compL h) \to (g = h)\).
- Postcomposition \(f \compL (-)\) reflects equality.
- \(\Hom(C, f): \Hom(C, A) \to \Hom(C, B)\) is injective.
- \(\Pull(f, f) \iso A\).
Epimorphism \(f: A \epi B\):
- \(\forall g, h: B \to C. (g \compL f = h \compL f) \to (g = h)\).
- Precomposition \((-) \compL f\) reflects equality.
- \(\Hom(f, C): \Hom(B, C) \to \Hom(A, C)\) is injective.
- \(\Push(f, f) \iso B\).
Morphisms from a terminal object are monomorphisms; morphisms to an initial object are epimorphisms.
Pullbacks preserve monomorphisms.
\[(n \compL g_1 = n \compL g_2) \limp (f \compL n \compL g_1 = f \compL n \compL g_2) \limp (m \compL f' \compL g_1 = m \compL f' \compL g_2) \limp (f' \compL g_1 = f' \compL g_2)\]
split mono/epi \(\limp\) regular mono/epi \(\limp\) mono/epi
Every isomorphism is an epimorphism and a monomorphism, but not vice versa.
A category is balanced if every monic epic morphism is an isomorphism.