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: How to express constraints in presheaf-based models?

Peva Blanchard (Oct 08 2025 at 14:21):

Consider the category $C$ with two objects $V,E$ and two non-identity arrows $V \xrightarrow{s,t} E$. Then a graph can be described as a presheaf $G : C^{op} \to \text{Set}$. In particular, we obtain a category ${\cal G}$ of graphs.

However, for a graph theorist, $G$ is more likely described as a directed multigraph possibly with self-loops. The usual graph our graph theorist has in mind usually involves more constraints. For the sake of simplicity, just consider the constraint stating $(\alpha)$ that there is at most one edge between any two vertices.

Now, say I want to describe this data structure with presheaves. I see, at least, two options:

1. I can just select the presheaves on $C$ which satisfy condition $(\alpha)$. I obtain a collection ${\cal G}(\alpha)$ of presheaves. But now it is not clear, at first sight, that we obtain a category (we need to work to check, e.g., if the ${\cal G}$-morphisms are compatible with $(\alpha)$).

2. Or maybe I can change the base category $C$ for another category $D$. Something like two objects $V, E$ and an epi $V \times V \twoheadrightarrow E$. And selecting only presheaves that preserve some stuff (e.g. products, epi to mono, ...)

Maybe there are other ways I am missing.

My question is: are there typical and nice ways to express constraints like $(\alpha)$ in a presheaf-based model? By nice, I mean, for instance, that some general results apply to produce an actual category ${\cal G}(\alpha)$.

Kenji Maillard (Oct 08 2025 at 14:52):

You could restate $(\alpha)$ using an [[orthogonality]] condition (see section orthogonality of morphisms to objects).

Consider the two following graphs $I = v_0 \to v_1$ with two vertices and a single edge (the walking edge) and $D$ with 2 vertices $v_0, v_1$ as well and two parallel edges $e_0, e_1 : v_0 \to v_1$ between these vertices. Let $\iota : I \to D$ map the unique edge of $I$ to $e_0$. Now given a graph $G$, $\mathrm{Hom}(I, G)$ is the set of edges of $G$ while $\mathrm{Hom}(D, G)$ is the set of parallel pairs in $G$. Precomposition by $\iota$ induces a restriction

$$\iota^* : \mathrm{Hom}(D, G) \to \mathrm{Hom}(I, G)$$

and this map is invertible exactly when $G$ has no distinct pair of parallel edges. This is exactly stating that $G$ is (right) orthogonal to $\iota : I \to D$.

Ryan Wisnesky (Oct 08 2025 at 15:01):

We usually start from a presentation of a category rather than a category, so you can literally write down equations you want to hold in your category. But certain classes of constraint, like an arrow being mono, will go beyond equational presentations.

Damiano Mazza (Oct 08 2025 at 15:41):

Just a remark concerning your particular example: "simple" directed graphs (in the sense of graphs with at most one edge $a\to b$ between any two nodes $a,b$) may be expressed as [[separated presheaves]] on the coverage saying that the two arrows $v\to e$ are a covering family. While this does not generalize to obtain more sophisticated constraints that you may have in mind, it does tell us that the category of simple directed graphs is a [[quasitopos]] (a potentially interesting side remark).

James Deikun (Oct 08 2025 at 15:51):

That's not just a potentially interesting side remark, it's a very important point. There are various ways of expressing constraints like this, but they all tell you something important about what the resulting category is like.

James Deikun (Oct 08 2025 at 15:53):

Another important point is that when you have constraints that only eliminate objects, there is no chance of ending up with something that isn't a category. It's only when you start eliminating arrows that that can happen.

Peva Blanchard (Oct 09 2025 at 05:52):

Thank you all for your answers. I didn't know about these concepts, I'll try to work them out on a few other cases.