Patterns in Patterns: Duality, Universal Properties, and More

And the end of all our exploring
Will be to arrive where we started
And know the place for the first time.
— T. S. Eliot, Little Gidding

Accessibility

This is the second article in a series on category theory. Please read the first article if you haven’t.

In the previous article on category theory, we saw a wide number of similar constructions: sums, products, quotients, subobjects, initial and terminal objects, and so on. If you’re the type to notice these patterns, you’re probably the type to notice the patterns within these patterns: the conspicuous “co” prefix in front of coproduct and coequalizer, and that many of these constructions have shockingly similar diagrams, just with their arrows reversed:

Construction	Dual construction
Terminal object A unique morphism from each object.	Initial object A unique morphism to each object.
Monomorphism For \(m : A \to B\) and every pair \(f,g : T \to A\): \[m \circ f = m \circ g \quad \Longrightarrow \quad f = g.\] Cancel \(m\) on the left.	Epimorphism For \(e : A \to B\) and every pair \(f,g : B \to T\): \[f \circ e = g \circ e \quad \Longrightarrow \quad f = g.\] Cancel \(e\) on the right.
Product \(u\) is unique and makes the diagram commute.	Coproduct \(u\) is unique and makes the diagram commute.
Equalizer \(h\) factors uniquely.	Coequalizer \(h\) factors uniquely.

The arrow-reversing construction is called duality, and the unique-factorization conditions characterize our universal properties (unlike the cancellation conditions for monos and epis). Investigating these two properties requires us to dissect even more profound patterns visible across mathematics.

Duality

Duality is the observation that reversing all the arrows in every single category is itself a way of constructing a category, called the opposite category.

Definition (Opposite Category)

Let \(\mathsf{C}\) be a category. Its opposite category \(\mathsf{C}^\mathrm{op}\) has the same objects as \(\mathsf{C}\), a morphism \(f^\mathrm{op} : \mathAmber{B} \to \mathSky{A}\) for each morphism \(f : \mathSky{A} \to \mathAmber{B}\) of \(\mathsf{C}\), and composition \(f^\mathrm{op} \circ g^\mathrm{op} = (g \circ f)^\mathrm{op}\).

A morphism \(I \to A\) in \(\mathsf{C}\) is a morphism \(A \to I\) in \(\mathsf{C}^\mathrm{op}\), so an initial object of \(\mathsf{C}\) is a terminal object of \(\mathsf{C}^\mathrm{op}\), and vice versa. Any theorem that holds in every category holds in \(\mathsf{C}^\mathrm{op}\) in particular. This is the duality principle: reversing arrows in a categorical definition or theorem gives its dual, and reversing the arrows in a proof proves the dual theorem. For example, uniqueness of terminal objects follows from uniqueness of initial objects without a separate proof.

Example (Opposite Rings and Matrix Transpose)

For a ring \(R\), the opposite ring \(R^{\mathrm{op}}\) has the same elements and addition, but reverses multiplication: \(a \mathbin{\cdot_{\mathrm{op}}} b = ba\). For example, consider the ring \(M_n(k)\) of square matrices over some field \(k\):

\[(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T} = A^{\mathsf T} \mathbin{\cdot_{\mathrm{op}}} B^{\mathsf T}.\]

Thus \(A \mapsto A^{\mathsf T}\) is a ring isomorphism \(M_n(k) \to M_n(k)^{\mathrm{op}}\): transpose preserves addition and the identity, reverses multiplication, and is its own inverse.

If we let \(R\) act on some object \(\ast\), then we can view \(R\) itself as a category given by the following:

• \(\ast\) is the only object;
• The morphisms are the elements of \(R\) (all acting on \(\ast\));
• Multiplication is defined as composition of morphisms;
• \(1\) is given by \(\id_\ast\);
• Addition is some extra structure on top of the morphisms that multiplication distributes over.

Then the opposite category (provided the same addition is retained) is the opposite ring.

Of course, if \(R\) is commutative, its opposite ring is just \(R\) again. Note also that finding the opposite ring isn’t the same as finding an isomorphism to it; an arbitrary ring need not be isomorphic to its opposite.

Duality lets us reverse arrows to abstract out common themes in definitions, theorems, and proofs; it absolutely doesn’t mean that any particular category or its opposite are equivalent, or that dual constructions have any resemblance. \(\mathsf{Grp}\) is not the same as \(\mathsf{Grp}^\mathrm{op}\): even though the (direct) product \(G \times H\) and the sum (the free product) \(G \ast H\) are dual, they’re not isomorphic in general.

Functors

We require a bit of extra language before we define universal properties; fortunately, this concept is extremely useful in its own right.

Many constructions are really maps between entire categories. Taking the fundamental group of a space, the homology of a chain complex, or the underlying set of a group all turn objects of one category into objects of another; importantly, they also take morphisms \(f: A \to B\) in the domain category to morphisms in the codomain category \(F(f): F(A) \to F(B)\).

Definition (Functor)

Let \(\mathsf{C}\) and \(\mathsf{D}\) be categories. A functor \(F : \mathsf{C} \to \mathsf{D}\) assigns to each object \(\mathSky{A}\) of \(\mathsf{C}\) an object \(\mathSky{F(A)}\) of \(\mathsf{D}\), and to each morphism \(f : \mathSky{A} \to \mathAmber{B}\) a morphism \(F(f) : \mathSky{F(A)} \to \mathAmber{F(B)}\), such that \(F(\id_{\mathSky{A}}) = \id_{\mathSky{F(A)}}\) and \(F(g \circ f) = F(g) \circ F(f)\).

