Representables as Building Blocks
The previous page closed with a promissory note. It proved that the
Yoneda embedding
preserves limits,
so that the limit of a diagram of
representable presheaves
is again representable whenever the underlying diagram already has a limit in the
small category. Its account of
the presheaf universe
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. The
initial presheaf is empty at every object, while no representable is.
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.
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. Second, 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 \(\mathbf{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)\) and one copy of \(H_L\) for
each element of \(X(L)\). The index set is therefore 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 are carried to 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 to 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 item of size bookkeeping 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)\), so the maps of \(\mathbf{E}(X)\), a union of such subsets over
the set of pairs of objects, also form a set. 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 building blocks 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 thus 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. Indeed, 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 claim from the opening section that every
presheaf is a colimit of representables in a canonical though not unique way. The
presentation is canonical because it 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.
Uniqueness fails 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 is
not such a rival presentation, as the next section confirms. 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 subset, the presheaf category plays the ambient space, and colimits
play the part of 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 further structural fact 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. 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, \(X\) is a directed multigraph.
The two representables are computed directly from the hom-sets. The representable
\(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. At this point 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.