33
$\begingroup$

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.
  1. 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.

  1. 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.
  2. 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?
$\endgroup$
8
  • 2
    $\begingroup$ Without looking at all the details of your question: Have you checked out Grothendieck's Alger Lecture Notes "Introduction au langage fonctoriel" from 1965/66, where the notion of "type de diagramme" is used. It is the same as the "carquois" in Bourbaki's TA II.1. $\endgroup$ May 1, 2021 at 10:28
  • 8
    $\begingroup$ Isn’t composition in the shape used to enforce commutativity of the diagram? $\endgroup$ May 1, 2021 at 10:41
  • 1
    $\begingroup$ Using categories is strictly more general, no? You can always replace a directed multigraph with the free category it generates. More generally you might consider "partial" categories where some composites may be undefined. I think this is what happens when developing the theory of quasicategories – there they allow arbitrary simplicial sets to be shapes. $\endgroup$
    – Zhen Lin
    May 1, 2021 at 11:35
  • 3
    $\begingroup$ @ZhenLin "You can always replace a directed multigraph with the free category it generates" Yes, and I have remarked this in the first point in my list, and I also explained why it does not give more limits. So, in the end it is not more general. $\endgroup$ May 1, 2021 at 11:43
  • 3
    $\begingroup$ Gabriel and Zisman ("Calculus of fractions and homotopy theory", 1967) use this, they call your directed multigraphs "Diagram schemes" $\endgroup$ May 1, 2021 at 15:07

5 Answers 5

25
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you for this answer. About your first point: "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." This is actually contrary to my observation, see also the examples mentioned in my post. Basically, I have observed that diagrams are usually defined on small "toy graphs", and Kan extensions seem to be one of the few exceptions. But I have to admit that I have not worked enough with higher category theory yet, maybe the situation is different there. ... $\endgroup$ May 5, 2021 at 13:21
  • 1
    $\begingroup$ ... But as already indicated by Tim Campion in another comment, of course in the $\infty$-categorical we would not take $1$-dimensional objects (graphs) as shapes of diagrams, but simplicial sets for instance ("$\infty$-categories without composition"). This should work then, right? If so, this is not an argument against using graphs for $1$-categories. $\endgroup$ May 5, 2021 at 13:26
  • $\begingroup$ @MartinBrandenburg I insist that there are many diagrams which are defined on categories. For instance, when you express the fact that any presheaf is a colimit of representable ones, or when you say that any object of finite type is a filtered colimit of objects of finite presentation. When we consider descent data, we have to deal with simplicial objects... $\endgroup$ May 5, 2021 at 17:32
  • $\begingroup$ However, it is true that we can express many features using $1$-dimensional objects, and it is important to point this out. The last part of my answer is an attempt to formalize this kind of things systematically. This is very compatible with Tim Campion's comments: it is important to understand how the description of categories as colimits of simpler objects affects our understanding/computation of categorical constructions... $\endgroup$ May 5, 2021 at 17:35
  • $\begingroup$ ... The higher dimensional version of this is the description of higher categories as colimits of simple objects such as simplices, and simplcial sets are a way to describe such presentations. $\endgroup$ May 5, 2021 at 17:35
14
$\begingroup$

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.)

$\endgroup$
4
  • 2
    $\begingroup$ Regarding the first point, I think filtered indexing categories provide another example which would be quite awkward in a graph-based approach. $\endgroup$
    – Tim Campion
    May 1, 2021 at 13:05
  • $\begingroup$ @TimCampion Yes, in fact, I wanted to mention them in my post, but just named the special case of directed partial orders. $\endgroup$ May 1, 2021 at 18:14
  • $\begingroup$ @TomLeinster: Thank you for your answer. Reflexive pairs, that is a really good point ... I probably missed this because monads don't appear in my book :), in particular no Beck's Theorem. The example about induction on the number of arrows is also a very instructive example. But I am not sure about the meaning of the sentence "I'm not convinced that what they've done is entirely respectable" - can you perhaps say this again with different words? $\endgroup$ May 1, 2021 at 18:17
  • $\begingroup$ Unfortunately I can only accept one answer :-) $\endgroup$ May 11, 2021 at 13:33
11
$\begingroup$

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)

$\endgroup$
6
  • 7
    $\begingroup$ I suppose Lurie's approach, where I believe limits and colimits are defined for diagrams indexed by any simplicial set rather than just any quasicategory, could be regarded as a higher analog of the graph-based approach. In fact, I can think of at least one key technical argument relying on this -- the fact that the poset $\mathbb N$ is the free category on a graph $G$ leads to the observation that the inclusion $G \to \mathbb N$ is cofinal. Moreover, $G$ is 1-skeletal. This observation is needed e.g. to construct all limits out of products and pullbacks IIRC. $\endgroup$
    – Tim Campion
    May 1, 2021 at 13:06
  • 1
    $\begingroup$ @TimCampion : I don't remember those details, so let me not be too confident about this; but I would say that this is very likely not essential to the proof. Furthermore, I still think it is misleading to say that compositions are not taken into account when you think of higher CT, because they are in many cases $\endgroup$ May 1, 2021 at 15:03
  • $\begingroup$ I think it is essential to the proof. In general one has all limits if one has totalizations and products, so it suffices to construct totalizations. A totalization is constructed as the limit of the tower of truncated totalizations (which are finite limits and thus constructible from pullbacks and termnal objects in the usual way), so it suffices to construct $\mathbb N^{op}$-indexed limits. These are constructed as an equalizer of products; the proof that this is correct uses the 1-skeletal initial simplicial subset $G^{op}$. This fails for higher ordinals, for instance. $\endgroup$
    – Tim Campion
    May 1, 2021 at 15:12
  • $\begingroup$ @MaximeRamzi Thank you for your answer. Can you please add some specific examples for 1d and 2b? I have never seen them, I guess. $\endgroup$ May 1, 2021 at 18:12
  • $\begingroup$ @MartinBrandenburg : I have added some examples to both - not as many as I would have liked because of course this is the type of situation where you forget all examples you ever knew the minute you're asked about some :D $\endgroup$ May 2, 2021 at 9:55
1
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ Correct, the definition of natural transformation does not involve composition in the domain. However, this is only true for 1-categories, not for higher categories. Thus, the graph approach doesn't "scale". $\endgroup$
    – Jonas Frey
    Nov 4, 2022 at 22:29
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Please see the first point in my question. Every limit can be reduced to one with respect to graphs. $\endgroup$ Nov 4, 2022 at 18:29
  • $\begingroup$ Ahh yes, the limit of an idempotent is just a limit of an endomorphism, which can be expressed by a graph-shape. But still sometimes you want to say that a category C does not have all limits indexed by a certain graph, but only a certain subclass which can be captured by a category structure on a graph. Another example is (apart from idempotents) is reflexive coequalizers. $\endgroup$
    – Jonas Frey
    Nov 4, 2022 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.