Functors must preserve isomorphisms: if \(f : A \to B\) has inverse \(g\), then \(F(g) \circ F(f) = F(g \circ f) = F(\id_A) = \id_{F(A)}\) (and similarly \(F(f)\circ F(g)=\mathrm{id}_{F(B)}\)) so \(F(f)\) is an isomorphism too.

Example (Cardinality of a Set)

You may have seen the definition of a function as a set: \(f: X \to Y\) is defined as \(f = \setbuild{(x, y) \in X \times Y}{f(x) = y}\) containing exactly one pair \((x, y)\) for each \(x \in X\). Frustratingly, this definition would exclude the perfectly well-defined cardinality map

\[X \mapsto \lvert X \rvert\]

because there’s no set of all sets to use as the domain.¹ Of course, if we consider the category \(\mathsf{Set}_{\mathrm{inj}}\) of sets with injective functions as the morphisms and the category \(\mathsf{Card}_\leq\) of cardinals with ordering as the morphisms, we obtain a perfectly valid functor

\[\lvert \cdot \rvert : \mathsf{Set}_{\mathrm{inj}} \to \mathsf{Card}_\leq\]

Not only is each set sent to its cardinality, our functor also captures that an injection \(f: X \to Y\) means \(\lvert X \rvert \leq \lvert Y \rvert\) because \(f\) gets mapped to that specific inequality between the cardinalities of \(X\) and \(Y\).

Restricting our attention to only finite sets in the domain, we get \(\N\) in the codomain:

\[\lvert \cdot \rvert: \mathsf{FinSet}_{\mathrm{inj}} \to (\N, \leq)\]

Example (The Derivative)

When I first learned calculus, I felt that there was something “special” about the chain rule. Category theory tells us why.

Let \(\mathsf{Euclid}_\ast\) be the category whose objects are pointed open sets \((O, x_0)\) with \(x_0 \in O \subseteq \R^n\) for every nonnegative integer \(n\), and the morphisms are differentiable maps \(f: (U, a) \to (V, b)\) satisfying \(f(a) = b\).

Let \(\mathsf{Mat}_\R\) be the category whose objects are nonnegative integers (representing dimensions) and whose morphisms \(n \to m\) are real \(m \times n\) matrices. Composition is matrix multiplication, and the identity morphism on \(n\) is the identity matrix \(I_n\).

The derivative map \(D: \mathsf{Euclid}_\ast \to \mathsf{Mat}_\R\) is a functor:

• It sends each object \((O \subseteq \R^n, x_0)\) in \(\mathsf{Euclid}_\ast\) to its dimension \(n\) in \(\mathsf{Mat}_\R\).
• It sends each arrow \(f: (U \subseteq \R^n, a) \to (V \subseteq \R^m, b)\) in \(\mathsf{Euclid}_\ast\) to its Jacobian matrix \(Df_a\) evaluated at the basepoint \(a\) in \(\mathsf{Mat}_\R\). Since the Jacobian is an \(m \times n\) matrix, it represents a morphism \(n \to m\) in \(\mathsf{Mat}_\R\).
  • In particular, it sends identities to identities: the derivative of the identity map is the identity matrix.

  • It also sends \(g \circ f\) in \(\mathsf{Euclid}_\ast\) to \(D(g) \circ D(f)\) in \(\mathsf{Mat}_\R\) by grace of the chain rule: the chain rule tells us for morphisms \(f: (U, a) \to (V, b)\) and \(g: (V, b) \to (W, c)\), that

    \[D(g \circ f)_a = Dg_b \, Df_a,\]

    where \(b=f(a)\). The right-hand side is precisely composition in \(\mathsf{Mat}_\R\), so differentiation preserves composition as well as identities.

The necessary step for proving functoriality is the chain rule: differentiating a composite gives the same result as composing the derivatives.

Example (Expected Value)

For a “set of outcomes” (probability space) \(\Omega\), the set of random variables \(X\) with expected values \(\E[\lvert X \rvert] < \infty\) is denoted \(L^1(\Omega)\).² The real numbers under addition are denoted \((\R, +)\). We can consider both of these additive groups as categories with only a single object:

• \(\mathsf{B}(L^1(\Omega), +)\)’s arrows are the random variables. Because there’s only a single object in this category (which we don’t care about at all), all arrows can be composed with each other, and composition \(X \circ Y\) is interpreted as addition \(X + Y\). The identity morphism on our anonymous object is just the deterministic random variable \(0_{\Omega}\) that always equals \(0\), and has expected value \(0\).
• \(\mathsf{B}(\R, +)\)’s arrows are real numbers. Again, because there’s only one object in this category, all arrows compose and we can define \(r_1 \circ r_2 = r_1 + r_2\). The identity morphism on the anonymous object is just \(0\).

Then expected value \(\E\) is a functor \(\E : \mathsf{B}(L^1(\Omega), +) \to \mathsf{B}(\R, +)\) with

\[\E[X + Y] = \E[X] + \E[Y] \quad \E[0_{\Omega}] = 0\]

