Category Theory

Why This Matters

Category theory provides a language for describing structure-preserving maps between mathematical objects. Algebra, topology, logic, and programming language theory all use this language. In ML theory, category theory appears in equivariant neural networks (functors preserving group actions), type-theoretic foundations of programming languages (Cartesian closed categories), and the algebraic structure of probability (the Giry monad).

For most ML practitioners, category theory is not a prerequisite for daily work. But for anyone studying equivariant learning, compositional semantics, or the algebraic foundations of probability, it provides precisely the right abstractions. The Yoneda lemma alone justifies learning the basics: it says that an object is completely determined by how other objects map into it.

Core Definitions

Definition

Category$\mathcal{C}$

A category $\mathcal{C}$ consists of:

1. A collection $\text{Ob}(\mathcal{C})$ of objects
2. For each pair of objects $A, B$, a collection $\text{Hom}(A, B)$ of morphisms (arrows) from $A$ to $B$
3. For each object $A$, an identity morphism $\text{id}_A \in \text{Hom}(A, A)$
4. A composition operation: for $f \in \text{Hom}(A, B)$ and $g \in \text{Hom}(B, C)$, a morphism $g \circ f \in \text{Hom}(A, C)$

Subject to two axioms:

• Associativity: $h \circ (g \circ f) = (h \circ g) \circ f$ for all composable triples
• Identity: $f \circ \text{id}_A = f$ and $\text{id}_B \circ f = f$ for all $f: A \to B$

Definition

Functor$F:\mathcal{C}\to \mathcal{D}$

A functor $F: \mathcal{C} \to \mathcal{D}$ between categories assigns:

1. To each object $A \in \mathcal{C}$, an object $F(A) \in \mathcal{D}$
2. To each morphism $f: A \to B$ in $\mathcal{C}$, a morphism $F(f): F(A) \to F(B)$ in $\mathcal{D}$

Such that:

• $F(\text{id}_A) = \text{id}_{F(A)}$ (preserves identities)
• $F(g \circ f) = F(g) \circ F(f)$ (preserves composition)

A functor is a structure-preserving map between categories.

Definition

Natural Transformation$\eta :F\Rightarrow G$

Given functors $F, G: \mathcal{C} \to \mathcal{D}$, a natural transformation $\eta: F \Rightarrow G$ assigns to each object $A \in \mathcal{C}$ a morphism $\eta_A: F(A) \to G(A)$ in $\mathcal{D}$, such that for every morphism $f: A \to B$ in $\mathcal{C}$, the following square commutes:

$G(f) \circ \eta_A = \eta_B \circ F(f)$

The morphisms $\eta_A$ are called the components of $\eta$. Naturality means the transformation is compatible with all morphisms in the source category.

Standard Examples

The following categories appear throughout mathematics and computer science:

Example

The forgetful functor

The forgetful functor $U: \textbf{Grp} \to \textbf{Set}$ sends each group $(G, \cdot)$ to its underlying set $G$, and each group homomorphism to itself (viewed as a function between sets). It "forgets" the group structure. Similarly, $U: \textbf{Vect}_k \to \textbf{Set}$ forgets the vector space structure.

Example

The free functor

The free functor $F: \textbf{Set} \to \textbf{Grp}$ sends a set $S$ to the free group on $S$ (all finite words in $S \cup S^{-1}$ modulo group axioms). A function $f: S \to T$ extends uniquely to a group homomorphism $F(f): F(S) \to F(T)$. The free functor and the forgetful functor form an adjunction.

Example

Natural transformation: determinant

Consider two functors from the category of commutative rings to the category of groups: the general linear group functor $\text{GL}_n(-)$ and the units functor $(-)^\times$. The determinant $\det: \text{GL}_n(R) \to R^\times$ defines a natural transformation. Naturality means: for any ring homomorphism $\phi: R \to S$, applying $\phi$ entry-wise to a matrix and then taking the determinant equals taking the determinant and then applying $\phi$.

Universal Properties

Definition

Universal Property

An object $U$ in a category has a universal property with respect to a construction if and only if every instance of that construction factors uniquely through $U$. Formally, $U$ is an initial object in a suitable category of solutions. Universal properties determine objects up to unique isomorphism.

Products, coproducts, limits, colimits, free objects, and tensor products are all defined by universal properties. The power of this approach: instead of constructing an object explicitly and then verifying properties, you specify the universal property and deduce that at most one object (up to isomorphism) can satisfy it.

Example

Product as a universal property

