adjoint-functorscategory-theoryfunctorsmonads
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.
These categories are indeed actually isomorphic, since the equivalence between them is actually bijective on objects. More generally, equivalences of concrete categories where the corresponding objects actually have the same underlying sets are typically isomorphisms (because the equivalence is just giving a bijection between structures of two different types on a given set, which respects the morphisms of the two types of structures).
Maybe category theorists don't care about that because equivalence is enough to say that two categories are "the same"?
Yes, this is exactly right. By far the most commonly used notion of "sameness" for categories is equivalence, not isomorphism. It could even be said that if you want to demand categories to be isomorphic rather than just equivalent, what you are doing is probably not really "category theory". So, on the rare occasions that you have an equivalence of categories that is actually in fact an isomorphism, many people would not even notice, and if they did notice, they would often not consider it worthy of mention.
Here is one way of defining "monad".
Definition 1. A monad in a 2-category $\mathcal{K}$ is a lax 2-functor $\mathbf{1} \to \mathcal{K}$, where $\mathbf{1}$ is the 2-category with a single object and only the trivial morphism and 2-morphism.
But there is a general theorem to the effect that lax 2-functors are the same as strict 2-functors, after replacing the domain with a different 2-category (the so-called lax morphism classifier, though in my opinion it should be called a coclassifier rather than a classifier). In this case, we have a very explicit construction.
Let $\mathbf{M}$ be the following 2-category:
There is only one object, $*$.
The morphisms are $\textrm{id}, t, t^2, t^3, \ldots$.
The 2-morphisms $t^n \Rightarrow t^m$ are the monotone maps $\{ 0, \ldots, n - 1 \} \to \{ 0, \ldots, m - 1 \}$.
In other words, $\mathbf{M}$ is the delooping of the augmented simplex category considered as a strict monoidal category. (Beware of differing numbering conventions for the objects in the augmented simplex category.)
Definition 2. A monad in 2-category $\mathcal{K}$ is a strict 2-functor $\mathbf{M} \to \mathcal{K}$.
The two definitions are equivalent in the following sense:
Proposition. There is a lax 2-functor $\mathbf{1} \to \mathbf{M}$ such that, for every lax 2-functor $\mathbf{1} \to \mathcal{K}$, there is a unique strict 2-functor $\mathbf{M} \to \mathcal{K}$ such that the composite $\mathbf{1} \to \mathbf{M} \to \mathcal{K}$ is the given lax 2-functor.
So much for monads. What about morphisms of monads? If we follow definition 1, the obvious notion of morphism is that of a lax natural transformation (of lax 2-functors), but we could also consider icons (= identity-component oplax natural transformations). If we follow definition 2, the obvious notion of morphism is that of a strict natural transformation (of strict 2-functors). But we could also look at lax or oplax or pseudo natural transformations (of strict 2-functors). Every strict natural transformation is pseudo, and every pseudo natural transformation is both lax and oplax. In principle, we might also consider things similar to pseudo natural transformations except that the naturality squares only commute up to an unspecified 2-isomorphism and no coherence axioms are imposed, but they do not seem to be useful.
As I said, what notion of morphism is appropriate depends on the application. For Eilenberg–Moore objects, it seems the right notion is that of a lax natural transformation of strict 2-functors. I described the universal property of the Eilenberg–Moore object of a monad previously, but if we define monad following definition 2, there is a succinct description: it is the lax limit of the strict 2-functor $\mathbb{T} : \mathbf{M} \to \mathcal{K}$. That is, it is an object $A$ in $\mathcal{K}$ together with a universal lax cone $\Delta A \Rightarrow \mathbb{T}$. Universality means that for every object $B$ in $\mathcal{K}$ and every lax cone $\Delta B \Rightarrow \mathbb{T}$ there is a unique morphism $B \to A$ such that the composite $\Delta B \Rightarrow \Delta A \Rightarrow \mathbb{T}$ is the lax cone you started with. If you have another strict 2-functor $\mathbb{T}' : \mathbf{M} \to \mathcal{K}$ and a lax natural transformation $\mathbb{T}' \Rightarrow \mathbb{T}$, you get an induced morphism from the lax limit of $\mathbb{T}'$ to the lax limit of $\mathbb{T}$, i.e. a morphism between the Eilenberg–Moore objects of the respective monads. In fact:
Proposition. Let $[\mathbf{M}, \mathcal{K}]_\textrm{strict, lax}$ be the following 2-category:
Assuming $\mathcal{K}$ has Eilenberg–Moore objects for every monad, there is a strict 2-functor $[\mathbf{M}, \mathcal{K}]_\textrm{strict, lax} \to \mathcal{K}$ sending each monad (i.e. strict 2-functor $\mathbf{M} \to \mathcal{K}$) to its Eilenberg–Moore object (i.e. lax limit).
We can easily dualise this to get the corresponding construction for comonads: just replace $\mathcal{K}$ with $\mathcal{K}^\textrm{co}$. If we shuffle the modifiers to get $\mathcal{K}$ to appear without ${}^\textrm{co}$, we get:
Proposition. Let $[\mathbf{M}^\textrm{co}, \mathcal{K}]_\textrm{strict, oplax}$ be the following 2-category:
Assuming $\mathcal{K}$ has Eilenberg–Moore objects for every comonad, there is a strict 2-functor $[\mathbf{M}^\textrm{co}, \mathcal{K}]_\textrm{strict, oplax} \to \mathcal{K}$ sending each comonad (i.e. strict 2-functor $\mathbf{M}^\textrm{co} \to \mathcal{K}$) to its Eilenberg–Moore object (i.e. oplax limit).
If you want to focus on monads on a single category you could take the evident full sub-2-category of $[\mathbf{M}, \mathcal{K}]_\textrm{strict, lax}$, or you could cut down the 1-morphisms (as Borceux does) to identity-component lax natural transformations. (Note that an identity-component lax natural transformation $\mathbb{T}' \Rightarrow \mathbb{T}$ will have among its data 2-morphisms $t \Rightarrow t'$. The arrows point in opposite directions, but this is what falls out of the definitions. You can fix this by thinking about icons instead, but that obscures the duality.)
Best Answer
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).