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: “Single-sorted” graph?

Amar Hadzihasanovic (Nov 20 2020 at 10:21):

How do you call the underlying structure of the “morphisms-only” definition of a (small) category?
That is, a set $X$ together with functions $s, t: X \to X$ satisfying $s\circ s = t\circ s = s$ and $s\circ t = t\circ t = t$.

Chad Nester (Nov 20 2020 at 10:27):

I think it's okay to call this a "quiver" or "directed pseudograph", or whatever you usually call the underlying structure of a category.

Chad Nester (Nov 20 2020 at 10:29):

If we consider the corresponding Lawvere theory, then it is Morita-equivalent to the usual two-sorted presentation of quivers: the objects of the idempotent splitting completion are $1_x$, the sort of edges, along with $s\simeq t$, the sort of vertices.

Chad Nester (Nov 20 2020 at 10:30):

So in particular the two versions have the same category of models.

Amar Hadzihasanovic (Nov 20 2020 at 10:32):

But the “underlying structure” functor, under the translation, would be the one that takes the usual “underlying quiver” but also deletes all the identity edges.

Amar Hadzihasanovic (Nov 20 2020 at 10:33):

That's the source of my discomfort with “just” calling it the underlying quiver/graph/whatever.

Chad Nester (Nov 20 2020 at 10:35):

I don't think that's quite right. The underlying structure forgets the identity edges, but they're still there, no? We could add a generator $id : X \to X$ with equations $id;s = 1_x$ and $id;t = 1_x$ to axiomatise reflexive graphs...

Amar Hadzihasanovic (Nov 20 2020 at 10:44):

Hmm, I'm thinking of the fact that we have two different possible equivalences:

• from single-sorted to two-sorted reflexive graphs: $E := X$ and $V := \{x \in X \mid sx = tx = x\}$, with $\varepsilon: V \to E$ being the inclusion of $V$ in $E$;
• from single-sorted to two-sorted graphs: same $V$ but $E := X \setminus V$.

If we take the underlying single-sorted graph of a category, then the first equivalence would take it to the standard underlying reflexive graph, but the second would not take it to the standard underlying graph. So there's an ambiguity...

Matteo Capucci (he/him) (Nov 20 2020 at 10:44):

Reflexive directed graphs?

Matteo Capucci (he/him) (Nov 20 2020 at 10:45):

Your definition is the same as here if I recall correctly https://ncatlab.org/nlab/show/cohesive+topos#Graphs

Amar Hadzihasanovic (Nov 20 2020 at 10:47):

I guess that would lead to the correct forgetful functor, yes.

Fawzi Hreiki (Nov 20 2020 at 10:51):

Surely though there cannot be a notion of non-reflexive single sorted graphs because every arrow has to have a source and a target and so for the whole thing to make sense as a graph, the arrows appearing as sources or targets should have themselves as their source and target.

Fawzi Hreiki (Nov 20 2020 at 10:52):

And this has to be preserved by the morphisms of the category (by virtue of just preserving the sources and targets)

Amar Hadzihasanovic (Nov 20 2020 at 10:55):

Well at the level of objects you can certainly form a bijection between generic (not necessarily reflexive) graphs $s, t: E \to V$ and single-sorted graphs: the second one that I described above. The inverse would be to take $X := E + V$, define $s, t$ as before on $E$ and as the identity on $V$.

Chad Nester (Nov 20 2020 at 10:56):

Indeed, it looks like what I said about idempotent-splitting completions is wrong! I can construct an arrow $s : 1_x \to s$ that works like $id : E \to V$...

Chad Nester (Nov 20 2020 at 10:56):

Thats really neat!

Amar Hadzihasanovic (Nov 20 2020 at 10:56):

At the level of morphisms, you would allow “contractions” of edges which identify their endpoints and remove them, which I agree is not the standard notion of morphism of graphs.

Amar Hadzihasanovic (Nov 20 2020 at 10:58):

So I agree, you have Morita-equivalence only with the two-sorted theory of reflexive graphs...