and sends the anonymous object in \(\mathsf{B}(L^1(\Omega), +)\) to the anonymous object in \(\mathsf{B}(\R, +)\). (We’ll discuss one-object categories and this mysterious \(\mathsf{B}\) symbol in a later article.)

Example (The Fundamental Group)

Let \(\mathsf{Top_\ast}\) be the category of pointed topological spaces: tuples \((X, x_0)\) of a topological space \(X\) and some point \(x_0\) in that space, and basepoint-preserving continuous maps as morphisms. The fundamental group defines a functor \(\pi_1: \mathsf{Top_\ast} \to \mathsf{Grp}\) sending \((X, x_0) \mapsto \pi_1(X, x_0)\) and mapping each continuous map \(f\) to the induced homomorphism \([ \gamma ] \mapsto [ f \circ \gamma ]\).

(For every positive integer \(n\), \(\pi_n\) is a functor. For \(n \geq 2\), these groups are all abelian, so we can use the category \(\mathsf{Ab}\) of abelian groups as the codomain.)

Example (Homology)

Let \(X\) be a topological space.

Basics of Homology

When \(X\) has a structure like a simplicial complex or a CW complex, we can use it to organize \(n\)-dimensional topological data about \(X\) (for each nonnegative integer \(n\)) into an abelian group \(C_n(X)\) called the \(n\)th chain group of \(X\). Each chain group is just raw data: “algebra soup” of all the \(n\)-dimensional topological data about \(X\). As such, they’re not very useful on their own.

But \(n\)-dimensional shapes have \((n-1)\)-dimensional boundaries, so we can define the boundary maps \(\partial_n: C_n(X) \to C_{n-1}(X)\), which are group homomorphisms connecting the \(n\)th chain group to the \((n-1)\)th chain group. The chain groups together with the boundary maps give us a sequence \(C_\ast(X)\) called a chain complex of \(X\):

The boundary maps satisfy \(\partial_n \circ \partial_{n+1} = 0\): intuitively speaking, a boundary has no boundary of its own, so applying two consecutive boundary maps gives us \(0\) (the identity). This tells us that the group of boundaries \(\im \partial_{n+1}\) in \(C_n\) is a subgroup of the group of cycles \(\ker \partial_n\) in \(C_n\); because they’re both abelian, we can take the quotient \(\ker \partial_n / \im \partial_{n+1}\):

This quotient \(H_n(X)\) is called the \(n\)th homology group of \(X\), and refines the chain complex’s algebra soup down to something much more informative:

These homology groups form a graded collection, with one group for each degree \(n\), denoted by \(H_\ast(X)\):

\[H_\ast(X)=\bigl\{(n,H_n(X))\mid n\geq0\bigr\}\]

\(H_\ast(X)\) is remarkably useful because it’s an algebraic invariant: if we have a continuous map \(f: X \to Y\) between topological spaces \(X\) and \(Y\), we obtain homomorphisms \(f_n: H_n(X) \to H_n(Y)\) for all \(n\). If \(f\) is a homeomorphism, then each \(f_n\) is an isomorphism. By contraposition, if two spaces \(X\) and \(Y\) have non-isomorphic homology groups \(H_n(X) \not \cong H_n(Y)\) for even a single \(n\), then \(X\) and \(Y\) cannot be homeomorphic. This is just one of many applications of homology.

For each nonnegative integer \(n\), homology defines a functor \(H_n: \mathsf{Top} \to \mathsf{Ab}\):

• Sending a topological space \(X\) to its \(n\)th homology group \(H_n(X)\).

• Preserving arrows in \(\mathsf{Top}\): a continuous map between topological spaces \(f: X \to Y\) induces a homomorphism \(f_\ast: H_n(X) \to H_n(Y)\) in \(\mathsf{Ab}\) between each space’s \(n\)th homology group. This assignment of induced homomorphisms preserves identities and composition:

  \[(\id_X)_\ast = \id_{H_n(X)} \quad \text{and} \quad (g \circ f)_\ast = g_\ast \circ f_\ast\]

Example (Forgetful Functors)

“Forgetful functor” is an informal name for a functor that “forgets” some structure on objects in its domain category. Consider the following examples:

• The functor \(\mathsf{Ring} \to \mathsf{Grp}\) that “forgets” the multiplication operation on the ring.
• The constant functor \(S: \mathsf{Vec}_k \to \mathsf{Field}\) that forgets the abelian group of vectors and sends all vector spaces to the underlying field \(k\) and every morphism to \(\id_k\), and the functor \(\mathsf{Vec}_k \to \mathsf{Ab}\) that forgets the field of scalars and sends every vector space to its abelian group of vectors.
• The functor \(\mathsf{Met} \to \mathsf{Top}\) that sends a metric space (with continuous maps as morphisms) to its underlying topological space.
• The functors that send each of the objects in the “sets with structure” categories (called concrete categories) to their underlying sets in \(\mathsf{Set}\).

Concrete Categories

Concrete categories are something we can define very intuitively: they’re any categories where we can define a forgetful functor to \(\mathsf{Set}\). “Forgetful” is just a loose intuitive term, but concreteness shouldn’t be. Let’s find a more rigorous definition than “forgetful” for this context so we can pin down a rigorous definition of concrete as well.

