previous: categories, functors and natural transformations in SET
home: sheaves and stacks
next: universal constructions – adjunction, limit and Kan extension
internal to$SET$;
we now define a notion of a category $Set$ of small sets internal to $SET$;
in terms of this, we obtain notions of
category of presheaves with values in small sets.
the notion of presheaf category leads to the concept of representable functor and then to the deepest triviality known to humanity, the Yoneda lemma;
this leads to the notion of universal constructions which are the heart of category theory.
We close with the central example
which leads over to the triptychon of universal constructions
which are the topic of the next part.
Elementary Theory of the Category of Sets:
the set of objects $Obj(Set)$ in $SET$ should behave like a “set of all sets”;
clearly, $Obj(Set)$ can’t “be” the collection of objects of $SET$, since whatever that is, it is not in turn an object of $SET$
but as before with the definition of $SET$ itself, it matters not so much what $Obj(Set)$ is itself, as rather how operations on it are performed: if all operations that one would expect to perform on the collection of all sets can be performed on $Obj(Set)$, then it serves that purpose
this idea is formalized by the notion of a
Grothendieck universe: a set $U$ that admits all the
operations which are expected on the “collection of all sets”: for instance for each element $s \in U$ there should be an element $p(s) \in U$ which plays the role of the power set of the set $s$;
A universe in $SET$ is a morphism $el:E\to U$ satisfying the axioms to follow. We think of $el:E\to U$ as a $U$-indexed family of objects (sets), and we define a morphism $a:A\to I$ (regarded as an $I$-indexed family of objects) to be $U$-small if there exists a morphism $f:I\to U$ and a pullback square
Note that $f$ is not, in general, unique: a universe can contain many isomorphic sets. With this definition, the pullback of a $U$-small morphism is automatically again $U$-small. We say that an object $X$ is $U$-small if $X\to 1$ is $U$-small.
The axioms which must be satisfied are the following four.
Every monomorphism is $U$-small.
The composite of $U$-small morphisms is $U$-small.
The two-element set $\Omega = \mathbf{2} = P(*)$, called the subobject classifier is $U$-small.
If $f:A\to I$ and $g:B\to A$ are $U$-small, then so is the dependent product $\Pi_f g$ (where $\Pi_f$ is the right adjoint to $f^*:\mathcal{E}/I\to \mathcal{E}/A$).
This last condition involves concepts we haven’t introduced yet, but we now spell out the relevant implications of these four axioms in familiar language, which is all we will actually need in the following.
Write $*$ for the terminal object in $SET$, the singleton set. Notice that for each ordinary element $u \in U$, i.e. $* \stackrel{u}{\to} U$, there is the set $E_u$ over $u$, defined as the pullback
We think of $E$ as being the disjoint union over $U$ of the $E_u$.
By the definition of $U$-smallness and the notation just introduced, an object $S$ in $SET$, regarded as a $*$-indexed family $S \to *$, is $U$-small precisely if it is isomorphic to one of the $E_u$.
If $S$ is a $U$-small set by the above and if $S_0 \hookrightarrow S$ is a monomorphism so that $S_0$ is a subset of $S$, it follows from 1) and 2) that the comoposite $(S_0 \hookrightarrow S \to *) = (S_0 \to *)$ is $U$-small, hence that $S_0$ is $U$-small. So: a subset of a $U$-small set is $U$-small.
Let $S$, $T$ and $K$ be objects of $SET$, regarded as $*$-indexed families $f : S \to *$, $T \to *$ and $K \to *$. Notice that $(SET\downarrow S)(f^* K, f^* T) \simeq (SET\downarrow S)(\array{K \times S \\ \downarrow^{p_2} \\ S}, \array{T \times S \\ \downarrow^{p_2} \\ S})$ is canonically isomorphic to $SET(K \times S, T)$. Since $\Pi_f$ is defined to be the right adjoint to $f^* : SET \to SET \downarrow S$ it follows that $\Pi_f f^* T \simeq T^S$ is the function set of functions from $S$ to $T$. By 3), if $S$, $T$ are $U$-small then so is the function set $T^S$.
Let $I$ be a $U$-small set, in that $I \to *$ is $U$-small, and let $S \to I$ be $U$-small, to be thought of as an $I$-indexed family of $U$-small sets $S_i$, where $S_i$ is the pullback $\array{ S_i &\to& S \\ \downarrow && \downarrow \\ * &\stackrel{i}{\to}& I }$, so that $S$ is the disjoint union of the $S_i$: $S = sqcup_{i \in I} S_i$. By axiom 2) the composite morphism $(S \to I \to *) = (S \to *)$ is $U$-small, hence $S$ is a $U$-small set, hence the $I$-indexed union of $U$-small sets $\sqcup_{i \in I} S_i$ is $U$-small.
By standard constructions in set theory from these properties the following further closure properties of the universe $U$ follow.
In summary
the sets $\emptyset, *, \mathbf{2}$ are $U$-small;
a subset of a $U$-small set is $U$-small;
the power set $P(S)$ of any $U$-small set is $U$-small;
the function set $T^S$ for any two $U$-small sets is $U$-small;
the union of a $U$-small family of $U$-small sets is $U$-small.
the product of a $U$-small family of $U$-small sets is $U$-small.
In order to make use of this we impose one more axiom on $SET$:
Axiom of universes
For every $S$ in the collection of objects of $SET$, there exists a universe $E \to U$ in $SET$ such that $S$ is $U$-small, i.e. such that there is $u \in U$ and $S \simeq E_u$.
We now fix a universe $E \to U$ once and for all.
Definition
The category denoted $U Set$ – or just $Set$ if the universe $U$ is understood – is the category given by
$Obj(Set) = U$;
for all $s,t \in U$ let $Set(s,t) := E_t^{E_s}$ be the function set of functions from $E_s$ to $E_t$;
$Mor(Set) = \sqcup_{s,t \in U} Set(s,t)$
with the obvious composition operation induced from the comoposition on function sets.
Remark There is a precise sense in which $Set$ is “like” $SET$: the category $Set$ of $U$-small sets is what is called an internal topos-object.
Definition A category $C$ in $SET$ is locally $U$-small if for all ordinary elements $x,y \in Obj(C)$ the hom-set $Hom_C(x,y)$ is $U$-small.
Here $Hom_C(x,y)$ is the pullback
in $SET$.
A category $C$ in $SET$ is $U$-small – or small if the universe $U$ is understood – if it is locally $U$-small and $Obj(C)$ is $U$-small.
It follows that for a $U$-small category also $Mor(C)$ is $U$-small.
A category is essentially $U$-small – or essentially small if the universe $U$ is understood – if it is equivalent to a $U$-small category.
Remarks
Examples: The classical categories
In terms of this we have now the “classical” large categories of small sets with extra structure:
Definition
For $C$, $D$ two categories, there is a set $[C,D]_0 \subset D_1^{C_1}$ of functors between them.
With natural transformations between them as morphisms, $[C,D]_1 \subset D_1^{C_0}$, this yields a category, $[C,D]$, the functor category between $C$ and $D$.
Example
our main example of interest are presheaf categories, discussed in the following;
for $A$ (respectively $G$) a monoid (respectively a group) and $\mathbf{B}A$ ($\mathbf{B}G$) the corresponding category, $[\mathbf{B}A, \mathbf{B}A]$ (respectively $[\mathbf{B}G, \mathbf{B}G]$) is the category (a groupoid) whose objects are the endomorphisms of $A$ (of $G$) and whose morphisms are intertwiners between these.
We still keep a universe $U$ fixed once and for all and say “small” for “$U$-small”, write $Set$ for $U Set$, etc.
Definition
A presheaf on a category $C$ is nothing but a functor $C^{op} \to Set$.
The point of calling these presheaves instead of just functors is two-fold:
calling a functor a presheaf indicates that one intends to regard it in the context of the Yoneda embedding, to be discussed below;
calling a functor a presheaf indicates that one intends to consider the structure of a site on $C$ and to ask if the functor satisfies the
sheaf condition (both to be discussed later in gluing – coverage and sheaves).
For $C$ a small category, we call the functor category
the presheaf category of $C$ and call
the co-presheaf category of $C$.
Remark Recall what the morphisms $\eta : F \to G$ in $[C^{op},Set]$ are like: for each object $c \in C$ these are given by maps of sets $\eta_c : F(c) \to G(c)$ such that for all morphisms $f : c \to d$ in $C$ these squares commute
Observation
But
Proof. An upper bound for the size of the set of morphisms between two functors $F,G : C^{op} \to U Set$ is the disjoint union indexed by the objects $c$ of $C$ over the $U$-small sets $G(c)^{F(c)}$. Now $G(c)^{F(c)} \in U$ since it is a function set and $\cup_{c \in Obj(C)} G(c)^{F(c)}$ by the assumption that unions stay in $U$. Hence also the subset $[F,G]_1 \subset \cup_{c \in Obj(C)} G(c)^{F(c)}$ is $U$-small.
Let $C$ be a small category.
Definition – Yoneda embedding
Every object $c \in C$ defines a presheaf $C(-,c) : C^{op} \to Set$, which sends
and
This extends to a functor from $C$ to presheaves on $C$
called the Yoneda embedding (for a reason described in a moment).
Definition – representable presheaf
A presheaf $F : C^{op} \to Set$ is representable if there exists $c \in C$ and an isomorphism $\eta : Y(c) \stackrel{\simeq}{\to} F$.
The pair $(c,\eta)$ is a representation of $F$.
Remarks
The Yoneda lemma is an elementary but deep and central result in category theory and in particular in sheaf and topos theory. It is essential background behind the central concepts of representable functor and universal construction.
Let $C$ be a locally small category, $[C^{op}, Set]$ the category of presheaves on $C$, then for all $c \in C$ there is a canonical isomorphism
This is natural in $c$ and $X$, i.e. there is in fact an isomorphism in the functor category $[C^{op} \times [C^{op},Set],Set]$ between the left and the right side. (The product appearing here is discussed later in monoidal and enriched categories).
The crucial point is that the naturality condition on any natural transformation $\eta : C(-,c) \Rightarrow X$ is sufficient to ensure that $\eta$ is already entirely fixed by the value $\eta_c(Id_c) \in F(c)$ of its component $\eta_c : C(c,c) \to X(c)$ on the identity $Id_c$. And every such value extends to a natural transformation $\eta$.
More in detail, the bijection is established by the map
where the first step is taking the component of a natural transformation at $c \in C$ and the second step is evaluation at $Id_c \in C(c,c)$.
The inverse of this map takes $f \in X(c)$ to the natural transformation $\eta^f$ with components
In the light of the interpretation in terms of space and quantity mentioned above the Yoneda lemma says that for $X$ a generalized space modeled on $C$, and for $c$ a test space, morphisms from $c$ to $X$ with $c$ regarded as a generalized space are just the morphisms from $c$ into $X$.
The Yoneda lemma has the following direct consequences. As the Yoneda lemma itself, these are as easily established as they are useful and important.
The Yoneda lemma implies that the Yoneda embedding functor $Y : C \to [C^op,Set]$ really is an embedding in that it is a full and faithful functor, because for $c,d \in C$ it naturally induces the isomorphism of Hom-sets.
Since the Yoneda embedding is a full and faithful functor, an isomorphism of representable presheaves $Y(c) \simeq Y(d)$ must come from an isomorphism of the representing objects $c \simeq d$:
A presheaf $X : C^{op} \to Set$ is representable precisely if the comma category $(Y,const_X)$ has a terminal object. If a terminal object is $(d, f : Y(d) \to X) \simeq (d, f \in X(d))$ then $X \simeq Y(d)$.
This follows from unwrapping the definition of morphisms in the comma category $(Y,const_X)$ and applying the Yoneda lemma to find
Hence $(Y,const_X)((c,f \in X(c), (d, g \in X(d))) \simeq pt$ says precisely that $X(-)(f) : C(c,d) \to X(c)$ is a bijection.
For emphasis, here is the interpretation of these three corollaries in words:
corollary I says that the interpretation of presheaves in $C$ as generalized objects probeable by objects of $c$ is consistent: the probes of $X$ by $c$ are indeed the maps of generalized objects from $c$ into $X$;
corollary II says that probes by objects of $C$ are sufficient to distinguish objects of $C$: two objects of $C$ are the same if they have the same probes by other objects of $C$.
corollary III characterizes representable functors by a universal property and is hence the bridge between the notion of representable functor and universal constructions.
A crucial class of examples of representable presheaves are adjoint functors.
Definition
Let $C$ and $D$ be small categories.
We say a functor $L : C\to D$ has a right adjoint $R : D \to S$ if for all $d$, the presheaf $Hom_D(L(-),d):D^{op}\to Set$ is representable, i.e. if there exists an object $R(d)$ and a natural isomorphism
There is then a unique way to define $R$ on arrows so as to make these isomorphisms natural in $d$ as well, so that there is an isomorphism of functor categories
This isomorphism is called the adjunction isomorphism.
Example: forgetful and free functors
The classical examples of pairs of adjoint functors are $L \dashv R$ where the right adjoint $R : C' \to C$ forgets structure in that it is a faithful functor. In these case the left adjoint $L : C \to C'$ usually is the functor that “adds structure freely”.
In fact, one usually turns this around and defines the free $C'$-structure on an object $c$ of $C$ as the image of that object under the left adjoint (if it exsists) to the functor $R : C' \to C$ that forgets this structure.
For instance
Notice how the adjunction property defines free constructions:
a group homomorphism from a free group $free(S)$ on some set into a given group $G$ is already fixed once its value on the generators in $S$ is fixed, hence is the same as a morphism of sets from $S$ to the set $forget(G)$ underlying $G$.
Proposition: adjoints are unique
If a functor $L$ has a right adjoint $R$, then $R$ is unique up to unique isomorphism. And conversely: if $R$ has a left adjoint $L$, then $L$ is unique up to unique isomorphism.
Proposition: adjoints and equivalences
the following are equivalent
$L$ and $R$ are both full and faithful;
$L$ is an equivalence;
$R$ is an equivalence;
Frequently it happens that $Hom_D(L(-),d):D^{op}\to Set$ is representable not for all $d$, but for some $d$. And frequently it happens that one is nevertheless interested in the representing object, which by slight abuse of notation we still write $R(d) \in C$.
We call $R(d)$ a local adjoint.
In the next chapter we look at the notion of limit and Kan extension as special cases of adjoint functors. Here in particular one is frequently interested in such local adjoints: limits and Kan extensions may exist in some, but not in all cases.
Last revised on April 24, 2009 at 11:18:07. See the history of this page for a list of all contributions to it.