# On the monadicity of Cat

I heard that the category of small categories is monadic over the category of small graphs, the monad being the free-graph functor. I interpreted that statement as: the Eilenberg-Moore category of the free-graph monad is isomorphic to the category of small categories.

However, I can't figure out such isomorphism.

Are those categories really isomorphic? Or are they only equivalent?

I would welcome any hint on how to define this isomorphism or equivalence.

Let $$C$$ be a small category, $$UC$$ its underlying graph, and $$FUC$$ the free category on $$UC$$. All of these entities have the same set of objects, say $$X$$. Now, $$F(UC)(x,y)$$ is the set of all formal paths in $$C$$ from $$x$$ to $$y$$. In other words, a typical element in $$FUC(x,y)$$ is a finite composable sequence of morphisms in $$C$$ starting at $$x$$ and ending at $$y$$. Since $$C$$ is a category, such a sequence can be composed in $$C$$ to yield a single morphism $$x\to y$$. This defines a function $$a\colon FUC(x,y)\to UC(x,y)$$. All of these patch together to give a morphism $$a\colon UFUC\to UC$$ in $$\mathbf{Grph}$$. It is easily seen to be an algebra for the monad $$UF$$, so each category $$C$$ determines an algebra structure on $$UC$$. Conversely, if $$G$$ is a graph and $$a\colon UFG\to G$$ is an algebra structure, then deciphering the unit and multiplication compatibilities show that $$a$$ resolves each composable sequence of morphisms into a single morphism. Further, it does so associatively and it assigns identities as well. In other words, an algebra structure on $$G$$ is a category structure on $$G$$. These two processes are each other's inverse, so, yes, the category of small categories is monadic in the sense that it is isomorphic to the Eilenberg-Moore category of the monad induced by the free category functor on graphs.

As usual with monads, the way the algebraic structure is encoded is unbiased; while typically in a category we think of identities and composition of two morphisms as the structure, and then impose associativity axioms, the monad way defines the category by first creating the object encoding all composition problems to be solved, and then the algebra structure is an assignment of a solution for each such problem, in a coherent way.

More generally, and with virtually the same proof, the category of small $$V$$-enriched categories is monadic over $$V$$-graphs, provided $$V$$ is symmetric cocomplete closed monoidal (it suffices that $$V$$ has all small coproducts and that the tensor product distributes over them).

• This looks very similar to a manual proof that the underlying set functor from monoids to sets is monadic -- which is probably unsurprising, given the interpretation of small categories as being essentially monoids with some "grading" structure. In particular, for example given algebra structure $a : UFG \to G$ you define composition of compatible maps $x,y$ as being $a([x, y])$ and then associativity follows from $a([a([x,y]),z]) = a([a([x,y]),a([z])]) = a(\mu([[x,y],[z]])) = a([x,y,z]) = \cdots = a([x,a([y,z])])$. Sep 30, 2021 at 22:29
• @Bob That would follow from $a([x, a([]) ]) = a([a([x]), a([]) ]) = a(\mu([ [x], [] ])) = a([x])$. Jan 27 at 17:09
• @DanielSchepler Why is $a([a([x]),a([])])$ equal to $a(μ([[x],[]]))$?
– Bob
Jan 27 at 21:43
• Because the left hand side is $(a \circ UFa)([ [x], [] ])$ since in general $UF(g)([y_1, \ldots, y_n]) = [g(y_1), \ldots, g(y_n)]$; and by the condition that $a$ is a $UF$-action, we must have $a \circ UFa = a \circ \mu$. Jan 27 at 22:15
• By induction on the length of the list, using the identity $a([y_1, \ldots, y_n]) = a(\mu([ [y_1, \ldots, y_{n-1}], [y_n] ])) = a(UFa([ [y_1, \ldots, y_{n-1}], [y_n] ])) = a([ a([y_1, \ldots, y_{n-1}]), a([y_n]) ]) = a([ a([y_1, \ldots, y_{n-1}]), y_n ])$, it follows that an algebra is uniquely determined by its actions on the empty list and on lists of two elements. And pretty much directly from the definitions, if you start from an algebra $(G, a)$ and get a category and another algebra, that new algebra agrees with the old one on the empty list and on two-element lists. Feb 1 at 17:34