All that we really require from our forgetful functor is that it send the objects to their underlying sets, and their morphisms to the underlying functions. You may recall that we can have many topologies on the same set: the discrete topology on \(\R\) and the open-ball topology on \(\R\) should both be sent to the same object in \(\mathsf{Set}\), despite being different objects in \(\mathsf{Top}\). Similarly, the Klein-4 group \(V_4 \cong C_2 \times C_2\) and the cyclic group on four elements \(C_4\) can share the same underlying set, despite having different morphisms going in and out. Our definition should allow these collisions.

But allowing objects to share an underlying set shouldn’t mean that we lose the distinction between morphisms \(f, g: A \to B\). In our examples, these morphisms are functions preserving some structure: if they’re genuinely different morphisms, their underlying functions must be different. We want a definition that forbids these kinds of collisions:

This property is called faithfulness:

Definition (Faithful Functor)

A functor \(F\) is faithful if, for any objects \(\mathSky{A}\) and \(\mathAmber{B}\), distinct morphisms \(f, g: \mathSky{A} \to \mathAmber{B}\) have distinct images \(F(f) \neq F(g)\).

Morphisms belonging to different source-target pairs may still have the same image if \(F\) identifies their domains and codomains.

This is exactly the definition we needed to finish our definition for concrete categories:

Definition (Concrete Category)

We call a category concrete if it admits a faithful functor to \(\mathsf{Set}\).

Functors and Duality

Here’s one more particularly motivating example:

Example (Duality)

• Reversing arrows is a functor \((\cdot)^\mathrm{op} : \mathsf{Cat} \to \mathsf{Cat}\), sending \(F : \mathsf{C} \to \mathsf{D}\) to \(F^\mathrm{op} : \mathsf{C}^\mathrm{op} \to \mathsf{D}^\mathrm{op}\). In fact, every one of the above examples in the duality section constitutes a functor.

Not only are all those examples in the duality section functors, they’re all functors that reverse arrows. These are given a fancy name:

Definition (Contravariant Functor)

A contravariant functor \(F: \mathsf{C} \to \mathsf{D}\) is just an ordinary functor \(\mathsf{C}^\mathrm{op} \to \mathsf{D}\):

Covariant functor	Contravariant functor
\[F(g \circ f) = F(g) \circ F(f)\]	\[F(g \circ f) = F(f) \circ F(g)\]

Note the different directions of the arrows in \(\mathsf{D}\); this describes functors like the Galois correspondence reversing inclusions and cohomology reversing maps of spaces.

Mathematics is full of contravariant functors:

Example (Dual Vector Spaces)

Recall that if \(V\) is an \(n\)-dimensional \(k\)-vector space, its dual space \(V^\ast\) is the set of all linear transformations \(V \to k\). Of course, this is just a collection of \(1 \times n\) matrices. It should be obvious that this vector space \(V^\ast\) is isomorphic to \(V\): each vector in \(V^\ast\) is just the transpose of a vector in \(V\). (However, this map requires us to choose a basis for \(V\).)

Importantly, the map sending \(V \mapsto V^\ast\) also sends a linear map \(T : V \to W\) to its transpose \(T^\ast : W^\ast \to V^\ast\), which goes the other way. This transpose turns injective linear maps into surjective ones, so subspaces of \(V\) become quotients of \(V^\ast\).

Example (The Galois Correspondence)

The fundamental theorem of Galois theory establishes an inclusion-reversing isomorphism: for a finite Galois extension \(L/K\), the correspondence can be expressed compactly as

\[\begin{aligned} \mathsf{Int}(L/K) &\cong \mathsf{Sub}(\Gal(L/K))^{\mathrm{op}}, \\ E &\longmapsto \Gal(L/E). \end{aligned}\]

Here \(\mathsf{Int}(L/K)\) is the poset of intermediate fields and \(\mathsf{Sub}(\Gal(L/K))\) is the poset of subgroups, both ordered by inclusion and viewed as categories.

Take \(L=\Q(\sqrt2,\sqrt3)\) and \(K=\Q\). Its Galois group is \(G=\langle\sigma,\tau\rangle\cong C_2\times C_2\), where \(\sigma\) changes the sign of \(\sqrt2\) and fixes \(\sqrt3\), while \(\tau\) changes the sign of \(\sqrt3\) and fixes \(\sqrt2\).

Intermediate fields \(E\)	Fixing subgroups \(\Gal(L/E)\)

Note the directions of the arrows, each of which represents an inclusion. They point upward in the category of fields, and downward in the subgroup poset, because a larger field leaves fewer automorphisms that fix it pointwise.

Example (Cohomology)

Basics of Cohomology

Consider the map \(D=\Hom(-,\Z)\) that sends chain groups in a chain complex to cochain groups \(C^n(X)=\Hom(C_n(X),\Z)\) and reverses the arrows, producing the cochain complex \(C^\ast(X)\):

Just as the chain complex yields homology groups \(H_n(X)\), the cochain complex yields cohomology groups \(H^n(X)\), by taking cocycles modulo coboundaries:

A continuous map \(f: X\to Y\) induces a reversed homomorphism in the cohomology groups:

\[\begin{aligned} \text{homology:}\quad &f_\ast:H_n(X)\longrightarrow H_n(Y),\\ \text{cohomology:}\quad &f^\ast:H^n(Y)\longrightarrow H^n(X). \end{aligned}\]

