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

  1. \(A + B \iso B + A\)
  2. \((A + B) + C \iso A + (B + C)\)
  3. \(A \times 1 \iso A\)
  4. \(A \times B \iso B \times A\)
  5. \((A \times B) \times C \iso A \times (B \times C)\)
  6. \(A \times B + A \times C \to A \times (B + C)\)
  7. \(1^A \iso 1\)
  8. \(A^1 \iso A\)
  9. \(A^{B + C} \iso A^B \times A^C\)
  10. \((A \times B)^C \iso A^C \times B^C\)
  11. \((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\).

  1. \((F \mu F, Fi)\) is an F-algebra, so there exists a unique F-algebra homomorphism \(u: \mu F \to F \mu F\).
  2. \(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}\).
  3. \(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\]