1
$\begingroup$

I am trying to prove that the forgetful functor $U\colon \textbf{DGph}\longrightarrow \textbf{Set}$ is monadic. The strategy for that is to show that $\textbf{DGph}$ is equivalent to the category of $M$-sets, where $M=\{1,c,d\}$ with $$ d^2=cd=d, \quad c^2=dc=c.$$

The category of $M$-sets is also equivalent to the functor category $[M,Set]$, where $M$ is considered as a category with a single object.

The definition of directed graph that I have is the following: it is a category without composition; that is, it has objects, morphisms, a domain and codomain and an endomorphism for each object.

However, I do not know how to prove that $\textbf{DGph}$ is equivalent to $[M,\textbf{Set}]$. For each directed graph, I should define a functor $F\colon M \longrightarrow \textbf{Set}$, but I have no idea of how to do it.

I have found here, https://ncatlab.org/nlab/show/reflexive+graph, that $\textbf{DGph}$ is the category of functors $R\longrightarrow \textbf{Set}$ where $R$ consists of two objects $0$ and $1$, and generated by arrows $i \colon 0 \longrightarrow 1$ and $s,t \colon 1 \longrightarrow 0$ with $si=\text{id}=ti$. Nevertheless, this does not help me since I do not understand the relation of this definition with the definition of directed graph that I have.

Can anyone help me, please? Thanks in advance.

$\endgroup$
1
  • $\begingroup$ There are lots of different notions of 'directed graph'; which one are you working with here? Are loops allowed, for example? $\endgroup$ Mar 22, 2018 at 18:14

1 Answer 1

2
$\begingroup$

The idea here is that $d$ means "domain" and $c$ means "codomain". Given a directed graph, let $X$ be the disjoint union of the set of objects and the set of morphisms. You can then define a map $d:X\to X$ which maps each morphism to its domain (and, since we have to also define it on objects, we'll just say it sends each object to itself). Similarly, we have a map $c:X\to X$ which maps each morphism to its codomain (and again sends each object to itself). Now you can verify that these maps $c$ and $d$ satisfy the identities $d^2=cd=d$ and $c^2=dc=c$.

So this gives a way to turn a directed graph into an $M$-set. I'll leave it to you to work out that this is actually an equivalence of categories (in other words, you can reverse this construction to start with an $M$-set and get a directed graph, and that the constructions in both directions are functorial and inverse up to natural isomorphism).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .