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$$.

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.

Hom-functor $$\Hom: \cC\op \times \cC \to \cSet$$ preserves limits in both arguments.

• $$\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)$

# 6 Limit & colimit examples

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 $$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 \circ (\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 \circ (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

For a fixed object $$A$$, let $$(-)^A: \cC \to \cC$$ be the endofunctor that assigns an object $$B$$ to the exponential object $$B^A$$.

$(-) \times A \adj (-)^A$

A category is cartesian closed if it has all finite products and exponentials.

The exponential objects of $$\cCat$$ are functor categories.

## 7.1 Composition

Precomposition:

$g^A: B^A \to C^A := g \circ (-)$

Postcomposition:

$A^f: C^B \to C^A := (-) \circ f$

Composition:

$\circ: C^B \times B^A \to C^A$

## 7.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$

## 7.3 Product

Product base:

$\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 exponent:

$\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)$

# 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 \\ \successor: && & 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 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$