# Monoids etc

Since we are done with categories, let’s look at some other structures that are also interesting — monoids. Like categories, monoids/groups are also abstract systems consisting of set of elements and operations for manipulating these elements, however the operations look different than the operations we have for categories. Let’s see them.

# What are monoids

Monoids are simpler than categories. A monoid is defined by a collection/set of elements (called the monoid’s underlying set, together with an monoid operation — a rule for combining two elements that produces a third element one of the same kind.

Let’s take our familiar colorful balls. We can define a monoid based on this set by defining an operation for “combining” two balls into one. An example of such operation would be blending the colors of the balls, as if we are mixing paint. You can probably think of other ways to define such an operation. This will help you realize that there can be many ways to create a monoid from a given set of set elements i.e. the monoid is not the set itself, it is the set together with the operation.

## Associativity

The monoid operation should, like functional composition, be associative i.e. applying it on the same number of elements in a different order should make no difference. When an operation is associative, this means we can use all kinds of algebraic operations to any sequence of terms (or in other words to apply equation reasoning), like for example we can replace any element with a set of elements from which it is composed of, or add a term that is present at both sides of an equation and retaining the equality of the existing terms. ## The identity element

Actually, not any (associative) operation for combining elements makes the balls form a monoid (it makes them form a semigroup, which is also a thing, but that’s a separate topic). To be a monoid, a set must feature what is called an identity element of a given operation, the concept of which you are already familiar from both sets and categories — it is an element that when combined with any other element gives back that same element (not the identity but the other one). Or simply $x • i = x$ and $i • x = x$ for any $x$.

In the case of our color-mixing monoid the identity element is the white ball (or perhaps a transparent one, if we have one). As you probably remember from the last chapter, functional composition is also associative and it also contains an identity element, so you might start suspecting that it forms a monoid in some way. This is indeed the case, but with one caveat, for which we will talk about later.

# Basic monoids

To keep the suspense, before we discuss the relationship between monoids and categories, we are going through see some simple examples of monoids.

## Monoids from numbers

Mathematics is not only about numbers, however numbers do tend to pop up in most of its areas, and monoids are no exception. The set of natural numbers $\mathbb{N}$ forms a monoid when combined with the all too familiar operation of addition (or under addition as it is traditionally said). This group is denoted $\left< \mathbb{N},+ \right>$ (in general, all groups are denoted by specifying the set and the operation, enclosed in angle brackets). If you see a $1 + 1 = 2$ in your textbook you know you are either reading something very advanced, or very simple, although I am not really sure which of the two applies in the present case.

Anyways, the natural numbers also form a monoid under multiplication as well. Question: Which are the identity elements of those monoids?

Task: Go through other mathematical operations and verify that they are monoidal.

## Monoids from boolean algebra

Thinking about operations that we covered, we may remember the boolean operations and and or. Both of them form monoids, which operate on the set, consisting of just two values ${ True, False }$.

Task: Prove that $\land$ is associative by expanding the formula $(A \land B) \land C = A \land (B \land C)$ with all possible values. Do the same for or.

Question: Which are the identity elements of the and and or operations?

# Monoid operations in terms of set theory

We now know what the monoid operation is, and we even saw some simple examples. However, we never defined the monoid rule/operation formally i.e. using the language of set theory with which we defined everything else. Can we do that? Of course we can — everything can be defined in terms of sets.

We said that a monoid consists of two things a set (let’s call it $A$) and a monoid operation that acts on that set. Since $A$ is already defined in set theory (because it is just a set), all we have to do is define the monoid operation.

Defining the operation is not hard at all. Actually, we have already done it for the operation $+$ — in chapter 2, we said that addition can be represented in set theory as a function that accepts a product of two numbers and returns a number (formally $+: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$). Every other monoid operation can also be represented in the same way — as a function that takes a pair of elements from the monoid’s set and returns one other monoid element. Formally, we can define a monoid from any set $A$, by defining an (associative) function with type signature $A \times A \to A$. That’s it. Or to be precise, that is one way to define the monoid operation. And there is another way, which we will see next. Before that, let’s examine some more categories.

# Other monoid-like objects

Monoid operations obey two laws — they are associative and there is an identity element. In some cases we come across operations that also obey other laws that are also interesting. Imposing more (or less) rules to the way in which (elements) objects are combined results in the definition of other monoid-like structures.

## Commutative (abelian) monoids

Looking at the monoid laws and the examples we gave so far, we observe that all of them obey one more rule (law) which we didn’t specify — the order in which the operations are applied is irrelevant to the end result. Such operations (ones for which combining a given set of elements yields the same result no matter which one is first and which one is second) are called commutative operations. Monoids with operations that are commutative are called commutative monoids.

As we said, addition is commutative as well — it does not matter whether if I have given you 1 apple and then 2 more, or if I have given you 2 first and then 1 more. All monoids that we examined so far are also commutative. We will see some non-commutative ones later.

## Groups

A group is a monoid such that for each of its elements, there is another element which is the so called “inverse” of the first one where the element and its inverse cancel each other out when applied one after the other. Plain-English definitions like this make you appreciate mathematical formulas more — formally we say that for all elements $x$, there must exist $x’$ such that $x • x’ = i$ ( where $i$ is the identity element).

If we view monoids as a means of modeling the effect of applying a set of (associative) actions, we use groups to model the effects of actions are also reversible.

A nice example of a monoid that we covered that is also a group is the set of integers under addition. The inverse of each number is its opposite number (positive numbers’ inverse are negatives and vice versa). The above formula, then, becomes $x + (-x) = 0$

The study of groups is a field that is much bigger than the theory of monoids (and perhaps bigger than category theory itself). And one of its the biggest branches is the study of the “symmetry groups” which we will look into next.

## Summary

But before that, just a quick note — the algebraic structures that we saw can be summarized based on the laws that define them in this table.

Semigroups Monoids Groups
Associativity X X X
Identity   X X
Invertability     X

And now for the symmetry groups.

# Symmetry groups and group classifications

An interesting kinds of groups/monoids are the groups of symmetries of geometric figures. Given some geometric figure, a symmetry is an action after which the figure is not displaced (e.g. it can fit into the same mold that it fit before the action was applied).

We won’t use the balls this time, because in terms of symmetries they have just one position and hence just one action — the identity action (which is its own reverse, by the way). So let’s take this triangle, which, for our purposes, is the same as any other triangle (we are not interested in the triangle itself, but in its rotations). ## Groups of rotations

Let’s first review the group of ways in which we can rotate our triangle i.e. its rotation group. A geometric figure can be rotated without displacement in positions equal to the number of its sides, so for our triangle there are 3 positions. Connecting the dots (or the triangles in this case) shows us that there are just two possible rotations that get us from any state of the triangle to any other one — a 120-degree rotation (i.e. flipping the triangle one time) and a 240-degree rotation (i.e. flipping it two times (or equivalently, flipping it once, but in the opposite direction)). Adding the identity action of 0-degree rotation makes up for 3 rotations (objects) in total. The rotations of a triangle form a monoid — the rotations are objects (of which the zero-degree rotation is the identity) and the monoid operation which combines two rotations into one is just the operation of performing the first rotation and then performing the second one.

NB: Note once again that the elements in the group are the rotations, not the triangles themselves, actually the group has nothing to do with triangles, as we shall see later.

## Cyclic groups/monoids

The diagram that enumerates all the rotations of a more complex geometrical figure looks quite messy at first. But it gets much simpler to grasp if we notice the following: although our group has many rotations, and there are more still for figures with more sides (if I am not mistaken, the number of rotations is equal to the number of the sides), all those rotations can be reduced to the repetitive application of just one rotation, (for example, the 120-degree rotation for triangles and the 45-degree rotation for octagons). Let’s make up a symbol for this rotation. Symmetry groups that have such “main” rotation, and, in general, groups and monoids that have an object that is capable of generating all other objects by its repeated application, are called cyclic groups. And such rotation are called the group’s generator.

All rotation groups are cyclic groups. Another example of a cyclic groups is, yes, the natural numbers under addition. Here we can use $+1$ or $-1$ as generators. Wait, how can this be a cyclic group when there are no cycles? This is because the integers are an infinite cyclic group.

A number-based example of a finite cyclic group is the group of natural numbers under modular arithmetic (sometimes called “clock arithmetic”). Modular arithmetic’s operation is based on a number called the modulus (let’s take $12$ for example). In it, each number is mapped to the remainder of the integer addition of that number and the modulus.

For example: $1 \pmod{12} = 1$ (because $1/12 = 0$ with $1$ remainder) $2 \pmod{12} = 2$ etc.

But $13 \pmod{12} = 1$ (as $13/12 = 1$ with $1$ remainder) $14 \pmod{12} = 2$, $15 \pmod{12} = 3$ etc.

In effect numbers “wrap around”, forming a group with as many elements as it the modulus number. Like for example a group representation of modular arithmetic with modulus $3$ has 3 elements. All cyclic groups that have the same number of elements (or that are of the same order) are isomorphic to each other (careful readers might notice that we haven’t yet defined what a group isomorphisms are, even more careful readers might already have an idea about what it is).

For example, the group of rotations of the triangle is isomorphic to the natural numbers under the addition with modulo $3$. All cyclic groups are commutative (or “abelian” as they are also called).

Task: Show that there are no other groups with 3 objects, other than $Z_3$.

There are abelian groups that are not cyclic, but, as we shall see below, the concepts of cyclic groups and of abelian groups are deeply related.

## Group isomorphisms

We already mentioned group isomorphisms, but we didn’t define what they are. Let’s do that now — an isomorphism between two groups is an isomorphism ($f$) between their respective sets of elements, such that for any $a$ and $b$ we have $f(a \circ b) = f(a) \circ f(b)$. Visually, the diagrams of isomorphic groups have the same structure. As in category theory, in group theory isomorphic groups they considered instances of one and the same group. For example the one above is called $Z_3$.

## Finite groups

Like with sets, the concept of an isomorphism in group theory allows us to identify common finite groups.

The smallest group is just the trivial group $Z_1$ that has just one element. The smallest non-trivial group is the group $Z_2$ that has two elements. $Z_2$ is also known as the boolean group, due to the fact that it is isomorphic to the ${ True, False }$ set under the operation that negates a given value.

Like $Z_3$, $Z_1$ and $Z_2$ are cyclic.

# Group/monoid products

We already saw a lot of abelian groups that are also cyclic, but we didn’t see any abelian groups that are not cyclic. So let’s examine what those look like. This time, instead of looking into individual examples, we will present a general way for producing abelian non-cyclic groups from cyclic ones — it is by uniting them by using group product.

Given any two groups, we can combine them to create a third group, comprised of all possible pairs of elements from the two groups and of the sum of all their actions.

Let’s see how the product looks like take the following two groups (which, having just two elements and one operation, are both isomorphic to $Z2$). To make it easier to imagine them, we can think of the first one as based on the vertical reflection of a figure and the second, just the horizontal reflection. We get set of elements of the new group by taking the Cartesian product of the set of the elements of the first group and the set of the element of the second one. And the actions of a product group are comprised of the actions of the first group, combined with the actions of the second one, where each action is applied only on the element that is a member of its corresponding group, leaving the other element unchanged. The product of the two groups we presented is called the Klein four-group and it is the simplest non-cyclic abelian group.

Another way to present the Klein-four group is the group of symmetries of a non-square rectangle. Task: Show that the two representations are isomorphic.

The Klein-four group is non-cyclic (because there are not one, but two generators) — vertical and horizontal spin. It is, however, still abelian, because the ordering of the actions still does not matter for the end results. Actually, the Klein-four group is the smallest non-cyclic group.

## Cyclic product groups

Product groups are non-cyclic, provided that the number of elements of the groups that comprise them (or their orders) aren’t relatively prime (have some GCD other than 1).

If two groups have orders that aren’t relatively prime, (like for example $2$ and $2$, (which are both divided by 2) as the groups that comprise Klein-four), then even if the two groups are cyclic and have just 1 generator each, their product would have 2 generators.

And if you combine two groups with orders that are relatively prime, (like $2$ and $3$) the resulting group would be isomorphic to a cyclic group of the same order, as the product of $Z_3$ and $Z_2$ is isomorphic to the group $Z_6$ ($Z_3 \times Z_2 \cong Z_6$) This is a consequence of an ancient result, known as the Chinese Remainder theorem.

## Abelian product groups

Product groups are abelian, provided that the groups that form them are abelian. We can see that this is true by noticing that, although the generators are more than one, each of them acts only on its own part of the group, so they don’t interfere with each other in any way.

## Fundamental theorem of Finite Abelian groups

Products provide one way to create non-cyclic abelian groups — by creating a product of two or more cyclic groups. The fundamental theory of finite abelian groups is a result that tells us that this is the only way to produce non-cyclic abelian groups i.e.

All abelian groups are either cyclic or products of cyclic groups.

We can use this law to gain intuitive understanding of the what abelian groups are, but also to test whether a given group can be broken down to a product of more elementary groups.

## Color-mixing monoid as a product

To see how can we use this theorem, let’s revisit our color mixing monoid that we saw earlier. As there doesn’t exist a color that, when mixed with itself, can produce all other colors, the color-mixing monoid is not cyclic. However, the color mixing monoid is abelian. So according to the theorem of finite abelian groups (which is valid for monoids as well), the color-mixing monoid must be (isomorphic to) a product.

And it is not hard to find the monoids that form it — although there isn’t one color that can produce all other colors, there are three colors that can do that — the prime colors. This observation leads us to the conclusion that the color-mixing monoid, can be represented as the product of three monoids, corresponding to the three primary colors. You can think of each color monoid as a boolean monoid, having just two states (colored and not-colored). Or alternatively, you can view it as having multiple states, representing the different levels of shading. In both cases the monoid would be cyclic.

# Dihedral groups

Now, let’s finally examine a non-commutative group — the group of rotations and reflections of a given geometrical figure. It is the same as the last one, but here besides the rotation action that we already saw (and its composite actions), we have the action of flipping the figure vertically, an operation which results in its mirror image: Those two operations and their composite results in a group called $Dih3$ that is not abelian (and is furthermore the smallest non-abelian group). Task: Prove that this group is indeed not abelian.

Question: Besides having two main actions, what is the defining factor that makes this and any other group non-abelian?

Groups that represent the set of rotations and reflections of any 2D shape are called dihedral groups

# Groups/monoids categorically

We began by defining a monoid as a set of composable elements. Then we saw that for some groups, like the groups of symmetries and rotations, those elements can be viewed as actions. And this is actually true for all other groups as well, e.g. the red ball in our color-blending monoid can be seen as the action of *adding the color red$to the mix, the number$2$in the monoid of addition can be seen as the operation$+2$etc. This observation leads to a categorical view of the theory of groups and monoids. ## Currying When we defined monoids, we saw that their operations are two-argument functions. And we introduced a way for representing such functions using set theory — by uniting the two arguments into one using products. i.e. we showed that a function that accepts two arguments (say$A$and$B$) and maps them into some result ($C$), can be thought as a mapping from the product of the sets of two arguments to the result. So$A\times B\to C$. However, this is not the only way to represent multi-argument function set-theoretically — there is another, equally interesting way, that doesn’t rely on any data structures, but only on functions: that way is to have a function that maps the first of the two arguments (i.e. from$A$) to another function that maps the second argument to the final result (i.e.$B \to C$). So$A\to B \to C$. The practice of transforming a function that takes a pair of objects to a function that takes just one object and returns a function that takes another one is called currying. It is achieved by a higher-order function. Here is how such a function might be implemented. const curry = <A, B, C> (f:(a:A, b:B) => C) => (a:A) => (b:B) => f(a, b)  And equally important is the opposite function, which maps a curried function to a multi-argument one, which is known as uncurry. const uncurry = <A, B, C> (f:(a:A) => (b:B) => C) => (a:A, b:B ) => f(a)(b)  There is a lot to say about these two functions, starting from the fact that its existence gives rise to an interesting relationship between the concept of a product and the concept of a morphism in category theory, called the adjunction. But we will cover this later. For now we are interested in the fact the two function representations are isomorphic, formally$A\times B\to C\cong A\to B \to C$. By the way, this isomorphism can be represented in terms of programming as well. It is equivalent to the statement that the following function always returns true for any arguments, (...args) => uncurry(curry(f(...args)) === f(...args)  This is one part of the isomorphism, the other part is the equivalent function for curried functions. Task: Write the other part of the isomorphism. ## Monoid elements as functions/permutations Let’s take a step back and examine the groups/monoids that we covered so far in the light of what we learned. We started off by representing group operation as a function from pairs. For example, the operation of a symmetric group,(let’s take$Z_3$as an example) are actions that converts two rotations to another rotation. Using currying, we can represent the elements of a given group/monoid as functions by uniting them to the group operation, and the group operation itself — as functional composition. For example, the 3 elements of$Z_3$can be seen as 3 bijective (invertable) functions from a set of 3 elements to itself (in group-theoretic context, these kinds of functions are called permutations, by the way). We can do the same for the addition monoid — numbers can be seen not as quantities (as in two apples, two oranges etc.), but as operations, (e.g. as the action of adding two to a given quantity). Formally, the operation of the addition monoid, that we saw above has the following type signature.$+: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$Because of the isomorphism we presented above, this function is equivalent to the following function.$+: \mathbb{Z} \to (\mathbb{Z} \to \mathbb{Z})$When we apply an element of the monoid to that function (say$2$), the result is the function$+2$that adds 2 to a given number.$+2: \mathbb{Z} \to \mathbb{Z}$And because the monoid operation is always a given in the context of a given monoid, we can view the element$2$and the function$+2$as equivalent in the context of the monoid.$2 \cong +2$In other words, in addition to representing the monoid elements in the set as objects that are combined using a function, we can represent them as functions themselves. ## Monoid operations as functional composition The functions that represent the monoid elements have the same set as source and target, or same signature, as we say (formally, they are of the type$A \to A$for some$A$). Because of that, they all can be composed with one another, using functional composition, resulting in functions that also has the same signature. And the same is valid for the addition monoid — number functions can be combined using functional composition.$+2 \circ +3 \cong +5$So, basically the functions that represent the elements of a monoid also form a monoid, under the operation of functional composition (and the functions that represent the elements that form a group also form a group). Question: Which are the identity elements of function groups? Task: Show that the functions representing inverse group elements are also inverse. ## Cayley’s theorem Once we learn how to represent the elements of any monoid as permutations that also form a monoid, using currying, it isn’t too surprising to learn that this constructed permutation monoid is isomorphic to the original one (the one from which it is constructed — this is a result known as the Cayley’s theorem: Any group is isomorphic to a permutation group. Formally, if we use$Perm$to denote the permutation group then$Perm(A) \cong A$for any$A$. Or in other words, representing the elements of a group as permutations actually yields a representation of the monoid itself (sometimes called its standard representation). Cayley’s theorem may not seem very impressive, but that only shows how influential it has been as a result. ## Interlude: Symmetric groups The first thing that you have to know about the symmetric groups is that they are not the same thing as symmetry groups. Once we have that out of the way, we can understand what they actually are: given a natural number$n$, the symmetric group of$n$, denoted$\mathrm{S}_n$(symmetric group of degree$n$) is the group of all possible permutations of a set with$n$elements. The number of the elements of such groups is equal to are$1\times 2\times 3…\times n$or$n!$(n-factorial). So, for example the group$\mathrm{S}_1$of permutations of the one-element set has just 1 element (because a 1-element set has no other functions to itself other than the identity function. The group$\mathrm{S}_2$, has$1 \times 2 = 2$elements (by the way, the colors are there to give you some intuition as to why the number of permutations of a$n$-element set is$n!$). And with$\mathrm{S}_3$we are already feeling the power of exponential (and even faster than exponential!) growth of the factorial function — it has$1\times 2\times 3=6$elements. Each symmetric group$\mathrm{S}_n$contains all groups of order$n$— this is so, because (as we saw in the prev section) every group with$n$elements is isomorphic to a set of permutations on the set of$n$elements and the group$\mathrm{S}_n$contains all such permutations that exist. Here are some examples: •$\mathrm{S}_1$is isomorphic to$Z_1$, the trivial group, and$\mathrm{S}_2$is isomorphic to$Z_2$, the boolean group, (but no other symmetric grops are isomorphic to cycle groups) • The top three permutations of$\mathrm{S}_3$are isomorphic to the group$Z_3$. •$\mathrm{S}_3$is also isomorphic to$Dih3$(but no other symmetric group is isomorphic to a dihedral group) Based on this insight, can state Cayley’s theorem in terms of symmetric groups in the following way: All groups are isomorphic to subgroups of symmetric groups. Task: Show how the two are equivalent. Fun fact: the study of group theory actually started by examining symmetric groups, so this theorem was actually a prerequisite for the emergence of the normal definition of groups that we all know and love (OK, at least I love it) — it provided a proof that the notion described by this definition is equivalent to the already existing notion of symmetric groups. ## Monoids as categories We saw that converting the monoid’s elements to actions/functions yields an accurate representation of the monoid in terms of sets and functions. However, it seems that the set part of the structure in this representation is kinda redundant — you have the same set everywhere — so, it would do it good if we can simplify it. And we can do that by depicting it as an external (categorical) diagram. But wait, if the monoids’ underlying sets correspond to objects in category theory, then the corresponding category would have just one object. And so the correct representation would involve just one point from which all arrows come and to which they go. The only difference between different monoids would be the number of morphisms that they have and the relationship between them. The intuition behind this representation from a category-theoretic standpoint is encompassed by the law of closure that monoid and group operations have and that categories lack — it is the law stating that applying the operation (functional composition) on any two objects always yields the same object, e.g. no matter how do you flip a triangle, you’d still get a triangle. Categories Monoids Groups Associativity X X X Identity X X X Invertibility X Closure X X When we view a monoid as a category, this law says that all morphisms in the category should be from one object to itself - a monoid, any monoid, can be seen as a category with one object. Let’s elaborate on this thought by reviewing the definition of a category from chapter 2. A category is a collection of objects (we can think of them as points) and morphisms (arrows) that go from one object to another, where: 1. Each object has to have the identity morphism. 2. There should be a way to compose two morphisms with an appropriate type signature into a third one in a way that is associative. Aside from the little-confusing fact that monoid objects are morphisms when viewed categorically, this describes exactly what monoids are. Categories have an identity morphism for each object, so for categories with just one object, there should also be exactly one identity morphism. And monoids do have an identity object, which when viewed categorically corresponds to that identity morphism. Categories provide a way to compose two morphisms with an appropriate type signature, and for categories with one object this means that all morphisms should be composable with one another. And the monoid operation does exactly that — given any two objects (or two morphisms, if we use the categorical terminology), it creates a third. Philosophically, defining a monoid as a one-object category means corresponds to the view of monoids as a model of how a set of (associative) actions that are performed on a given object alter its state. Provided that the object’s state is determined solely by the actions that are performed on it, we can leave it out of the equation and concentrate on how the actions are combined. And as per usual, the actions (and elements) can be anything, from mixing colors in paint, or adding a quantities to a given set of things etc. ## Group/monoid presentations When we view cyclic groups/monoids as categories, we would see that they correspond to categories that (besides having just one object) also have just one morphism (which, as we said, is called a generator) along with the morphisms that are created when this morphism is composed with itself. In fact the infinite cyclic monoid (which is isomorphic to the natural numbers), can be completely described by this simple definition. This is so, because applying the generator again and again yields all elements of the infinite cyclic group. Specifically, if we view the generator as the action$+1$then we get the natural numbers. Finite cyclic groups/monoids are the same, except that their definition contains an additional law, stating that that once you compose the generator with itself$n$number of times, you get identity morphism. For the cyclic group$Z_3$(which can be visualized as the group of triangle rotations) this law states that composing the generator with itself$3$times yields the identity morphism. Composing the group generator with itself, and then applying the law, yields the three morphisms of$Z_3\$. We can represent product groups this way too. Let’s take Klein four-group as an example, The Klein four-group has two generators that it inherits from the groups that form it (which we viewed like vertical and horizontal rotation of a non-square rectangle) each of which comes with one law. To make the representation complete, we add the law for combining the two generators. And then, if we start applying the two generators and follow the laws, we get the four elements. The set of generators and laws that defines a given group is called the presentation of a group. Every group has a presentation.

## Interlude: Free monoids

We saw how picking a different selection of laws gives rise to different types of monoid. But what monoids would we get if we pick no laws at all? These monoids (we get a different one depending on the set we picked) are called a free monoids (the word “free” is used in the sense that once you have the set, you can upgrade it to a monoid for free (i.e. without having to define anything else).

If you revisit the previous section you will notice that we already saw one such monoid. The free monoid with just one generator is isomorphic to the monoid of integers. We can make a free monoid from the set of colorful balls — the monoid’s elements would be sequences of all possible combinations of the balls. The free monoid is a special one — each element of the free monoid over a given set, can be converted to a corresponding element in any any other monoid that uses the same set of generators by just applying the monoid’s laws. For example, here is how the elements above would look like if we apply the laws of the color-mixing monoid. Task: Write up the laws of the color-mixing monoid.

If we put out programmers’ hat, we will see that the type of the free monoid under the set of generators T (which we can denote as FreeMonoid<T>) is isomorphic to the type List<T> (or Array<T>, if you prefer) and that the intuition behind the special property that we described above is actually very simple: keeping objects in a list allows you to convert them to any other structure i.e. when we want to perform some manipulation on a bunch of objects, but we don’t know exactly what this manipulation is, we just keep a list of those objects until it’s time to do it.

While the intuition behind free monoids seems simple enough, the formal definition is not our cup of tea… yet, simply because we have to cover more stuff.

We understand that, being the most general of all monoids for a given set of generators, a free monoid can be converted to all of them. i.e. there exist a function from it to all of them. But what kind of function would that be? Tune in after a few chapters to find out.