Schreiber presheaf categories with values in small sets

previous: categories, functors and natural transformations in SET

home: sheaves and stacks

next: universal constructions – adjunction, limit and Kan extension

---

presheaves with values in small sets

• recall that previously we had set up the topos $SET$ and then had defined categories

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

  • locally small category,

  • small category,

  • functor category

  • 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

• adjoint functor

which leads over to the triptychon of universal constructions

• adjoint functor

• limit

• Kan extension

which are the topic of the next part.

small sets

• to proceed, we need something like a “category of sets” $Set$ inside the Category of Sets $SET$ defined previously as the

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$;

• more precisely, Grothendieck universes are defined in the context of a material set theory such as ZFC with a global element relation $\in$. – For our structural set theory ETCS we make use of the structural analog, called universe in a topos, where for us the topos in question is $SET$.

universe in SET

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

$$\array{A & \to & E\\ ^a\downarrow && \downarrow^{el}\\ I& \underset{f}{\to} & U.}$$

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.

1. Every monomorphism is $U$-small.

2. The composite of $U$-small morphisms is $U$-small.

3. The two-element set $\Omega = \mathbf{2} = P(*)$, called the subobject classifier is $U$-small.

4. 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

$$\array{ E_u &\to& E \\ \downarrow && \downarrow \\ * &\stackrel{u}{\to}& U }$$

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.

  • In particular, let $\emptyset$ be the initial object, which is a subset $\emptyset \hookrightarrow \Omega$ of $\Omega = \mathbf{2}$. So: the empty 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$.

  • Since by 4) $\Omega = \mathbf{2}$ is $U$-small and for every $S$ the function set $\mathbf{2}^S \simeq P(S)$ is the power set of $S$, it follows that the power set of a $U$-small set is $U$-small.

• 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.

• For $I$ a $U$-small set and $S \to I$ an $I$-indexed family of $U$-small sets $S_i$, the cartesian product $\prod_{i \in I} S_i$ is $U$-small, as it is a subset of $P(I \times S)$.

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.

Axiom of universes

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$.

small and locally small categories

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

$$\array{ Hom_C(x,y) &\to& Mor(C) \\ \downarrow && \downarrow^{s \times t} \\ * &\stackrel{x \times y}{\to}& Obj(C) \times Obj(C) }$$

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

• By the axiom of universes, every category is small with respect to some universe.
• A locally small category is a $Set$-enriched category.
• A small category is a category internal to $Set$.

Examples: The classical categories

• The category $U-Set$ itself is not $U$-small: it is “$U$-large”. But by the axiom of universes it is $V$-small for some other universe $V$.

In terms of this we have now the “classical” large categories of small sets with extra structure:

• Top, Grp, etc.

functor categories

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.

Presheaves

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

$$PSh(C) := [C^{op}, Set]$$

the presheaf category of $C$ and call

$$CoPSh(C) := [C,Set]$$

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

$$\array{ F(c) &\stackrel{\eta_c}{\to}& G(c) \\ \uparrow^{F(f)} && \uparrow^{G(f)} \\ F(d) &\stackrel{\eta_d}{\to}& G(d) }$$

Observation

• Except for the degenerate case that $C$ is empty, the category $PSh(C)$ is large, i.e. not small with respect to the universe $U$ with respect to which $C$ is small. (But of course, by the axiom of universes, $PSh(C)$ is small with respect to some other universe $V$.)

But

• $PSh(C)$ is locally small.

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.

Representable presheaves and the Yoneda lemma

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

$$a \mapsto C(a,c) = Hom_C(a,c)$$

and

$$(a \stackrel{f}{\to} b) \mapsto ( (-) \circ f : (b \stackrel{g}{\to} c) \mapsto (a \stackrel{ g\circ f}{\to} c) )$$

This extends to a functor from $C$ to presheaves on $C$

$$Y: C \to [C^{op}, Set]$$

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 below will imply that representations are unique up to isomorphism.

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.

The Yoneda Lemma

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

$$[C^op,Set](C(-,c),X) \simeq X(c) \,.$$

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).

Proof

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

$$[C^{op}, Set](C(-,c),X) \stackrel{|_{c}}{\to} Set(C(c,c), X(c)) \stackrel{ev_{Id_c}}{\to} X(c)$$

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

$$\eta^f_d := X(-)(f) : C(d,c) \to X(d) \,.$$

Remarks

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$.

Corollaries

The Yoneda lemma has the following direct consequences. As the Yoneda lemma itself, these are as easily established as they are useful and important.

corollary I: Yoneda embedding

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.

$$[C^{op},Set](C(-,c),C(-,d)) \simeq (C(-,d))(c) = C(c,d)$$

corollary II: uniqueness of representing objects

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$:

$$Y(c) \simeq Y(d) \;\; \Leftrightarrow \;\; c \simeq d$$

corollary III: universality of representing objects

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

$$(Y,const_X)((c,f \in X(c)), (d, g \in X(d))) \simeq \{ u \in C(c,d) : X(u)(g) = f \} \,.$$

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.

Interpretation

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.

Adjoint functors in terms of representability

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

$$Hom_D(L(-),d) \cong Hom_C(-,R(d)).$$

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

$$Hom_D(L(-),-) \simeq Hom_C(-,R(-)) \,.$$

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

• forgetful right adjoint $R = forget :$ Grp $\to$ Set forgets the group structure on a group and just rememebers the underlying set – the left adjoint $L = free : Set \to Grp$ sends each set to the free group over it.

Notice how the adjunction property defines free constructions:

$$Grp(free(S),G) \simeq Set(S,forget(G))$$

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$.

• The main example of this which we will see later in sheafification as the left adjoint to the forgetful functor from sheaves to presheaves.

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;

locally defined adjoints

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.