Why free monoid?

Posted Sunday November 5 2023.

why free monoid? Just because I think they are cool.. For example, a discrete-time dynamical system: you have a set \(X\) of states and function \(f:X \to X\) which updates the state. Any initial state \(x_0 \in X\) has a trajectory \(\{x_0,x_1,x_2,\cdots\}\) given by \(x_t = f^t(x_0)=f(f(\cdots(f(x_0))\cdots))\) (\(f\) is applied \(t\) times). It obeys \(f^{s+t}(x_0) = f^s(f^t(x_0))\) which is derived from the fact that the set of natural numbers \(\mathbb{N}=\{0,1,2,\cdots\}\) along with the operation of addition forms a monoid, sometimes denoted as \((\mathbb{N},+)\) to emphasize the monoid consists of both a set and the operation. This monoid is special because it is the free monoid on 1 generator.

Given a set \(S=\{x,y,z\}\) of “symbols”, you can form the free monoid on \(S\) (aka the free monoid generated by \(S\)) which consists of all the finite sequences of elements of \(S\). These are sometimes called “words” of elements in \(S\), and the set of all words is often denoted by \(S^\*\), where * is the Kleene star. For example, some finite sequences of the aforementioned \(S\) could be written as \([x,x]\), \([x,y]\), \([y,x]\), \([x,x,x]\), \([x,x,x,x]\), the empty list \([]\), etc. The monoid operation on these lists is to concatenate them, e.g. \([x,y] + [y,z] = [x,y,y,z]\). The empty list is an identity element for this operation because concatenating it to any list has no effect.

Returning to the case of 1 generator, suppose \(S\) contains just one symbol, \(S = \{ x \}\). Then the free monoid on \(S\) consists of \(S^\*=\{[], [x], [x,x], [x,x,x], [x,x,x,x],\cdots\}\). Notice that

The two properties described above characterize the monoid of natural numbers. What we have just shown is that the free monoid on 1 generator is isomorphic to the monoid of natural numbers. In fact, if we label the list containing \(n\) \(x's\) by \([x]^n\), then the map \(n \mapsto [x]^n\) is the isomorphism!

In the language of category theory, there is a functor \(F:Set \to Mon\) from the category of sets to the category of monoids called the free monoid functor. As we just showed, \(F(1) \cong (\mathbb{N},+)\). Being a functor, if \(A\) and \(B\) are two sets with the same cardinality (same size) then \(F(A)\) is isomorphic to \(F(B)\). Also, for any sets \(X\) and \(S\), the actions of \(F(S)\) on \(X\) are in one-to-one correspondence with maps \(S \to (X \to X)\). This is why earlier we could specify an action of \(\mathbb{N}\) on \(X\) by choosing some point \(1 \to (X \to X)\), i.e. some function \(f: X \to X\).

In computer science these are called transition systems and are apparently typically defines in terms of a graph where each vertex represents a state of the system, and each vertex has a labelled set of outgoing edges going to other states. With non-determinism, you already have plenty of interesting problems, such as speedrunning: suppose my initial state is \(x_0 \in X\) and I have a target state \(x^* \in X\) - what sequence of actions will get me there quickest?