Categories & Functors

Overview & Motivation

Machine learning is built on composition. A neural network is a sequence of layers applied one after the other. A data pipeline chains transformations end-to-end. A probabilistic model threads random variables through a sequence of conditional distributions. In every case, the structure that matters is not what the individual pieces are but how they compose.

Category theory makes composition the central idea. A category is a collection of objects and morphisms (structure-preserving maps) between them, equipped with a composition operation that satisfies two axioms: associativity and the existence of identities. That’s it — and from these two axioms, an enormous amount of structure follows.

Why should an ML practitioner care? Because the categories that matter to us are the ones we already work in:

• Vec — the category of vector spaces and linear maps. Every neural network layer is a morphism in Vec (or a nonlinear enrichment of it). The Spectral Theorem guarantees that symmetric endomorphisms in Vec have complete eigenbases.
• Meas — the category of measurable spaces and measurable functions. Every random variable is a morphism in Meas. The entire apparatus of measure-theoretic probability is the study of this category’s structure.
• Set — the category of sets and functions. Data transformations, feature maps, and loss functions are all morphisms in Set.
• Top — the category of topological spaces and continuous maps. Topological data analysis works in Top and its subcategories.

The power of category theory is not that it replaces these concrete settings — it is that it reveals the compositional patterns they share. A functor is a structure-preserving map between categories: it takes objects to objects and morphisms to morphisms, preserving composition and identities. The forgetful functor from Vec to Set “forgets” the linear structure and remembers only the underlying set. The adjacency matrix construction is a functor from the category of graphs to Vec. Recognizing these as instances of the same concept — functor — is what lets us transfer techniques across domains.

What we cover:

1. Categories — objects, morphisms, composition, identity, and the two axioms.
2. A gallery of categories — the concrete categories that ML practitioners work in daily.
3. Morphism types — isomorphisms, monomorphisms, epimorphisms, endomorphisms, automorphisms.
4. Functors — covariant and contravariant structure-preserving maps between categories.
5. Opposite categories, Cat, and endofunctors — the category of categories, duality, and self-maps.
6. Products, coproducts, and universal properties — characterizing constructions by what they do.
7. The Hom functor — the functor that reframes linear algebra.
8. Computational notes — categories and functors in Python, neural networks as categorical composition.

---

Categories: Objects, Morphisms, and Composition

The central idea is composition. Before we give the formal definition, consider what composition means concretely: if $f: A \to B$ is a function from set $A$ to set $B$, and $g: B \to C$ is a function from $B$ to $C$, then the composite $g \circ f: A \to C$ is the function that first applies $f$, then applies $g$. This composite is associative — $(h \circ g) \circ f = h \circ (g \circ f)$ — and every set has an identity function $\mathrm{id}_A: A \to A$ that acts as a no-op for composition. A category axiomatizes exactly these two properties.

The definition requires remarkably little: objects, arrows between them, a way to compose arrows, identity arrows, and two axioms. Notice what it does not require — it says nothing about what objects or morphisms “are” internally. A morphism is not required to be a function, and an object is not required to be a set. This generality is the source of the theory’s power.

The following explorer lets you build small categories from scratch and verify the axioms interactively. Try the presets to see how different structures — a simple chain of arrows, a partially ordered set, even a monoid — all satisfy the same two axioms.

Category:Two Objects (one arrow)Three Objects (triangle)Poset {a ≤ b ≤ c}Monoid (ℤ/3, +)Discrete (3 objects)IdentitiesComposition table

Composition table (g ∘ f)

g ∖ f	id_A	id_B	f
id_A	id_A	—	—
id_B	—	id_B	f
f	f	—	—

✓Associativity: All composable triples

✓Identity law: All objects

Objects = colored circlesMorphisms = directed arrowsDashed loops = identity morphismsTable cell = g ∘ f (or — if not composable)

---

A Gallery of Categories

The power of the definition comes from the range of examples it encompasses. Here are the categories that ML practitioners encounter regularly. In every case, the pattern is the same: objects are mathematical structures, and morphisms are the maps that preserve that structure.

