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: why graphs are not algebraic?

Ambroise (Mar 08 2021 at 01:39):

I am trying to understand Adamek-Rosicky's example 3.8 in their monograph about Locally presentable categories explaining why graphs (i.e., sets equipped with a binary relation) do not form a variety: take a non discrete graph equipped with an equivalence relation on its vertices. By
equipping this equivalence with a discrete graph structure, it upgrades into an equivalence relation in graphs, which is not the kernel pair of any other graph morphism, and thus graphs cannot form a variety. Unfortunately, I don't see why the induced equivalence relation on graphs is reflexive. What am I missing? I found the same argument in Adamek-Rosicky-Vitale's monograph on algebraic categories, Example 3.15.

Todd Trimble (Mar 08 2021 at 04:05):

I think you're right, inasmuch as there is no "diagonal" $K \to E$ (using their notation), which is needed in order to have an internal equivalence relation on $K$. But I think this can be fixed by considering the following example: take $K = (0 \to 1)$, and take $E$ to consist of vertices $(0,0), (0, 1), (1, 0), (1, 1)$, with a single edge $(0, 0) \to (1, 1)$. Then the obvious pair of projections $p_1, p_2: E \rightrightarrows K$ is an equivalence relation which won't be the kernel pair of any map $K \to Q$.

Ambroise (Mar 08 2021 at 20:58):

Thanks! But, in your example, isn't E ⇉ K the kernel pair of the terminal morphism, since E = K×K ? Maybe the following example works: take K consisting of two looping arrows, and E extends K with two points. Now, the domain of the kernel pair of a morphism K → G is either K or K×K, depending on whether the looping arrows are mapped to the same element in G, so E ⇉ K cannot be a kernel pair. It seems that this example can be adapted to show that even the full subcategory of Set^→ consisting of injections is not a variety.

Todd Trimble (Mar 08 2021 at 21:25):

It's possible I made a mistake, but I thought I did extend $K$ with two points.

Anyway, there are lots of ways of seeing that these examples are not Barr exact. In the case of graphs: these form a quasitopos. If it were Barr exact, then it would also be a topos, and hence balanced. But that can't possibly be right.

Todd Trimble (Mar 08 2021 at 21:42):

Ambroise said:

Thanks! But, in your example, isn't E ⇉ K the kernel pair of the terminal morphism, since E = K×K ? Maybe the following example works: take K consisting of two looping arrows, and E extends K with two points. Now, the domain of the kernel pair of a morphism K → G is either K or K×K, depending on whether the looping arrows are mapped to the same element in G, so E ⇉ K cannot be a kernel pair. It seems that this example can be adapted to show that even the full subcategory of Set^→ consisting of injections is not a variety.

$Set^{inj \to}$ is also a quasitopos, and the same argument as in my last comment applies: if it were Barr exact, then it would be balanced.

Fawzi Hreiki (Mar 08 2021 at 22:03):

Is it not possible to just see that a product preserving functor need not preserve monos and thus need not preserve graphs?

Todd Trimble (Mar 08 2021 at 22:37):

Fawzi, are you arguing for another way of seeing that the category of graphs is not monadic over any power of $Set$? That's what I understood this discussion to be about.

Fawzi Hreiki (Mar 08 2021 at 22:41):

You're right. I think I misunderstood.

Ambroise (Mar 09 2021 at 00:53):

Todd Trimble said:

It's possible I made a mistake, but I thought I did extend $K$ with two points.

Anyway, there are lots of ways of seeing that these examples are not Barr exact. In the case of graphs: these form a quasitopos. If it were Barr exact, then it would also be a topos, and hence balanced. But that can't possibly be right.

So, what is $K \times K$ in your example? When I compute it, I find it is indeed $K$ extended with two points: in $K\times K$ there must be 4 points and 1 arrow, since in $K$ there are 2 points and 1 arrow. Am I wrong?

Todd Trimble (Mar 09 2021 at 03:18):

Ambroise, I'll probably decline to pursue this since you seem satisfied that you have an example, which is good. I'm not saying you're wrong, and there's a good chance my example was botched, but the main point I wanted to make is that there are various ways of seeing that sets equipped with a binary relation cannot possibly be Barr exact.

Ambroise (Mar 09 2021 at 04:59):

Sure! Thanks for your help!

Tom Hirschowitz (Mar 09 2021 at 14:13):

@Ambroise, I think I agree that @Todd Trimble's argument doesn't quite work. Would you agree that it does work for preorders? Your example for graphs looks good to me.