Is a graph with a single vertex and multiple edges already a free category

category-theorygraph theory

I am reading Category Theory for Programmers. Challenge 3.1.4 gave me a head scratch:

Generate a free category from… a graph with a single node and 26 arrows marked with the letters of the alphabet: a, b, c … z.

My understanding is that, to make this graph a category, each object must have an identity morphism AND each morphism must compose associatively.

My first thought was that this graph is already a category; my second thought is that I might be missing something. Is this graph already a category?

enter image description here


Here are some questions that came to mind. I do not need answers to them all, but I thought I would put them down here anyway to show my thinking.

  1. What is the meaning of a graph with a single node that has multiple edges? Are those edges redundant with each other, or can we assume that there is something to differentiate them, such as each having a different weight.
  2. Does each edge already represent an identity morphism, or do we need to add the identity morphism explicity?
  3. Do we need to add the composition morphisms explicitly, or can we assume that the composition of edgeA with edgeB is the same as the original edgeA, because they both start and end with the same object?

Best Answer

A graph can be defined as a pair of functions $s,t:E\to V$, where the elements of the sets $E,V$ are referred to as 'edges' and 'vertices', and $s$ selects the 'source' and $t$ the 'target' of an edge $e\in E$.

  1. In that regard, the given graph has $|V|=1$ and $|E|=26$, so the 26 edges can be distinguished from each other, though each goes $x\to x$ where $x$ denotes the only vertex.
  2. If we generate a free category on a graph, we always have to add the identity morphisms, even if the graph contains loops.
  3. With your artificial choice of composition (and adding an identity), we indeed get a category. However, this is not the free category generated by that graph.
    In the free category, composition is defined formally, so that we will have an arrow for every word (finite sequence) of the given edges.

In general, the morphisms of the free category generated by a graph are exactly the paths of the graph (including paths of zero length for the identities).

Note also that if a category has only one object, it is basically a monoid, as any two arrows can be composed, and thus the exercise is to find the free monoid on 26 generators.