Category	Objects	Morphisms	Composition	Identity
Set	Sets	Functions	Function composition	Identity function
Vec$_\mathbb{R}$	Real vector spaces	Linear maps	Matrix multiplication	Identity matrix
Grp	Groups	Group homomorphisms	Composition of homomorphisms	Identity homomorphism
Top	Topological spaces	Continuous maps	Composition	Identity map
Meas	Measurable spaces	Measurable functions	Composition	Identity function

Set is the most familiar category. Its objects are sets, its morphisms are functions between sets, and composition is ordinary function composition. For an ML practitioner, Set is the category of data transformations: feature maps, loss functions, and evaluation metrics are all morphisms in Set.

Vec$_\mathbb{R}$ is the workhorse of machine learning. Its objects are finite-dimensional real vector spaces, and its morphisms are linear maps. Every fully connected neural network layer (before the activation function) is a morphism in Vec — a matrix multiplication $\mathbf{x} \mapsto W\mathbf{x}$. The Spectral Theorem tells us that symmetric endomorphisms in Vec have complete eigenbases — a fact that drives spectral methods throughout ML.

Meas is the category of measure-theoretic probability. Its objects are measurable spaces $(X, \mathcal{F})$, and its morphisms are measurable functions. A random variable $X: (\Omega, \mathcal{F}) \to (\mathbb{R}, \mathcal{B}(\mathbb{R}))$ is a morphism in Meas. Composition of random variables corresponds to chaining probabilistic transformations.

Beyond these standard examples, there are categories built from algebraic structures:

• Posets as categories. Any partially ordered set $(P, \leq)$ defines a category: the objects are the elements of $P$, and there is exactly one morphism from $a$ to $b$ if and only if $a \leq b$. Composition is transitivity: if $a \leq b$ and $b \leq c$, then $a \leq c$. The identity morphism on $a$ is the reflexivity $a \leq a$.

• Monoids as one-object categories. A monoid $(M, \cdot, e)$ — a set with an associative binary operation and an identity element — is a category with a single object $*$. The morphisms are the elements of $M$, composition is the monoid operation $\cdot$, and the identity morphism is $e$. The integers $(\mathbb{Z}, +, 0)$ form a one-object category with morphisms $\ldots, -2, -1, 0, 1, 2, \ldots$

• Discrete categories. A set $S$ with no structure beyond its elements forms a discrete category: the objects are the elements of $S$, and the only morphisms are the identities. Every object is an island.

---

Morphism Types

Within a category, morphisms have special properties that generalize familiar notions from set theory — injectivity, surjectivity, and bijectivity — to the abstract setting.

In Set, monomorphisms are exactly injective functions and epimorphisms are exactly surjective functions. But this correspondence does not hold in every category.

In Vec, an endomorphism of $\mathbb{R}^n$ is an $n \times n$ matrix. An automorphism is an invertible matrix — an element of the general linear group $\mathrm{GL}(n, \mathbb{R})$.

---

Functors: Structure-Preserving Maps Between Categories

If categories are mathematical universes with their own objects and composition laws, then functors are the translations between universes. A functor maps objects to objects and morphisms to morphisms, preserving the composition structure.

Key examples:

• Forgetful functor $U: \mathbf{Vec} \to \mathbf{Set}$. Sends each vector space $V$ to its underlying set $U(V)$ (forgetting the linear structure) and each linear map $T$ to the underlying function $U(T)$. This “forgets” the algebraic structure — a vector space is just a set with extra properties, and a linear map is just a function that happens to be linear.

• Free functor $F: \mathbf{Set} \to \mathbf{Vec}$. Sends each set $S$ to the free vector space $F(S) = \mathbb{R}^S$ (with basis elements indexed by $S$) and each function $f: S \to T$ to the linear extension $F(f): \mathbb{R}^S \to \mathbb{R}^T$. This “freely adds” linear structure.

• Power set functor $P: \mathbf{Set} \to \mathbf{Set}$. Sends each set $X$ to its power set $P(X) = 2^X$ and each function $f: X \to Y$ to the direct image map $P(f): P(X) \to P(Y)$ defined by $P(f)(S) = f(S) = \{f(x) \mid x \in S\}$.

The following visualizer shows how functors map objects and morphisms between categories. Select a functor from the dropdown to see the mapping in action — notice how the connecting arrows show which objects and morphisms correspond, and how the axiom verifier confirms that composition and identities are preserved.

