Introduction to Category Theory/Monoids

From Binary Operators to Arrows

Binary operators

A Binary operator on set A is a function from the product set $A\times A$ to set A. A Binary operator f is called commutative, if all elements a and b in A satisfy the equation:

• $f(a,b)=f(b,a)\,$.

Otherwise it is non-commutative. A binary operator f is called associative if all elements a, b, c in A satisfy the equation:

• $f(f(a,b),c)=f(a,f(b,c))\,$

We've already seen two binary operators: union and intersection of subsets of set A are binary operators in the powerset of A. Are they commutative or non-commutative? Associative or non-associative?

Let's take a look at two other simple binary operators.

Addition of Integers

If m and n are integers, then the sum of m and n is an integer. So addition is a binary operator in the set of integers. We usually write addition with the symbol '+', but we can also write it Add(m,n).

$\operatorname {Add} (3,5)=3+5=8$

Concatenation of words

Let S be the set of three letters {a,b,c}. Then the set of all words generated by letters S is the set

$F(S)=\{-,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac,...\}\,$.

That is, finite sequences of elements of S, including the empty sequence, here designated by the symbol '$-$'.

In this set we can define binary operator

$\operatorname {Concat} :F(S)\times F(S)\to F(S)$

by writing two words together without any separating space between them. Concat(abac,cab) = abaccab. Concat(-,acca) = acca. Concat is non-commutative operator

$\operatorname {Concat} (ab,ba)=abba\neq baab=\operatorname {Concat} (ba,ab)$.

But it is associative:

$\operatorname {Concat} (\operatorname {Concat} (a,b),c)=\operatorname {Concat} (a,\operatorname {Concat} (b,c))$

Unary operators

A Unary operator on a set A is a function from the set A to itself.

Unary concatenation

On a set of all the words of the latin alphabet L={a, b, c, ..., z}, we can define the unary operator Abbaify, that will add word abba in front of it's argument. Abbaify(xyz) = abbaxyz, Abbaify(rox) = abbarox, Abbaify(Abbaify(qwerty)) = abbaabbaqwerty. In fact we can define similar function for every single word.

Helloify: $F(L)\to F(L)$, Helloify(world) = helloworld

Canyouify: $F(L)\to F(L)$, Canyouify(readthis) = canyoureadthis

All these function form a set

FrontAdders = {set of all functions that add fixed word in front of its argument}

There's also a function from the set of words to the set FrontAdders

$\operatorname {MakeAdder} :F(L)\to FrontAdders$

For example

MakeAdder(abba) = Abbaify

MakeAdder(hello)(there) = Helloify(there) = hellothere

For every pair of words x and y, the following equation holds

Concat(x,y) = MakeAdder(x)(y)

Unary addition of integers

For every integer n, there's a unary operator

$\operatorname {Addn} :\mathbb {Z} \to \mathbb {Z}$

that adds n to its argument. Add5(7) = 12, Add3(13)=16, Add0(123)=123, Add[-2](5) = 3. We can define set Adders = {..., Add[-2], Add[-1], Add0, Add1, Add2, ...} and a function

$\operatorname {MakeAdder} :\mathbb {Z} \to Adders$

that take integer n to funtion Addn. For example

$\operatorname {MakeAdder} (5)=\operatorname {Add5}$

$\operatorname {MakeAdder} (10)(-4)=\operatorname {Add10} (-4)=6$

For every integer x and y, following equation holds

$\operatorname {MakeAdder} (x)(y)=\operatorname {Add} (x,y)=x+y$

So the set Adders of unary operators can do everything that binary operator Add can. In the next section we define set of arrows (or nullary operators) that take no arguments, and yes, they still can add integers.

Cayley's Theorem

If you've done a bit of group theory (if you haven't, you should, but for the moment you can just ignore this paragraph), you can see that the basic idea of the two examples above is the same as that of Cayley's theorem, which says that any group is isomorphic to a certain subgroup of that group's group of bijections. That is, elements of the group can be regarded as being the same thing as certain unary operations applying to that group. The isomorphism consists of mapping a group element $a\in G$ onto the mapping $f_{a}:G\rightarrow G$ defined by $f_{a}(x)=a*x\,$. (To fill in the details here, first prove that $f_{a}\,$ is a bijection of $G\,$ onto $G\,$, then that the mapping $a\rightarrow f_{a}$ is an injective homomorphism (monomorphism) from $G\,$ onto the group of bijections of $G\,$, with composition of functions corresponding to the group operation.)

Arrows

Don't argue with arrows, they take none. —Tlep

In the original conception of binary operators, we take two members of a set, and apply an operation to them to give another. With the shift to unary operators, we apply a unary operation to a single member of a set to get another. But since the unary operation applies to every member of the set, we can think of this as something that is done to the whole set, with no consideration of individual members. Thinking of the integers, for example, the old view is (approximately) represented by the left-hand side of the figure below, where we have a set containing various members, and a single binary operation combining them (the binarity of the operation is not represented):

Two different points of view to integers.

On the right, we see the proposed new view, where 'the integers' are presented as an unstructured blob, with a collection of unary operations applying to it.

If we stop worrying about what these unary operations do to whatever they apply to, which amounts to thinking of them as 'zero place' operations that don't actually apply to anything, but just go from one place to another, we arrive at the basic idea of arrow, which can be informally defined as follows:

Arrow $f:A\to B$ is an object, that points from A to B and can be composed with other arrows that either end at A or start from B.

What does it mean to compose two arrows? When is the composition of arrows $f:A\to B$ and $g:B\to C$ equal to arrow $h:A\to C$? There needs to be some rule of composition. When arrows are based on unary operations, composition of arrows amounts to successive application of the operations (that is, composition of functions). Let's take a look at two examples.

Example: integers as arrows

For every integer n, there's a corresponding arrow ${\text{Addn}}:\mathbb {Z} \to \mathbb {Z}$. Composition of two arrows has the rule

$({\text{Addm}}\circ {\text{Addn}})={\text{Add}}[m+n]$.

So in this case, the rule of composition is essentially the same as the binary operator Add of the underlying set $\mathbb {Z}$. At first it might seem that we haven't achieved much, but that's not true. We have shifted the point of view from elements of a set to arrows outside the set. It is an important observation: what is an arrow from one point of view, is an object from another point of view. Note that these integer-arrows compose associatively.

Example: words as arrows

letters of alphabet

Every word is a sequence of letters and every word is written one letter at a time. So if our alphabet consists of three letters a, b, and c, each of which is also an arrow starting and ending at the same point, then every word corresponds to exactly one path along the arrows. Two compositions of words are the same, if their decomposition into letters are the same. For example

Hardify() $\circ$ Lyricsify() = Hardlyify() $\circ$ Ricsify()

since they both can be decomposed into

$h\circ a\circ r\circ d\circ l\circ y\circ r\circ i\circ c\circ s$.

So composition of word-arrows is also associative (in fact, if people call something an arrow, its composition is always associative).

Monoids

Definition

Monoid is an object M together with a collection of arrows $f:M\to M$ that satisfy the following properties:

• For every pair of arrows f,g in M, the composition $g\circ f$ of arrows is also in M.
• Composition of arrows is associative. In other words for every triplet of arrows f, g, and h in M the equation

$h\circ (g\circ f)=(h\circ g)\circ f$ holds.

• There's a special arrow $1_{M}$, called the identity arrow of M that satisfies

$1_{M}\circ f=f=f\circ 1_{M}$ for every arrow f in M.

Arrows of a monoid are also called morphisms (or endomorphisms or simply elements).

If in addition $g\circ f=f\circ g$ for every arrow f,g in M, we say that monoid is commutative, otherwise it's non-commutative.

More familiarly and less abstractly, perhaps: A monoid is a set that is closed under an associative binary operation and has an identity element . Note that unlike a group, its elements need not have inverses. It can also be thought of as a semigroup with an identity element.

A monoid must contain at least one element.

A monoid that is commutative is, not surprisingly, known as a commutative monoid.

Monoid of integers

Set $\mathbb {Z}$ together with arrows Addn is a monoid:

• For every triplet l,m,n of integers

$Addl\circ (Addm\circ Addn)=Addl\circ Add[m+n]=Add[l+m+n]=Add[l+m]\circ Addn=(Addl\circ Addm)\circ Addn$

• Add0 is the identity arrow

$Addn\circ Add0=Add[n+0]=Addn=Add[0+n]=Add0\circ Addn$

From now on we will drop cumbersome notation Addn and will simple write n, and instead of using composition symbol circle '$\circ$', we'll use symbol plus '+'.

Monoid of words

For every word in F(L) there is a corresponding arrow Wordify.

• Composition of arrows corresponds to concatenation of words, so it is not commutative.
• Composition of arrows is associative. Example:

$Redify\circ (Greenify\circ Blueify)=Redify\circ Greenblueify=Redgreenblueify$

$(Redify\circ Greenify)\circ Blueify=Redgreenify\circ Blueify=Redgreenblueify$

• There is an identity Ify.

$Ify\circ Colorify=Colorify\circ Ify=Colorify$

Functor between monoids

Functor F from monoid M to monoid N is a function from arrows of M to arrows of N, with following properties:

• F takes the identity arrow of M to the identity arrow of N

$F(1_{M})=1_{N}$

• Functor preserves composition of arrows

$F(f\circ _{M}g)=F(f)\circ _{N}F(g)$ for all arrows f,g in M.

Functors between two monoids are also called monoid homomorphisms.

Length of word

Function Length() that counts the number of letters in word is a monoid homomorphism.

• Length of empty word is 0
• If word x has m letters and word y has n letters, then concatenation $x\circ y$ of words has m+n letters, for example

Length(homo + morphism) = Length(homomorphism) = 12 = 4 + 8 = Length(homo) + Length(morphism).

Free Monoid

Let M be a monoid and let S be a subset of arrows in M. We say that monoid M is generated by the set S, if every arrow in M is a finite composition of arrows in S.

The monoid of natural numbers (0,1,2,3,...) is generated by the arrow 1, since every positive integer is a finite sum of 1's. Number zero is a composition of zero generators; that is, zero is the sum of zero 1's.

The monoid of integers (...,-2,-1,0,1,2,...} is generated by the set {-1,1} of arrows. This monoid is also generated by {-5,2}, since -5+2+2 = -1 and -5+2+2+2 = 1.

The empty monoid, with nothing but the identity arrow, is generated by the empty set { }.

We say that monoid M is freely generated by the set S of arrows if every arrow in M is a finite composition of arrows in S in exactly one way. That is if

$f=s_{1}\circ s_{2}\circ ...\circ s_{n}=r_{1}\circ r_{2}\circ ...\circ r_{m}$

with all $s_{i}$ and $r_{i}$ in the set S (but not necessary distinct), then

$n=m\;$ and $s_{1}=r_{1},s_{2}=r_{2},...,s_{n}=r_{m}\;$.

We say that monoid M is a free monoid if it's freely generated by some subset of arrows.

The set of all words generated by a set L of letters is free by the definition of word. This set is sometimes written

$F(L)=1+L+L\times L+L\times L\times L+L\times L\times L\times L+\ldots$

The monoid of natural numbers is a free monoid. It's freely generated by the number 1.

Proposition. Monoid of integers is not free.

Proof. If the set of generators contains the number 1, then it can't contain any other positive integer, since every positive integer is a finite sum of 1's. It can't contain any negative numbers either, since any negative number plus a finite sum of 1's is 1.

On the other hand every set of generators must generate number 1, so 1 is the finite sum $(s_{1}+s_{2}+...+s_{n})$ of generators. But a finite sum of finite sums is a finite sum, so every positive generator $s_{0}\;$ can be composed as

$s_{0}=(s_{1}+...+s_{n})_{1}+(s_{1}+...+s_{n})_{2}+...+(s_{1}+...+s_{n})_{s_{0}}\;$.

For a negative generator $-s_{0}\;$ we have

$-s_{0}+(s_{1}+...+s_{n})_{1}+(s_{1}+...+s_{n})_{2}+...+(s_{1}+...+s_{n})_{s_{0}+2}=1=(s_{1}+...+s_{n})$

that gives two different compositions for the number 1. $\Box$

Exercises

Cyclic monoid of period 5.

1. A monoid $M\;$ is called cyclic if there's an arrow $f\;$ such that every arrow of $M\;$ can be written as $f^{k}\;$ for some positive integer $k$ — that is, $M\;$ is generated by $f\;$ — and $f^{k}=1_{M}\;$ for some $k>0$. If $g\;$ is any arrow of a monoid $N\;$ and $n$ is the smallest positive integer such that $g^{n}=1_{N}\;$, then we call $n$ the period of $g\;$. The period of a cyclic monoid is the period of its generator. If cyclic monoid $M\;$ has period $m$, and cyclic monoid $N\;$ has period $n$, describe all monoid homomorphisms from $M\;$ to $N\;$.

Related resources

• w:Binary operation
• w:Unary operation
• w:Monoid
• w:Endomorphism
• w:Free semigroup
• w:Formal language
• w:Homomorphism
• w:Cyclic group