The product of objects $A$ and $B$ in a category $\mathcal{C}$ is an object $A \times B$ equipped with projection morphisms $\pi_1: A \times B \to A$ and $\pi_2: A \times B \to B$, such that for any object $X$ with morphisms $f: X \to A$ and $g: X \to B$, there exists a unique morphism $\langle f, g \rangle: X \to A \times B$ with $\pi_1 \circ \langle f, g \rangle = f$ and $\pi_2 \circ \langle f, g \rangle = g$. In Set, this is the Cartesian product. In Grp, it is the direct product. In Top, it is the product topology.

The Yoneda Lemma

The Yoneda lemma is the most important result in basic category theory. It says that an object is completely characterized by its relationships with all other objects.

Definition

Representable Functor$\text{Hom}(A,-)$

For an object $A$ in a locally small category $\mathcal{C}$, the covariant representable functor $\text{Hom}(A, -): \mathcal{C} \to \textbf{Set}$ sends each object $B$ to the set $\text{Hom}(A, B)$ and each morphism $f: B \to C$ to the function $f_* = f \circ -: \text{Hom}(A, B) \to \text{Hom}(A, C)$.

Lemma

Yoneda Lemma

Statement

For any functor $F: \mathcal{C} \to \textbf{Set}$ and any object $A \in \mathcal{C}$, there is a bijection:

$\text{Nat}(\text{Hom}(A, -), F) \cong F(A)$

that is natural in both $A$ and $F$. Here $\text{Nat}(\text{Hom}(A, -), F)$ denotes the set of natural transformations from the representable functor $\text{Hom}(A, -)$ to $F$.

Intuition

A natural transformation $\eta: \text{Hom}(A, -) \Rightarrow F$ is completely determined by $\eta_A(\text{id}_A) \in F(A)$. Given any element $x \in F(A)$, you can reconstruct the entire natural transformation by defining $\eta_B(f) = F(f)(x)$ for each $f: A \to B$. Naturality forces this to be the only possibility. So the "space of natural transformations out of a representable" is just the set $F(A)$.

Proof Sketch

Define the bijection explicitly. Given a natural transformation $\eta: \text{Hom}(A, -) \Rightarrow F$, map it to $\eta_A(\text{id}_A) \in F(A)$. Conversely, given $x \in F(A)$, define $\eta_B(f) = F(f)(x)$ for each $f \in \text{Hom}(A, B)$.

To show $\eta$ is natural: for any $g: B \to C$, we need $F(g) \circ \eta_B = \eta_C \circ g_*$. Evaluating at $f: A \to B$: $F(g)(\eta_B(f)) = F(g)(F(f)(x)) = F(g \circ f)(x) = \eta_C(g \circ f) = \eta_C(g_*(f))$. Functoriality of $F$ gives the third equality.

To show this is a bijection: if $\eta$ is any natural transformation, then naturality forces $\eta_B(f) = F(f)(\eta_A(\text{id}_A))$, so $\eta$ is determined by $\eta_A(\text{id}_A)$.

Why It Matters

The Yoneda lemma has a corollary called the Yoneda embedding: the functor $Y: \mathcal{C}^{op} \to [\mathcal{C}, \textbf{Set}]$ defined by $A \mapsto \text{Hom}(A, -)$ is full and faithful. Since $\text{Hom}(A, -): \mathcal{C} \to \textbf{Set}$ is covariant, it is an object of the functor category $[\mathcal{C}, \textbf{Set}]$; the variance in the source $\mathcal{C}^{op}$ reflects that $\text{Hom}(-, -)$ is contravariant in its first argument. This means every category embeds into a category of "generalized sets." Two objects $A$ and $B$ are isomorphic if and only if $\text{Hom}(A, -)$ and $\text{Hom}(B, -)$ are naturally isomorphic: an object is determined by its morphisms.

Failure Mode

The Yoneda lemma requires a locally small category (hom-sets are actual sets, not proper classes). For large categories where hom-collections are proper classes, the statement must be reformulated using universe enlargement or other size-management techniques. In practice, all categories arising in applications are locally small.

Cite as claim:category-theory::yoneda-lemma

report a correction →

Adjunctions

Definition

Adjunction$F⊣G$

An adjunction between categories $\mathcal{C}$ and $\mathcal{D}$ consists of functors $F: \mathcal{C} \to \mathcal{D}$ (the left adjoint) and $G: \mathcal{D} \to \mathcal{C}$ (the right adjoint) together with a natural bijection:

$\text{Hom}_{\mathcal{D}}(F(A), B) \cong \text{Hom}_{\mathcal{C}}(A, G(B))$

