Shapes for category theory

Question

Most texts on category theory define a (small) diagram in a category $\mathcal{A}$ as a functor $D : \mathcal{I} \to \mathcal{A}$ on a (small) category $\mathcal{I}$, called the shape of the diagram. A cone from $A \in \mathcal{A}$ to $D$ is a morphism of functors $\Delta(A) \to D$, a limit is a universal cone. Observe that, however, that composition in $\mathcal{I}$ is never used to define the limit. One can therefore argue, and this is what I would like to discuss here, that directed multigraphs ("categories without composition") are better suited as the shapes of diagrams:

If $\Gamma$ is a directed multigraph, then a diagram of shape $\Gamma$ in $\mathcal{A}$ is a morphism of graphs $D : \Gamma \to U(\mathcal{A})$, where $U$ forgets composition. A cone from $A \in \mathcal{A}$ to $D$ is a morphism of diagrams $\Delta(A) \to D$, a limit is a universal cone. In my category theory textbook (published 2015) I chose this definition, which leads to an equivalent theory, but offering several advantages over the more common definition:

1. As alreay indicated, the limit of a functor $\mathcal{I} \to \mathcal{A}$ in $\mathcal{A}$ is just the limit of the graph morphism $U(\mathcal{I}) \to U(\mathcal{A})$ in $\mathcal{A}$, so it seems awkward to have a category structure around when we do not use it all. Conversely, the limit of a graph morphism $\Gamma \to U(\mathcal{A})$ is just the limit of the corresponding functor $\mathrm{Path}(\Gamma) \to \mathcal{A}$, so in end we end up with the same limits. In particular, the definition cannot be totally wrong, and much of the discussion will be more of philosophical or pedagogical nature.

2. When we talk about specific types of diagrams and limits, we never really care about composition, and also never write down identities, since they are not relevant at all. For example, binary products are limits of shape$$\bullet ~~ \bullet$$which is just a graph with two vertices and no edges. We don't need to write down identity morphisms in this approach. Arbitrary products are similar. An equalizer is a limit of the shape $$\bullet \rightrightarrows \bullet$$ which is just a graph with two vertices and two parallel edges between them. A fiber product is a limit of the shape $$\bullet \rightarrow \bullet \leftarrow \bullet.$$ Limits of shape $$\cdots \to \bullet \to \bullet \to \bullet$$ also appear very naturally. Put differently, the typical indexing categories you will find in most texts on category theory are actually already the path categories on directed multigraphs. For me this is the most convincing argument. Barr and Wells argue in their book Toposes, Triples and Theories in a similar way:

Limits were originally taken over directed index sets—partially ordered sets in which every pair of elements has a lower bound. They were quickly generalized to arbitrary index categories. We have changed this to graphs to reflect actual mathematical practice: index categories are usually defined ad hoc and the composition of arrows is rarely made explicit. It is in fact totally irrelevant and our replacement of index categories by index graphs reflects this fact. There is no gain—or loss—in generality thereby, only an alignment of theory with practice.