Thus cohomology is a contravariant functor on spaces, or equivalently a functor \(H^n:\mathsf{Top}^{\mathrm{op}}\to\mathsf{Ab}\). I’m eliding a lot of the details; the point is that cohomology really is a dual construction.

The contravariant functor \(D=\Hom(-,\Z)\) on abelian groups extends degree by degree to chain complexes, and this construction leads to contravariant cohomology functors on topological spaces.

• For abelian groups:

  • Objects: \(D\) sends an abelian group \(A\) to the abelian group \(\Hom(A,\Z)\) of homomorphisms to \(\Z\), with addition defined pointwise.

  • Arrows: A homomorphism \(f:A\to B\) induces a homomorphism in the opposite direction by precomposition:

    \[\begin{aligned} D(f):\Hom(B,\Z)&\longrightarrow\Hom(A,\Z),\\ \varphi&\longmapsto\varphi\circ f. \end{aligned}\]

    Precomposing with an identity changes nothing, and for \(f:A\to B\) and \(g:B\to C\),

    \[D(g\circ f)(\varphi)=\varphi\circ g\circ f=D(f)\bigl(D(g)(\varphi)\bigr).\]

    Thus \(D(g\circ f)=D(f)\circ D(g)\): composition is reversed, exactly as required for a contravariant functor.

• For chain complexes: Applying \(D\) reverses the boundary maps to give the coboundary maps \(\delta^n=D(\partial_{n+1})\) and the resulting cochain complex \(C^\ast(X)\):

  Applying \(D\) degree by degree also reverses chain maps between complexes, producing cochain maps in the opposite direction. Identities and reversed composition hold degree by degree, so this construction is contravariant too.

• For topological spaces: If we have a continuous map \(f: X \to Y\), homology preserves the direction of the induced maps, while cohomology reverses it. Here \(H_\ast\) and \(H^\ast\) collect all degrees:

Universal Properties

The constructions we’ve now seen (equalizers, products, sums, quotients) were defined the same way: among all the candidates for some job, pick the one that makes the diagram commute and has exactly one morphism to (or from) every other candidate. A definition of this shape is called a universal property, which specifies an object, together with its structure maps, as an initial or terminal object in a category of candidates whose morphisms preserve that structure. More formally,

Definition (Universal Property)

Let \(F : \mathsf{D} \to \mathsf{C}\) be a functor and \(\mathSky{A}\) an object of \(\mathsf{C}\). A universal morphism from \(\mathSky{A}\) to \(F\) is a pair \((\mathRose{U}, \eta)\), where \(\mathRose{U}\) is an object of \(\mathsf{D}\) and \(\eta : \mathSky{A} \to \mathRose{F(U)}\), such that for every object \(\mathIndigo{T}\) of \(\mathsf{D}\) and every morphism \(f : \mathSky{A} \to \mathIndigo{F(T)}\), there exists a unique morphism \(u : \mathRose{U} \to \mathIndigo{T}\) satisfying

\[F(u) \circ \eta = f.\]

Equivalently, the following diagram in \(\mathsf{C}\) commutes:

What Is the Category of Candidates?

Here the candidates are pairs \((T, f)\), and a morphism from \((U, \eta)\) to \((T, f)\) is precisely a map \(u\) satisfying this equation; thus \((U, \eta)\) is initial in the category of candidates. The dashed arrow indicates the factorization induced by the unique \(u\) in \(\mathsf{D}\).

Reversing the arrows, a universal morphism from \(F\) to \(A\) is a pair \((U, \varepsilon)\) with \(\varepsilon : F(U) \to A\) such that every \(f : F(T) \to A\) factors uniquely as \(f = \varepsilon \circ F(u)\) for a morphism \(u : T \to U\). This makes \((U, \varepsilon)\) terminal in the corresponding category of candidates.

You can see this commuting diagram in every one of our object constructions, alongside many familiar constructs from algebra and topology:

Example (Abelianization in \(\mathsf{Grp}\))

For any group \(G\), its abelianization is the quotient \(G^{\mathrm{ab}} = G / [G, G]\) by the subgroup \([G, G]\) generated by all commutators \(ghg^{-1}h^{-1}\).

Letting \(q : G \to G^{\mathrm{ab}}\) be the quotient map, every homomorphism \(f\) from \(G\) to an abelian group \(A\) factors through a unique homomorphism \(\bar f : G^{\mathrm{ab}} \to A\):

with \(\bar f \circ q = f, \qquad \bar f(g[G,G]) = f(g)\).

Proof

Since \(A\) is abelian, \(f\) sends every commutator to the identity, so the formula is well defined. The resulting map is a homomorphism because \(f\) is. Since \(q\) is surjective, it leaves no choice for \(\bar f\). Thus abelianization is universal among homomorphisms from \(G\) to abelian groups.

In the formal definition, take the inclusion functor \(F : \mathsf{Ab} \to \mathsf{Grp}\), with \(G\) as the source object and \(\eta=q\).

For example, the abelianization of the symmetric group on three elements \(S_3\) is the cyclic group with two elements \(C_2\), with \(q\) given by the sign map \(\operatorname{sgn}\):

