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 SETSET and then had defined categories

internal toSETSET;

We close with the central example

which leads over to the triptychon of universal constructions

which are the topic of the next part.

small sets

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

Elementary Theory of the Category of Sets:

the set of objects Obj(Set)Obj(Set) in SETSET should behave like a “set of all sets”;

  • clearly, Obj(Set)Obj(Set) can’t “be” the collection of objects of SETSET, since whatever that is, it is not in turn an object of SETSET

  • but as before with the definition of SETSET itself, it matters not so much what Obj(Set)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)Obj(Set), then it serves that purpose

  • this idea is formalized by the notion of a

Grothendieck universe: a set UU that admits all the

operations which are expected on the “collection of all sets”: for instance for each element sUs \in U there should be an element p(s)Up(s) \in U which plays the role of the power set of the set ss;

universe in SET

A universe in SETSET is a morphism el:EUel:E\to U satisfying the axioms to follow. We think of el:EUel:E\to U as a UU-indexed family of objects (sets), and we define a morphism a:AIa:A\to I (regarded as an II-indexed family of objects) to be UU-small if there exists a morphism f:IUf:I\to U and a pullback square

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

Note that ff is not, in general, unique: a universe can contain many isomorphic sets. With this definition, the pullback of a UU-small morphism is automatically again UU-small. We say that an object XX is UU-small if X1X\to 1 is UU-small.

The axioms which must be satisfied are the following four.

  1. Every monomorphism is UU-small.

  2. The composite of UU-small morphisms is UU-small.

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

  4. If f:AIf:A\to I and g:BAg:B\to A are UU-small, then so is the dependent product Π fg\Pi_f g (where Π f\Pi_f is the right adjoint to f *:/I/Af^*:\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 SETSET, the singleton set. Notice that for each ordinary element uUu \in U, i.e. *uU* \stackrel{u}{\to} U, there is the set E uE_u over uu, defined as the pullback

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

We think of EE as being the disjoint union over UU of the E uE_u.

  • By the definition of UU-smallness and the notation just introduced, an object SS in SETSET, regarded as a **-indexed family S*S \to *, is UU-small precisely if it is isomorphic to one of the E uE_u.

  • If SS is a UU-small set by the above and if S 0SS_0 \hookrightarrow S is a monomorphism so that S 0S_0 is a subset of SS, it follows from 1) and 2) that the comoposite (S 0S*)=(S 0*)(S_0 \hookrightarrow S \to *) = (S_0 \to *) is UU-small, hence that S 0S_0 is UU-small. So: a subset of a UU-small set is UU-small.

    • In particular, let \emptyset be the initial object, which is a subset Ω\emptyset \hookrightarrow \Omega of Ω=2\Omega = \mathbf{2}. So: the empty set is UU-small.
  • Let SS, TT and KK be objects of SETSET, regarded as **-indexed families f:S*f : S \to *, T*T \to * and K*K \to *. Notice that (SETS)(f *K,f *T)(SETS)(K×S p 2 S,T×S p 2 S)(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×S,T)SET(K \times S, T). Since Π f\Pi_f is defined to be the right adjoint to f *:SETSETSf^* : SET \to SET \downarrow S it follows that Π ff *TT S\Pi_f f^* T \simeq T^S is the function set of functions from SS to TT. By 3), if SS, TT are UU-small then so is the function set T ST^S.

    • Since by 4) Ω=2\Omega = \mathbf{2} is UU-small and for every SS the function set 2 SP(S)\mathbf{2}^S \simeq P(S) is the power set of SS, it follows that the power set of a UU-small set is UU-small.
  • Let II be a UU-small set, in that I*I \to * is UU-small, and let SIS \to I be UU-small, to be thought of as an II-indexed family of UU-small sets S iS_i, where S iS_i is the pullback S i S * i I\array{ S_i &\to& S \\ \downarrow && \downarrow \\ * &\stackrel{i}{\to}& I }, so that SS is the disjoint union of the S iS_i: S=sqcup iIS iS = sqcup_{i \in I} S_i. By axiom 2) the composite morphism (SI*)=(S*)(S \to I \to *) = (S \to *) is UU-small, hence SS is a UU-small set, hence the II-indexed union of UU-small sets iIS i\sqcup_{i \in I} S_i is UU-small.

By standard constructions in set theory from these properties the following further closure properties of the universe UU follow.

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

In summary

  • the sets ,*,2\emptyset, *, \mathbf{2} are UU-small;

  • a subset of a UU-small set is UU-small;

  • the power set P(S)P(S) of any UU-small set is UU-small;

  • the function set T ST^S for any two UU-small sets is UU-small;

  • the union of a UU-small family of UU-small sets is UU-small.

  • the product of a UU-small family of UU-small sets is UU-small.

