Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

  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.


share|cite|improve this question

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).

share|cite|improve this answer
That's a much better example than the one I was trying to construct. – Michael Burge Oct 12 '12 at 15:36
up vote 0 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.