Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am a complete novice in the art of categorification, so this may not be a great question.


  • The groupoid $\mathbf {FSet}$ of finite sets and bijections categorifies the natural numbers and the functor category $\mathbf {FSet}^{\mathbf {FSet}}$ (called the category of combinatorial species) categorifies generating functions.
  • If $X$ is a finite set, the slice category $\mathbf {FSet}/X$ of finite sets over $X$ (or $X$-indexed families of finite sets) categorifies the free commutative monoid on $X$, the forgetful functor $\mathbf {FSet}/X\longrightarrow \mathbf {FSet}$ categorifies word length (or degree of a monomial) and I believe the functor category $(\mathbf {FSet}/X)^{\mathbf {FSet}/X}$ categorifies generating functions in commuting variables $X$.
  • Question. Is there a categorification $\mathbf C$ of the free monoid on a finite set $X$ together with a ''forgetful" functor $\mathbf C\longrightarrow \mathbf {FSet}/X$ categorifying the abelianization map such that $\mathbf C^{\mathbf C}$ categorifies generating functions in non-commuting variables $X$.

    I assume the answer will be some sort of "free" monoidal category. Please take into account that I am a category-friendly mathematician, but not a category theorist, when formulating your answer.

    Vague motivation. Is there a categorification of the Chomsky-Schützenberger theorem on context-free grammars and algebraic power series?

    I realize that species categorify exponential generating fuctions and Chomsky-Schützenberger is about ordinary generating functions, but this shouldn't matter.

    Update.. The free monoidal category is no good because it only has identity morphisms. It doesn't even work to recover the 1-generated case.

    share|improve this question
    Can anybody figure out why my link to the Chomsky-Schützenberger theorem is not showing? Thanks! –  Benjamin Steinberg Dec 7 '11 at 13:43
    The answer is literally the free monoidal category on $X$. Its objects are words on the elements of $X$ and its morphisms are freely generated by the identity morphisms under tensor product (so there are not very many of them unless you give $X$ itself additional structure). You aren't using the right definition of combinatorial species: the domain category is the category of finite sets and bijections, not the ordinary category of finite sets. –  Qiaochu Yuan Dec 7 '11 at 15:16
    Sorry Quaochu, I forgot to say that but meant it. Does the free monoidal category work for generating functions? What is the forgetful functor to FSet/X. –  Benjamin Steinberg Dec 7 '11 at 15:41
    @Benjamin: the forgetful functor to $\text{FSet}/X$ sends a word to the set of its letter positions together with their names (the function to $X$). I think the only morphisms in the free monoidal category on a set are identity morphisms, though, so this isn't a particularly interesting observation. –  Qiaochu Yuan Dec 7 '11 at 16:07
    Yes, the free monoidal category on a set $X$ is equivalent to the discrete category given by the free monoid on $X$, as Qiaochu says, so nothing too exciting here, unfortunately. –  Todd Trimble Dec 7 '11 at 16:26

    Your Answer


    By posting your answer, you agree to the privacy policy and terms of service.

    Browse other questions tagged or ask your own question.