Introduction to Category Theory/Monoids

From Wikiversity
Jump to navigation Jump to search

From Binary Operators to Arrows[edit | edit source]

Binary operators[edit | edit source]

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

  • .

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

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[edit | edit source]

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

Concatenation of words[edit | edit source]

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


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

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


But it is associative:

Unary operators[edit | edit source]

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

Unary concatenation[edit | edit source]

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: , Helloify(world) = helloworld
Canyouify: , 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

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[edit | edit source]

For every integer n, there's a unary operator

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

that take integer n to funtion Addn. For example

For every integer x and y, following equation holds

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[edit | edit source]

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 onto the mapping defined by . (To fill in the details here, first prove that is a bijection of onto , then that the mapping is an injective homomorphism (monomorphism) from onto the group of bijections of , with composition of functions corresponding to the group operation.)

Arrows[edit | edit source]

Don't argue with arrows,
they take none.


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 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 and equal to arrow ? 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[edit | edit source]

For every integer n, there's a corresponding arrow . Composition of two arrows has the rule


So in this case, the rule of composition is essentially the same as the binary operator Add of the underlying set . 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[edit | edit source]

letters of alphabet
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() Lyricsify() = Hardlyify() Ricsify()

since they both can be decomposed into


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

Monoids[edit | edit source]

Definition[edit | edit source]

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

  • For every pair of arrows f,g in M, the composition 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
  • There's a special arrow , called the identity arrow of M that satisfies
for every arrow f in M.

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

If in addition 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[edit | edit source]

Set together with arrows Addn is a monoid:

  • For every triplet l,m,n of integers
  • Add0 is the identity arrow

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

Monoid of words[edit | edit source]

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:
  • There is an identity Ify.

Functor between monoids[edit | edit source]

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
  • Functor preserves composition of arrows
for all arrows f,g in M.

Functors between two monoids are also called monoid homomorphisms.

Length of word[edit | edit source]

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 of words has m+n letters, for example
Length(homo + morphism) = Length(homomorphism) = 12 = 4 + 8 = Length(homo) + Length(morphism).

Free Monoid[edit | edit source]

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

with all and in the set S (but not necessary distinct), then

and .

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

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 of generators. But a finite sum of finite sums is a finite sum, so every positive generator can be composed as


For a negative generator we have

that gives two different compositions for the number 1.

Product of Monoids[edit | edit source]

Exercises[edit | edit source]

Cyclic monoid of period 5.
  1. A monoid is called cyclic if there's an arrow such that every arrow of can be written as for some positive integer — that is, is generated by — and for some . If is any arrow of a monoid and is the smallest positive integer such that , then we call the period of . The period of a cyclic monoid is the period of its generator. If cyclic monoid has period , and cyclic monoid has period , describe all monoid homomorphisms from to .

Related resources[edit | edit source]