Semigroups, quasigroups

Lisbon  Prague

Lisbon and Prague are two of the most beautiful cities in Europe. In the last week of July 2011, Lisbon hosted a conference on groups and semigroups, and Prague one on quasigroups and loops. I was at the Lisbon conference, as was Michael Kinyon, though it may have been expected that he would be at the other one. His talk was an attempt to build a bridge between the two communities. Inspired by this, I want to talk about various generalisations of groups.

Groups

So to definitions. A group is traditionally defined as a set G with a binary operation (I will temporarily write this as  • ) which satifies the four axioms

  1. For any a,b in G, ab ∈ G.
  2. For any a,b,c in G, a•(bc) = (ab)•c.
  3. There is a particular element e in G with the property that, for any a in G, we have ea = ae = a.
  4. For any element a in G, there exists an element a* in G such that aa* = a*•a = e, where e is as in the third axiom.

A couple of comments on the axioms are in order before we proceed.

  • I used the bullet symbol to suggest that the operation is completely arbitrary and is not necessarily anything to do with multiplication; but from now on I will simplify the notation and write ab instead of ab. The usual practice in group theory is to write 1 for e in the third axiom and a-1 for a* in the fourth.
  • The axioms are called the closure, associative, identity and inverse laws. It is easy to show that the identity element e is unique and that every element a has a unique inverse a*.

These axioms weren’t just made up from idle curiosity. At the end of the eighteenth century, it was observed that the collection of all symmetries of a mathematical or geometrical object are functions from the object to itself, and so can be composed; moreover,

  • the composition of symmetries is a symmetry;
  • the identity function leaving everything fixed is a symmetry;
  • for any symmetry, the inverse function taking everything back to where it came from is a symmetry.

There is a superficial resemblance to axioms 1, 3 and 4 for a group; but the interpretation is different. Composition is a specific operation; the identity and the inverse are specific symmetries.

In the mid-nineteenth century, Dyck and Cayley wrote down the group axioms and made two important observations. First, the symmetries of an object satisfy them: composition of functions is always associative, and the identity and inverse symmetries do satisfy axioms 3 and 4. Second, given an arbitrary “group”, that is, a set with a binary operation satisfying axioms 1–4, one can “represent” the group as transformations of a set, and hence as symmetries of a certain object. (The first part is “Cayley’s theorem”, while the object referred to in the second is the “Cayley graph”, with colours and directions on the edges.)

Thus, a group, a structure satisfying the axioms, is the same thing as the collection of all symmetries of some object. So there was no discontinuity in the development of group theory.

Generalisations

Generalisation for its own sake seldom produces rich mathematics. Almost always we generalise because the existing theory does not cover the objects we want to investigate. For example, in the early development of topology, there was some debate about whether the Hausdorff separation condition should be one of the axioms for a topological space; it was decided not to do this because there are many interesting spaces (such as the Zariski topology on an algebraic variety) which do not satisfy it.

In the twentieth century, various generalisations of groups were considered. The most straightforward way to generalise is to simply omit some of the axioms. Ths, a semigroup is a set with a binary operation satisfying axioms 1 and 2, and a monoid, or “semigroup with identity”, satisfies 1, 2 and 3. Any collection of functions from a set to itself which is closed under composition is a semigroup, while if it contains the identity function it is a monoid.

Thus a monoid arises naturally as the set of all endomorphisms, or structure-preserving maps, from an object to itself.

Some other generalisations are less straightforward, since we want to keep the spirit, rather than the letter, of the axioms we retain. Suppose we wish to retain axioms 1 and 4 and delete the others. Axiom 4 makes no sense without axiom 3. But in a group, if we think of the group operation as “multiplication”, then both “left division” and “right division” are possible and unique; that is,

  • for any a and b, there is a unique x satisfying xa = b;
  • for any a and b, there is a unique y satisfying ay = b.

