Do I need an "explicit" identity morphism to have a category?

Question

I'm trying to study category theory as an autodidact, using Bartosz Milewski's Category Theory for Programmers, and I've just finished chapter 1, where the last question/exercises is whether a directed graph is a category.

So looking at a simple graph example as this, where there are no arrows connecting a point directly to itself.

But is that necessary? I'd say no, as I can compose the other non-identity morphisms (one is actually not even necessary, the counter-clockwise arrow) to get all of the three identity morphisms.

So, I thought that a directed graph is a category if I can reach any point from any point, as that seems to me as a sufficient condition for being able to write an identity morphism for each of the points.

Answer 1

The convention I stick to firmly is that questions like "is a directed graph a category" are meaningless; it's neither true nor false, the question is just ungrammatical. You can see this blog post awhile ago for examples and discussion of other ungrammatical questions in mathematics.

Here is a simpler example to understand: the question "is a set a group" is also meaningless, because being a group is a structure, not a property. The definition of a group breaks up into two bits: a group is a collection of data subject to some axioms, and the meaningful way to ask "is $X$ a group" is for $X$ to be a collection of the appropriate data for which you are being asked to check the axioms, namely

• a set $X$,
• a candidate multiplication $m : X^2 \to X$, and
• a candidate identity $e : 1 \to X$.

You might call such a tuple $(X, m, e)$ a pregroup; then it's meaningful / grammatically correct to ask whether a pregroup is a group, since satisfying the group axioms is a property of a pregroup.

It is similarly meaningless to ask whether a directed graph is a category. The definition of a category again breaks up into two bits, a bunch of data subject to a bunch of axioms, and again the meaningful way to ask "is $C$ a category" is for $C$ to be a collection of the appropriate data for which you are being asked to check the axioms, namely

• a collection $C_1$ of candidate morphisms and a collection $C_0$ of candidate objects,
• candidate source and target maps $s, t : C_1 \to C_0$,
• a candidate composition map $\circ : C_1 \times_{C_0} C_1 \to C_1$ (leaving the source and target maps needed to write the pullback implicit), and
• candidate identity morphisms $\text{id} : C_0 \to C_1$.

And again you might call such a tuple $(C_1, C_0, s, t, \circ, \text{id})$ a precategory, and then it's meaningful / grammatically correct to ask whether a precategory is a category, since satisfying the category axioms is a property of a precategory.

A directed graph does not supply the necessary data for a precategory; it consists at best of candidates for $C_1$ (the edges), $C_0$ (the vertices), and $s, t$ (the source and target maps identifying the endpoints of the edges), but contains no candidates for either composition or identity morphisms. This is true whether or not there exist such candidates (and there generally won't); every set admits at least one group structure but I still maintain that this does not imply that the answer to "is a set a group" is "yes."

Answer 2

Your example has a class (in fact, set) of objects: the three blue dots (I call them $1,2,3$ in the obvious order in the image.

For every two objects $a,b$, you have a (candidate) set of morphisms: the set of arrows from $a$ to $b$. Note that this set is empty for several pairs, e.g., there is no morphism from $2$ to $1$ and no morphism from $1$ to $3$. No problem, that's okay and happens eben in the best categories. But there is also no ("explicit") morphism from any object to itself. Nor do we have a law of composition: Two arrows together do not make an arrow.

So in order to speak of a category, we must define the set of morphisms from $a$ to $b$ differently. It somewhat suggests itself to take the set of walks from $a$ to $b$ as set of morphisms. This solves all problems we have automatically:

• We have the empty walk from $a$ to $a$ as identity morphism. (Even though all three empty walks are the same, we should still distinguish them by their varying "starting" and "end" points).
• We have a law of composition: A walk from $a$ to $b$ followed by a walk from $b$ to $c$ is a walk from $a$ to $c$.
• We verify that composition is associative and that empty walks do indeed behave as identities (i.e., neutral under composition)

An even more sophisticated choice of morphisms might be to take all walks modulo an equivalence relation where going along a double-arrow and immediately back cancels (i.e., the two directions of such an arrow are inverses). This works, but showing associativity of composition requires a bit more care.

If we had an explicit arrow $1\to 1$, say, then the walk $1\to 1\to 2$ would not be the same walk as $1\to 2$ alone, i.e., $1\to 1$ would not act as identity. We'd still have only the empty walk act as identity!