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 work with composable sequences of arrows of a cat?

Francesco Bilotta (May 16 2021 at 15:40):

Suppose I am given a (small) category $\mathcal{C}$.
I would like some ideas about what structure is enjoyed by the sequences of composable arrows of $\mathcal{C}$.
I heard about the nerve construction, showing that sequences of composable arrows arrange in a simplicial complex, giving a topological model of the category. This is thanks to compositionality, in the sense that given two arrows $f$ and $g$ we get a two simplex having $f,g$ and $fg$ as faces, for instance.
This is really nice but I would like to know if we can have sequences of composable encoded (as objects or morphism or otherwise) in another category $\mathsf{Seq}(\mathcal{C})$, in order to have a kind of semantical place to talk about them. Moreover I would like to consider possibly infinite composition sequences.
What I thought is to consider the functor category:
$\mathbb{N}^{op}\to\mathcal{C}$
But I would be curious about other way of reasoning about the same data.

Jade Master (May 16 2021 at 16:21):

What you might want is the free category on the underlying graph of C. This will have objects given by objects of C and a morphism from x to y will be a sequence of composable morphisms in C starting in x and ending in y.

Francesco Bilotta (May 16 2021 at 18:01):

Thanks, that would indeed be the idea if C was simply a graph, but C is already a category, so I don't clearly see which information I would add doing so

Amar Hadzihasanovic (May 16 2021 at 18:09):

Jade is right, you would get what you are asking for except for the “infinite sequences” part.

There is an adjunction $F \dashv U$ between the category of small categories and the category of directed graphs/quivers; $F$ builds the “free category on the graph” and $U$ takes the “underlying graph” of a category. Jade is suggesting that you consider $FU\mathcal{C}$ for a small category $\mathcal{C}$. A morphism in $FU\mathcal{C}$ is precisely a (finite) sequence of composable morphisms in $\mathcal{C}$. You get its composite through the counit of the adjunction $\epsilon_\mathcal{C}: FU\mathcal{C} \to \mathcal{C}$.

Mike Shulman (May 16 2021 at 18:13):

In fact you can use $FU$ to build a whole "comonad resolution" of $\mathcal{C}$ that generates a simplicial category.

Francesco Bilotta (May 16 2021 at 18:41):

@Amar Hadzihasanovic , thanks, it absolutely makes sense: I read @Jade Master comment too quickly.
@Mike Shulman, you mean iterating the construction to get something like $\dots FUFUC\xrightarrow{FU\epsilon_C}FUC\xrightarrow{\epsilon_C}C$ ?
where can I read about it ? It seems interesting

Fawzi Hreiki (May 16 2021 at 18:43):

It's called the Bar resolution

Fawzi Hreiki (May 16 2021 at 18:43):

Mac Lane in his chapter on monoidal categories is a good introduction

Francesco Bilotta (May 16 2021 at 18:45):

Thanks!

Fawzi Hreiki (May 16 2021 at 18:49):

The nLab page is also pretty good. By the way, this works not just for monads but for any monoid in a monoidal category. This is because the augmented simplex category $\Delta_a = \{[-1], [0], [1], [2], ...\}$ is the free monoidal category on a monoid so any such monoid gives you a simplicial object in this way.

Francesco Bilotta (May 17 2021 at 07:54):

Since the construction of the free category on a graph has been mentioned, I take advantage to ask a curiosity about it.
Obviously isomorphic graphs are sent to isomorphic categories by the free functor, and I think I also heard somewhere that it reflects equivalence of categories to isomorphism of graphs.
Anyhow, we often compare graphs with other notions than functional isomorphism. For instance, what about bisimilar graphs? Can we obtain a relation between the free categories in this case ? I know we can formalize the category of graphs and bisimilarity in terms of coalgebra, but I never saw this problem addressed.

Fawzi Hreiki (May 17 2021 at 08:32):

What is bisimilarity of graphs?

Francesco Bilotta (May 17 2021 at 09:06):