\[\operatorname{sgn}(\sigma)= \begin{cases} +1 & \text{if }\sigma\text{ is even},\\ -1 & \text{if }\sigma\text{ is odd}. \end{cases}\]

A permutation is even or odd according to whether it can be expressed as an even or odd number of swaps. Every homomorphism from \(S_3\) to any abelian group factors uniquely through \(\operatorname{sgn}\).

Example (Polynomial Evaluation Maps in \(\mathsf{Ring}\))

Recall that a unital homomorphism is a ring homomorphism \(\varphi: R_1 \to R_2\) sending \(1_{R_1} \mapsto 1_{R_2}\).

Let \(R\) and \(A\) be commutative rings, let \(\varphi: R \to A\) be a ring homomorphism, and recall that \(R[x]\) is the ring of all single-variable polynomials in \(x\) with coefficients in \(R\).

For every \(a \in A\), there exists a unique homomorphism \(\widetilde\varphi_a : R[x] \to A\) that extends \(\varphi\) and sends \(x\) to \(a\), called the polynomial evaluation map:

\[\widetilde\varphi_a\left(\underbrace{\sum_{i=0}^n r_i x^i}_{p(x) \in R[x]}\right) = \underbrace{\sum_{i=0}^n \varphi(r_i)a^i}_{\varphi(p)(a) \in A}\]

This map just takes a polynomial \(p(x)\), sends all its coefficients through the homomorphism \(\varphi\) to \(A\) to get a polynomial \(\varphi(p)(x)\) in \(A[x]\), then “plugs in” the value \(a \in A\) to get \(\varphi(p)(a)\) which is just a member of \(A\).

Writing \(\varphi[x]:R[x]\to A[x]\) for the map on coefficients and \(\operatorname{ev}_a:A[x]\to A\) for evaluation at \(a\), we obtain the factorization:

Thus \(\widetilde\varphi_a=\operatorname{ev}_a\circ\varphi[x]\). The uniqueness of this homomorphism once its values on the coefficients and on \(x\) are prescribed is a universal property.

Writing \(\iota:R\to R[x]\) for the inclusion of constant polynomials, this universal property has the following commuting triangle, with the additional requirement \(\widetilde\varphi_a(x)=a\):

One interesting example is the unique ring homomorphism \(\R[x] \to \C\) that fixes every real constant and sends \(x \mapsto i\). This homomorphism is a polynomial evaluation map, sending \(p \mapsto p(i)\). Its kernel is the ideal \((x^2 + 1)\); you might recognize its generating polynomial \(x^2 + 1\) as the monic polynomial of least degree with roots \(i\) and \(-i\). This is one way to define the complex numbers: as equivalence classes of real polynomials, where two polynomials are identified when their difference is a multiple of \(x^2+1\).

Example (Gluing the Ends of an Interval in \(\mathsf{Top}\))

The circle is the quotient of \([0,1]\) obtained by identifying its endpoints, thus “gluing them together”.

Let \(q : [0,1] \to S^1\) be \(q(t) = e^{2\pi i t}\). For every space \(Y\) and continuous map \(f : [0,1] \to Y\) satisfying \(f(0) = f(1)\), there is a unique continuous map \(\bar f : S^1 \to Y\) such that

\[\bar f \circ q = f, \qquad \bar f(e^{2\pi i t}) = f(t).\]

To prove that every such \(f\) factors uniquely through \(q\), we need to show that \(\bar f\) exists, is continuous, and is the only map satisfying \(\bar f\circ q=f\).

Proof

• Existence: Every point of \(S^1\) is \(q(t)\) for some \(t\in[0,1]\), so define \(\bar f(q(t))=f(t)\). The only distinct inputs that \(q\) identifies are \(0\) and \(1\). Since \(f(0)=f(1)\), both choices give the same value, so this defines a function on the circle. By construction, \(\bar f\circ q=f\): this is the required factorization.

• Continuity: In the quotient topology, a subset \(U\subseteq S^1\) is open exactly when \(q^{-1}(U)\) is open in \([0,1]\). For any open subset \(V\subseteq Y\),

  \[q^{-1}\bigl(\bar f^{-1}(V)\bigr)=f^{-1}(V).\]

  The right-hand side is open because \(f\) is continuous, so \(\bar f^{-1}(V)\) is open in the circle. Thus \(\bar f\) is continuous.

• Uniqueness: Suppose another map \(h:S^1\to Y\) satisfies \(h\circ q=f\). Then

  \[h(q(t))=f(t)=\bar f(q(t))\]

  for every \(t\in[0,1]\). Since \(q\) reaches every point of the circle, \(h\) and \(\bar f\) agree everywhere.

Thus a continuous map out of the circle is precisely a continuous path whose endpoints agree.

We’ve also seen that any two initial objects have a unique isomorphism between them (dually, the same is true for terminal objects). An object with specified structure maps satisfying a universal property is therefore unique (up to a unique isomorphism preserving those maps). That’s what justifies saying “the product” or “the quotient”, even though each is only defined up to isomorphism.

Categories Themselves

Enough about you. Let’s talk about me. — Anonymous

One question has been screaming out from our definition of categories: can categories refer to themselves? With all the effort put into defining categories so they can cover almost any collection of similar mathematical objects, we’d hope that they’d be able to talk about themselves. Naturally, they can.

Categories of Categories

