nLab free commutative monoid




Monoid theory



The free commutative monoid [S]\mathbb{N}[S] on a set SS is the commutative monoid whose elements are formal \mathbb{N}-linear combinations of elements of SS.




U:CMonSet U \colon CMon \longrightarrow Set

be the forgetful functor from the category CMon of commutative monoids, to the category Set of sets. This has a left adjoint free construction:

[]:SetCMon. \mathbb{N}[-] \colon Set \longrightarrow CMon \,.

This is the free commutative monoid functor. For SS \in Set, the free commutative monoid [S]\mathbb{N}[S] \in CMon is the free object on SS with respect to this free-forgetful adjunction.

Of course, this notion is meant to be invariant under isomorphism: it doesn’t depend on the left adjoint chosen. Thus, if a functor of the form hom Set(S,U):CMonSet\hom_{Set}(S, U-): CMon \to Set is representable by a commutative monoid MM, then we may say MM is a free commutative monoid on SS. A specific choice of isomorphism

hom CMon(M,)hom Set(S,U)\hom_{CMon}(M, -) \cong \hom_{Set}(S, U-)

corresponds, via the Yoneda lemma, to a function SUMS \to U M which exhibits SS, or rather its image under this function, as a specific basis of MM. If MM is so equipped with such a universal arrow SUMS \to U M, then it is harmless to call MM “the” free commutative monoid on SS.

Explicit descriptions of free commutative monoid are discussed below.


In terms of formal linear combinations


A formal linear combination of elements of a set SS is a function

a:S a : S \to \mathbb{N}

such that only finitely many of the values a sa_s \in \mathbb{N} are non-zero.

Identifying an element sSs \in S with the function SS \to \mathbb{N} which sends ss to 11 \in \mathbb{N} and all other elements to 0, this is written as

a= sSa ss. a = \sum_{s \in S} a_s \cdot s \,.

In this expression one calls a sa_s \in \mathbb{N} the coefficient of ss in the formal linear combination.


Definition of formal linear combinations makes sense with coefficients in any commutative monoid MM, not necessarily the natural numbers.

M[S][S]M. M[S] \coloneqq \mathbb{N}[S] \otimes M \,.

For SS \in Set, the monoid of formal linear combinations [S]\mathbb{N}[S] is the monoid whose underlying set is that of formal linear combinations, def. , and whose monoid operation is the pointwise addition in \mathbb{N}:

( sSa ss)+( sSb ss)= sS(a s+b s)s. (\sum_{s \in S} a_s \cdot s) + (\sum_{s \in S} b_s \cdot s) = \sum_{s \in S} (a_s + b_s) \cdot s \,.

The free commutative monoid on SSetS \in Set is, up to isomorphism, the monoid of formal linear combinations, def. , on SS.


For SS a set, the free commutative monoid [S]\mathbb{N}[S] is the biproduct in CMon of |S|{|S|}-copies of \mathbb{N} with itself:

[S] sS. \mathbb{N}[S] \simeq \oplus_{s \in S} \mathbb{N} \,.


Last revised on May 21, 2021 at 22:29:48. See the history of this page for a list of all contributions to it.