Let (G,→) be a graph. A relation R on G is a bisimulation if the following holds: whenever x R y,
If x → x′, then there is some y → y′ such that x′ R y′.
If y → y′, then there is some x → x′ such that x′ R y′.
A bisimulation between two graphs G,G' is a bisimulation on their disjoint union G+G'.
Two graphs are bisimilar if there exist a bisimulation which includes all their vertices.
I think that you may equivalent think a bisimulation between two graphs as the graph of a zig-zag morphism of graph: one which not only preserves but also reflects arrows.
Here is further explanation https://plato.stanford.edu/entries/nonwellfounded-set-theory/#3

Francesco Bilotta (May 17 2021 at 09:19):

For instance, the graph with one point and one self-arrow
$$*\circle$$
should be bisimilar to the graph
0→1→ 2→...
via the relation:
$\{(*,0),(*,1),(*,2),...,(*,n),...\}$

Jade Master (May 17 2021 at 16:19):

It's true that if $f:G \to H$ gives an isomorphism of free categories $F(f) : F(G) \to F(H)$ then f is an iso of graphs but it's not true that every isomorphism $F(G) \to F(H)$ gives an Isomorphism between their underlying graphs... isomorphisms of categories are more general.

Jade Master (May 17 2021 at 16:23):

If your category of graphs is set up right, then simulations will just be morphisms and a bisimulation between G and H will be a span of graphs $G \leftarrow A \to H$. Maybe you also want to say that the two morphisms in this span are surjective or some other condition.

Jade Master (May 17 2021 at 16:25):

If bisimulations are defined this way then you can hit it with the free category functor to get a span of categories $F(G) \leftarrow F(A) \to F(H)$. Functoriality of the morphisms in this span say that the bisimulation actually preserves paths in G and H.

Martti Karvonen (May 17 2021 at 16:47):

Jade Master said:

It's true that if $f:G \to H$ gives an isomorphism of free categories $F(f) : F(G) \to F(H)$ then f is an iso of graphs but it's not true that every isomorphism $F(G) \to F(H)$ gives an Isomorphism between their underlying graphs... isomorphisms of categories are more general.

Do you have an example of this? Free categories are funny in that you can recognize the edges of the original graphs as those morphisms that don't admit nontrivial factorizations, so I wouldn't be surprised if any isomorphism would let you recover an isomorphism of graphs as well

Fawzi Hreiki (May 17 2021 at 17:19):

Are there any examples of isomorphisms of free categories which don't give isomorphisms of their underlying graphs?

Jade Master (May 17 2021 at 17:29):

@Martti Karvonen oh yeah you're right. I should have said equivalence of categories. An isomorphism of categories must be a bijection on objects and a bijection on morphisms. If it sends an edge to an identity then it's not injective and if it sends an edge to a composite then it's not surjective.

Kenji Maillard (May 17 2021 at 17:44):

Aren't isomorphic objects in a free category necessarily equal ? (so that an equivalence between free categories is actually an isomorphism)

Jade Master (May 17 2021 at 18:02):

Okay okay what I was really thinking of was a homotopy equivalence between their nerves lol it is a big leap

Tom Hirschowitz (May 18 2021 at 05:02):

Jade Master said:

If your category of graphs is set up right, then simulations will just be morphisms and a bisimulation between G and H will be a span of graphs $G \leftarrow A \to H$. Maybe you also want to say that the two morphisms in this span are surjective or some other condition.

Not quite, I think. Another way to define bisimulations of graphs is:

• Let $s: [0] \to [1]$ denote the "source" morphism, mapping the walking vertex to the walking edge, picking up the source of the latter.

• A functional bisimulation is any graph morphism weakly right orthogonal to $s$ (after Joyal, Nielsen, Winskel).

• A bisimulation is a span of graphs whose legs are both functional bisimulations.

• A bisimulation relation is a relation whose associated span is a bisimulation.

• Two graphs are bisimilar when there exists a bisimulation between them, whose legs are both surjective.

Tom Hirschowitz (May 18 2021 at 05:07):