Axiom of universes

In order to make use of this we impose one more axiom on SETSET:

Axiom of universes

For every SS in the collection of objects of SETSET, there exists a universe EUE \to U in SETSET such that SS is UU-small, i.e. such that there is uUu \in U and SE uS \simeq E_u.

small and locally small categories

We now fix a universe EUE \to U once and for all.

Definition

The category denoted USetU Set – or just SetSet if the universe UU is understood – is the category given by

  • Obj(Set)=UObj(Set) = U;

  • for all s,tUs,t \in U let Set(s,t):=E t E sSet(s,t) := E_t^{E_s} be the function set of functions from E sE_s to E tE_t;

  • Mor(Set)= s,tUSet(s,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 SetSet is “like” SETSET: the category SetSet of UU-small sets is what is called an internal topos-object.

Definition A category CC in SETSET is locally UU-small if for all ordinary elements x,yObj(C)x,y \in Obj(C) the hom-set Hom C(x,y)Hom_C(x,y) is UU-small.

Here Hom C(x,y)Hom_C(x,y) is the pullback

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

in SETSET.

A category CC in SETSET is UU-small – or small if the universe UU is understood – if it is locally UU-small and Obj(C)Obj(C) is UU-small.

It follows that for a UU-small category also Mor(C)Mor(C) is UU-small.

A category is essentially UU-small – or essentially small if the universe UU is understood – if it is equivalent to a UU-small category.

Remarks

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

Examples: The classical categories

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

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

functor categories

Definition

  • For CC, DD two categories, there is a set [C,D] 0D 1 C 1[C,D]_0 \subset D_1^{C_1} of functors between them.

  • With natural transformations between them as morphisms, [C,D] 1D 1 C 0[C,D]_1 \subset D_1^{C_0}, this yields a category, [C,D][C,D], the functor category between CC and DD.

Example

  • our main example of interest are presheaf categories, discussed in the following;

  • for AA (respectively GG) a monoid (respectively a group) and BA\mathbf{B}A (BG\mathbf{B}G) the corresponding category, [BA,BA][\mathbf{B}A, \mathbf{B}A] (respectively [BG,BG][\mathbf{B}G, \mathbf{B}G]) is the category (a groupoid) whose objects are the endomorphisms of AA (of GG) and whose morphisms are intertwiners between these.

Presheaves

We still keep a universe UU fixed once and for all and say “small” for “UU-small”, write SetSet for USetU Set, etc.

Definition

A presheaf on a category CC is nothing but a functor C opSetC^{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 CC and to ask if the functor satisfies the

sheaf condition (both to be discussed later in gluing – coverage and sheaves).

For CC a small category, we call the functor category

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

the presheaf category of CC and call

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

the co-presheaf category of CC.

Remark Recall what the morphisms η:FG\eta : F \to G in [C op,Set][C^{op},Set] are like: for each object cCc \in C these are given by maps of sets η c:F(c)G(c)\eta_c : F(c) \to G(c) such that for all morphisms f:cdf : c \to d in CC these squares commute

F(c) η c G(c) F(f) G(f) F(d) η d G(d) \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 CC is empty, the category PSh(C)PSh(C) is large, i.e. not small with respect to the universe UU with respect to which CC is small. (But of course, by the axiom of universes, PSh(C)PSh(C) is small with respect to some other universe VV.)

But

  • PSh(C)PSh(C) is locally small.

Proof. An upper bound for the size of the set of morphisms between two functors F,G:C opUSetF,G : C^{op} \to U Set is the disjoint union indexed by the objects cc of CC over the UU-small sets G(c) F(c)G(c)^{F(c)}. Now G(c) F(c)UG(c)^{F(c)} \in U since it is a function set and cObj(C)G(c) F(c)\cup_{c \in Obj(C)} G(c)^{F(c)} by the assumption that unions stay in UU. Hence also the subset [F,G] 1 cObj(C)G(c) F(c)[F,G]_1 \subset \cup_{c \in Obj(C)} G(c)^{F(c)} is UU-small.

Representable presheaves and the Yoneda lemma

Let CC be a small category.

Definition – Yoneda embedding

Every object cCc \in C defines a presheaf C(,c):C opSetC(-,c) : C^{op} \to Set, which sends

aC(a,c)=Hom C(a,c) a \mapsto C(a,c) = Hom_C(a,c)

and

(afb)(()f:(bgc)(agfc)) (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 CC to presheaves on CC

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

called the Yoneda embedding (for a reason described in a moment).

Definition – representable presheaf

A presheaf F:C opSetF : C^{op} \to Set is representable if there exists cCc \in C and an isomorphism η:Y(c)F\eta : Y(c) \stackrel{\simeq}{\to} F.

The pair (c,η)(c,\eta) is a representation of FF.

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.

The Yoneda Lemma

Let CC be a locally small category, [C op,Set][C^{op}, Set] the category of presheaves on CC, then for all cCc \in C there is a canonical isomorphism

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

This is natural in cc and XX, i.e. there is in fact an isomorphism in the functor category [C op×[C op,Set],Set][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 η:C(,c)X\eta : C(-,c) \Rightarrow X is sufficient to ensure that η\eta is already entirely fixed by the value η c(Id c)F(c)\eta_c(Id_c) \in F(c) of its component η c:C(c,c)X(c)\eta_c : C(c,c) \to X(c) on the identity Id cId_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)| cSet(C(c,c),X(c))ev Id cX(c) [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 cCc \in C and the second step is evaluation at Id cC(c,c)Id_c \in C(c,c).

The inverse of this map takes fX(c)f \in X(c) to the natural transformation η f\eta^f with components

η d f:=X()(f):C(d,c)X(d). \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 XX a generalized space modeled on CC, and for cc a test space, morphisms from cc to XX with cc regarded as a generalized space are just the morphisms from cc into XX.

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[C op,Set]Y : C \to [C^op,Set] really is an embedding in that it is a full and faithful functor, because for c,dCc,d \in C it naturally induces the isomorphism of Hom-sets.

[C op,Set](C(,c),C(,d))(C(,d))(c)=C(c,d) [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)Y(d)Y(c) \simeq Y(d) must come from an isomorphism of the representing objects cdc \simeq d:

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

corollary III: universality of representing objects

A presheaf X:C opSetX : C^{op} \to Set is representable precisely if the comma category (Y,const X)(Y,const_X) has a terminal object. If a terminal object is (d,f:Y(d)X)(d,fX(d))(d, f : Y(d) \to X) \simeq (d, f \in X(d)) then XY(d)X \simeq Y(d).

This follows from unwrapping the definition of morphisms in the comma category (Y,const X)(Y,const_X) and applying the Yoneda lemma to find

(Y,const X)((c,fX(c)),(d,gX(d))){uC(c,d):X(u)(g)=f}. (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,fX(c),(d,gX(d)))pt(Y,const_X)((c,f \in X(c), (d, g \in X(d))) \simeq pt says precisely that X()(f):C(c,d)X(c)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 CC as generalized objects probeable by objects of cc is consistent: the probes of XX by cc are indeed the maps of generalized objects from cc into XX;

  • corollary II says that probes by objects of CC are sufficient to distinguish objects of CC: two objects of CC are the same if they have the same probes by other objects of CC.

  • 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 CC and DD be small categories.

We say a functor L:CDL : C\to D has a right adjoint R:DSR : D \to S if for all dd, the presheaf Hom D(L(),d):D opSetHom_D(L(-),d):D^{op}\to Set is representable, i.e. if there exists an object R(d)R(d) and a natural isomorphism

Hom D(L(),d)Hom C(,R(d)).Hom_D(L(-),d) \cong Hom_C(-,R(d)).

There is then a unique way to define RR on arrows so as to make these isomorphisms natural in dd as well, so that there is an isomorphism of functor categories

Hom D(L(),)Hom C(,R()). 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 LRL \dashv R where the right adjoint R:CCR : C' \to C forgets structure in that it is a faithful functor. In these case the left adjoint L:CCL : C \to C' usually is the functor that “adds structure freely”.

In fact, one usually turns this around and defines the free CC'-structure on an object cc of CC as the image of that object under the left adjoint (if it exsists) to the functor R:CCR : C' \to C that forgets this structure.

For instance

  • forgetful right adjoint R=forget:R = forget : Grp \to Set forgets the group structure on a group and just rememebers the underlying set – the left adjoint L=free:SetGrpL = 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)Set(S,forget(G)) Grp(free(S),G) \simeq Set(S,forget(G))

a group homomorphism from a free group free(S)free(S) on some set into a given group GG is already fixed once its value on the generators in SS is fixed, hence is the same as a morphism of sets from SS to the set forget(G)forget(G) underlying GG.

Proposition: adjoints are unique

If a functor LL has a right adjoint RR, then RR is unique up to unique isomorphism. And conversely: if RR has a left adjoint LL, then LL is unique up to unique isomorphism.

Proposition: adjoints and equivalences

locally defined adjoints

Frequently it happens that Hom D(L(),d):D opSetHom_D(L(-),d):D^{op}\to Set is representable not for all dd, but for some dd. And frequently it happens that one is nevertheless interested in the representing object, which by slight abuse of notation we still write R(d)CR(d) \in C.

We call R(d)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.