3. Let's talk about interchanging limits. The usual formulation starts with a functor $D : \mathcal{I} \times \mathcal{J} \to \mathcal{A}$. This includes, in particular all "diagonal" morphisms $D(f,g)$ for morphisms $f$ in $\mathcal{I}$ and $g$ in $\mathcal{J}$. However, in practice, I only want to define $D(f,j)$ and $D(i,g)$, and I don't want to show that $D$ is a functor. For example, interchanging fiber products should be about commuting diagrams of shape $$\begin{array}{ccccc} \bullet & \rightarrow & \bullet & \leftarrow & \bullet \\ \downarrow && \downarrow && \downarrow \\ \bullet & \rightarrow & \bullet & \leftarrow & \bullet \\ \uparrow && \uparrow && \uparrow \\ \bullet & \rightarrow & \bullet & \leftarrow & \bullet\end{array}$$ which actually appear in practice (see also here). I don't want to bother about all the diagonal morphisms (and the identities) in that diagram, and actually nobody does when applying "interchanging limits" in concrete examples. The theorem for directed multigraphs is as follows: Let $\Gamma,\Lambda$ be directed multigraphs. Consider the tensor product $\Gamma \otimes \Lambda$ (pair the vertices, pair edges in $\Gamma$ with vertices of $\Lambda$, and pair edges in $\Lambda$ with vertices in $\Gamma$) and a diagram $D$ of shape $\Gamma \otimes \Lambda$ in $\mathcal{A}$ such that for all edges $i \to j$ in $\Gamma$ and edges $i' \to j'$ in $\Lambda$ the diagram $$\begin{array}{ccc} D(i,j) & \rightarrow & D(i,j') \\ \downarrow && \downarrow \\ D(i',j) & \rightarrow & D(i',j') \end{array}$$ commutes. Then, we have $\lim_{i \in \Gamma} \lim_{j \in \Lambda} D(i,j) \cong \lim_{(i,j) \in \Gamma \otimes \Lambda} D(i,j)$; when the left side exists, then also the right side, and they are isomorphic.
4. This is a bit vague, but for me it seems awkward and random, almost like a "type error", that categories have two purposes in the usual theory: One purpose it to collect structured objects and their morphisms. The other purpose is to axiomatize diagram shapes. Similarly, functors have two purposes in the usual theory. I find it quite pleasant when the second purpose is fulfilled by a different thing. Also connected to that is the observation that shapes are usually small, but categories tend to be large.

Although the theory works out very well, meanwhile, I am not so confident anymore about my decision, and I am thinking about changing it in the next edition of the book. So here are some disadvantages:

1. 99% of the category theory literature (textbooks and research papers) define diagrams as functors, resp. their shapes are just small categories. It is awkward to do something which nobody else does, and this can also be irritating for the readers as well. I didn't bother about this too much when writing the book, but I am increasingly worried about this issue.
2. Directed diagrams/colimits are indexed by directed partial orders, and here we really want a functor to ensure compatibility between the various morphisms. Barr-Wells offer a workaround in Chapter 1, Section 10, but they admit themselves that it is slightly awkward.
3. The theory of Kan extensions: The left Kan extension of a functor $F : \mathcal{I} \to \mathcal{A}$ along a functor $G : \mathcal{I} \to \mathcal{J}$ at $J \in \mathcal{J}$ can usually be described as the colimit of the functor $G \downarrow J \to \mathcal{I} \to \mathcal{A}$, and it seems artificial to just consider the underlying graph of $G \downarrow J$ here.

This explains hopefully enough background for the following

Questions.

1. Can you list further mathematical advantages and disadvantages when taking directed multigraphs as the shapes of diagrams and limits / colimits?
2. Can you name pedagogical advantages and disadvantages of this definition?
3. Can you list other textbooks on category theory which use this definition? The book Toposes, Triples and Theories by Barr and Wells is an example, see Chapter 1, Section 7. They also define sketches in a "composition-free" way in Chapter 4. Not a book, but Grothendieck also defines diagrams this way in his famous Tohoku paper Sur quelques points d'algèbre homologique, Section 1.6.
4. (More general side question) For those of you who already wrote a book or monograph, what other criteria did you choose to decide if a common definition should be changed? And how did you decide in the end?

Answer 1

I think focusing on graphs is not a good idea. We focus on functors for very good reasons. Here are a few:

• Many diagrams which are used in practice are functors between categories, and forgetting that they are compatible with composition could seem artificial in many cases.
• We want to compute colimits. A very fundamental tool for this is the notion of colimit-cofinal functor: those functors $u:A\to B$ such that, for any functor $f:B\to C$, the colimit of $f$ exists if and only if the colimit of $fu$ exists, in which case both are isomorphic in $C$. Those functors are characterized by connectivity properties on comma categories, the formation of which is sensitive to compositions. Furthermore, (co)limits are special cases of pointwise Kan left Kan extensions, the formation of which cannot be determined by underlying graphs.
• Category theory is used in homotopical contexts for a long time, and we now have the theory of $\infty$-categories to explain conceptually how this is possible. Many features of ordinary categories (such as the theory of (co)limits and Kan extensions) are robust enough to be promoted to $\infty$-categories. However, only the version with functors can be transposed to higher categories: if you have a functor $f:I\to C$ from a category $I$ to an $\infty$-category $C$, it is not true that the colimit of $f$ in $C$ can be determined by the restriction of $f$ on the graph of $I$ only (think of the kind of homology you would get if you would define cellular homology of a CW-complex by stopping short at its $1$-skeleton). In ordinary category theory, this holds because there is no ambiguity about the notion of composition of two maps in $C$, whereas in a higher category it could be you have a space/category of possible compositions of two maps that cannot be ignored. Therefore, if we have in mind possible generalizations of category theory to homotopical or higher categorical context, focusing on underlying graphs is very misleading.

There are instances where the point of view of graphs is very useful, though. For instance, there is Nori's construction of an abelian category of motives, which relies heavily on singular cohomology seen as a map of graphs; this is documented in this book of Annette Huber and Stefan Müller-Stach, for instance.

If you really want to focus on graphs, then I guess that, in a monograph on category theory, you may write a chapter explaining why we naturally speak the language of graphs when we express ourselves in the language of category theory. For instance, the category of small category is monadic on the category of graphs. In particular, any category is a colimit of free categories. There are many fundamental examples of free categories, and is true that, when we write a diagram explicitly, we only write the images of generators, because this is what working on free objects is good for. It is also interesting to see how categorical constructions (such as colimits) are compatible with the presentations of categories as colimits of free ones. But you will see then that the colimits of interest in this respect are in fact those which are equivalent to their corresponding 2-colimits (i.e. you will start do do homotopy theory where weak equivalences are equivalences of categories). Expressing a given category as $2$-colimits of elementary free categories can be instructive. Cases where we have such a nice inductive procedure of this kind are interesting in practice: this is what is happening with direct Reedy categories, for instance.

Answer 2

On questions 1 and 2: how would you handle reflexive coequalizers with the graphs-as-shapes approach? I agree that it can be done, but isn't it more natural with categories as shapes?

On question 3: there's a point in Mac Lane and Moerdijk's Sheaves in Geometry and Logic where they implicitly use the graphs approach. Lemma VII.6.1 states that a small category is filtering if and only if every finite diagram on it admits a cone. They prove "only if" by induction on the number of nonidentity arrows in the diagram. When I read it, I thought it was a mistake, for obvious reasons: you can't do induction on categories like that. But when I put this to Moerdijk, he said that they were really using the graphs-as-shapes viewpoint, which would make induction possible. I'm not convinced that what they've done is entirely respectable, but it's an answer to your question.

Question 4: in my Basic Category Theory, I used the categories-as-shapes approach. Honestly, I don't think I gave it a lot of thought: I just went with what I'd been brought up with. But if I imagine rewriting the book with graphs as shapes, my first objection would be that it introduces a new concept: graph. At present, the word "graph" doesn't appear once in the whole book. Unnecessarily introducing an extra concept seems like a step backwards. (Which is not to say there couldn't be advantages outweighing this disadvantage.)