I don’t want to belong to any club that will accept me as a member.
— Groucho Marx

Functors can be composed (apply one, then the other), and every category has an identity functor, so categories and functors form a category of their own. Most of the categories we’ve seen fit into the category \(\mathsf{CAT}_{\mathrm{ls}}\) of locally small categories:

Definition (Small and Locally Small)

A category is small if its objects and morphisms each form a set, and locally small if each \(\Hom(\mathSky{A}, \mathAmber{B})\) is a set.

When using universes, “set” here means a set belonging to our chosen small universe.

\(\mathsf{Set}\) isn’t small since there’s no set of all sets, but it is locally small, as are \(\mathsf{Grp}\), \(\mathsf{Top}\), and nearly every other category in our tables.

We can now distinguish a few categories of categories:

• \(\mathsf{Cat}\) has small categories as objects and functors as morphisms. It is large but locally small: the functors between any two small categories form a set. Since \(\mathsf{Cat}\) itself is not small, it is not one of its own objects.
• \(\mathsf{CAT}_{\mathrm{ls}}\) has locally small categories within our chosen size bounds as objects and functors as morphisms. It contains \(\mathsf{Cat}\), \(\mathsf{Set}\), \(\mathsf{Grp}\), \(\mathsf{Top}\), and nearly every other category in our tables. It is not itself locally small: functors \(\mathbf{1} \to \mathsf{Set}\) correspond to sets, and these do not form a small set.
• \(\mathsf{CAT}\) allows categories within the size bounds of whatever Grothendieck universe we’ve chosen, and can contain \(\mathsf{CAT}_{\mathrm{ls}}\) as an object if we choose a large enough universe. It is, again, not a member of itself.³

Most categories encountered in ordinary mathematics are locally small and thus fit inside \(\mathsf{CAT}_{\mathrm{ls}}\). The only exceptions I’m aware of are (obviously) constructions involving categories of categories which can require more careful size bounds, categories of functors, and presheaves (whatever those are) on large categories. This series will mostly stay inside \(\mathsf{CAT}_{\mathrm{ls}}\).

Anyways, for any “category of categories” \(\mathsf{C}\), the empty category is initial and the category \(\mathbf{1}\) with one object and one morphism is terminal. (Provided of course that \(\mathsf{C}\) actually includes those categories, and allows the arrows required for them to be initial and terminal.)

A Category of All Categories?

The small/large distinction reflects our choice of foundations; unfortunately, typical formulations of ZF impose size limitations that do not allow for a category of all categories including itself.

Of course, we could consider the one object \(c\) in the category \(\mathbf{1}\) with only one morphism \(\id_c\) to be a representation of \(\mathbf{1}\) itself; but if this category is talking about itself, it says nothing interesting. The point is that no “category of categories” can describe the interplay between itself and all other categories even just in its own universe.

In alternative set theories such as New Foundations with Urelements (NFU), we can construct a category that includes all categories including itself.

The tradeoff is that the equivalent category to ZFC’s \(\mathsf{Set}\), which I’ll call \(\mathsf{Set_{NFU}}\), does not have the nice property of being cartesian closed, whereas ZFC’s \(\mathsf{Set}\) is. We’ll use the conventional small/large framework here, but an unrestricted category of categories is a serious subject of study, known as unlimited category theory.

Subcategories

Definition (Subcategory)

A subcategory selects some objects and morphisms of a category, retaining the identity of every selected object and keeping the selected morphisms closed under composition. It uses the same identities and composition as the containing category.

Definition (Full Subcategory)

A subcategory is full if it retains every morphism between its selected objects.

For example, \(\mathsf{Field}\) is a full subcategory of \(\mathsf{Ring}\). \(\mathsf{Ell}_k\) is a subcategory of \(\mathsf{AbVar}_k\), but not a full one: it retains only isogenies between elliptic curves, excluding zero homomorphisms. The lack of sums, products, initial objects, terminal objects, etc. in categories without them is often fixed by moving to a larger category, like \(\mathsf{Ring}\) and \(\mathsf{AbVar}_k\), which have all of the above.

Definition (Equalizer of Functors)

Given functors \(F,G : \mathsf{C} \to \mathsf{D}\), their equalizer is the subcategory of \(\mathsf{C}\) consisting of objects \(A\) with \(F(A) = G(A)\) and morphisms \(f\) between those objects with \(F(f)=G(f)\). These are literal equalities, not merely isomorphisms. Any functor \(H : \mathsf{T} \to \mathsf{C}\) satisfying \(F \circ H=G \circ H\) lands in this subcategory and factors uniquely through its inclusion.

Constructing Categories

Definition (Product Category)

For categories \(\mathsf{C}\) and \(\mathsf{D}\), the product category \(\mathsf{C} \times \mathsf{D}\) has pairs \((A, B)\) as objects and pairs of morphisms \((f, g) : (A, B) \to (A^\prime, B^\prime)\) as morphisms, composed one coordinate at a time, with identity morphisms \((\id_A, \id_B)\).

It comes with projection functors to \(\mathsf{C}\) and \(\mathsf{D}\), and it’s exactly the product in \(\mathsf{CAT}\) (and in \(\mathsf{Cat}\) when the factors are small): a functor \(\mathsf{T} \to \mathsf{C} \times \mathsf{D}\) is the same thing as a pair of functors from \(\mathsf{T}\), one into \(\mathsf{C}\) and one into \(\mathsf{D}\).

