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:
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:
- Objects are the vertices
- Morphisms are the edges.
- 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.
- 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:
- 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.
- 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.
- 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.