Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Closed structure on presheaf category

Joshua Meyers (Feb 08 2021 at 14:12):

So apparently for any small category $C$, the presheaf category $\text{Set}^C$ is Cartesian closed. The closed structure is given by $R^Q=\text{Hom}(y(-)\times Q,R)$, as shown in this post. I follow the argument in the post, but I still don't have any intuition for this closed structure. Maybe someone can give me some intuition?

Mike Stay (Feb 08 2021 at 15:30):

For discrete C, you just get multiple copies of Set and the hom is computed pointwise. For C with arrows, a functor $C\to Set$ is a "model of C", and the hom is a homomorphism of models. For instance, if C is the category with two objects V, E and two morphisms $s,t: E\to V,$ then $G:C \to {\rm Set}$ is a (directed multi-)graph with vertices G(V) and edges G(E). An edge e in G(E) has source G(s)(e) and target G(t)(e). A natural transformation $\alpha:G \Rightarrow H$ in ${\rm Set}^C$ is a graph homomorphism, i.e. it assigns to the objects V and E morphisms $\alpha_V, \alpha_E$ that make the relevant squares commute.

Mike Stay (Feb 08 2021 at 15:33):

BTW, usually presheaf categories are taken to be ${\rm Set}^{C^{\rm op}}$ rather than ${\rm Set}^C$ so that the Yoneda embedding is covariant. (The Yoda embedding, contravariant it is.)

John Baez (Feb 08 2021 at 16:25):

It really helps to work out the closed structure in the case of graphs, as Mike was indicating... but carry it out to the point of computing the graph $G^H$ for a couple of graphs $G$ and $H$. It's the graph of maps from $H$ to $G$... and it's good to get an intuition for what that is.

Joshua Meyers (Feb 08 2021 at 16:27):

The graph example is interesting to compute directly. Given graphs $G'=(E'\rightrightarrows V')$ and $G=(E\rightrightarrows V)$, what is $G^{G'}$. Firstly, its vertices correspond to morphisms $(0\rightrightarrows 1)\rightarrow G^{G'}$, which correspond to morphisms $(0\rightrightarrows 1)\times G'\rightarrow G$, which correspond to functions $V'\rightarrow V$. So far so good.

Secondly, its edges correspond to morphisms $(1\rightrightarrows 2)\rightarrow G^{G'}$, which correspond to morphisms $(1\rightrightarrows 2)\times G'\rightarrow G$. We can think of $(1\rightrightarrows 2)\times G'$ as a "bipartitization" of $G'$: it has the same edges as $G'$, but for each vertex $v$ of $G'$ it has a source version $v_\sigma$ and a target version $v_\tau$. The new source and target maps are defined always to map to the correct version of a vertex. Thus the target of one edge is never the source of another. Now a morphism $(1\rightrightarrows 2)\times G'\rightarrow G$ consists of an edge map $e:E'\rightarrow E$ and two vertex maps $v_\sigma,v_\tau: V'\rightarrow V$, one for source-vertices and one for target-vertices. This might seem like an unnatural construction, but a true exponential object must satisfy $\text{Hom}(G'',G^{G'})\cong \text{Hom}(G''\times G',G)$ for any $G''$, and if we choose $G''=(1\rightrightarrows 2)$ then $G''\times G'$ is the bipartitization of $G'$, so $G^{G'}$ must accommodate for the possibility that "source-vertices" and "target-vertices" are sent to different places.

Finally, the the source and target of an edge $(e,v_\sigma,v_\tau)$ are just $v_\sigma$ and $v_\tau$ respectively.

John Baez (Feb 08 2021 at 16:36):

Nice! It's worth noting that

1) any category has an underlying graph

source, target: {morphisms} $\rightrightarrows$ {objects}

2) any functor has an underlying morphism of graphs

3) any natural transformation has an underlying "transformation between graph morphisms" where

4) the vertices of $H^G$ are graph morphisms and the edges are transformations between graph morphisms