for all objects $A \in \mathcal{C}$ and $B \in \mathcal{D}$. We write $F \dashv G$.

Adjunctions are everywhere:

The currying adjunction $\text{Hom}(X \times A, B) \cong \text{Hom}(X, B^A)$ is the categorical statement that a function of two arguments is the same as a function returning a function. This is the foundation of the Curry-Howard-Lambek correspondence connecting logic, computation, and category theory.

When Category Theory Matters (and When It Does Not)

For ML practitioners, category theory is genuinely useful in these specific areas:

• Equivariant neural networks: a $G$-equivariant map is precisely a natural transformation between certain functors. The classification of equivariant linear maps uses Schur's lemma, which is cleanly stated categorically.
• Type theory and programming languages: Cartesian closed categories model the simply typed lambda calculus. Monads (a categorical concept) structure effects in functional programming.
• Compositional semantics: DisCoCat models in NLP use monoidal functors to map grammatical structure to vector space computations.
• Algebraic probability: the Giry monad gives a categorical framework for probability measures.

For most applied ML work (training models, tuning hyperparameters, engineering features), category theory adds no practical value. The honest assessment: learn it if you work on the topics above or if you want the conceptual unification it provides. Skip it if your work is empirical.

Common Confusions

Watch Out

Categories are not just sets with extra structure

A common first impression is that a category is "a set of objects with arrows." But the objects of a category need not form a set (they can form a proper class, as in Set itself). The morphisms carry the real information: two categories with the same objects but different morphisms are completely different. The arrows, not the objects, are what matter.

Watch Out

Functors preserve structure; they do not create it

A functor $F: \mathcal{C} \to \mathcal{D}$ must preserve composition and identities. It cannot "add" relationships that do not exist in the source. If there is no morphism from $A$ to $B$ in $\mathcal{C}$, the functor says nothing about the relationship between $F(A)$ and $F(B)$ beyond what is implied by the existing morphisms.

Watch Out

Isomorphism in a category is not equality

Two objects $A$ and $B$ are isomorphic ($A \cong B$) if and only if there exist morphisms $f: A \to B$ and $g: B \to A$ with $g \circ f = \text{id}_A$ and $f \circ g = \text{id}_B$. In Set, this means a bijection. In Top, a homeomorphism. Category theory works up to isomorphism, not equality. The principle of equivalence: no categorical construction should distinguish between isomorphic objects.

Exercises

ExerciseCore

Problem

Verify that vector spaces over a field $k$ and linear maps form a category Vect$_k$. Specifically, check that composition of linear maps is linear and that the identity map is linear.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Prove the Yoneda lemma for the special case $F = \text{Hom}(B, -)$. That is, show:

$\text{Nat}(\text{Hom}(A, -), \text{Hom}(B, -)) \cong \text{Hom}(B, A)$

and explain why this means the Yoneda embedding is full and faithful.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Show that the free-forgetful adjunction $F \dashv U$ between Grp and Set satisfies $\text{Hom}_{\textbf{Grp}}(F(S), G) \cong \text{Hom}_{\textbf{Set}}(S, U(G))$ by describing both sides explicitly when $S = \{a, b\}$ and $G = \mathbb{Z}$.

Hint

Reveal Solution

ExerciseResearch

Problem

A $G$-equivariant neural network layer is a map $\phi: V \to W$ between $G$-representations satisfying $\phi(\rho_V(g) \cdot x) = \rho_W(g) \cdot \phi(x)$ for all $g \in G$. Express this condition as a natural transformation between appropriate functors. What does the Yoneda perspective tell you about classifying such maps?

Hint

Reveal Solution

References

Canonical:

• Mac Lane, Categories for the Working Mathematician (1998), Chapters 1-4 for categories, functors, natural transformations, and adjunctions
• Awodey, Category Theory (2010), Chapters 1-8 for a modern introduction at the graduate level
• Riehl, Category Theory in Context (2016), Chapters 1-6, particularly Chapter 2 for the Yoneda lemma

Accessible:

• Leinster, Basic Category Theory (2014), Chapters 1-4 for a concise treatment aimed at beginners
• Fong & Spivak, An Invitation to Applied Category Theory (2019), for applications-oriented readers

ML connections:

• Shiebler, Gavranovic, Wilson, "Category Theory in Machine Learning" (2021 survey), Sections 2-5 on equivariant networks and compositional models

Next Topics

• Sets, functions, and relations: the prerequisite set theory that categories generalize
• Dependent type theory: where Cartesian closed categories meet proof theory