# Yoneda embedding target

I'm learning about representable functors from Vistoli notes thanks to Charles Siegel's answer.

I see that any category $\mathcal C$ can be embedded into $\text{Hom}\\,(\mathcal C^{op}, \mathcal Set)$ by means of Yoneda embedding. I wonder if there are examples where the latter category would be interesting in itself, other then for these purposes?

-
Just a little note for you, you can write the functor category $(\mathcal{C}^{op},\mathcal{S}et)$ as $\mathcal{P}sh(\mathcal{C})$, which is called the category of presheaves of sets over $\mathcal{C}$. –  Harry Gindi Jan 2 '10 at 0:29

Lots! Categories of that form (when C is small) are often called "presheaf categories". Many interesting categories are presheaf categories, such as simplicial sets, cubical sets, symmetric sets, etc. In particular, any presheaf category is a topos, and many interesting toposes are presheaf categories. The category of G-sets for any discrete group G is another nice example, since G can be regarded as a groupoid, hence as a category. Presheaves on a topological space are also interesting, if only as a means to the construction of sheaves. And simplicial presheaves on a category C (which are the same as presheaves on $C\times \Delta$) are sometimes easier to work with (once you put a nice model structure on them) than simplicial sheaves.

Many other interesting categories are full subcategories of some presheaf category; in fact a category is a full subcategory of a presheaf category as soon as it has a small dense subcategory. Thus, in particular, any accessible category is a subcategory of a presheaf category. This includes almost any "algebraic" category, such as groups, rings, fields, Lie algebras, etc.

-
To clarify what Mike means, you're thinking of a "Grothendieck Topos", which is the sheaf category over any site (presheaf category is the sheaf category over the discrete site). In fact, all Grothendieck toposes are general toposes, but not conversely. –  Harry Gindi Jan 1 '10 at 20:08
Mikael, rather. –  Harry Gindi Jan 1 '10 at 20:09
Although, to be fair, Grothendieck was the original user of the word "topos," which was only later co-opted by Lawvere and Tierney for the more general notion of "elementary topos," necessitating the adjective "Grothendieck" to disambiguate the original definition. Many people quite justifiably still say "topos" to mean "Grothendieck topos". –  Mike Shulman Jan 1 '10 at 20:57
I don't think anyone quite answered Ilya's question. There are two slightly different things called toposes: elementary toposes (more general) and Grothendieck toposes (less general, but still including all presheaf categories). I'll use "topos" to mean "elementary topos". There is an accompanying notion of subtopos; a subtopos of a topos is a subcategory with certain properties. Now: it's a fact that a topos is Grothendieck iff it is a subtopos of some presheaf category. So if in your question "topos" means "Grothendieck topos", the answer is yes. –  Tom Leinster Jan 2 '10 at 0:27
Harry, the point is that "Grothendieck topos" is the same as "category of sheaves on a site." Certainly once you know that, along with the meaning of "sheaf," then it follows trivially that any Grothendieck topos is a full subcategory of a presheaf category. But depending on your definition of "Grothendieck topos," the identification of such toposes with categories of sheaves might be definitional, or it might be Giraud's theorem. –  Mike Shulman Jan 2 '10 at 16:19

Sure, take the category of simplicial sets, which is Hom(Δop, Set). We don't usually think of it as a way of studying the category Δ! There are many other examples along these lines in homotopy theory.

Edit: To elaborate slightly more on what I had in mind with the last comment, take a look at my answer here" where I describe a presentation of the category of monoids, i.e., a way to embed it as a reflective subcategory of a presheaf category (in fact, the category of simplicial sets). This point of view is more commonly encountered in homotopy theory, because to get a good, non-strict notion of, say, topological monoid, one cannot simply write down operations with relations that are required to hold on the nose. This kind of presentation as objects of a presheaf category which send some diagrams to homotopy limit diagrams is one way to resolve the issue.

-
Mm, yes, what are other examples? –  Ilya Nikokoshev Jan 1 '10 at 18:52
Mike just explained basically everything I wanted to say, so I'll just refer you to his answer. –  Reid Barton Jan 1 '10 at 18:58

Various categories of graphs are presheaf categories.

The category of directed graphs is (equivalent to) presheaves on $C$, where $C$ is a category with two objects, call them $V$ and $E$, and two parallel morphisms $s, t : V \to E$. If you have never seen this example, you should compute for yourself that a functor $G : C^{op} \to \text{Set}$ is the same thing as a directed graph. You may find this "Guided tour of the topos of graphs" illuminating.

Other categories of graphs are (almost) presheaf categories. For example, take the monoid $M$ of all endomaps $\lbrace 0,1\rbrace \to \lbrace0,1\rbrace$. This is a four-element monoid whose elements are the identity $id$, two constant maps $0$ and $1$, and the "twist" map $t$. View $M$ as a category (one object, four morphisms). The presheaves on $M$ are what is sometimes called "reflexive" graphs. Since this is not apparent at first sight, let me spell it out a bit. Consider a fuctor $F : M^{op} \to \text{Set}$, which is the same thing as a set $S$ with a right action of $M$. The corresponding graph $G$ has as its vertices the set $V = \lbrace x \in S \mid x \cdot 0 = x\rbrace$ of elements fixed by the action of the constant map $0$ (exercise: the points fixed by the constant map $0$ are the same as the points fixed by the constant map $1$). The edges of $G$ are the elements of $S$. An edge $e \in S$ has as its source the vertex $e \cdot 0$ and the target $e \cdot 1$. But since we also have the action of the twist map $t$, the situation is symmetric: to every edge $e$ going from $e \cdot 0$ to $e \cdot 1$ there corresponds the opposite edge $e \cdot t$ going from $(e \cdot t) \cdot 0 = e \cdot 1$ to $(e \cdot t) \cdot 1 = e \cdot 0$. So we are talking about symmetric graphs. Our graphs may be degenerate in the sense that an edge $e$ could be its own opposite (and then it is also a loop since $e \cdot 1 = e \cdot 0$). The graphs are reflexive because a homomorphism between them is allowed to "squish" edges to vertices, which is another exercise in computing natural transformations.

All of this and more (perhaps too much) can be found in:

Categories of spaces may not be generalized spaces as exemplified by directed graphs, F. William Lawvere, Revista Colombiana de Matematicas, XX (1986) 179-186. (Republished in: Reprints in Theory and Applications of Categories, No. 9 (2005) pp. 1-7)

-
Quite amazing connection with graph theory, thanks! –  Ilya Nikokoshev Jan 2 '10 at 0:17

Just thought of another one: Kripke models of intuitionistic logic are (very closely related to) presheaves on the poset of possible worlds. The interpretation of intuitionistic logic in a Kripke model coincides with the internal logic of the corresponding presheaf topos.

-
Do you mind adding some links or background? –  Ilya Nikokoshev Jan 2 '10 at 0:31
The poset of possible worlds... Sounds vague. –  Harry Gindi Jan 2 '10 at 0:39
@Ilya: I suppose Wikipedia is a good starting place, see en.wikipedia.org/wiki/Kripke_semantics, although now I see it claims that Kripke's semantics should not be called "posssible worlds" semantisc. Who knew. @Harry: before you speak, learn the subject. "Possible world" is a specific technical term. –  Andrej Bauer Jan 2 '10 at 1:12