# Why don't all transitive graphs with a single loop define a category?

I'm reading Abstract & Concrete Categories: The Joy of Cats. On exercise 3A(c), the author defines the graph of a category C to be the large graph whose vertices are the objects in C, and whose edges are the morphisms. He then gives 4 examples of finite graphs and asks which are graphs of a category. The convention is that all nodes have an implicit identity. You can read the exact text since the author kindly put his book online for free:

http://katmat.math.uni-bremen.de/acc/acc.pdf

All of the author's graphs are transitive in the sense that if there is an edge between vertices x and y, and vertices y and z, then there is an edge between vertices x and z.

Define a category over any transitive graph to be the category where:

1. Objects are the vertices
2. Morphisms are the edges.
3. The identity is implicitly on every node. Since multiple loops on a vertex might give problems $(id_a = id_a \circ id_b = id_b)$, let's forbid those - none of the author's example have multiple loops.
4. Composition: Identities compose like $id_v \circ x = x; x \circ id_v = x$. For non-identities, since the graph is transitive, given $f$ in $\hom(x,y)$ and $g$ in $\hom(y,z)$, there exists at least one edge in $\hom(x,z)$. Define two morphisms to be equivalent if they're in the same hom-set. Use the axiom of choice to pick a representative out of each equivalence class, and define it to be the result of $f \circ g$.

I've given all 4 of the things that make up a category, and convinced myself they satisfies the 3 constraints of associativity, identities behaving as they should, and morphisms between objects are pairwise disjoint:

1. Edges between vertices are pairwise disjoint because you can't have an edge on more than 2 vertices. So, an edge belongs to at most one pair.
2. Associativity: This is just function composition. Let (a,b,c) be 3 edges we want to compose(in $\hom(x,y), \hom(y,z), \hom(z,w)$ respectively). The composition law picks a representative r from the set of edges joining each vertex. Then $r = (a \circ b) \circ c$ - that is, r is an edge in $\hom(x,w)$. We're considering the case where $a \circ (b \circ c)$ - also an edge in $\hom(x,w)$ - is different. As long as we always pick the same representative for composition each time, I don't see why this isn't associative.
3. Identities: We have at least one identity on each vertex v by the convention, and they were defined to behave properly.

So every loopless transitive graph defines a category - in particular all of the author's? I feel like I'm missing something, since the exercise seems to intend to be teaching what sorts of categories can and can't be represented as graphs.

Thanks,

-

Well, there can be loops in a category other than identities.

I would say, any transitive directed graphs with at least one loop on each vertex can be a graph of a category (may also contain parallel edges)

Anyway, all graphs determine a category in a natural way: the so called free category on the graph, and its arrows are going to be the paths of the graph (including paths of length $0$ as well).

-
That's a much better example than the one I was trying to construct. –  Michael Burge Oct 12 '12 at 15:36

Oh, I spotted the error. The author wants the given graph for a category, not a category from the given graph. My construction $c$ works if there aren't multiple edges I think, but if there are on a graph $x$ then $(g \circ c \circ g)(x) \neq g(x)$.

I originally thought "It's transitive, so why not just connect the edges?" and ended up answering a different question after I worked out the details.

-