Definition (Disjoint Union of Categories)

For categories \(\mathsf{C}\) and \(\mathsf{D}\), their disjoint union \(\mathsf{C} \amalg \mathsf{D}\) keeps separate copies of each category’s objects and morphisms, with no arrows between the two components. Identities and composition are inherited from each category.

A functor \(\mathsf{C} \amalg \mathsf{D} \to \mathsf{T}\) is uniquely determined by a pair of functors \(\mathsf{C} \to \mathsf{T}\) and \(\mathsf{D} \to \mathsf{T}\), so this is the coproduct in \(\mathsf{CAT}\), and in \(\mathsf{Cat}\) when the two categories are small.

Definition (Coequalizer of Functors)

Given functors \(F,G : \mathsf{C} \to \mathsf{D}\) between categories, their coequalizer constructs a quotient category: it is a functor \(Q : \mathsf{D} \to \mathsf{E}\) that identifies \(F(A)\) with \(G(A)\) and \(F(f)\) with \(G(f)\) for every object \(A\) and morphism \(f\) of \(\mathsf{C}\). Identifying objects can make new pairs of arrows composable, so we also include the necessary composites and impose the category laws and the composition relations already present in \(\mathsf{D}\).

The result satisfies the familiar universal property: every functor \(H : \mathsf{D} \to \mathsf{T}\) with \(H \circ F=H \circ G\) factors uniquely through \(Q\).

These constructions satisfy the universal properties we studied last time. The question is whether the resulting category is still an object of the category of categories we’re working in:

Construction	\(\mathsf{Cat}\)	\(\mathsf{CAT}_{\mathrm{ls}}\)	\(\mathsf{CAT}\)
Product	Yes	Yes	Yes
Disjoint union (coproduct)	Yes	Yes	Yes
Equalizer	Yes	Yes	Yes
Coequalizer	Yes	Not in general	Yes

Each column assumes its ingredients belong to that category of categories; for \(\mathsf{CAT}\), we use the fixed larger universe that bounds the categories admitted into it. Products, disjoint unions, and equalizers preserve local smallness. Coequalizers need not: identifying objects can gather a collection of arrows that is not small into a single Hom-collection. In that case, the construction still gives a coequalizer in \(\mathsf{CAT}\), but its result is not an object of \(\mathsf{CAT}_{\mathrm{ls}}\). The issue is membership in the category, not a failure of the universal-property equations, as the following example shows:

Example (A Quotient That Leaves \(\mathsf{CAT}_{\mathrm{ls}}\))

Take a category \(\mathsf{D}\) with a separate copy of the two-object category \(\mathSky{A_S}\to\mathAmber{B_S}\) for every small set \(S\), with no arrows between copies. Here “small” refers to our original size boundary; the collection of all small sets fits inside our larger universe but is not itself small. Between any two fixed objects there is at most one arrow, so \(\mathsf{D}\) is locally small and belongs to \(\mathsf{CAT}_{\mathrm{ls}}\).

Now form a quotient \(Q:\mathsf{D}\to\mathsf{E}\) by identifying all the \(\mathSky{A_S}\) as one object \(\mathSky{A}\) and all the \(\mathAmber{B_S}\) as another object \(\mathAmber{B}\), keeping the arrows distinct. There is now a distinct arrow \(\mathSky{A}\to\mathAmber{B}\) for every small set. Since the collection of all small sets is not small, \(\Hom_{\mathsf{E}}(\mathSky{A},\mathAmber{B})\) is not small either.

Thus \(\mathsf{E}\) belongs to \(\mathsf{CAT}\) but not to \(\mathsf{CAT}_{\mathrm{ls}}\). Each individual Hom-set started tiny, but identifying objects gathered too many arrows into one Hom-collection: the quotient left our chosen category of categories.

Conclusion

My undergraduate advisor once told me that category theory tests whether the problems we think are hard are actually hard: putting a problem into categorical language can often reveal that it’s substantially simpler than it first appears. (I wish I had known that before jumping into my first algebraic topology course!)

Category theory is incredibly expressive and powerful; it is to math what functional programming is to computer science. (That’s probably why Haskell enthusiasts keep trying to convince everyone else of their intelligence by saying “functor” and “monad” over and over again.) The commonalities that the field can describe span almost the entire corpus of modern mathematics, and I plan to cover some of these in future articles.

With all that said, I have little interest in category theory for its own sake, which is largely what we’ve done in this article. The next article in the series will focus on Cantor’s diagonal argument, Gödel’s first incompleteness theorem, Turing’s proof of undecidability of the halting problem, Rice’s theorem, and many others, revealing them all as corollaries of a single theorem in category theory: Lawvere's fixed-point theorem.

Footnotes

1. ZFC defines this function as a class function. ↩

2. In \(L^1(\Omega)\), we consider two random variables \(X_1\) and \(X_2\) to be equal when \(\Pr(X_1\neq X_2)=0\). This is called equality almost surely. ↩

3. For more on these size conventions, see Shulman’s Set Theory for Category Theory. Working with Grothendieck universes containing the natural numbers, and larger universes containing those, requires additional foundational assumptions that ZFC alone does not guarantee. ↩