Functor:Forgetful: Vec → SetFree: Set → VecIdentity: C → CContravariant: Dual V*

Functor Axiom Verification

Identity preservation

✓F(id_ℝ) = id_{{1,2}}✓F(id_ℝ²) = id_{{a,b,c}}✓F(id_ℝ³) = id_{{x}}

Composition preservation

✓F(S∘T) = g∘f [g∘f]

Hover an object to highlight its mapping● Source● Target⇢ Functor map

---

Opposite Categories, Cat, and Endofunctors

The opposite category is a powerful tool for duality. Every theorem about categories has a dual theorem obtained by replacing $\mathcal{C}$ with $\mathcal{C}^{\mathrm{op}}$. Under this substitution, source and target swap, monomorphisms become epimorphisms, products become coproducts, and initial objects become terminal objects. We get two theorems for the price of one.

A contravariant functor $F: \mathcal{C} \to \mathcal{D}$ is the same thing as a covariant functor $F: \mathcal{C}^{\mathrm{op}} \to \mathcal{D}$. This reformulation often simplifies proofs — instead of tracking arrow reversals, we simply work with the opposite category.

The category Cat. Small categories themselves form a category, written Cat:

• Objects: Small categories (those whose objects and morphisms form sets).
• Morphisms: Functors between categories.
• Composition: Functor composition — $(G \circ F)(A) = G(F(A))$ on objects, $(G \circ F)(f) = G(F(f))$ on morphisms.
• Identity: The identity functor $\mathrm{Id}_\mathcal{C}: \mathcal{C} \to \mathcal{C}$ sending every object and morphism to itself.

Endofunctors. A functor $F: \mathcal{C} \to \mathcal{C}$ from a category to itself is an endofunctor. Endofunctors can be iterated: $F^2 = F \circ F$, $F^3 = F \circ F \circ F$, and so on. The power set functor $P: \mathbf{Set} \to \mathbf{Set}$ is an endofunctor.

A functor $F: \mathcal{C} \to \mathcal{D}$ is:

• Faithful if $F$ is injective on each Hom set: $F(f) = F(g) \implies f = g$ for all $f, g: A \to B$.
• Full if $F$ is surjective on each Hom set: every morphism $F(A) \to F(B)$ in $\mathcal{D}$ is of the form $F(f)$ for some $f: A \to B$ in $\mathcal{C}$.
• Fully faithful if $F$ is bijective on each Hom set. A fully faithful functor is an “embedding” — it identifies $\mathcal{C}$ with a subcategory of $\mathcal{D}$.

The forgetful functor $U: \mathbf{Vec} \to \mathbf{Set}$ is faithful (distinct linear maps are distinct as functions) but not full (not every function between vector spaces is linear).

---

Products, Coproducts, and Universal Properties

Category theory characterizes mathematical constructions not by what they are made of but by what they do. The tool for this is the universal property: a construction is defined by being the best solution to a particular mapping problem. This is a profound shift in perspective — from internal structure to external relationships.

The word “unique” in the definition is doing all the work. Many objects might come equipped with morphisms to $A$ and $B$, but the product is the one through which all such morphisms factor uniquely.

The concrete meaning of products and coproducts depends on the category:

Category	Product $A \times B$	Coproduct $A \sqcup B$
Set	Cartesian product	Disjoint union
Vec	Direct sum $A \oplus B$	Direct sum $A \oplus B$
Grp	Direct product	Free product
Top	Product topology	Disjoint union topology
Poset	Meet (greatest lower bound)	Join (least upper bound)

In Vec, the product and coproduct coincide — both are the direct sum. This is a special property of abelian categories.

In Set, the initial object is the empty set $\emptyset$ (there is exactly one function $\emptyset \to X$ for any set $X$ — the empty function), and the terminal object is any singleton set $\{*\}$ (for any set $X$, the unique function $X \to \{*\}$ sends everything to $*$). In Vec, the zero vector space $\{0\}$ is both initial and terminal — a zero object.

ProductCoproductInitialTerminal

Category:SetVecPosetShow concrete values

π₁ ∘ h = f and π₂ ∘ h = g where h = ⟨f, g⟩

