Introduction to Category Theory/Monoids

From Binary Operators to Arrows

edit

Binary operators

edit

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

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

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

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

Unary concatenation

edit

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

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

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

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

Definition

edit

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

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

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

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

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

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

Exercises

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