If these axioms hold, together with axiom 1, we call our structure a quasigroup. The elements x and y are commonly denoted by a\b and b/a respectively; the operations \ and / are left division and right division respectively. A quasigroup with identity (that is, satisfying axiom 3, is a loop. Thus an object is a group if and only if it is both a semigroup and a loop, or both a monoid and a quasigroup.

I described here some time ago the origin of the term “loop”. I learned in Lisbon that Albert had originally intended to call these objects “knots” but was dissuaded.

An operation on a finite set can be represented by an operation table, a square table whose rows and columns are indexed by the underlying set G, with the entry in row a and column b being ab (or a • b, to be more formal). A quasigroup is precisely a structure whose operation table is a Latin square; it is a loop precisely when, assuming that the first element is the identity e, the first row and column are the same as the row and column labels.

Note one difference between the theories of semigroups and quasigroups. In a semigroup, the associative law holds, so we can write products like abcd unambiguously. In a quasigroup or loop, we would have to specify which of the five possible bracketings of this product is intended.

What about deleting axiom 1? In a sense this axiom is unnecessary anyway, since by definition a binary operation is everywhere defined. But we could imagine a set with a “partial operation” which is not everywhere defined. The operation table for such a structure will have some gaps.

It seems that, to get a reasonable theory, we must put some restrictions on these gaps. The most popular way leads to a structure called a groupoid. Behind the scenes, we have a set of “objects”, and we think of the elements of the groupoid as “arrows”, each of which has an initial and a terminal object. Now the composition of a and b is defined if and only if the terminal object of a is equal to the initial object of b; if ab and bc are defined, then (ab)c and a(bc) are also defined and we require them to be equal. (This is a suitably restricted version of the associative law.) Also, we require that, for each object o, there is an identity element 1o which is a left identity for anything with initial object o, and a right identity for anything with terminal object o; and we require that each element a has an inverse a* (with initial and terminal objects reversed) so that aa* is the identity of the initial object of a, and similarly for a*a. Thus, for any object o, the set of elements of the groupoid with initial and terminal objects equal to o is a group with identity element 1o.

If this seems a bit of a mouthful, there is a simple example: the “sliding block puzzle”, with fifteen tiles sliding in a 4×4 frame. The elements of the groupoid are the transformations effected by sequences of moves; the objects are the 16 positions of the empty square. The group corresponding to the object in the bottom right consists of all permutations of the other fifteen tiles that can be realised by sequences of moves; it happens to be the alternating group A15.

If we also delete the inverse axiom, the structure we obtain is a category. Thus groupoids bear the same relation to categories as groups do to monoids.

Groups from quasigroups

Let G be a quasigroup. Then all the right multiplications ρaGG defined by the rule that ρa maps x to xa, are permutations: the inverse is right division by a. These permutations generate a group, the right multiplication group of G. If G is a group, then the right multiplication group is isomorphic to G: this is the proof of Cayley’s Theorem. For an arbitrary quasigroup, this group will be larger than G (it will act transitively but not regularly on G). In fact, for a random finite quasigroup, the right multiplication group is the symmetic group (all permutations of G) with high probability.

There is an analogously defined left multiplication group. Together they generate the multiplication group of G. If G is a loop, the inner multiplication group of G is the stabiliser of the identity in the multiplication group; it is so-called because, if G happens to be a group, then this is the group of inner automorphisms of G (the conjugations xa-1xa).

Apart from purely combinatorial results on Latin squares, the best structural results on quasigroups certainly come from looking at their multiplication groups.

The closest relatives of groups

Even hard-core semigroup and quasigroup theorists will admit that these theories are not as well developed as the theory of groups. Indeed, few parts of mathematics can boast a result of the depth and beauty of the classification of finite simple groups.

So it is no surprise that some of the best-developed parts of both these theories concern objects which are as close to groups as possible.

In the case of semigroup theory, these are the inverse semigroups, those with the following property:

  • For any element a, there is an element a* such that aa*a = a and a*aa* = a*.

The elements aa* and a*a are idempotent. (An idempotent is an element e satisfying ee = e.) Now if e is an idempotent, the set G(e) of elements a satisfying a*a = aa* = e) is a group, having e as identity element.

There is a standard model for inverse semigroups, playing the role of the symmetric group for groups. This is the symmetric inverse semigroup, the set of all bijections between subsets of a set. The Vagner–Preston Theorem asserts that any inverse semigroup is isomorphic to a sub-semigroup of the symmetric inverse semigroup on some set. (This is surprisingly much more difficult to prove than Cayley’s Theorem.)

For loops, the closest to groups are the Moufang loops, which first arose in the foundations of geometry in the work of Ruth Moufang. One of these is defined to be a loop satisfying one of the following identities (they are all equivalent):

  • c(a(cb)) = ((ca)c)b,
  • a(c(bc)) = ((ac)b)c,
  • (ca)(bc) = (c(ab))c,
  • (ca)(bc) = c((ab)c).

Note that these are all special cases of the associative law.

A Moufang loop has the property that the subloop generated by any two elements is associative. (All possible instances of the associative law in which two of the three variables are equal follow from the above identities.)

After groups, the most celebrated examples of Moufang loops are the unit octonions; there are many others.

Every finite Moufang loop satisfies Lagrange’s Theorem: the order of every subloop divides the order of the loop. Remarkably, this was only proved in 2005, by Grishkov and Zavarnitsine in the Proceedings of the Cambridge Philosophical Society.

Kinyon’s work

Both Lisbon and Prague are situated on impressive wide rivers. Their inhabitants knew that the best place to build a bridge is where the two banks are not too far apart.

Michael Kinyon’s talk followed this principle. He defined a Moufang semiloop to be a set with a binary operation satisfying the Moufang identities. Thus both semigroups and Moufang loops are examples. He was particularly concerned with the class of inverse Moufang semiloops, satisfying the extra requirement which defines inverse semigroups among semigroups. Much of the theory of both inverse semigroups and Moufang loops extends to this class; one can define multiplication semigroups; there is a Vagner–Preston theorem; and so on.

Michael’s abstract is on the conference website. I believe that the slides of his talk will appear there sometime.

He speculated that, sometime in the future, the two conferences would have a joint session. Perhaps in another of Europe’s beautiful cities?

About these ads

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition and tagged , , , , . Bookmark the permalink.

8 Responses to Semigroups, quasigroups

  1. Pingback: Inverse funtion | Catdate

  2. Pingback: Weekly Picks « Mathblogging.org — the Blog

  3. Colin McQuillan says:

    A correction: in “If these axioms hold, together with 1 and 2, we call our structure a quasigroup”, axiom 2 (associativity) shouldn’t be in the definition of quasigroup.

  4. Michael Kinyon’s slides are now available here.
    The slides of many other talks are also available; take a look!

  5. Benjamin Steinberg says:

    Peter: Your definition of G(e) for an inverse semigroup is slightly off. For example if M is an inverse monoid and e is the identity you would get the whole inverse monoid. You want G(e) to be all elements x with xx*=e=x^*x.

  6. Ben Phillips says:

    As a student working on a thesis on Profinite loops, I especially appreciated reading this blog entry! Thanks for drawing some attention to this topic!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s