Structural morphismsUser-defined morphismsUnique mediating morphism

---

The Hom Functor

The Hom functor is one of the most important constructions in category theory. It takes two objects and produces their “space of maps” — and this construction is itself functorial.

The Hom functor concretizes linear algebra. In Vec, $\mathrm{Hom}(\mathbb{R}^m, \mathbb{R}^n)$ is the space of all linear maps from $\mathbb{R}^m$ to $\mathbb{R}^n$ — which is isomorphic to $\mathrm{Mat}(n \times m)$, the space of $n$-by-$m$ matrices. The covariant Hom functor $\mathrm{Hom}(\mathbb{R}^m, -)$ sends a vector space $V$ to the matrix space $\mathrm{Mat}(\dim V \times m)$ and sends a linear map $T: V \to W$ to post-composition by $T$ — which is matrix multiplication on the left.

A functor $F: \mathcal{C} \to \mathbf{Set}$ is representable if it is naturally isomorphic to $\mathrm{Hom}(A, -)$ for some object $A$. The representing object $A$ is unique up to isomorphism. Representable functors are ubiquitous: the functor sending a group to its underlying set is representable (represented by $\mathbb{Z}$), and the functor sending a vector space to its dual is represented by the ground field.

The Yoneda Lemma — the deepest result in basic category theory — says that natural transformations from $\mathrm{Hom}(A, -)$ to any functor $F$ are in bijection with elements of $F(A)$. We develop the Yoneda Lemma fully in Natural Transformations.

---

Computational Notes

Categories and functors are not only abstract mathematics — they have direct computational implementations. Here we show how to represent finite categories in Python and verify functorial properties programmatically.

A Python category class. A finite category can be represented as a dictionary of Hom sets with a composition function:

class Category:
    """A finite category with explicit objects, morphisms, and composition."""
    def __init__(self, objects, hom, comp_table, identity):
        self.objects = objects          # list of object labels
        self.hom = hom                 # dict: (A, B) -> list of morphism labels
        self.comp_table = comp_table   # dict: (g, f) -> g ∘ f label, or absent
        self.identity = identity       # function: A -> id_A label

    def compose(self, g, f):
        """Return g ∘ f if composable, else None."""
        return self.comp_table.get((g, f))

# Example: the triangle category {A, B, C}
triangle = Category(
    objects=['A', 'B', 'C'],
    hom={
        ('A','A'): ['id_A'], ('B','B'): ['id_B'], ('C','C'): ['id_C'],
        ('A','B'): ['f'],    ('B','C'): ['g'],    ('A','C'): ['gf'],
    },
    comp_table={
        ('g','f'): 'gf', ('id_B','f'): 'f', ('g','id_B'): 'g',
        ('id_A','id_A'): 'id_A', ('gf','id_A'): 'gf',
        ('id_C','gf'): 'gf', ('id_C','g'): 'g', ('f','id_A'): 'f',
        ('id_B','id_B'): 'id_B', ('id_C','id_C'): 'id_C',
    },
    identity=lambda A: f'id_{A}',
)

A functor class with axiom verification:

class Functor:
    """A functor F: C -> D with axiom checking."""
    def __init__(self, source, target, on_objects, on_morphisms):
        self.source = source
        self.target = target
        self.on_obj = on_objects       # dict: src_obj -> tgt_obj
        self.on_mor = on_morphisms     # dict: src_mor -> tgt_mor

    def verify_identities(self):
        """Check F(id_A) = id_{F(A)} for all objects. Returns (ok, violations)."""
        violations = []
        for A in self.source.objects:
            src_id = self.source.identity(A)
            tgt_id = self.target.identity(self.on_obj[A])
            if self.on_mor[src_id] != tgt_id:
                violations.append(A)
        return len(violations) == 0, violations

    def verify_composition(self):
        """Check F(g ∘ f) = F(g) ∘ F(f) for composable pairs. Returns (ok, violations)."""
        violations = []
        for g_label in sum(self.source.hom.values(), []):
            for f_label in sum(self.source.hom.values(), []):
                gf = self.source.compose(g_label, f_label)
                if gf is not None:
                    Fgf = self.on_mor[gf]
                    Fg_Ff = self.target.compose(self.on_mor[g_label], self.on_mor[f_label])
                    if Fgf != Fg_Ff:
                        violations.append((g_label, f_label))
        return len(violations) == 0, violations

