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

Let $\mathcal{D}$ be a category. Ittay Weiss wrote about Free($\mathcal{D}$) in chat with me. He said Free($\mathcal{D}$) is the free category on the underlying graph of $\mathcal{D}$. Is Free($\mathcal{D}$) different from $\mathcal{D}$? I would like to know the exact definition of Free($\mathcal{D}$) and applications of the notion.

EDIT(Jan. 14, 2013) Is Free($\mathcal{D}$) isomorphic or equivalent to $\mathcal{D}$? Counterexamples?

share|cite|improve this question
There is a forgetful functor from the category of categories to the category of (directed multi)graphs. The free functor is the left adjoint. The explicit construction is more-or-less what you expect: it has morphisms for each generating edge, as well as all formal compositions of such. – Zhen Lin Jan 13 '13 at 18:50
Almost always. For example, the free category on the empty graph is the empty category; but as soon as there are two composable arrows then the free category is different. – Zhen Lin Jan 13 '13 at 19:23
@ZhenLin Actually, if I understand correctly, the question is: is $Free(U(\mathcal{D}))$ different from $\mathcal{D}$, where $\mathcal{D}$ is a category and U is the forgetful functor $U:Cat \to Graph$ – magma Jan 13 '13 at 20:37
Suppose given a pair of morphisms $f, g$ with composite $h=g\circ f$. Then in the free category has morphisms $f,g,h$ as well, but now $h\ne g\circ f$. – Zhen Lin Jan 13 '13 at 20:59
@Zhen: Wrong side of the adjunction: with the symbols defined in the OP, we get the counit map $\text{Free}(\mathcal{D}) \to \mathcal{D}$ given by multiplying a formal product. – Hurkyl Jan 15 '13 at 1:24

For a graph $G$ with object set $O$ let $C=FG$ be the category with the same objects and whose arrows from $a$ to $b$ are strings $$a=a_1\stackrel{f_1}⟶a_2\stackrel{f_2}⟶...\stackrel{f_{n-1}}⟶a_n=b$$ of length $n-1$. We define the composition of two strings by juxtaposition, where the lengths are added. This is by its very nature associative. A string of length $0$ is thus the identity. Let's write such strings as $(a_1,f_1,f_2,...,f_{n-1},a_n)$. It can be decomposed as $(a_{n-1},f_{n-1},a_n)∘...∘(a_1,f_1,a_2)$. Let $η:G→UC$ be the graph map sending $f:a→b$ to $(a,f,b)$.
Now, consider any graph map $g:G→UB$ for a category $B$. Using the decomposition of a string of length $n$ into strings of length $1$, it is easy to see that there is a unique functor $g':C→B$ such that $Ug'∘η=g$. Hence $η$ is universal from $G$ to $U$. The object function $F$ can then be made into a free functor $\mathbf{Grph}\to\mathbf{Cat}$.

share|cite|improve this answer

I didn't notice until now that this isn't a new question, but since Makoto asked for a fleshed-out example, I may as well post this.

The category on one object with only the identity morphism has as underlying graph a single vertex with a loop. The free category on the single vertex with a loop is the category on one object with countably many non-identity arrows $a,a\circ a,...$ i.e. as a monoid it is $\mathbb{N}$. The counit functor, of course, just sends all these arrows to the identity. The possibly-subtle point is that these non-identity arrows $a$ are generated by an arrow that was the identity before we applied the forgetful functor. But this is necessary because not every node in every graph has a distinguished loop to map to the identity in generating a free category.

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.