reperiendi

Monoids

Posted in Category theory, Math by Mike Stay on 2007 September 12

A set has no structure. It’s just a collection of things, all of them equally unimportant.

\{ \blacksquare, \blacktriangle, \bigstar \}

Figure 1. A set.

 

1 = \{ \bullet \}

Figure 2. Another set, the one-element set we’ll call “1.”

A function, or map, “goes between” sets. It has a source set (also called the domain) and a target set (also called the range). To each element of the source set, it assigns an element of the target set. We’ll use the usual shorthand for denoting functions, with the name of the function, a colon, the source set, an arrow, and the target set. Underneath, we’ll write a typical element of the source, an arrow with a small bar at the start, and the element of the target it goes to. For example, consider the function d mapping each integer to its double. The integers are denoted by the symbol \mathbb{Z} (German Zahlen, “numbers”), so we have

\begin{array}{rl} d:\mathbb{Z} & \to \mathbb{Z} \\ x & \mapsto 2x\end{array}

Perhaps the simplest structure we can add to a set is to pick an element of it and make that element important. A pointed set S is

  • a set S equipped with
  • a function e:1\to S, where 1 is the one-element set \{\bullet\}.

The special element of S is given by e(\bullet). The name e should bring to mind the word “element,” since there’s a different choice for what this map should be for each element of S. For example, given the set S=\{ \blacksquare, \blacktriangle, \bigstar \}, there are three possible choices for the function e, corresponding to the three different elements we could pick:

  1. e(\bullet)=\blacksquare
  2. e(\bullet)=\blacktriangle
  3. e(\bullet)=\bigstar

A monoid is a pointed set with a little more structure. Way back in kindergarten, they taught us how to count. We counted fingers and marbles and cookies. We used base 1, unary, tally marks:

\blacksquare\blacksquare+\blacksquare\blacksquare\blacksquare=\blacksquare\blacksquare\blacksquare\blacksquare\blacksquare.

Sometimes they had us add things that weren’t the same:

\blacksquare \blacktriangle \bigstar + \clubsuit \blacksquare = \blacksquare \blacktriangle \bigstar \clubsuit \blacksquare.

Note that when we add this way, the order matters:

\blacksquare \blacktriangle \blacksquare \blacktriangle \blacksquare = \blacksquare \blacktriangle \blacksquare + \blacktriangle \blacksquare \ne \blacktriangle \blacksquare + \blacksquare \blacktriangle \blacksquare = \blacktriangle \blacksquare \blacksquare \blacktriangle \blacksquare.

While the number of symbols is the same, the result is not!

It takes a long time to teach kids to abstract the concept of a number that’s independent of the order of the symbols in the result. Since that’s one of the earliest things we learn in math, it’s particularly hard to forget, so when anyone says “addition,” we automatically assume it’s commutative. When we get to sticking things like matrices together, there are a couple of natural ways to do it; the commutative way we call “addition,” and the noncommutative one we call “multiplication.”

The only thing a generic monoid knows how to do is stick things together like a kindergartener who hasn’t abstracted the concept of a number yet. Since (in the general case) that’s noncommutative, we call it “multiplication.” When we learned about multiplication in school, we had to memorize our “times table.” The table had numbers across the top and numbers down the sides. Given a row and a column of the table, we could look up the result of multiplying those two numbers.

A “times table” is a function m:S\times S\to S; the set S\times S cosists of ordered pairs of elements of a pointed set S, a row and a column. The output of the function is the value in that cell of the table. When we were memorizing the times table, the easiest row was multiplying by 1. You just got the same thing back! So one of the elements of S should behave like 1. And the function e tells us which one we should pick!

So that’s one constraint on the table: multiplying by e(\bullet) shouldn’t do anything. We call this “obeying the left-and right-unit laws.” When we use real numbers, we write it like this:

1a=a=a1,

so in our multiplication table, we have

\displaystyle m(e(\bullet), a) = a = m(a, e(\bullet)).

The other constraint on the table is that if you’re multiplying three things, it shouldn’t matter in what order you multiply the pairs. We call this “being associative.” For real numbers, it looks like this:

a(bc) = (ab)c,

so in our multiplication table, we have

\displaystyle m(a, m(b,c)) = m(m(a,b), c).

Now we’re ready for the definition: a monoid consists of a pointed set S, where the special point e(\bullet) is called the “multiplicative identity,” and a times table m that’s associative and obeys the left-and right-unit laws above. Here are several more examples of monoids:

1. The trivial monoid:

  • S=\{1\}
  • e(\bullet)=1
  • m(1,1)=1

2. The free monoid on one element (tally marks under concatenation)

  • S=\{\mbox{(blank)},1,11,111,1111,\ldots\}
  • e(\bullet)= (blank)
  • m(\underbrace{1\ldots 1}_{a},\underbrace{1\ldots 1}_{b}) = \underbrace{1\ldots 1}_{a+b}

3. The whole numbers under addition:

  • S=\{0,1,2,3,\ldots\}
  • e(\bullet)=0
  • m(a,b)=a+b

4. The free monoid on two elements (binary strings under concatenation):

  • S=\{\mbox{(blank)},0,1,00,01,10,11,000,001,\ldots\}
  • e(\bullet)= (blank)
  • m(a,b)=ab, where ab is the string a followed by the string b

5. The reals under multiplication:

  • S=\mathbb{R}
  • e(\bullet)=1
  • m(a,b)=ab
  • Note: the multiplicative group of real numbers excludes 0, because a group has to have inverses. A monoid does not have to have inverses, so we can include it here.

6. Functions from a set T to itself under composition

  • S= all functions of the form a:T\to T
  • e(\bullet) = the identity function
  • m(a,b) = b\circ a, where \circ is composition of functions:

    (b \circ a)(x) = b(a(x)).

So, for example, given the set T=\{0,1\}, we have

  • S contains the four possible functions from T back to itself:
    00) The constant function mapping everything to zero:

    \begin{array}{rl}k_0:T & \to T\\ t & \mapsto 0\end{array}

    01) The identity function:

    \begin{array}{rl}1_T:T & \to T\\ t & \mapsto t\end{array}

    10) The function that toggles the input:

    \begin{array}{rl}NOT:T & \to T\\ t & \mapsto (1-t)\end{array}

    11) The constant function mapping everything to one:

    \begin{array}{rl}k_1:T & \to T\\ t & \mapsto 1\end{array}

  • e(\bullet) = 1_T, the identity function
  • m(a,b) = b \circ a

The identity function is the unit for composition:

(a \circ 1_T)(t) = a(1_T(t)) = a(t)

(1_T \circ a)(t) = 1_T(a(t)) = a(t)

Exercise: verify that composition is associative.

5 comments

5 Responses

Subscribe to comments with RSS.

  1. summerstay said, on 2007 October 1 at 7:56 am

    I like this and I’m glad you’re attempting to create an explanation. I tried to think of things that might improve it.
    This mixes too many levels of ability in the same explanation. If you really want to explain it to everyone, you need to start with junior high math and work your way up.
    I liked the explanation with the cookies. Maybe you could start with that, and use it as an example whenever you start a new concept.
    Avoid words like monoid, composition, commutitive, etc… In fact, avoid the concepts where possible. Decide the main point you want to get across and don’t go off on too many tangents. Don’t worry about being complete in your explanation. Ordinary people are different from mathematicians that way. Give us the approximate truth first, make us understand it, and put the rigor in a footnote or appendix.
    Example 6 is too difficult for now.
    No one in the family except for you and me have studied abstract algebra. The whole concept is very tricky to wrap your head around at first. You need to keep emphasizing that this is not “math”in the sense of solving equations, but the study of patterns. You need to explain the idea that there are all kinds of different things that can be “added” or “multiplied” in lots of different ways, and that you’re talking about studying the rules that apply no matter which set or operation you’re using. People are used to the idea that 3+3=6 can refer to 3 apples plus 3 apples or 3 oranges plus 3 oranges, but the idea that + can refer to some other operation is completely new to most people.
    Whenever you use an example, use at least two examples. That helps people to see what the examples have in common.
    Don’t show the completely trivial example first. Its okay to show it later, after people have the idea in their heads how it usually works.
    Repeat yourself often. Tell us what you are going to explain, explain it, and then tell us what you just explained.

    Reply
  2. Monoids: What They Are « Ireneo’s Memory said, on 2008 April 29 at 1:43 am

    […] Monoids: What They Are April 29, 2008 at 8:43 am | In Mathematics | Tags: computer science, logic, math, Mathematics, monoids Curious about monoids?  Learn more here! […]

    Reply
  3. Link (1) « .junk said, on 2009 April 24 at 1:51 pm

    […] Link (1) Daca esti interesat de structuri algebrice, uite un post introductiv despre monoizi aici. […]

    Reply
  4. drozzy said, on 2011 December 19 at 11:55 am

    Great article!
    Is it also possible to make “m(a,b) = a composed b” as opposed to “b composed a”?

    Reply

Leave a comment