Answer 3

Here are some leads for 1. and 2. (this is far from a full answer, but slightly too long for a comment). I only went in the "disadvantages of this approach" direction, too so that's another reason it's not a full answer.

1.

a- A mathematical advantage is that when you go to higher category theory/homotopy theory, then composition in the shape does matter (you need the naturality square for $f,g$ and $f\circ g$ to be compatible, and so on for higher morphisms). So in a sense what you describe is the consequence of the fact that in 1-category theory, equality of morphisms is a property and not extra structure. In particular, with the definition "shapes as categories", the higher generalization is clearer. This is to me the main disadvantage of that approach, especially in this day and age.

b- Another advantage is that it allows for a unified framework (categories), where you don't have to introduce a new notion ("the category of diagrams with shape a directed multigraph") for something that already exists and is useful for many reasons (functor categories) - I guess this is somewhat the other side of the coin for your point 4.

c- Related to that is Zhen Lin's comment, that things indexed by categories somehow strictly generalize things indexed by directed multigraphs precisely because of your point 1 - this is also related to the previous point, that the category of diagrams is a special case of a functor category, but not the other way around (note that co/limits are not generalized that way, but categories of diagrams are)

d- Finally, a last advantage that I can see (related to your point about Kan extensions) is that many of the diagrams you naturally encounter - except for the "standard diagrams" : $\mathbb N$, co/products, co/equalizers, pullbacks/pushouts - are "naturally" indexed by categories. That is, often when you encounter a co/limit, it'll be because you had a functor in your hand, and wanted to understand something about it.

Here are some examples of this phenomenon:

i. In all questions of "generation by colimits" (e.g. the fact that presheaves are canonical colimits of representable presheaves), you get functors that are "naturally" indexed by slice categories $S_{/x} = S\times_C C_{/x}$ for some $S$ with a functor to $C$. Oftentimes, the properties of the category $S_{/x}$ are important to get some information out of that, or about that : is it filtered, is it sifted, weakly contractible, ... ? This relates of course to your example about Kan extensions, but comes up often in practice (e.g. if $F$ is a finite limit preserving presheaf on $C$, then $C_{/F}$ will be filtered, which allows for the multiple characterizations of the ind-completion)

ii. Many objects are defined as functors on some (non free) category, and you often want to take their colimit along the indexing category, or something related to it - but this almost always "naturally" comes in the form of a diagram indexed by a category. For a specific example, take $BG$ : functors out of it are objects with a $G$-action, and you'll often be interested in taking orbits or fixed points and stuff like that.

iii. This is very specific but comes up a lot: oftentimes, you have a construction that produces a functor $\Delta^{op}\to C$ out of some piece of data in $C$ (a monad on $C$, or more specialized, a monoid in $C$, a left and a right module thereon, ...), and whose colimit is very interesting (or the limit if you get a functor from $\Delta$). Again, you could forget the fact that $\Delta^{op}$ is a category, but the diagram you got was "naturally" a functor. Another way to phrase this is that you often want to precompose diagrams (see 2.b- below) with functors, and this might not be possible with graphs, or at the very least more complicated to phrase.

2.

a- Point 1.b- above seems to also be a pedagogical advantage as far as I can tell : you have strictly less things to remember/understand if diagrams are introduced as being indexed by categories.

b- A certain number of arguments about limits and colimits involves taking composites $F(f)\circ F(g)$ where $cod(g) = dom(f)$, and are then just easier to state if you can reduce to $F(f\circ g)$ (here "easier" may be an overstatement, I should say "less awkward")

For instance, suppose you have an inverse limit indexed by $\mathbb N$ and want to replace it with the one indexed by $2\mathbb N$ for some cofinality argument - of course you can do the construction by hand, but it's easier to just define a functor $2\mathbb N\to \mathbb N$ than a directed multigraph morphism (which is a notion you have to introduce too anyways - this comes back to point 2.a- above).

But cofinality arguments aren't even the only ones where you want to something like this (to give a second example, a condition you often meet is "for every $f$, $F(f)$ is blah" for some interesting notion "blah", which you would have to replace with "for every composable sequence, ...").

Here are some examples:

i. Let me stress the cofinality example, which is especially important in higher category theory where you can less often compute co/limits by hand, and so cofinality arguments come in very handy.

ii. When you're working with directed colimits in concrete categories, it's just less awkward, in the situation $i\leq j \leq k$, to have the composite be part of the diagram rather than have to say "well it works because $F(ij)$ and $F(jk)$ are in the diagram"

iii. The Mittag-Leffler argument, when you're working with $\mathbb N$-indexed diagrams in suitably nice abelian categories (even very concrete), is always very nice, and it's just less awkward to write "the sequence $\mathrm{im}(f_{ki})$ stabilizes" than "the sequence $\mathrm{im}(f_{k(k-1)}\circ f_{(k-1)(k-2)}...f_{(i+1)i})$ stabilizes". (this is secretly a cofinality argument, but with a different feel so let me add it anyways, because this part is about pedagogy)

Answer 4

I just noticed something which invalidates my argument nr. 1 for the definition using graphs.

If $F,G : \mathcal{C} \to \mathcal{D}$ are functors, the notion of a morphism $F \to G$ (aka natural transformation) also just uses the underlying graph of $\mathcal{C}$. The naturality square only involves composition in $\mathcal{D}$.

But of course this does not imply that the notion of a morphism of functors should be restricted to functors on graphs.

Also, there is a different definition of a morphism of functors which actually uses composition in $\mathcal{C}$ and in $\mathcal{D}$: For every morphism $f : c \to c'$ in $\mathcal{D}$ we have a morphism $\alpha(f) : F(c) \to G(c')$ in $\mathcal{D}$ such that $\alpha(g \circ f) = \alpha(g) \circ F(f)$ and $\alpha(g \circ f) = G(g) \circ \alpha(f)$.

Answer 5

A limit of an idempotent (viewed as a diagram whose shape is the "idempotent category") is a splitting of the idempotent. This cannot be expressed using directed graphs as shapes I think.