Representables as Building Blocks
The previous page closed with a promissory note. It proved that the
Yoneda embedding
preserves limits,
so that limits of
representable presheaves
taken from the embedded copy of a small category never lead outside the
representables, and then showed that
colimits
behave in the opposite way. When the small category has an initial object, the
colimit of the empty diagram, the embedding fails to send it to the initial
presheaf, which is empty at every object while no representable is
(the presheaf universe).
Far from a defect, that failure is the door through which new objects enter.
Colimits of representables genuinely leave the representables, and this page
proves that they reach everything. Every presheaf whatsoever is a colimit of
representables, in a canonical way.
Two analogies set expectations. Every positive integer is a product of primes, in an
essentially unique way, and the primes are the multiplicative building blocks of arithmetic.
Every presheaf will turn out to be a colimit of representables, canonically though not
uniquely, and the representables are the colimit building blocks of the presheaf universe.
Alternatively, a holomorphic function near the origin is assembled from the monomials
\(z \mapsto z^k\) by scaling and summation, its power series expansion. In the categorical
setting the representables play the role of the monomials, and the assembly operations are
the various kinds of colimit.
Before the general construction, an easy special case shows the whole mechanism
in miniature. Let \(\mathbf{A}\) be the category with exactly two objects \(K\)
and \(L\) and no maps other than the two identities, a discrete category. A
presheaf
\(X\) on \(\mathbf{A}\) has no structure maps to record beyond identities, so it
is just a pair of sets \((X(K), X(L))\), and a natural transformation is just a
pair of functions. The identification
\[
[\mathbf{A}^{\mathrm{op}}, \mathbf{Set}] \cong \mathbf{Set} \times \mathbf{Set}
\]
matches each presheaf with its pair of values.
Under this identification, the two representables become especially simple.
Writing \(\mathbf{1}\) for a fixed one-element set,
\[
\begin{align*}
H_K(K) &= \mathbf{A}(K, K) = \{1_K\}, \\\\
H_K(L) &= \mathbf{A}(L, K) = \emptyset,
\end{align*}
\]
so \(H_K\) corresponds to the pair \((\mathbf{1}, \emptyset)\), and
symmetrically \(H_L\) corresponds to \((\emptyset, \mathbf{1})\).
Now decompose an arbitrary presheaf. A
sum
is a colimit over a discrete category, and two prior results compute sums of
presheaves completely: colimits in the presheaf category are
computed pointwise,
and the
colimit formula in Set,
applied to a diagram with no maps, produces a disjoint union with no
identifications. Sums of presheaves are therefore pointwise disjoint unions.
Suppose for instance that \(X(K)\) has three elements and \(X(L)\) has two. Then
\[
(X(K), X(L)) \cong
(\mathbf{1}, \emptyset) + (\mathbf{1}, \emptyset) + (\mathbf{1}, \emptyset) +
(\emptyset, \mathbf{1}) + (\emptyset, \mathbf{1}),
\]
which is to say
\[
X \cong H_K + H_K + H_K + H_L + H_L
\]
in \([\mathbf{A}^{\mathrm{op}}, \mathbf{Set}]\). The arbitrary presheaf \(X\) is
a sum of representables.
Read the indexing of that sum carefully, because it contains the general idea.
The summands are indexed not by the two objects of \(\mathbf{A}\) but by the
elements of \(X\): one copy of \(H_K\) for each element of \(X(K)\), one copy of
\(H_L\) for each element of \(X(L)\), so the index set is the sum
\(X(K) + X(L)\). The sum is a colimit whose shape is discrete, and here the
index category has the elements of \(X\) as its objects.
For a general presheaf the values \(X(A)\) are related by nontrivial structure
maps, and elements of different values map onto one another, so the index
category can no longer be discrete. It must have the elements of \(X\) as
objects, with maps that remember the action of \(X\) on them. Constructing that
category precisely is the next task.
The Category of Elements
The index category must have one object for each element of the presheaf, wherever that
element lives, and its maps must record how the structure maps of the presheaf carry
elements onto elements. Both requirements are met by the following construction, the one
genuinely new concept of this page.
Definition: Category of Elements
Let \(\mathbf{A}\) be a category and \(X\) a presheaf on \(\mathbf{A}\). The
category of elements \(\mathbf{E}(X)\) of \(X\) has as objects the
pairs \((A, x)\) with \(A \in \mathbf{A}\) and \(x \in X(A)\), and as maps
\((A', x') \to (A, x)\) the maps \(f : A' \to A\) in \(\mathbf{A}\) satisfying
\[
(Xf)(x) = x' .
\]
Composition and identities are those of \(\mathbf{A}\). The projection
functor \(P : \mathbf{E}(X) \to \mathbf{A}\) is given by \(P(A, x) = A\) on
objects and \(P(f) = f\) on maps.
The definition owes the reader two checks. First, the prescribed composites and
identities do stay inside \(\mathbf{E}(X)\). If \(f : (A', x') \to (A, x)\) and
\(g : (A'', x'') \to (A', x')\) are maps of \(\mathbf{E}(X)\), then
\(f \circ g : A'' \to A\) satisfies, by the contravariant functoriality of
\(X\),
\[
\begin{align*}
\big(X(f \circ g)\big)(x)
&= \big(Xg\big)\big((Xf)(x)\big) \\\\
&= (Xg)(x') \\\\
&= x'' ,
\end{align*}
\]
so \(f \circ g\) is a map \((A'', x'') \to (A, x)\). And \(X(1_A) = 1_{X(A)}\)
fixes \(x\), so \(1_A\) is a map \((A, x) \to (A, x)\). Associativity and the
identity laws are inherited from \(\mathbf{A}\), and \(\mathbf{E}(X)\) is a
category. Functoriality of \(P\) is then immediate, since \(P\) leaves maps
untouched.
Second, the direction of the maps deserves a word, because it is the reverse of
what a first glance suggests. A presheaf is contravariant, so a map
\(f : A' \to A\) of \(\mathbf{A}\) induces \(Xf : X(A) \to X(A')\), pulling
elements backward. A map \((A', x') \to (A, x)\) of \(\mathbf{E}(X)\) is exactly
a witness that \(x\) pulls back to \(x'\) along \(f\), and it points the same
way as \(f\) itself.
One finiteness bookkeeping item is load-bearing for what follows. If
\(\mathbf{A}\) is
small,
then \(\mathbf{E}(X)\) is small as well. Its objects are the pairs \((A, x)\)
with \(A\) ranging over the set of objects of \(\mathbf{A}\) and \(x\) over the
set \(X(A)\), and a collection of pairs drawn from a set-indexed family of sets
is a set. Each collection of maps \((A', x') \to (A, x)\) is a subset of the
hom-set \(\mathbf{A}(A', A)\). Consequently every functor out of
\(\mathbf{E}(X)\) is a
diagram
in the standard sense, with a small shape, and the colimits of the previous
pages apply to it without further comment.
The construction has a second description that explains its name and prepares
the theorem of the next section. Recall that a
generalized element
of an object is a map into it, of shape the domain of that map. Take the ambient
category to be \([\mathbf{A}^{\mathrm{op}}, \mathbf{Set}]\) and the object to be
\(X\), and restrict attention to generalized elements of representable shape.
Since a small category is locally small, its hom-collections being subsets of
its set of maps, the
Yoneda lemma
applies and identifies the generalized elements of \(X\) of shape \(H_A\) with
the set \(X(A)\). An object \((A, x)\) of \(\mathbf{E}(X)\) is therefore the
same thing as a representable probe \(H_A \to X\), namely the map classified by
\(x\).
The maps of \(\mathbf{E}(X)\) fit the same picture. Writing
\(\alpha_x : H_A \to X\) for this map, the naturality in \(A\) of the Yoneda
bijection, proved as part of the lemma, states that \(\alpha_x \circ H_f\) is
classified by \((Xf)(x)\). The condition \((Xf)(x) = x'\) is thus equivalent to
the commutativity of the triangle \(\alpha_x \circ H_f = \alpha_{x'}\). In
summary, \(\mathbf{E}(X)\) is the category of representable probes of \(X\) and
of the triangles over \(X\) that connect them.
The discrete example of the opening section passes through the definition
unchanged. For the two-object discrete category and the presheaf \(X\) with
three elements at \(K\) and two at \(L\), every structure map of \(X\) is an
identity, so the condition \((Xf)(x) = x'\) admits only identity witnesses. The
category \(\mathbf{E}(X)\) is the discrete category with five objects, precisely
the index category of the sum that decomposed \(X\).
What remains for the general case is to say what the summands are and how they
vary along the maps of \(\mathbf{E}(X)\). The probe description already answers
in outline: each object \((A, x)\) contributes its representable \(H_A\), each
map \(f\) contributes \(H_f\), and the assignment is the composite of \(P\) with
the Yoneda embedding. Making that diagram official and computing its colimit is
the business of the density theorem.
The Density Theorem
The pieces are assembled. The probe description of the previous section names a
functor out of \(\mathbf{E}(X)\): the composite of the projection with the
Yoneda embedding,
\[
\mathbf{E}(X) \xrightarrow{P} \mathbf{A} \xrightarrow{H_\bullet} [\mathbf{A}^{\mathrm{op}}, \mathbf{Set}] ,
\]
sending each object \((A, x)\) to the representable \(H_A\) and each map \(f\)
to \(H_f\). Since \(\mathbf{E}(X)\) is small, the composite is a diagram of
small shape, and asking for its colimit is legitimate. The theorem that the
previous page promised in closing states that this colimit is \(X\) itself.
Theorem: Density
Let \(\mathbf{A}\) be a small category and \(X\) a presheaf on \(\mathbf{A}\). Then
\(X\) is the colimit of the diagram \(H_\bullet \circ P : \mathbf{E}(X) \to
[\mathbf{A}^{\mathrm{op}}, \mathbf{Set}]\), that is,
\[
X \cong \operatorname{colim}_{\mathbf{E}(X)} \big(H_\bullet \circ P\big) .
\]
A colimit cocone is the tautological one, whose leg at the object \((A, x)\) is the
probe \(\alpha_x : H_A \to X\) classified by \(x\).
Proof
Fix an arbitrary presheaf \(Y \in [\mathbf{A}^{\mathrm{op}}, \mathbf{Set}]\). The plan
is to compute the
cocones
on \(H_\bullet \circ P\) with vertex \(Y\), in three translation steps, and to find that
they are exactly the maps \(X \to Y\).
Cocones as compatible families of probes. A cocone on
\(H_\bullet \circ P\) with vertex \(Y\) is a family of natural
transformations
\[
\big(\alpha_{A,x} : H_A \to Y\big)_{(A,x) \in \mathbf{E}(X)} ,
\]
one leg for each object of \(\mathbf{E}(X)\), such that for every map of
\(\mathbf{E}(X)\) the triangle formed with the two relevant legs commutes. A
map of \(\mathbf{E}(X)\) into the object \((A, x)\) is just a map
\(f : A' \to A\) of \(\mathbf{A}\), its source forced to be
\((A', (Xf)(x))\), and the diagram sends it to \(H_f\). As the target ranges
over all objects, the maps of \(\mathbf{E}(X)\) are exhausted by the pairs
of a map \(f\) and an element it acts on. The cocone condition therefore
reads: for every map \(f : A' \to A\) in \(\mathbf{A}\) and every
\(x \in X(A)\),
\[
\alpha_{A,x} \circ H_f = \alpha_{A',\,(Xf)(x)} .
\]
From probes to elements. The
Yoneda lemma
classifies each leg by an element. Let \(y_{A,x} \in Y(A)\) be the element
corresponding to \(\alpha_{A,x} : H_A \to Y\). The naturality in \(A\) of
the Yoneda bijection, in the form already used in the previous section,
states that \(\alpha_{A,x} \circ H_f\) corresponds to \((Yf)(y_{A,x})\),
while \(\alpha_{A',\,(Xf)(x)}\) corresponds to \(y_{A',\,(Xf)(x)}\) by
definition. Since the bijection is injective, the cocone condition holds if
and only if
\[
(Yf)\big(y_{A,x}\big) = y_{A',\,(Xf)(x)}
\quad \text{for all } f : A' \to A \text{ in } \mathbf{A} \text{ and } x \in X(A).
\]
Cocones on \(H_\bullet \circ P\) with vertex \(Y\) thus correspond
bijectively to families of elements \(\big(y_{A,x}\big)_{(A,x)}\) subject to
this compatibility.
From families of elements to a single map. A family assigning to
each \(A \in \mathbf{A}\) and each \(x \in X(A)\) an element
\(y_{A,x} \in Y(A)\) is the same data as a family of functions
\[
\bar{\alpha}_A : X(A) \to Y(A), \quad \bar{\alpha}_A(x) = y_{A,x} ,
\]
one for each object \(A\). In this notation the compatibility condition just
obtained becomes
\((Yf)\big(\bar{\alpha}_A(x)\big) = \bar{\alpha}_{A'}\big((Xf)(x)\big)\) for
all \(f : A' \to A\) and \(x \in X(A)\), which is exactly the statement that
for every map \(f\) the square
\[
\begin{array}{ccc}
X(A) & \xrightarrow{\bar{\alpha}_A} & Y(A) \\[4pt]
{\scriptstyle X f}\big\downarrow & & \big\downarrow{\scriptstyle Y f} \\[4pt]
X(A') & \xrightarrow{\bar{\alpha}_{A'}} & Y(A')
\end{array}
\]
commutes. Compatible families are therefore exactly the
natural transformations
\(\bar{\alpha} : X \to Y\). Chaining the three steps yields a bijection
\[
\operatorname{Cocone}\big(H_\bullet \circ P, Y\big)
\cong
[\mathbf{A}^{\mathrm{op}}, \mathbf{Set}]\big(X, Y\big) .
\]
Naturality in \(Y\). Let \(\theta : Y \to Y'\) be a map of
presheaves. Post-composition carries a cocone with vertex \(Y\) to one with
vertex \(Y'\), with legs \(\theta \circ \alpha_{A,x}\). By the naturality in
the presheaf variable of the Yoneda bijection, also part of the lemma, the
leg \(\theta \circ \alpha_{A,x}\) is classified by \(\theta_A(y_{A,x})\).
The corresponding map of presheaves therefore has components
\(x \mapsto \theta_A\big(\bar{\alpha}_A(x)\big)\), which are the components
of \(\theta \circ \bar{\alpha}\). The bijection therefore intertwines
post-composition on the two sides and is natural in \(Y\).
Conclusion. The proposition that
limits are representations,
applied in the opposite category
\([\mathbf{A}^{\mathrm{op}}, \mathbf{Set}]^{\mathrm{op}}\), states dually
that representations of the covariant functor
\(\operatorname{Cocone}(H_\bullet \circ P, -)\) correspond to colimit
cocones on \(H_\bullet \circ P\), with representing objects the colimit
objects. Its hypotheses hold here: the shape \(\mathbf{E}(X)\) is small, and
\([\mathbf{A}^{\mathrm{op}}, \mathbf{Set}]\) is locally small, since a
natural transformation between presheaves is a family of functions indexed
by the set of objects of \(\mathbf{A}\), and these families form a subset of
a set-indexed product of function sets. The displayed bijection, natural in
\(Y\), is precisely a representation of this functor with representing
object \(X\). Hence \(X\) is a colimit of \(H_\bullet \circ P\). The colimit
cocone can be identified explicitly. Taking \(\bar{\alpha} = 1_X\) gives
\(y_{A,x} = x\), whose classifying probe is \(\alpha_x : H_A \to X\) itself,
so the cocone corresponding to \(1_X\) is the tautological family
\(\big(\alpha_x\big)_{(A,x)}\). By the naturality of the bijection, the
cocone corresponding to an arbitrary \(\bar{\alpha} : X \to Y\) is the
postcomposite of this family with \(\bar{\alpha}\), and bijectivity makes
that \(\bar{\alpha}\) unique. Every cocone on \(H_\bullet \circ P\) thus
factors uniquely through the tautological family, which is exactly the
universal property defining a
colimit
cocone, as claimed.
The theorem substantiates both halves of the phrase from the opening section:
every presheaf is a colimit of representables in a canonical though not unique
way. Canonical, because the presentation requires no choices whatsoever. The
shape \(\mathbf{E}(X)\), the diagram \(H_\bullet \circ P\), and the cocone of
probes are all manufactured directly from \(X\), with no auxiliary data selected
along the way. Not unique, because nothing forbids other diagrams of
representables from sharing the same colimit. A representable \(H_A\) is already
the colimit of the one-object diagram picking out \(H_A\), a far smaller
presentation than the one through \(\mathbf{E}(H_A)\). The discrete
decomposition of the opening section will turn out to be the density colimit in
disguise rather than a competitor. The theorem does not claim minimality. It
claims availability, uniformly and without choices, for every presheaf at once.
Density in Action
The first test of the general machinery is the example that motivated it. Take
again the discrete example, with its three elements at \(K\) and two at \(L\).
Its category of elements is discrete with five objects, as computed when the
definition was introduced, and the diagram \(H_\bullet \circ P\) sends the three
objects over \(K\) to the representable \(H_K\) and the two objects over \(L\)
to \(H_L\). A colimit over a discrete category is a sum, so the density theorem
asserts
\[
X \cong H_K + H_K + H_K + H_L + H_L ,
\]
which is letter for letter the decomposition found by hand in the opening
section. The ad hoc computation was the density colimit in disguise, and the
general theorem reproduces it with no case analysis, exactly as promised.
The theorem's name comes from a picture in analysis. A subset of a
metric space is dense
when its closure is the whole space, so that every point of the ambient space
can be obtained as a limit of points of the subset. The embedded copy of
\(\mathbf{A}\) plays the role of the subspace, the presheaf category plays the
ambient space, and colimits play the limits of sequences. Every object of
\([\mathbf{A}^{\mathrm{op}}, \mathbf{Set}]\) is a colimit of objects coming from
\(\mathbf{A}\). In this sense \(\mathbf{A}\) sits densely inside its presheaf
category, and the theorem records precisely how each presheaf is approximated,
indeed reached, from the representables.
One structural consequence sharpens the picture of representables as atoms. The
previous page exhibited a single colimit that the Yoneda embedding fails to
preserve. The failure is in fact systematic. Representables can never be
assembled from smaller summands at all.
Proposition: Representables are Indecomposable
Let \(\mathbf{A}\) be a small category. If a representable presheaf \(H_A\) is
isomorphic to a sum \(X + Y\) of presheaves, then \(X\) or \(Y\) is the initial
presheaf, empty at every object. Consequently, the sum of two representables is never
representable.
Proof
Sums of presheaves are pointwise disjoint unions, with coprojections whose
components are the inclusions, since colimits of presheaves are
computed pointwise.
Naturality of the inclusions says exactly that the structure maps of
\(X + Y\) act componentwise. For \(f : B' \to B\), the map \((X+Y)(f)\)
carries \(X(B)\) into \(X(B')\) and \(Y(B)\) into \(Y(B')\).
Let \(\iota : H_A \to X + Y\) be an isomorphism. The identity
\(1_A \in H_A(A)\) lands in one of the two components, say
\(\iota_A(1_A) \in X(A)\). Now every element of every value of \(H_A\) is
generated from \(1_A\). For \(g \in H_A(B) = \mathbf{A}(B, A)\), the
structure map \(H_A(g) : H_A(A) \to H_A(B)\) is precomposition with \(g\),
so \(H_A(g)(1_A) = 1_A \circ g = g\). Naturality of \(\iota\) then gives
\[
\begin{align*}
\iota_B(g)
&= \iota_B\big(H_A(g)(1_A)\big) \\\\
&= \big((X+Y)(g)\big)\big(\iota_A(1_A)\big) \\\\
&\in X(B) ,
\end{align*}
\]
the membership by the componentwise action, since \(\iota_A(1_A) \in X(A)\).
The image of the bijection \(\iota_B\) thus lies entirely in \(X(B)\), and
surjectivity forces \(Y(B) = \emptyset\) for every \(B\). Hence \(Y\) is the
initial presheaf.
For the consequence, suppose \(H_{A'} + H_{A''} \cong H_C\). By the part
just proved, applied to this decomposition of \(H_C\), one of \(H_{A'}\),
\(H_{A''}\) is the initial presheaf. But a representable is never empty at
its own object, since \(H_{A'}(A')\) contains \(1_{A'}\). This contradiction
completes the proof.
The prime analogy of the opening section thus acquires a literal instance. Primes admit no
factorization into smaller positive integers, and representables admit no decomposition
into a sum of two nonempty presheaves. The two results of this page frame the presheaf
universe from opposite sides: the density theorem says the representables generate
everything under colimits, and indecomposability says they are genuine atoms, not
themselves assembled from anything smaller by the most basic colimit of all.
Insight: Primitive Shapes and Their Gluings
The density theorem turns concrete the moment the base category is chosen to
encode combinatorial shape. Take \(\mathbf{A}\) to be the category with two
objects \(V\) and \(E\) and, beyond identities, exactly two maps
\(s, t : V \to E\). A presheaf \(X\) on this category is a set \(X(V)\) of
vertices, a set \(X(E)\) of edges, and two structure maps
\(X(s), X(t) : X(E) \to X(V)\) reading off the source and target of each
edge, in other words a directed multigraph. The two representables are
computed directly from the hom-sets: \(H_V\) has a single vertex and no
edges, and \(H_E\) has two vertices joined by a single edge, its vertex set
\(\mathbf{A}(V, E) = \{s, t\}\).
The density theorem then says that every directed graph, however large, is a
colimit of copies of the one-vertex graph and the single-edge graph, glued
along the maps of the category of elements, and those maps record the
endpoints of every edge. The graph is literally assembled from its atomic
shapes.
This assembly from primitive shapes is the pattern that makes presheaf
categories the ambient setting of choice in compositional accounts of
computation and learning, the point at which the previous page's closing
remark becomes a theorem. A base category records the primitive shapes of a
signal domain, whether vertices and edges, simplices of each dimension, or
the primitive interfaces of a process calculus, and the presheaf universe
supplies every dataset over those shapes. Density guarantees that nothing in
that universe is exotic: every such object, a graph carrying data no less
than a graph alone, decomposes canonically into the primitives, and any
construction that respects colimits is determined by its behavior on the
primitives alone. The representables are at once the probes with which
presheaves are measured, by the Yoneda lemma, and the atoms from which they
are built, by density.
This double role of a single class of objects is the deeper content of the
page, and the starting point for the study of how structure on a base
category extends to structure on everything the base generates.