Category Theory Illustrated - Monoids

"prev

next"

Monoids etc

Since we are done with categories, let’s look at some other structures that are also interesting — monoids.

What are monoids

Like categories, monoids/groups are abstract systems consisting of a set of elements and operations, however, the operations look different than the operations we have for categories. Here is the definition:

A monoid is defined by a collection/set of elements $A$ (called the monoid’s underlying set), together with an associative monoid operation — a rule for combining two elements that produces a third element one of the same kind — $A \circ A \to A$.<br>Also, there should be an identity element $I$, such that $I \circ A = A$ and $A \circ I = A$.

Let’s take our familiar colorful balls.

We can define a monoid based on this set by specifying an operation for “combining” two balls into one. An example of such an operation would be blending the colours of the balls as if we are mixing paint.

You can probably think of other ways to define a similar 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. the way in which elements are grouped when applying the operation does not make any 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, or add a term that is present at both sides of an equation and retain the equality of the existing terms.

The identity element

Actually, not any (associative) operation for combining elements makes for a monoid (it makes for 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 the operation, a 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, 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 and 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}$ (\(\{ 0, 1, 2, 3 ...\}\)) forms a monoid when combined with the all too familiar operation of addition (or under addition as it is traditionally said). This monoid is denoted $\left$ (in general, all monoids 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.

Task 1: Which are the identity elements of those monoids?

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

Task 3: The natural numbers form a monoid under multiplication, but not a group. Find out why.

Monoids and boolean algebra

Thinking about operations that we covered, we may remember the boolean operations and and or. The operation and forms a monoid on the set, consisting of just two values ${ True, False }$, in which $True$ is the identity element (the symbol $\land$ means and).

The operation or also forms a similar monoid.

Task 4: Prove that and $\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.<br>Task 5: Which are the identity elements of the or operations?

Monoid operations in terms of sets

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...