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: Underlying Graph

Jacques Carette (Jun 01 2020 at 18:57):

There is a forgetful functor from categories to its underlying digraph or, perhaps more precisely, Quiver. This shows up most prominently in two ways: 1) when we draw pictures of (small) categories, and 2) in the Free Category on a directed graph construction, giving a path category.

The problem I have is that this forgetful function seems to do something we don't want: it does not respect the principle of equivalence. Specifically, if one takes the 1-object 1-morphism category (call it One), and the 2-object indiscrete category (or codiscrete 2-object groupoid if you prefer; call it ITwo), the graph of One has 1 vertex and 1 edge, while the graph of ITwo has 2 vertices and 4 edges. So they are 'clearly' not the same graph. And yet the two categories are equivalent as ITwo is contractible.

Two questions:

Have I erred somewhere in the above?
If I have not, is there a 2-categorical (and 2-Quiver) version of the above that makes the example I show above satisfy the principle of equivalence again?

My suspicion is that the resolution of my conundrum indeed involves 2- (and perhaps higher) issues, and that 'truncating' at the 1- level is what produces this phenomenon. This is because the two categories above are equivalent only in a 2-categorical setting, as the natural transformations involved are not trivial (one of them, in one direction, requires a choice).

I don't want an ELI5 explanation, but perhaps one at the 4th year undergraduate level would be appreciated, if that's possible. It does feel that this is somehow 'basic', and ought to have a 'basic' explanation too.

Gershom (Jun 01 2020 at 19:07):

Jacques, I think the "higher" analogue of the underlying digraph that you're looking for is the nerve (https://ncatlab.org/nlab/show/nerve). Since $N : Cat \to SSet$ is full and faithful, then I think that should give your "principle of equivalence".

John Baez (Jun 01 2020 at 19:08):

You're correct, equivalent categories can have inequivalent underlying quivers. (Category theorists call quivers simply "graphs" so I'll do so henceforth; of course "graph" means other things too and "quiver" is less ambiguous.)
This is an interesting question but I don't know the answer. I'll just say this:

There's something a bit like a 2-category of graphs, but it's not a 2-category. The category Graph of graphs is cartesian closed, so it automatically becomes enriched over itself: i.e., for any two graphs $G$ and $H$ we can define a graph of morphisms from $G$ to $H$ . This graph has as its vertices the usual sort of graph morphisms from $G$ to $H$ . Its edges are called graph transformations, which are very much like natural transformations except that the naturality condition - the commuting square condition - is dropped, since it makes no sense to say a square in a graph commutes.

Similarly Cat is cartesian closed, so it automatically becomes enriched over itself, i.e. for any two categories $C$ and $D$ we can define a category of morphisms from $C$ to $D$ . This category has functors from $C$ to $D$ as objects and natural transformations as morphisms.

A Cat-enriched category is a 2-category; a Graph-enriched category is not necessarily.

I believe the forgetful functor U: Cat $\rightarrow$ Graph lifts, via base change, to a funny kind of enriched functor from the 2-category Cat to the Graph-enriched category Graph. I could say more about this but I'm not sure this is what you want. Explaining it requires explaining when we can define a functor from a $V$ -enriched category to a $W$ -enriched category, where $V$ and $W$ are not the same!

Jacques Carette (Jun 01 2020 at 21:32):

Thanks. This will need a bit of ponder time.

For a bit more background: I'm working in a Setoid-enriched setting without Choice (or excluded middle). So defining what it means for 2 edges of a graph to be equivalent is a non-trivial question, and is indeed about graph transformations.

I am interested in knowing whether there is a sensible Bicategorical analogue. I've seen things in the literature, but they all seem like they don't forget enough. The idea of having Graph enriched over itself is very appealing, so if there's a generalization in that direction/setting, I would be quite interested.

Even more background: in my setting, getting Agda to believe that what I'm doing is not nonsense is... delicate. There are issues around strictness that bother me. I'm trying to be as weak as possible, as things mostly work just fine, but this (and finite categories) are two places where things don't work so well.

John Baez (Jun 01 2020 at 21:46):

I'll just say that a Graph-enriched category is a lot like a 2-category; what it lacks is the ability to "vertically" compose 2-morphisms, because you can't compose edges in a graph. I don't know any useful 2-category or bicategory of graphs.

Jacques Carette (Jun 01 2020 at 21:49):

Wouldn't it be a 2-category of 2-graphs, i.e. with 2-edges between paths? You can't just erase that 2- structure, it has to go somewhere.

John Baez (Jun 01 2020 at 21:51):

As I said, the "underlying graph of a category" is really an enriched functor from the Cat-enriched category (i.e. 2-category) Cat to the Graph-enriched category Graph. The 2-structure doesn't get erased: natural transformations get mapped to graph transformations.

John Baez (Jun 01 2020 at 21:53):

Again, it takes some work to explain what I mean by an enriched functor from a $V$ -enriched category to a $W$ -enriched category (while the notion of enriched functor is standard if $V = W$ ).

John Baez (Jun 01 2020 at 21:53):

So, I won't explain it unless someone wants to know.

Gershom (Jun 01 2020 at 22:08):

So part of my intuition on the relationship to nerve comes from David Spivak's paper which talks about hypergraph models of networks and their relationship to sset. I don't know if there's anything there, but it might be worth considering: http://math.mit.edu/~dspivak/informatics/HDMSN.pdf

Morgan Rogers (he/him) (Jun 02 2020 at 11:11):

Even including graph transformations, the concept of equivalence of graphs is not well-defined if we enrich over graphs, since even if we have what should be 'invertible' transformations, we have no way of formalising composition to the identity.
A possible route around your dilemma could be to consider subsuming both categories and graphs into a category of paracategories, which amount to quivers with partially-defined composition. If it's possible to enrich this category over itself (I haven't studied these, so have no idea if the monoidal product one might guess at is well-defined, let alone closed) then there's just enough structure to make equivalences of graphs make sense. It might be some work, but the relationships between categories, paracategories and graphs look to mesh into a satisfying theory.