5) you can compose natural transformations but you can't, in general, compose transformations between graph morphisms.

John Baez (Feb 08 2021 at 16:47):

All this is perhaps a bit less about understanding cartesian closed structures of presheaf categories and a bit more about understanding the link between graph theory and category theory. But the categories Graph and Cat are both cartesian closed so it's good to ponder how the forgetful functor Cat $\to$ Graph interacts with this fact.

Mike Stay (Feb 08 2021 at 16:51):

Note that the "graph of homomorphisms" between two objects in the topos of graphs is very different than the "graph of homomorphisms" between two objects in the topos of reflexive graphs. The edges of the latter are much more like natural transformations.

John Baez (Feb 08 2021 at 16:54):

How are they much more like natural transformations? I'm sure you're right. But there's still no commutative square condition involved, and you still can't compose them, so I'm mainly aware of how they're not like natural transformations.

Mike Stay (Feb 08 2021 at 16:56):

It comes down to the difference in the product of two edge graphs. In the topos of mere graphs, the product of two directed edges a->b and c->d is a single directed edge ab->cd. But in the topos of reflexive graphs, you can keep one vertex constant using the canonical self-edge, so you get a box shape with a diagonal through it.

Mike Stay (Feb 08 2021 at 16:58):

This is a great source for understanding all the variations: "Graphs of morphisms of graphs" https://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1a1
It considers toposes of {directed, undirected} × {reflexive, non-reflexive} graphs.

John Baez (Feb 08 2021 at 17:11):

Oh, okay, yes. I'd say the product in the category of reflexive graphs more closely resembles the product in Cat.

Tom Hirschowitz (Feb 08 2021 at 17:26):

Here is a very vague, vastly insufficient, syntactic intuition. Thinking of $C$, e.g., as a Lawvere theory, $Q,R: C^{op} \to \mathbf{Set}$ are some sort of generalised predicates, in the sense that they are equipped with an action by substitutions: a morphism $f = (f_1,\ldots,f_n): m \to n$ in $C$ is like a substitution of the variables $1,\ldots,n$ by $f_1,\ldots,f_n$. The point is that natural transformations $Q \to R$ do not naturally come equipped with such an action by substitutions, because of contravariance on the left of the arrow. The solution is to parameterise them over all potential instantiations. Thus, for any object $c \in C$, $[[{-},c] \times Q, R]$ says something like "give me a substitution $d \to c$ of the variables in $c$, and I'll return a map $Q(d) \to R(d)$." It is then a little exercise to show that this is indeed equipped with an action as desired.

Tom Hirschowitz (Feb 08 2021 at 17:27):

It might also be helpful to draw intuition from the interpretation of $\Rightarrow$ in Kripke-Joyal semantics, which has been explained at large in the literature. Does anyone confirm this?

fosco (Feb 09 2021 at 21:25):

A very neat syntactic intuition! Maybe I can add that the end you're performing to compute $\hom(y(-)\times Q,R)$ as a limit is exactly the "quantification over all potential instantiations"? This dates back to Lawvere of course...

Tom Hirschowitz (Feb 09 2021 at 22:15):

Yes, absolutely.

Mike Stay (Feb 09 2021 at 23:33):

John Baez said:

Oh, okay, yes. I'd say the product in the category of reflexive graphs more closely resembles the product in Cat.

The upshot of the difference in the product is that the "graph of homomorphisms" in the topos of mere graphs doesn't actually have graph homomorphisms as vertices! Instead, it has a weakened notion that @Joshua Meyers worked out above (see also page 3 of https://arxiv.org/abs/math/0306394). So the "graph transforms" between them are also correspondingly weird.

The very unfortunately named "cartesian product of graphs", which ought to be called the "box product of graphs", is a symmetric monoidal product on graphs that makes the internal hom have graph homomorphisms as vertices and graph transforms as edges. The categorical product of reflexive graphs includes the box shape and doesn't break anything, so the vertices and edges of the internal hom graph are also graph homomorphisms and transforms.