"Hey, I've Seen This One!" A Motivated Introduction to Category Theory
The same constructs appear across different fields: morphisms, subobjects, sums, products, and quotients. Category theory provides a consistent framework for recognizing and studying these patterns.
Mathematics is the art of giving the same name to different things.
— Henri Poincaré, Science and Method
Some of the most striking patterns in mathematics emerge after studying multiple fields: groups, rings, vector spaces, topological spaces, chain complexes, abelian varieties, etc. all have similar notions (but different names for) isomorphisms between objects of the same type. This idea extends directly out of homomorphisms or other ways to indicate similarity. We also often have sub-objects (subspaces, subgroups, subgraphs, etc.), products (Cartesian products, direct products, the product topology, etc.), quotients, “trivial” objects, and many, many other similar concepts.
We might chalk these similarities up to common schools of thought in mathematics: of course every field defines isomorphisms; it’s part of how we determine what properties we’re actually interested in studying! But if there are common threads underlying each of these definitions, we ought to formalize what it actually means to take the product of two or more objects of the same type. If we ever start studying a new field, this gives us clear ideas of what to look for: what does a product look like? What about a quotient? Perhaps this bookkeeping will help us to fill in gaps in subjects we’re already familiar with, or illuminate some concepts as more universal than they first appear.
Category theory originated to help wrangle the complexity of algebraic topology and homological algebra. With the need to simplify such complicated ideas, category theory developed a pleasantly tidy and accessible (if a bit jargon-heavy) language for describing the similarities we’ve noticed. The field has gotten increasing appreciation from mathematicians and bloomed into what is sometimes called a “bird’s eye view” of mathematics.
Accessibility
My aim here is to provide a broadly accessible introduction to anyone who has a strong grasp of set theory and familiarity with linear algebra; if you remember Cartesian products and the term “linear homomorphism” or “linear isomorphism” you should hopefully be fine, but some concepts like sums and quotients might be a bit exotic. For this reason, I’d recommend at least one course in any of abstract algebra, topology, graph theory, or so on.
Categories
First, let’s define what we even mean by “objects of the same type”. In category theory, we conceive of these things as all living in a shared collection, called a category:
Definition (Category)
A category \(\mathsf{C}\) consists of
- a collection of objects;
- for each pair of objects \(\mathSky{A}\) and \(\mathAmber{B}\), a collection \(\Hom_{\mathsf{C}}(\mathSky{A}, \mathAmber{B})\) of morphisms \(f : \mathSky{A} \to \mathAmber{B}\);
- for each object \(\mathSky{A}\), an identity morphism \(\id_{\mathSky{A}} : \mathSky{A} \to \mathSky{A}\);
- for each \(f : \mathSky{A} \to \mathAmber{B}\) and \(g : \mathAmber{B} \to \mathGreen{C}\), a composite morphism \(g \circ f : \mathSky{A} \to \mathGreen{C}\),
such that composition is associative, \(h \circ (g \circ f) = (h \circ g) \circ f\), and the identities are units for it, \(f \circ \id_{\mathSky{A}} = f = \id_{\mathAmber{B}} \circ f\) for every \(f : \mathSky{A} \to \mathAmber{B}\).
Unlike most other fields of math, categories aren’t defined as “sets with structure on top”; they’re allowed a proper class of objects if necessary.1 The objects are, of course, often whatever “sets with structure on them” are of interest in that particular field:
| Category | Objects | Morphisms |
|---|---|---|
| \(\mathsf{Set}\) | Sets | Functions |
| \(\mathsf{Grp}\) | Groups | Group Homomorphisms |
| \(\mathsf{Ring}\)Unital rings, possibly noncommutative, including the zero ring | Rings | Ring Homomorphisms |
| \(R\text{-}\mathsf{Mod}\)Left modules over a fixed unital ring \(R\) | Modules | Module Homomorphisms |
| \(\mathsf{Field}\) | Fields | Field Homomorphisms |
| \(\mathsf{Vec}_k\) | Vector Spaces over \(k\) | Linear Maps |
| \(\mathsf{Top}\) | Topological Spaces | Continuous Maps |
| \(\mathsf{Haus}\) | Hausdorff Spaces | Continuous Maps |
| \(\mathsf{Man}\)Smooth Hausdorff, second-countable manifolds without boundary, including empty manifolds and components of different finite dimensions | Smooth Manifolds | Smooth Maps |
| \(\mathsf{Ch}(R)\)Chain complexes of left modules over a fixed unital ring \(R\) | Chain Complexes | Chain Maps |
| \(\mathsf{AbVar}_k\) | Abelian Varieties over \(k\) | Homomorphisms of Algebraic Groups over \(k\) |
| \(\mathsf{Ell}_k\) | Elliptic Curves over \(k\) | Isogenies over \(k\) |
| \(\mathsf{Meas}\) | Measurable Spaces | Measurable Functions |
| \(\mathsf{Prob}\)Probability spaces with measure-preserving maps, compared pointwise rather than a.e. | Probability Spaces | Measure-Preserving Maps |
| \(\mathsf{Ban}\) | Banach Spaces | Bounded Linear Maps |
| \(\mathsf{Hilb}\) | Hilbert Spaces | Bounded Linear Maps |
| \(\mathsf{Graph}\)Undirected graphs with loops allowed but no multiple edges. | Graphs | Graph Homomorphisms |
| \(\mathcal{P}(\Sigma^\ast)\) | Languages over \(\Sigma\) | Inclusion |
| \(\mathsf{Lang}_\mathrm{P}\) | Decision Problems | Polynomial-Time Many-One Reducibility |
The morphisms are typically the structure-preserving maps between objects in each category. We don’t actually require that these be structure-preserving functions or even functions at all, but we do require that they at least compose like functions do. Because we typically express categorical data with diagrams, we often call morphisms “arrows”.
Posets and Preorders as Categories
Categories needn’t consist of “sets with structure” and functions, though. Any partially ordered set \(P\) can be viewed as a category: the objects are the elements of \(P\), there is exactly one morphism \(a \to b\) when \(a \leq b\) and none otherwise, composition is transitivity, and identities are reflexivity. The \(\mathcal{P}(\Sigma^\ast)\) row is one of these, with languages ordered by inclusion.
The same construction works for a preorder, which need not be antisymmetric. Here \(\mathsf{Lang}_\mathrm{P}\) is the preorder category with exactly one arrow \(L \to M\) when a polynomial-time many-one reduction from \(L\) to \(M\) exists, and none otherwise. Individual reduction functions are not separate arrows. Two problems are therefore isomorphic in this category exactly when each reduces to the other.
Morphisms
In nova fert animus mutatas dicere formas corpora.
[My spirit moves me to speak of forms changed into new bodies.]
— Ovid, Metamorphoses
As we’ve already seen, morphisms (often called “homomorphisms” in their respective categories) are the basic units of category theory, and need no definition. However, we might want to talk about all morphisms from one object \(A\) to \(B\) in \(\mathsf{C}\). (As mentioned in the definition of categories, this collection is usually denoted \(\Hom(A, B)\)). We write \(\Hom(A, \cdot)\) for the family of Hom-sets \(\Hom(A, B)\) as \(B\) varies, and similarly \(\Hom(\cdot, A)\) for the family \(\Hom(B, A)\).
Of course, there are specific types of morphisms that are worth discussing:
- An endomorphism of an object \(A\) is an arrow \(f : A \to A\). In other words, it’s a member of \(\Hom(A, A)\), which we typically denote by \(\End(A)\) for short.
- An isomorphism is an arrow \(f : A \to B\) with a corresponding morphism \(g : B \to A\) with \(g \circ f = \id_A\) and \(f \circ g = \id_B\). (In that case we say \(A\) and \(B\) are isomorphic and write \(A \cong B\); as you would expect, this is an equivalence relation.)
- An automorphism is an isomorphism from an object to itself. The collection of all of an object’s automorphisms is denoted \(\Aut(A)\).
Isomorphisms in Different Categories
| Category | Isomorphism |
|---|---|
| \(\mathsf{Set}\) | Bijection |
| \(\mathsf{Grp}\) | Isomorphism |
| \(\mathsf{Ring}\) | Isomorphism |
| \(R\text{-}\mathsf{Mod}\) | Isomorphism |
| \(\mathsf{Field}\) | Isomorphism |
| \(\mathsf{Vec}_k\) | Linear Isomorphism |
| \(\mathsf{Top}\) | Homeomorphism |
| \(\mathsf{Haus}\) | Homeomorphism |
| \(\mathsf{Man}\) | Diffeomorphism |
| \(\mathsf{Ch}(R)\) | Chain Isomorphism |
| \(\mathsf{AbVar}_k\) | Isomorphism of Algebraic Groups over \(k\) |
| \(\mathsf{Ell}_k\) | Isomorphism |
| \(\mathsf{Meas}\) | Measurable Isomorphism |
| \(\mathsf{Prob}\) | Measure-Preserving Isomorphism |
| \(\mathsf{Ban}\) | Bounded Linear Isomorphism |
| \(\mathsf{Hilb}\) | Bounded Linear Isomorphism |
| \(\mathsf{Graph}\) | Isomorphism |
| \(\mathcal{P}(\Sigma^\ast)\) | Equality |
| \(\mathsf{Lang}_\mathrm{P}\) | Polynomial-Time Equivalence |
Initial and Terminal Objects
I am Alpha and Omega, the beginning and the end, the first and the last.
— Revelation 22:13 (KJV)
The need to have two definitions here might be a little tricky if you’re only thinking algebraically: the trivial group \(\set{e}\) is obviously a subgroup of (and therefore has a unique homomorphism into) every group; this motivates the definition of an initial object:
Definition (Initial Object)
An object \(\mathRose{I}\) of a category \(\mathsf{C}\) is initial if for every object \(\mathSky{A}\) there is exactly one morphism \(\mathRose{I} \to \mathSky{A}\).
| Category | Initial Object |
|---|---|
| \(\mathsf{Set}\) | \(\varnothing\) |
| \(\mathsf{Grp}\) | \(\set{e}\) |
| \(\mathsf{Ring}\) | \(\Z\) |
| \(\mathsf{Top}\) | \(\varnothing\) |
| \(\mathsf{AbVar}_k\) | \(\Spec{k}\) |
(As an aside, the unique morphism from \(\Z\) to a ring \(R\) actually determines the ring’s characteristic!)
But if you consider \(\mathsf{Set}\), you’ll notice a problem: the empty set \(\varnothing\) is definitely an initial object because for any set \(S\), we can define the trivial function \(f : \varnothing \to S\) which takes no values. (Functions aren’t required to have nonempty domains!)
But we could just as easily notice that every group has a morphism onto \(\set{e}\); this motivates a second definition:
Definition (Terminal Object)
An object \(\mathRose{1}\) of a category \(\mathsf{C}\) is terminal if for every object \(\mathSky{A}\) there is exactly one morphism \(\mathSky{A} \to \mathRose{1}\).
| Category | Terminal Object |
|---|---|
| \(\mathsf{Set}\) | Any singleton \(\set{\ast}\) |
| \(\mathsf{Grp}\) | \(\set{e}\) |
| \(\mathsf{Ring}\) | The trivial ring with \(0 = 1\) |
| \(\mathsf{Top}\) | Any one-point space \(\set{p}\) |
| \(\mathsf{AbVar}_k\) | \(\Spec{k}\) |
Note also that there is more than one terminal object in categories like \(\mathsf{Set}\) and \(\mathsf{Top}\): terminal and initial objects only have to be unique up to (unique) isomorphism.
You may have also noticed that the initial and terminal objects in \(\mathsf{Grp}\) and \(\mathsf{AbVar}\) coincide; these objects’ unique morphisms in and out do tend to be “trivial” in both directions, so they’re typically called zero objects:
Definition (Zero Object)
An object of a category is a zero object if it is both initial and terminal. In a category with a zero object \(\mathRose{0}\), the zero morphism \(0 : \mathSky{A} \to \mathAmber{B}\) is the composite \(\mathSky{A} \to \mathRose{0} \to \mathAmber{B}\).
Categories with at least one object that is both initial and terminal are called pointed categories. Initial and terminal objects are unique (up to unique isomorphism) in any category, so of course zero objects are as well.
Proof (Zero Object is Unique in Pointed Categories)
Let \(0\) and \(0^\prime\) be zero objects. Since \(0\) is initial, there is exactly one morphism \(f : 0 \to 0^\prime\), and since \(0^\prime\) is initial, there is exactly one morphism \(g : 0^\prime \to 0\). Then \(g \circ f\) is a morphism \(0 \to 0\), but since \(0\) is initial, the only such morphism is \(\id_0\), so \(g \circ f = \id_0\). By the same argument, \(f \circ g = \id_{0^\prime}\). So \(f\) is an isomorphism, and it is the only morphism \(0 \to 0^\prime\), so \(0\) and \(0^\prime\) are isomorphic by a unique isomorphism.
The proof above only used the fact that \(0\) and \(0^\prime\) are initial, so it really shows that any two initial objects are isomorphic by a unique isomorphism. Reversing the arrows gives the same result for terminal objects. Their definitions differ only in the direction of their arrows. This isn’t the only time this pattern appears.
Constructing Objects I
From all things one, and from one all things.
— Heraclitus (Fragment B10)
The names “sum” and “product” come from \(\mathsf{Set}\): for finite sets, \(\lvert A \amalg B \rvert = \lvert A \rvert + \lvert B \rvert\) and \(\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert\). Taking cardinalities, we see that the initial object \(\varnothing\) (the empty set) and the terminal object \(\lbrace \ast \rbrace\) (the singleton set) have cardinalities \(0\) and \(1\), respectively, so these operations were termed “sum” and “product” despite unfortunately not possessing any nice ring-like interactions. (More concretely, it’s not true in general that the product operation distributes over the sum operation, though we’ll see a large class of categories where it does in part 3.) In many algebraic categories like \(\mathsf{Vec}_k\), the sum and the product are the same object, \(V \oplus W\).
Sums of Objects: The Coproduct
A sum captures the idea of combining two objects \(A\) and \(B\) into a new object \(A \amalg B\), equipped with maps from each of \(A\) and \(B\) into the combined object. In sets, we can think of these maps as telling us which “part” of \(A \amalg B\) “comes from” each set: both maps are injections, defined by sending each element to its tagged copy.
Example (A Disjoint Union in \(\mathsf{Set}\))
Take \(\mathSky{A} = \set{0,1}\) and \(\mathAmber{B} = \set{1,2}\). Their ordinary union has only three elements, because it merges the two copies of \(1\). The disjoint union keeps them separate by tagging each element with its source:
\[\mathSky{A} \amalg \mathAmber{B} = \set{(0,\mathSky{0}),(1,\mathSky{0}),(1,\mathAmber{1}),(2,\mathAmber{1})}.\]Here the second coordinate is the tag: \(\mathSky{0}\) for \(\mathSky{A}\) and \(\mathAmber{1}\) for \(\mathAmber{B}\). (This is why the disjoint union is often called the “tagged union”.)
The injections are \(\iota_{\mathSky{A}}(a)=(a,\mathSky{0})\) and \(\iota_{\mathAmber{B}}(b)=(b,\mathAmber{1})\). In particular, \(\iota_{\mathSky{A}}(1) \neq \iota_{\mathAmber{B}}(1)\).
Of course, we could just as easily inject \(A\) and \(B\) into a larger set with extra elements, so the injections alone don’t tell us that we’ve captured precisely their sum. We need a condition saying that maps out of \(A \amalg B\) correspond exactly to independently chosen maps out of \(A\) and \(B\).
How can we express that? Well, if I had some kind of map \(u: A \amalg B \to T\) to some arbitrary “test” object \(T\), then I could cook up maps \(f: A \to T\) and \(g: B \to T\) by just restricting \(u\) to the “\(A\) part” of \(A \amalg B\) to get \(f\) (and similarly for \(g\)). In terms of composition, \(f = u \circ \iota_A\) and \(g = u \circ \iota_B\). These equalities make the corresponding diagram commute:
Definition (Commuting Diagram)
A diagram of objects and morphisms commutes if any two directed paths with the same starting object and ending object give the same morphism when we compose the arrows along each path. For example, the triangular diagram below:
commutes exactly when \(g\circ f=h\): going from \(\mathSky{A}\) to \(\mathGreen{C}\) via \(\mathAmber{B}\) gives the same morphism as taking \(h\) directly. This notion extends to more complicated diagrams, like the square diagram below:
which commutes exactly when \(g\circ f=k\circ h\): the path through \(\mathAmber{B}\) and the path through \(\mathGreen{C}\) give the same morphism from \(\mathSky{A}\) to \(\mathViolet{D}\).
While we’re at it, this way of breaking morphisms like \(f\) and \(g\) apart looks remarkably like factoring an integer. Let’s give it a name:
Definition (Factorization)
A morphism \(h: \mathIndigo{T} \to \mathSky{A}\) factors through a morphism \(i: \mathRose{S} \to \mathSky{A}\) if there exists a morphism \(u: \mathIndigo{T} \to \mathRose{S}\) making the following triangle commute:
In other words, \(h=i\circ u\): we can obtain \(h\) by first applying \(u\) and then applying \(i\).
So in our discussion above, we say that \(f\) factors as \(u \circ \iota_A\) and \(g\) factors as \(u \circ \iota_B\).
Starting with \(u\), we can always obtain \(f\) and \(g\) by composing with the \(\iota\) maps. The requirement we actually want goes the other way: for any “test” object \(T\) and independently chosen maps \(f: A \to T\) and \(g: B \to T\), there must be exactly one map \(u: A \amalg B \to T\) giving both factorizations.
In our set theory example above, existence means we can assign values independently on the two tagged parts, even giving the two copies of \(1\) different values. Uniqueness means that those assignments determine \(u\) on the whole set: there are no extra elements whose values are left unspecified. This is how we capture the sum of our chosen \(A\) and \(B\).
This leads us to the category-theoretic notion of a sum, called a coproduct:
Definition (Coproduct)
Let \(\mathSky{A}\) and \(\mathAmber{B}\) be objects of a category \(\mathsf{C}\). A coproduct (or sum) of \(\mathSky{A}\) and \(\mathAmber{B}\) is an object \(\mathRose{A \amalg B}\) together with morphisms \(\iota_{\mathSky{A}} : \mathSky{A} \to \mathRose{A \amalg B}\) and \(\iota_{\mathAmber{B}} : \mathAmber{B} \to \mathRose{A \amalg B}\) such that for any object \(\mathIndigo{T}\) and morphisms \(f : \mathSky{A} \to \mathIndigo{T}\) and \(g : \mathAmber{B} \to \mathIndigo{T}\), there is a unique morphism \(u : \mathRose{A \amalg B} \to \mathIndigo{T}\) making the following diagram commute:
The morphisms \(\iota_A\) and \(\iota_B\) are called the canonical injections (or coprojections), and they’re part of the data of a coproduct: its defining condition is a statement about the triple \((A \amalg B, \iota_A, \iota_B)\), not about the object alone. The name comes from \(\mathsf{Set}\), where they really are inclusions, but in a general category they need not be injective.
Example (Disjoint Unions in \(\mathsf{Set}\) Are Coproducts)
For any set \(\mathIndigo{T}\) and functions \(f: \mathSky{A}\to \mathIndigo{T}\) and \(g: \mathAmber{B}\to \mathIndigo{T}\), we can also define
\[\begin{aligned} u(a,\mathSky{0}) &= f(a),\\ u(b,\mathAmber{1}) &= g(b). \end{aligned}\]so \(u\circ\iota_{\mathSky{A}}=f\) and \(u\circ\iota_{\mathAmber{B}}=g\). These two equations define the values of \(u\) on every element of the disjoint union, so no other function can replace \(u\). These functional equations and the uniqueness of \(u\) satisfy our requirements for the disjoint union to be a coproduct.
| Category | Sum |
|---|---|
| \(\mathsf{Set}\) | Disjoint Union \(A \amalg B\) |
| \(\mathsf{Grp}\) | Free Product \(G * H\) |
| \(\mathsf{Ring}\) | Free Product \(A * B\) |
| \(R\text{-}\mathsf{Mod}\) | Direct Sum \(M \oplus N\) |
| \(\mathsf{Field}\) | [Not in general] |
| \(\mathsf{Vec}_k\) | Direct Sum \(V \oplus W\) |
| \(\mathsf{Top}\) | Disjoint Union \(X \amalg Y\) |
| \(\mathsf{Haus}\) | Disjoint Union \(X \amalg Y\) |
| \(\mathsf{Man}\) | Disjoint Union \(M \amalg N\) |
| \(\mathsf{Ch}(R)\) | Degreewise Direct Sum \(C \oplus D\) |
| \(\mathsf{AbVar}_k\) | Product \(A \times B\) |
| \(\mathsf{Ell}_k\) | [None] |
| \(\mathsf{Meas}\) | Disjoint Union \(X \amalg Y\) |
| \(\mathsf{Prob}\) | [None]Coproducts do not exist in general, although special cases do. For example, two one-point probability spaces have a coproduct given by a two-point space with the indiscrete sigma-algebra (only the empty set and the whole space are measurable). |
| \(\mathsf{Ban}\) | Direct Sum \(X \oplus Y\) |
| \(\mathsf{Hilb}\) | Orthogonal Direct Sum \(H \oplus K\) |
| \(\mathsf{Graph}\) | Disjoint Union \(G \amalg H\) |
| \(\mathcal{P}(\Sigma^\ast)\) | Union \(L \cup M\) |
| \(\mathsf{Lang}_\mathrm{P}\) | Join \(L \oplus L^\prime\) |
Products of Objects
Products are very similar to sums, except that the arrows go in the opposite direction: instead of having injections \(\iota\) from the summands \(A\) and \(B\) to the sum \(A \amalg B\), we have projection maps \(\pi_A: A \times B \to A\) and \(\pi_B: A \times B \to B\), typically defined by something like \((a, b) \mapsto a\) and \((a, b) \mapsto b\).
Example (A Cartesian Product in \(\mathsf{Set}\))
Take the same sets \(\mathSky{A}=\set{0,1}\) and \(\mathAmber{B}=\set{1,2}\). Their product is
\[\mathRose{A\times B}=\set{(0,1),(0,2),(1,1),(1,2)}\]We can define the projections \(\pi_{\mathSky{A}}(a,b)=a\) and \(\pi_{\mathAmber{B}}(a,b)=b\).
From there, much of the discussion about coproducts repeats, and we obtain the definition of a product:
Definition (Product)
Let \(\mathSky{A}\) and \(\mathAmber{B}\) be objects of a category \(\mathsf{C}\). A product of \(\mathSky{A}\) and \(\mathAmber{B}\) is an object \(\mathRose{A \times B}\) together with morphisms \(\pi_{\mathSky{A}} : \mathRose{A \times B} \to \mathSky{A}\) and \(\pi_{\mathAmber{B}} : \mathRose{A \times B} \to \mathAmber{B}\) such that for any object \(\mathIndigo{T}\) and morphisms \(f : \mathIndigo{T} \to \mathSky{A}\) and \(g : \mathIndigo{T} \to \mathAmber{B}\), there is a unique morphism \(u : \mathIndigo{T} \to \mathRose{A \times B}\) making the following diagram commute:
Example (Cartesian Products in \(\mathsf{Set}\) Are Products)
For any set \(\mathIndigo{T}\) and functions \(f: \mathIndigo{T} \to \mathSky{A}\) and \(g: \mathIndigo{T} \to \mathAmber{B}\), we can define
\[u(t) = (\mathSky{f(t)},\mathAmber{g(t)})\]so \(\pi_{\mathSky{A}} \circ u = f\), and \(\pi_{\mathAmber{B}} \circ u = g\). These equations force \(u(t) = (f(t), g(t))\), which defines the function uniquely. These two equalities and the uniqueness of \(u\) satisfy the category-theoretic definition of a product.
| Category | Product |
|---|---|
| \(\mathsf{Set}\) | Cartesian Product \(A \times B\) |
| \(\mathsf{Grp}\) | Direct Product \(G \times H\) |
| \(\mathsf{Ring}\) | Direct Product \(A \times B\) |
| \(R\text{-}\mathsf{Mod}\) | Direct Sum \(M \oplus N\) |
| \(\mathsf{Field}\) | [Not in general] |
| \(\mathsf{Vec}_k\) | Direct Sum \(V \oplus W\) |
| \(\mathsf{Top}\) | \(X \times Y\) with the Product Topology |
| \(\mathsf{Haus}\) | \(X \times Y\) with the Product Topology |
| \(\mathsf{Man}\) | Product Manifold \(M \times N\) |
| \(\mathsf{Ch}(R)\) | Degreewise Direct Sum \(C \oplus D\) |
| \(\mathsf{AbVar}_k\) | Product \(A \times B\) |
| \(\mathsf{Ell}_k\) | [None] |
| \(\mathsf{Meas}\) | \(X \times Y\) with the Product \(\sigma\)-Algebra |
| \(\mathsf{Prob}\) | [Not in general] |
| \(\mathsf{Ban}\) | Direct Sum \(X \oplus Y\) |
| \(\mathsf{Hilb}\) | Orthogonal Direct Sum \(H \oplus K\) |
| \(\mathsf{Graph}\) | Tensor Product \(G \times H\) |
| \(\mathcal{P}(\Sigma^\ast)\) | Intersection \(L \cap M\) |
| \(\mathsf{Lang}_\mathrm{P}\) | [Not in general] |
Subobjects
The whole is greater than the part.
— Euclid, Elements
Before jumping into equivalence relations and quotient objects, it would be useful to detour into another topic of interest: subobjects. We’d like to have a nice, general definition that pins down what it really means for an object \(S\) to be a “subobject” of another object \(A\) in the same category. The naive definition (based on monomorphisms) captures what we want in most categories, but some categories like \(\mathsf{Top}\) and \(\mathsf{Meas}\) require a more complex definition that we’ll converge on later in this section.
(Ordinary) Subobjects: Monomorphisms
You may also have noticed in your travels throughout the world of math that one object is a subobject of another if there exists an injective morphism that includes the subobject in the larger object:
- A subset \(S \subseteq X\) comes with the inclusion function \(S \hookrightarrow X\).
- A subgroup \(H \leq G\) comes with the inclusion homomorphism \(H \hookrightarrow G\).
- A subspace \(W \subseteq V\) comes with the inclusion linear map \(W \hookrightarrow V\).
Injectivity is a statement about elements, and category theory doesn’t care about (or even define) elements. The trick is to notice that a function \(m\) is injective exactly when it can be cancelled on the left: if \(m \circ g_1 = m \circ g_2\), then \(g_1 = g_2\). That condition is phrased only in terms of morphisms, so it makes sense in any category. This gives us the following definition:
Definition (Monomorphism)
A morphism \(m : \mathSky{A} \to \mathAmber{B}\) is a monomorphism (or mono) if for any pair of morphisms \(g_1, g_2 : \mathIndigo{T} \to \mathSky{A}\), \(m \circ g_1 = m \circ g_2\) implies \(g_1 = g_2\).
In \(\mathsf{Set}\), \(\mathsf{Grp}\), and \(\mathsf{Vec}_k\), monos are exactly the injective homomorphisms, so monos are a reasonable stand-in for inclusions, and we can now define subobjects:
Definition (Subobject)
Two monos \(i : \mathRose{S} \to \mathSky{A}\) and \(i^\prime : \mathRose{S}^\prime \to \mathSky{A}\) are equivalent if there is an isomorphism \(\varphi : \mathRose{S} \to \mathRose{S}^\prime\) with \(i^\prime \circ \varphi = i\).
A subobject of \(\mathSky{A}\) is an equivalence class of monos into \(\mathSky{A}\). The map \(i : \mathRose{S} \to \mathSky{A}\) specifies how \(\mathRose{S}\) sits inside \(\mathSky{A}\); the object \(\mathRose{S}\) alone does not determine the subobject.
There are two related uses of “subobject” here. Formally, it is the equivalence class of a mono \(i : S \to A\). In practice, we often call the representative map \(i\), or even its domain \(S\), “the subobject” when the map into \(A\) is understood. We’ll use this shorthand, but the inclusion data is always part of what we mean.
The equivalence relation identifies different presentations of the same subobject inside the fixed ambient object \(A\), not all abstractly isomorphic objects. The condition \(i^\prime \circ \varphi = i\) is essential: for example, two distinct lines through the origin in \(\R^2\) are isomorphic as vector spaces, but their inclusions represent different subobjects of \(\R^2\).
Isomorphic Objects, Different Subobjects
The Gaussian integers \(\Z[i]\) give a useful example. As an additive group, \(\Z[i] \cong \Z \times \Z\) via \((a,b) \mapsto a+bi\); internally, it is the direct sum of the subgroups \(\Z\) and \(i\Z\). Those two subgroups are isomorphic by \(n \mapsto ni\), but they are different subobjects of \(\Z[i]\): one is the real axis, the other the imaginary axis. They just have arrows representing isomorphisms between them in \(\mathsf{Grp}\).
Writing their inclusions as \(j : \Z \hookrightarrow \Z[i]\) and \(k : i\Z \hookrightarrow \Z[i]\) makes the distinction precise. The isomorphism \(\varphi(n)=ni\) does not satisfy \(k \circ \varphi = j\): at \(1\), the two sides give \(i\) and \(1\):
This triangle does not commute: \(k\circ\varphi\neq j\). In fact, no isomorphism can satisfy that equation, since the inclusions have different images in \(\Z[i]\). Subobjects identify presentations that are isomorphic over \(A\), not merely isomorphic as abstract objects.
There is a category that packages this distinction: the slice category \(\mathsf{C}/A\). Its objects are morphisms \(j : S \to A\) in \(\mathsf{C}\). A morphism from \(j : S \to A\) to \(k : S^\prime \to A\) is a morphism \(\varphi : S \to S^\prime\) satisfying \(k \circ \varphi = j\); identities and composition come from \(\mathsf{C}\). Thus two objects of the slice are isomorphic precisely when their domains are isomorphic in a way that preserves their maps into \(A\).
We can therefore describe subobjects of \(A\) as isomorphism classes of monomorphisms, viewed as objects of \(\mathsf{C}/A\). (Restricting to regular monomorphisms gives regular subobjects, both of which we’ll see later in this section.) The equivalence relation in our definition is exactly isomorphism in this slice category.
This is a perfectly fine definition for subgroups, subgraphs, sublanguages, etc., but it can also capture classes of objects that are too broad:
| Category | (Ordinary) Subobject |
|---|---|
| \(\mathsf{Set}\) | Subset |
| \(\mathsf{Grp}\) | Subgroup |
| \(\mathsf{Ring}\) | Subrings |
| \(R\text{-}\mathsf{Mod}\) | Submodule |
| \(\mathsf{Field}\) | Subfields |
| \(\mathsf{Vec}_k\) | (Vector) Subspace |
| \(\mathsf{Top}\) | Subsets with Finer Topologies than the Subspace Topology |
| \(\mathsf{Haus}\) | Subsets with Finer Topologies than the Subspace Topology |
| \(\mathsf{Man}\) | Injectively Mapped Manifolds |
| \(\mathsf{Ch}(R)\) | Subcomplex |
| \(\mathsf{AbVar}_k\) | Homomorphisms with Finite Kernel |
| \(\mathsf{Ell}_k\) | Isogenies |
| \(\mathsf{Meas}\) | Subsets with Finer (\sigma)-Algebras than the Trace (\sigma)-Algebra |
| \(\mathsf{Prob}\) | Injectively Mapped Probability Spaces |
| \(\mathsf{Ban}\) | Linear Subspaces with Stronger Banach Norms |
| \(\mathsf{Hilb}\) | Linear Subspaces with Stronger Hilbert Norms |
| \(\mathsf{Graph}\) | Subgraphs |
| \(\mathcal{P}(\Sigma^\ast)\) | Sublanguages |
| \(\mathsf{Lang}_\mathrm{P}\) | Problems Reducible to the Given Problem in Polynomial Time |
Take \(\mathsf{Top}\) for example: the monos are exactly the injective continuous maps, and an injective continuous map need not be the inclusion of a subspace. The map \(x \mapsto x\) from \(\R\) with the discrete topology to \(\R\) with its usual open-ball topology is injective and continuous, so it’s a mono, but it certainly doesn’t mean that discrete \(\R\) is a subspace of ordinary \(\R\); the domain object has a finer topology than the subspace topology. So despite being a subobject by the category-theoretic definition, this doesn’t represent the inclusion of a subspace in the stricter sense that we’re interested in when working in \(\mathsf{Top}\).
If we want to talk about subspaces and only subspaces (and the equivalent notions in a general category), we need a stronger condition that detects this difference.
Equalizing Morphisms
We can begin by reframing how we think about subobjects. One way to specify a subobject is with an equation that “carves it out” of a larger object:
Example (An Axis Defined by an Equation in \(\mathsf{Top}\))
In topology, the \(x\)-axis in \(\mathSky{\R^2}\) consists of the points satisfying \(y = 0\). These are exactly the points where the continuous maps \(f,g : \mathSky{\R^2} \to \mathAmber{\R}\) given by \(f(x,y)=y\) and \(g(x,y)=0\) agree.
Example (A Plane Defined by an Equation in \(\mathsf{Vec}_\R\))
In linear algebra, the plane in \(\mathSky{\R^3}\) defined by \(x+y+z=0\) is where the linear maps \(f,g : \mathSky{\R^3} \to \mathAmber{\R}\) given by \(f(x,y,z)=x+y+z\) and \(g(x,y,z)=0\) agree.
Example (Even Integers Defined by an Equation in \(\mathsf{Grp}\))
In group theory, the subgroup \(\mathRose{2\Z}\) of \(\mathSky{\Z}\) consists of the even integers. These are where the homomorphisms \(f,g : \mathSky{\Z} \to \mathAmber{\Z/2\Z}\) given by \(f(n)=n \bmod{2}\) and \(g(n)=0 \bmod{2}\) agree.
In each case, \(A\) is the larger object, \(f, g: A \to B\) express the two sides of the equation, and \(B\) is their codomain where we compare the two sides of the equation (the outputs of \(f\) and \(g\)) to see if they’re equal. Given two morphisms \(f, g : A \to B\), we’d like \(S\) to capture exactly where they agree; in set-theoretic terms, we’d take \(\setbuild{a \in A}{f(a) = g(a)}\). The challenge is to describe this using only morphisms, in a way that also captures the appropriate structure on \(S\).
Definition (Equalizing Morphism)
Given morphisms \(f,g : \mathSky{A} \to \mathAmber{B}\), a morphism \(h : \mathIndigo{T} \to \mathSky{A}\) is an equalizing morphism for \(f\) and \(g\) if the two composites from \(\mathIndigo{T}\) to \(\mathAmber{B}\) in the following diagram are equal, so \(f \circ h = g \circ h\):
We say that \(h\) equalizes \(f\) and \(g\).
The equalizing morphism requires agreement on the image of \(T\), but that’s all it requires: it doesn’t necessarily restrict to subobject inclusions, which is what we wanted. Even if we demand that our equalizing morphism also be a subobject inclusion, this doesn’t determine a unique answer:
This matters if, rather than starting with \(S\) and wanting to justify it as a subobject of \(A\), we start off with an equation described by some \(f\) and \(g\) and want to find the subobject \(S\) of \(A\) containing only solutions to the equation, and all such solutions. In terms of elements, we want
\[a \in S \iff f(a) = g(a)\]However, equalizing inclusion morphisms only give the forward implication \(a \in S \implies f(a) = g(a)\), but candidates for \(S\) can exclude solutions. The equalizing morphism doesn’t single out the full solution subobject from the smaller candidates.
We could ask for the “largest” subobject on which the maps \(f\) and \(g\) agree: the subobject \(S\) that contains every other candidate. To express “containing” categorically, each equalizing candidate’s morphism \(h: T \to A\), whether it’s an inclusion or not, must factor uniquely through the map \(i: S \to A\) that actually includes the subobject \(S\) we want. Factoring accounts for every morphism into \(A\) on which \(f\) and \(g\) agree, and the uniqueness singles out \(S\) as the subobject we actually want. The object \(S\) together with its morphism \(i\) are called an equalizer of \(f\) and \(g\).
Regular Subobjects: Equalizers
Definition (Equalizer)
Let \(f, g : \mathSky{A} \to \mathAmber{B}\) be morphisms in a category \(\mathsf{C}\). An equalizer of \(f\) and \(g\) is an object \(\mathRose{S}\) together with a morphism \(i : \mathRose{S} \to \mathSky{A}\) such that:
\(i\) is an equalizing morphism: \(f \circ i = g \circ i\), and
Every equalizing morphism factors uniquely through \(i\): for any morphism \(h : \mathIndigo{T} \to \mathSky{A}\) with \(f \circ h = g \circ h\), there is a unique morphism \(u : \mathIndigo{T} \to \mathRose{S}\) making the following diagram commute:
so \(i \circ u = h\).
The definition closes the gap in our previous attempt. The equation \(f \circ i = g \circ i\) says that \(S\) contains only agreement; the requirement involving every test object \(T\) says that \(S\) can’t miss any parts where \(f\) and \(g\) agree. In sets, take \(T\) to be a singleton and let \(h\) pick any point \(a \in A\) where \(f(a) = g(a)\). The map \(u\) must then pick a point of \(S\) that \(i\) sends to \(a\), so no point of agreement can be left out. Uniqueness says that this point of \(S\) is determined: \(S\) cannot contain multiple copies of the same point of \(A\).
Example (The Subgroup \(2\Z\) of \(\Z\) in \(\mathsf{Grp}\))
Let’s prove that the inclusion \(i : \mathRose{S} \hookrightarrow \mathSky{A}\) from the subgroup \(\mathRose{S} = \mathRose{2\Z}\) into \(\mathSky{A} = \mathSky{\Z}\) is an equalizer. To do this, we need two homomorphisms out of \(\mathSky{\Z}\) that agree on exactly \(\mathRose{2\Z}\).
Parity gives us a suitable test: choose \(\mathAmber{B} = \mathAmber{\Z/2\Z}\), with \(f(n) = n \bmod{2}\) and \(g(n) = 0\). They agree on every even integer, so the equalizing morphism condition \(f \circ i = g \circ i\) is satisfied.
For existence and uniqueness, we can take any group \(\mathIndigo{T}\) and homomorphism \(h : \mathIndigo{T} \to \mathSky{\Z}\) with \(f \circ h = g \circ h\). Every value of \(h\) is even, so \(u(t) = h(t)\) defines a homomorphism \(u : \mathIndigo{T} \to \mathRose{2\Z}\). It satisfies \(i \circ u = h\), and the inclusion leaves no other choice for \(u\). Thus \(i\) is the equalizer of this pair.
All this noise is necessary because these maps uniquely identify \(\mathRose{2\Z}\) as the only possible subgroup. Let’s consider another subgroup, \(4\Z\): \(f(n) = g(n)\) for every \(n\) in \(4\Z\), so its inclusion into \(\mathSky{\Z}\) is an equalizing morphism. While we could cook up a \(u\) for \(\mathRose{2\Z}\) that allows any test object to factor, we can show that \(4\Z\) can’t be the subgroup \(\mathRose{S}\) identified by the maps we’ve chosen.
First, choose a test object \(\mathIndigo{T}\) — let’s choose \(\mathIndigo{\Z}\) — and a homomorphism, \(h: \mathIndigo{\Z} \to \mathSky{\Z}\) given by \(h(n) = 2n\). This homomorphism can’t factor through the inclusion \(j: 4\Z \hookrightarrow \mathSky{\Z}\) because \(h(1) = 2\) and \(2\) isn’t in \(4\Z\), so the factorization fails:
The same issue happens for every other proper subgroup of \(\mathRose{2\Z}\): we can always cook up a test object \(\mathIndigo{T}\) and morphism \(\mathIndigo{T} \to \mathSky{\Z}\) that fails to factor for every candidate \(S\) except the one we wanted, \(\mathRose{2\Z}\). (Taking the whole group \(\Z\) as the candidate subobject would simply fail the equalizing condition!)
Example (The Subspace \(\R \times \set{0}\) of \(\R^2\) in \(\mathsf{Top}\))
Let’s prove that the inclusion \(i : \mathRose{S} \hookrightarrow \mathSky{A}\) from the horizontal axis \(\mathRose{S} = \mathRose{\R \times \set{0}}\) into \(\mathSky{A} = \mathSky{\R^2}\) is an equalizer. Give \(\mathSky{\R^2}\) its usual topology and \(\mathRose{S}\) the subspace topology. To do this, we need two continuous maps out of \(\mathSky{\R^2}\) that agree on exactly \(\mathRose{\R \times \set{0}}\).
The vertical coordinate gives us a suitable test: choose \(\mathAmber{B} = \mathAmber{\R}\), with \(f(x,y) = y\) and \(g(x,y) = 0\). They agree exactly on the horizontal axis, so the equalizing morphism condition \(f \circ i = g \circ i\) is satisfied.
For existence and uniqueness, we can take any topological space \(\mathIndigo{T}\) and continuous map \(h : \mathIndigo{T} \to \mathSky{\R^2}\) with \(f \circ h = g \circ h\). Every value of \(h\) lies on the axis, so \(u(t) = h(t)\) defines a map \(u : \mathIndigo{T} \to \mathRose{S}\). The subspace topology makes \(u\) continuous. It satisfies \(i \circ u = h\), and the inclusion leaves no other choice for \(u\). Thus \(i\) is the equalizer of this pair.
Here the test also identifies the topology we wanted. Let’s give the same axis the discrete topology and call this space \(S_{\mathrm{disc}}\). Its inclusion \(j : S_{\mathrm{disc}} \hookrightarrow \mathSky{\R^2}\) is still continuous and injective, and \(f\) and \(g\) still agree on every point of its image, so it’s an equalizing morphism. But it can’t be the equalizer of this pair.
First, choose a test object \(\mathIndigo{T}\) — let’s choose \(\mathIndigo{\R}\) with its usual topology — and a continuous map \(h : \mathIndigo{\R} \to \mathSky{\R^2}\) given by \(h(t) = (t,0)\). We have \(f \circ h = g \circ h = 0\), but this map can’t factor through \(j\) by a continuous map:
The equation \(j \circ u = h\) would force \(u(t) = (t,0)\). But the singleton \(\lbrace (0,0) \rbrace\) is open in the discrete axis, while its inverse image \(\lbrace 0 \rbrace\) isn’t open in \(\mathIndigo{\R}\). Thus this \(u\) isn’t continuous, so it isn’t a morphism in \(\mathsf{Top}\). The candidate contains all the right points, but the test map detects that it has the wrong topology.
You can see here why we test with an arbitrary \(T\): the condition detects both missing points and unsuitable structure, using only objects and morphisms.
Of course, when specifying that something is a regular subobject, we only care about the inclusion map \(i: S \hookrightarrow A\). The definition of “equalizer” demands that we specify some pair of \(f\) and \(g\) that map to an object \(B\), and that test object \(T\) is also implied. We don’t care about any of that; we only care to imply that satisfactory morphisms \(f\) and \(g\) exist for \(i\) somewhere out in the wild. Let’s cook up a less cumbersome equivalent definition:
Definition (Regular Monomorphism)
A morphism \(i\) is a regular monomorphism if it is the equalizer of some pair of morphisms.
At last, we can state the more restrictive notion of subobject that captures the familiar subspace examples:
Definition (Regular Subobject)
Let \(\mathSky{A}\) and \(\mathRose{S}\) be objects in a category \(\mathsf{C}\). A regular subobject of \(\mathSky{A}\) is an equivalence class of regular monomorphisms into \(\mathSky{A}\), where \(i : \mathRose{S} \to \mathSky{A}\) and \(i^\prime: \mathRose{S}^\prime \to \mathSky{A}\) are equivalent if there exists an isomorphism \(\varphi : \mathRose{S} \to \mathRose{S}^\prime\) such that \(i^\prime \circ \varphi = i\).
If \(i\) is clear from context, then we call \(\mathRose{S}\) itself a regular subobject of \(\mathSky{A}\).
The qualifier matters: a subobject allows any mono; a regular subobject requires an equalizer. In \(\mathsf{Set}\), \(\mathsf{Grp}\), and \(\mathsf{Vec}_k\), every mono is regular, so the distinction disappears. In \(\mathsf{Top}\), regular subobjects are precisely subspaces with their subspace topology; in \(\mathsf{Haus}\), they are closed subspaces; and in \(\mathsf{Graph}\), they are induced subgraphs. For posets, only isomorphisms represent regular subobjects, so strictly smaller elements give nonregular subobjects.
| Category | Regular Subobject |
|---|---|
| \(\mathsf{Set}\) | Subset |
| \(\mathsf{Grp}\) | Subgroup |
| \(\mathsf{Ring}\) | Equalizer SubringOrdinary subrings are the usual notion in ring theory and may be preferred here. Regular subobjects restrict to subring inclusions that are equalizers; not every subring inclusion qualifies. |
| \(R\text{-}\mathsf{Mod}\) | Submodule |
| \(\mathsf{Field}\) | Equalizer SubfieldOrdinary subfields are the usual notion in field theory and may be preferred here. Regular subobjects restrict to subfield inclusions that are equalizers; not every subfield inclusion qualifies. |
| \(\mathsf{Vec}_k\) | (Vector) Subspace |
| \(\mathsf{Top}\) | Subspace |
| \(\mathsf{Haus}\) | Closed Subspace |
| \(\mathsf{Ch}(R)\) | Subcomplex |
| \(\mathsf{AbVar}_k\) | Abelian Subvariety |
| \(\mathsf{Ell}_k\) | Whole Elliptic CurveOnly isomorphisms are regular monomorphisms here. Every isogeny is epic, so any pair it equalizes must already be equal; an equalizer of an equal pair is an isomorphism. |
| \(\mathsf{Meas}\) | Subspace with the Trace \(\sigma\)-Algebra |
| \(\mathsf{Prob}\) | Full-Measure Subspaces (Examples)Every measurable subset of measure 1, with the trace sigma-algebra and restricted measure, gives a regular subobject. Compare its indicator function with the constant function 1, both mapping to a two-point space whose mass is concentrated at 1. This includes the whole space and may include proper subsets. |
| \(\mathsf{Ban}\) | Closed Subspace |
| \(\mathsf{Hilb}\) | Closed Subspace |
| \(\mathsf{Graph}\) | Induced SubgraphOrdinary subgraphs may be preferred when selecting edges as well as vertices, as with paths, matchings, and spanning trees. Induced subgraphs retain every ambient edge between the selected vertices; both notions are standard in graph theory. |
| \(\mathcal{P}(\Sigma^\ast)\) | Whole LanguageOrdinary subobjects are sublanguages, the usual notion of inclusion in language theory. Regular subobjects in this poset are only identities, so the ordinary notion is usually more useful. |
| \(\mathsf{Lang}_\mathrm{P}\) | Polynomial-Time Equivalent ProblemOrdinary subobjects are problems reducible to the given problem in polynomial time, the usual comparison of difficulty. Regular subobjects require reductions in both directions, so the ordinary notion may be preferred. |
For smooth Hausdorff manifolds, an equalizer must have closed image: points of its domain correspond exactly to the points where two smooth maps agree, and the agreement set is closed because the target is Hausdorff. Thus not every embedded submanifold is a regular subobject; the open interval’s inclusion into the real line is a counterexample. We omit a general classification for manifolds from the table.
Sometimes this notion is a bit too strict, like with rings, fields, and languages. Whether we want an “ordinary” subobject or a regular subobject differs by context; the point is that we now have the vocabulary to specify.
Constructing Objects II
We’ve seen the concept of equalizers, which describe the subobject \(S\) of \(A\) telling us where two morphisms \(f\) and \(g\) agree. There is a related notion of a coequalizer, which generalizes the idea of forming a quotient by identifying different elements within an object. Our element-based intuition directs us to generalize the relation like so: given two morphisms \(f, g: B \to A\), for each input \(x\), place \(f(x)\) and \(g(x)\) in the same equivalence class: \(f(x) \sim g(x)\).
But of course, category theory would prefer to avoid definitions relying on the behaviors of elements \(x\) within objects so this definition applies to categories whose objects don’t contain elements. Instead, we can capture the relation by introducing a morphism \(q: A \to Q\) that does this identification for us:
\[q \circ f = q \circ g\]Such a morphism is a coequalizing morphism, which satisfies one of the conditions we’d like. Of course, just like with equalizing morphisms above, it’s too loose: a coequalizing morphism could identify elements in the domain of \(q\) beyond what the element-wise equation \(q(f(x)) = q(g(x))\) demands.
Example (A Coequalizing Morphism in \(\mathsf{Set}\))
Let \(\mathSky{A}=\set{0,1,2,3}\) and let \(\mathAmber{R}\subseteq \mathSky{A}\times \mathSky{A}\) relate two elements when they’re both even or both odd. Define the projections \(r_1,r_2:\mathAmber{R}\to \mathSky{A}\) by
\[r_1(a,b)=a,\qquad r_2(a,b)=b.\]We want to identify \(0\) with \(2\) and \(1\) with \(3\). The constant map \(q:\mathSky{A}\to \set{\ast}\) certainly does:
\[q(0)=q(1)=q(2)=q(3)=\ast.\]Since \(q(a)=q(b)\) for every pair in \(\mathAmber{R}\), we’ve satisfied the equation \(q\circ r_1=q\circ r_2\) necessary for \(q\) to be a coequalizing morphism.
But this is obviously not what we wanted: \(q\) goes beyond our desired equivalence relation. Clearly this definition is not satisfactory.
We need a condition saying that every way of mapping out of \(A\) that coequalizes \(f\) and \(g\) is accounted for: each such morphism must factor uniquely through \(q\). This leads to the following definition. (Which should not be confused with “coequalizing morphism”, despite the similar names.)
Definition (Coequalizer)
Let \(f, g : \mathAmber{B} \to \mathSky{A}\) be morphisms in a category \(\mathsf{C}\). A coequalizer of \(f\) and \(g\) is an object \(\mathRose{Q}\) together with a morphism \(q : \mathSky{A} \to \mathRose{Q}\) such that:
\(q\) is a coequalizing morphism: \(q \circ f = q \circ g\), and
every coequalizing morphism factors uniquely through \(q\): for any morphism \(h : \mathSky{A} \to \mathIndigo{T}\) with \(h \circ f = h \circ g\), there is a unique morphism \(u : \mathRose{Q} \to \mathIndigo{T}\) making the following diagram commute:
so \(u \circ q = h\).
The unique-factorization condition says that every map \(h\) out of \(A\) that identifies the required outputs must pass through \(q\), with \(u \circ q = h\). In sets, this prevents unnecessary identifications: if \(q\) merged two points that some such \(h\) kept distinct, no map \(u\) could recover that distinction. Uniqueness also prevents \(Q\) from carrying extra points whose images under \(u\) would be unconstrained.
Example (Equivalence Relations in \(\mathsf{Set}\) Determine Quotients)
Let \(\mathSky{A} = \set{a,b,c,d}\) and \(\mathAmber{B} = \set{1,2}\), and define
\[\begin{aligned} f(1) &= a &g(1) &= b\\ f(2) &= b &g(2) &= c \end{aligned}\]We identify \(a \sim b\) and \(b \sim c\), so transitivity also identifies \(a \sim c\). The coequalizer has two elements: the classes \(\mathRose{\set{a,b,c}}\) and \(\mathRose{\set{d}}\). Every function \(h\) satisfying \(h \circ f = h \circ g\) is constant on each class, so it defines exactly one function out of this two-element quotient.
In general, the coequalizer in \(\mathsf{Set}\) uses the smallest equivalence relation \(\sim\) containing every pair \((f(b),g(b))\):
\[{\sim}\;=\bigcap\left\{R\subseteq \mathSky{A}\times \mathSky{A}: R\text{ is an equivalence relation and } f(b)\,R\,g(b)\text{ for every }b\in \mathAmber{B}\right\}.\]When the identifications already form an equivalence relation, we apply the same construction to its two projections:
Definition (Quotient)
Let \(\mathSky{A}\) be an object of a category \(\mathsf{C}\), and let \(\mathAmber{R}\) be an equivalence relation on \(\mathSky{A}\), given as a subobject of \(\mathSky{A} \times \mathSky{A}\) with projections \(r_1, r_2 : \mathAmber{R} \to \mathSky{A}\). The quotient \(\mathRose{A / R}\) is the coequalizer of \(r_1\) and \(r_2\), when this coequalizer exists.
The map \(q : A \to A / R\) is the quotient map, and its defining condition says that a morphism out of \(A / R\) is the same thing as a morphism out of \(A\) that “doesn’t distinguish \(R\)-related elements”: in other words, it’s constant on each equivalence class of \(A\) (where that equivalence relation identifies \(a, b \in A\) whenever the tuple \((a, b) \in R\)).
Example (An Equivalence Relation in \(\mathsf{Set}\))
Let \(\mathSky{A}=\set{0,1,2,3}\). We can define an equivalence relation \(\mathAmber{R}\) that equates \(a \sim b\) if they’re both even or both odd. Recall that equivalence relations can be represented by sets, so we end up with
\[\mathAmber{R} = \setbuild{(a, b) \in \mathSky{A} \times \mathSky{A}}{a \equiv b \bmod 2} \subseteq \mathSky{A} \times \mathSky{A}\]which neatly partitions \(\mathSky{A}\) into the equivalence classes \(\mathRose{E}=\set{0,2}\) and \(\mathRose{O}=\set{1,3}\).
We can verify that this does in fact produce a quotient in the category-theoretic sense by further defining the quotient set \(\mathRose{A/R} = \mathRose{\set{E, O}}\) and the quotient map \(q: \mathSky{A} \to \mathRose{A/R}\) by:
\[\begin{aligned} q(0)=q(2)&=\mathRose{E}\\ q(1)=q(3)&=\mathRose{O} \end{aligned}\]and the projections \(r_1, r_2: \mathAmber{R} \to \mathSky{A}\):
\[r_1(a,b)=a, \qquad r_2(a,b)=b\]With all the definitions out of the way, we can verify that because \(q(a)=q(b)\) for all pairs \((a, b)\) in \(\mathAmber{R}\), we have \(q\circ r_1 = q\circ r_2\). We’ve shown \(q\) is a coequalizing morphism.
Now we just need to check unique factorization. Let \(\mathIndigo{T}\) be some arbitrary set and let \(h:\mathSky{A}\to \mathIndigo{T}\) be a function that respects our equivalence relation: \(h(0)=h(2)\) and \(h(1)=h(3)\).
Then there exists a unique function \(u\) such that:
\[u(\mathRose{E})=h(0),\qquad u(\mathRose{O})=h(1).\]The choice of representative doesn’t matter: using \(2\) instead of \(0\), or \(3\) instead of \(1\), gives the same values. Thus \(u\circ q=h\), and these two values determine \(u\) uniquely. We’ve satisfied our unique factorization condition, and we can conclude this construction is a quotient.
Furthermore, a function with \(h(0)\neq h(2)\) can’t factor through \(q\), because the quotient has deliberately “forgotten” that distinction.
| Category | Quotient |
|---|---|
| \(\mathsf{Set}\) | Equivalence Classes \(X / {\sim}\) |
| \(\mathsf{Grp}\) | Quotient Group \(G / N\) |
| \(\mathsf{Ring}\) | Quotient Ring \(A / I\) |
| \(R\text{-}\mathsf{Mod}\) | Quotient Module \(M / N\) |
| \(\mathsf{Field}\) | [No nontrivial quotients] |
| \(\mathsf{Vec}_k\) | Quotient Space \(V / W\) |
| \(\mathsf{Top}\) | Quotient Topology |
| \(\mathsf{Haus}\) | Largest Hausdorff Quotient |
| \(\mathsf{Man}\) | [Not in general] |
| \(\mathsf{Ch}(R)\) | Degreewise Quotient \(C / D\) |
| \(\mathsf{AbVar}_k\) | Quotient \(A / B\) by an Abelian Subvariety |
| \(\mathsf{Ell}_k\) | No Nontrivial CoequalizersEvery isogeny is monic, so a pair admitting a coequalizing arrow must already be equal; its coequalizers are isomorphisms. Geometric quotients by finite subgroup schemes exist, but are not nontrivial categorical coequalizers in this isogeny-only category. |
| \(\mathsf{Meas}\) | Quotient \(\sigma\)-Algebra |
| \(\mathsf{Prob}\) | Pushforward Measure on the Quotient |
| \(\mathsf{Ban}\) | Quotient \(X / Y\) by a Closed Subspace |
| \(\mathsf{Hilb}\) | Quotient \(H / K \cong K^\perp\) by a Closed Subspace \(K\) |
| \(\mathsf{Graph}\) | Quotient Graph |
| \(\mathcal{P}(\Sigma^\ast)\) | Trivial |
| \(\mathsf{Lang}_\mathrm{P}\) | Trivial |
Quotient Maps and Epimorphisms
Reversing the cancellation condition for a monomorphism gives the categorical counterpart of surjectivity:
Definition (Epimorphism)
A morphism \(e : \mathSky{A} \to \mathAmber{B}\) is an epimorphism (or epi) if for any pair of morphisms \(g_1, g_2 : \mathAmber{B} \to \mathIndigo{T}\), \(g_1 \circ e = g_2 \circ e\) implies \(g_1 = g_2\).
An epimorphism is defined by cancellation, not by hitting every element of its target. These notions coincide in sets, groups, and vector spaces, but not in every category:
- In \(\mathsf{Ring}\), the inclusion \(\mathbb{Z} \hookrightarrow \mathbb{Q}\) is an epi even though it’s nowhere near surjective. A ring homomorphism out of \(\mathbb{Q}\) is determined by what it does to \(\mathbb{Z}\), since \(g(1/n)\) has to be \(g(n)^{-1}\).
- In \(\mathsf{Haus}\), the inclusion \(\mathbb{Q} \hookrightarrow \mathbb{R}\) is an epi, because two continuous maps into a Hausdorff space that agree on a dense subset agree everywhere. The epis in \(\mathsf{Haus}\) are exactly the maps with dense image.
Every coequalizer \(q : A \to Q\) is an epi: if two maps out of \(Q\) agree after composition with \(q\), they are two factorizations of the same map out of \(A\), so the coequalizer’s uniqueness condition makes them equal. Thus the quotient maps defined here are epis, but being an epi alone does not supply the coequalizer condition.
Do Quotients Relate to Products?
Quotients unfortunately come from the same overly set-theoretic naming convention that gave us “sum” and “product”: if every equivalence class in a finite set \(X\) has \(k > 0\) elements, then \(\lvert X / R \rvert = \lvert X \rvert / k\); this situation often comes up in group theory, and is essentially Lagrange’s theorem from group theory. So “quotient as division” is about as apt as “product as multiplication”.
But, by sheer coincidence, quotients actually can undo products. The projection \(\pi_B : A \times B \to B\) is itself a quotient map: it identifies \((a, b) \sim (a^\prime, b)\), and \((A \times B) / {\sim} \cong B\). In \(\mathsf{Grp}\), this says \((A \times B) / (A \times \lbrace e \rbrace) \cong B\), and the same holds in \(\mathsf{Set}\) (as long as \(A\) is nonempty), \(\mathsf{Vec}_k\), and \(\mathsf{Top}\) (again, if \(A\) is nonempty).
The converse fails in general. Take \(\mathsf{Grp}\) for example: a normal subgroup \(N\) and the quotient \(G / N\) don’t determine \(G\), which needn’t be \(N \times G / N\). Classifying the ways to glue \(G\) together from them is the extension problem; the short exact sequences in part 3 measure exactly this.
Conclusion
Curiosity killed the cat, but satisfaction brought it back.
— proverb
We’ve covered an enormous amount of ground thus far in this article, and made many very pretty pictures along the way. Let’s take inventory:
| 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. |
Hopefully, this presentation has revealed even more patterns in each of these constructions. All of these constructions have a dual construction, often starting with “co-“; this property of categories is called duality. Furthermore, each of these diagrams (except monos and epis) requires a unique morphism; this condition makes all of our constructions into universal properties.
We’ll dissect these constructions and more in the next article, Patterns in Patterns.
Footnotes
This sometimes runs into foundational issues; see Shulman’s Set Theory for Category Theory. One common extra assumption is the existence of a hierarchy of Grothendieck universes containing the natural numbers, which ZFC alone does not guarantee. ↩