nLab
free monoid

Given a set $S$, the free monoid on $S$ is the set $S^{*}$ of all lists (finite sequences) of elements of $S$, made into a monoid using concatenation. The free functor from Set to Mon? takes $S$ to $S^{*}$.

Definitions

We will give three definitions, which can all be shown equivalent.

As functions

An element of $S^{*}$ consists of a natural number $n$ (possibly $n=0$) and function from $[n]$ to $S$, where $[n]$ is the subset $\{i:N\mid i<n\}$ of $N=\{0,1,2,\dots \}$. Such an element is called a list or (to specify $n$) $n$-tuple of elements of $S$. The number $n$ is called the length of the list.

The empty list is the unique list of length $0$. It may be written $()$, $*$, or $ϵ$, perhaps with a subscript $S$ if desired.

If $n>0$, then the list which assigns $0,\dots ,n-1$ to $a_0,a_1,\dots ,a_{n-1}$ may be written $(a_0,a_1,\dots ,a_{n-1})$. For example, if $a,b,c$ are elements of $S$, then $(a,b,c)$ is an element of $S^{*}$.

Given two lists $x$ and $y$, the former of length $m$ and the latter of length $n$, their concatenation $x*y$ is a list of length $m+n$, given as follows:

$$i\mapsto \{\begin{array}{cc}{x}_i& \mathrm{if}i<m\\ x_{i-m}& \mathrm{if}i\ge m\end{array}$$i \mapsto \left\{ \array { x_i & if\; i \lt m \\ x_{i-m} & if\; i \geq m } \right.

One can now show that concatenation is associative with the empty list as identity; hence $S^{*}$ is a monoid.

Recursively

The (underlying) set $S^{*}$ may be defined as an inductive type? as follows. There are two basic constructors, one with no arguments, and one with two arguments, of which one is an element of $S$ and the other is an element of $S^{*}$. By the yoga of inductive types, that is a complete definition, but we spell it out in more detail while also giving terminology and notation.

So, a list is either the empty list or the cons (short for ‘constructor’ and deriving from Lisp) of an element $a$ of $S$ and a (previously constructed) list $x$. The empty list may may be written $()$, $*$, or $\mathrm{nil}$, perhaps with a subscript $S$ if desired; the cons of $a$ and $x$ may be written $s:x$, $(a)*x$, or $\mathrm{cons}(a,x)$. We interpret the definition recursively?, so we can list the elements of $S^{*}$ in the order in which they appear:

* $()$,

• $a:()$,
• $a:b:()$,
• $a:b:c:()$,
• etc.

Here, $a,b,c,\dots$ are elements of $S$. We may continue the ‘etc’ as far as we like, but no farther; while there are lists of arbitrarily long finite length, there are no lists of infinite length. (We would get such lists, however, if we interpreted the definition corecursively.) We normally abbreviate the lists above as follows: * $()$,

• $(a)$,
• $(a,b)$,
• $(a,b,c)$,
• etc.

We still must define the monoidal structure on $S^{*}$; we define the concatenation $x*y$ of $x$ and $y$ recursively in $x$. To be explicit:

• $()*y=y$;
• $(a:x)*y=a:(x*y)$ (with parentheses for grouping, but the parentheses can be dropped now that have this definition).

One can now show that concatenation is associative with the empty list as identity; hence $S^{*}$ is a monoid.

By general abstract nonsense

In the course of proving that the category Mon? of monoids is a complete category, one normally shows that the forgetful functor $U$ (from $\mathrm{Mon}$ to the category Set of sets) preserves all limits. Thus, the adjoint functor theorem defines a left adjoint to $U$ if a size condition is met; this adjoint is the functor $*$ that takes a set to its free monoid $S^{*}$.

To be sure, meeting the solution set condition basically requires starting the constructions in one of the other definitions above; but the proofs may all be thrown onto the adjoint functor theorem.

Examples

• If $S$ is the empty set, then $S^{*}$ consists only of the empty list; it is the trivial monoid, one manifestation of the point.
• If $S$ is the point, then $S^{*}$ is $N$; the only information in a list of indistinguishable points is the length of the list. The monoid operation on $N$ is addition.
• If $S$ is $N$, then $N^{*}$ is still a denumerable set. But note that $N\cong N^{*}$ only as sets (that is, $\mid N^{*}\mid =\mid N\mid ={\aleph }_0$ as cardinal numbers); they are quite different as monoids.
• Generalising the above, $\mid S^{*}\mid =\mid S\mid$ is $S$ is an infinite set, or more generally $\mid S^{*}\mid =\max ({\aleph }_0,S)$ if $S$ is an inhabited set. (These theorems probably require the axiom of choice, but I haven't checked thoroughly.)

The free monoid monad

If the free moniod functor $F:\mathrm{Set}\to \mathrm{Mon}$ is followed by the forgetful functor $U:\mathrm{Mon}\to \mathrm{Set}$, then we get a monad on $\mathrm{Set}$. This monad is very important in computer science, where it is known as the list monad.

The list monad bears the same relation to multicategories as the identity monad on $\mathrm{Set}$ bears to ordinary categories. This relation should be explained at generalized multicategory.

Foundational relevance

Every definition of free monoid makes use of some form of axiom of infinity, either $N$ directly or the ability form general inductive types. Indeed, as $N={\mathrm{pt}}^{*}$, the axiom of infnity follows from the existence of free monoids.