Neural networks as categorical composition. A feedforward neural network is a sequence of morphisms in (an enrichment of) Vec:

import torch.nn as nn

# A 3-layer network: R^784 → R^256 → R^128 → R^10
# Each layer is a morphism in Vec (before activation)
network = nn.Sequential(
    nn.Linear(784, 256),   # f: R^784 → R^256
    nn.ReLU(),
    nn.Linear(256, 128),   # g: R^256 → R^128
    nn.ReLU(),
    nn.Linear(128, 10),    # h: R^128 → R^10
)
# The composite h ∘ g ∘ f: R^784 → R^10 is associative
# by construction — (h ∘ g) ∘ f = h ∘ (g ∘ f)

The following explorer demonstrates associativity concretely. Select a category — Set, Vec, or Poset — and step through the composition of three morphisms. Both parenthesizations produce the same result, making associativity visceral rather than axiomatic.

Category:SetVecPoset

PlayResetStep →Step 0 / 3

Associativity: h \u2218 (g \u2218 f) = (h \u2218 g) \u2218 fStep through both parenthesizations to see they produce the same composite morphism.

---

Connections & Further Reading

Where this fits

Categories and functors are the foundation of the Category Theory track. Everything that follows builds on the definitions and examples introduced here:

• Natural Transformations — Natural transformations are morphisms between functors — the next level of abstraction. The Yoneda lemma, which characterizes objects by their morphisms, is the deepest result in basic category theory. Equivariance of neural networks is precisely the naturality condition.

• Adjunctions — formalizes the free-forgetful pair $F \dashv U$ between Set and Vec as the prototypical adjunction. The unit-counit formulation, Galois connections, RAPL theorem, and connections to Lagrangian duality and attention mechanisms.

• Monads & Comonads — develops monads as monoids in the category of endofunctors $[\mathcal{C}, \mathcal{C}]$, with the Giry monad providing the categorical foundation of Bayesian probability and the neighborhood comonad unifying GNN message passing — the culmination of the Category Theory track.

Cross-track connections

The language of categories and functors connects to every prior track on formalML:

• The Spectral Theorem guarantees that symmetric endomorphisms in Vec have complete eigenbases — the eigendecomposition of the graph Laplacian, the covariance matrix in PCA, and the kernel matrix in SVMs all rely on this fact about the category Vec.

• Measure-Theoretic Probability works in the category Meas of measurable spaces. Random variables are morphisms, and the pushforward of probability measures is a functor.

• The category of graphs and graph homomorphisms is a concrete example where the adjacency matrix construction is a functor from Graph to Vec.

• Smooth Manifolds form a category Man where the tangent bundle construction $T: \mathbf{Man} \to \mathbf{VectBund}$ is a functor.

• Convex Analysis: convex sets and affine maps form a category where products are Cartesian products and the subdifferential is functorial.

Notation summary

Symbol	Meaning
$\mathcal{C}, \mathcal{D}$	Categories
$\mathrm{Ob}(\mathcal{C})$	Objects of $\mathcal{C}$
$\mathrm{Hom}(A, B)$	Morphisms from $A$ to $B$
$f: A \to B$	A morphism from $A$ to $B$
$g \circ f$	Composition (apply $f$ first, then $g$)
$\mathrm{id}_A$	Identity morphism on $A$
$F: \mathcal{C} \to \mathcal{D}$	Functor from $\mathcal{C}$ to $\mathcal{D}$
$\mathcal{C}^{\mathrm{op}}$	Opposite category
$A \times B$	Product
$A \sqcup B$	Coproduct
$\pi_1, \pi_2$	Projections
$\iota_1, \iota_2$	Inclusions
$\exists!\, h$	Unique existence
$\mathrm{End}(A)$	Endomorphisms of $A$
$\mathrm{Aut}(A)$	Automorphisms of $A$
$A \cong B$	$A$ is isomorphic to $B$
$\mathbf{Set}, \mathbf{Vec}, \mathbf{Grp}, \mathbf{Top}, \mathbf{Meas}$	Named categories
$\mathbf{Cat}$	Category of small categories