I'd have to think a bit more to answer @Francesco Bilotta's question, but there is a notion of bisimilarity in categories, obtained by taking weak right orthogonality w.r.t. the image of $s$ by the "free category" functor. This will probably be similar to weak bisimilarity, in the sense that it will be insensitive to "non-branching" arrows, so my guess is bisimilarity will be preserved, but not reflected by the "free cat" functor.

John Baez (May 18 2021 at 05:32):

@Francesco Bilotta wrote:

Obviously isomorphic graphs are sent to isomorphic categories by the free functor, and I think I also heard somewhere that it reflects equivalence of categories to isomorphism of graphs.

Ignoring equivalence for a minute and just thinking about the category of categories, "$F$ reflects isomorphism" means: if $f: G \to H$ is a morphism of graphs such that $F(f): F(G) \to F(H)$ is an isomorphism, than $f$ is an isomorphism.

I will prove this true by proving something stronger. I'll show that $\alpha: F(G) \to F(H)$ is any isomorphism, it equals $F(f)$ for some isomorphism of graphs $f: G \to H$.

Jade Master said:

it's not true that every isomorphism $F(G) \to F(H)$ gives an Isomorphism between their underlying graphs...

I'll prove you wrong. :smiling_devil:

Given a free category on a graph, say $C$, we can figure out what graph $G$ it's free on:

• The set of vertices of $G$ is the set of objects of $C$.

• The set of edges of $G$ is the set of prime morphisms of $C$: nonidentity morphisms that can't be factored as a product of two nonidentity morphisms .

• The source and target maps sending edges of $G$ to vertices are just the source and target maps in $C$, restricted to morphisms that are edges of $G$.

Now suppose $\alpha: F(G) \to F(H)$ is an isomorphism between categories that are free on graphs.

Since $\alpha$ is a bijection on objects, it gives a bijection between vertices of $G$ and vertices of $H$.

How about morphisms?

$\alpha$ sends identity morphisms to identity morphisms. Because $\alpha$ is a bijection on morphisms, $\alpha$ thus sends nonidentity morphisms to nonidentity morphisms.

Thus, $\alpha$ sends morphisms that can be factored as a product of two nonidentity morphisms to morphisms that can be so factored.

Since $\alpha$ is a bijection on morphisms, it must therefore send morphisms that can't be factored as a product of two nonidentity morphisms to morphisms that can't be so factored.

Thus, $\alpha$ sends prime morphisms of $F(G)$ to prime morphisms of $F(H)$.

Thus $\alpha$ sends edges of $G$ to edges of $H$.

Since the same is true of $\alpha^{-1}$, $\alpha$ must be a bijection between edges of $G$ and edges of $H$.

With a bit more work, we see that $\alpha = F(f)$ for some isomorphism of graphs $f: G \to H$. This $f$ is just the restriction of $\alpha$ to vertices (which are objects) and edges (which are prime morphisms).

Francesco Bilotta (May 18 2021 at 06:49):

Thanks to all for the interesting discussion!

John Baez (May 18 2021 at 14:24):

I just fixed my proof... it had a mistake.

Jade Master (May 18 2021 at 14:37):

@Tom Hirschowitz Are you using the "open map" definition of simulation. I.e. a map is open if it has the path lifting property? I had a long conversation on here about it and also did a lot of thinking and I realized that this definition of open map is pretty much the usual definition of morphism in Grph.

Jade Master (May 18 2021 at 14:38):

By usual morphism I mean a function between edges and a function between vertices which preserve source and target.

Jade Master (May 18 2021 at 14:39):

@John Baez thanks :upside_down:

Jade Master (May 18 2021 at 14:43):

The "pretty much" aspect is that your definition of open depends on what sorts of graphs you decide will be paths

Tom Hirschowitz (May 18 2021 at 16:12):

@Jade Master I think there must be a misunderstanding somewhere: the map $s$ above (from the walking vertex to the walking arrow, picking the source) is one of your usual graph maps, but is not open in my sense, because that would in particular entail that it has a section.

To answer your question, the usual definition of open map is, iirc, for rooted graphs. What I'm using here is a non-rooted adaptation, which is in fact simpler because there is only one generating cofibration.