Vignette 11
Operations from Another World

You have been familiar with binary operations since the early days of school.  A binary operation is simply a rule for combining two objects of a given type, to obtain another object of that type.  Through elementary school and most of high school, the objects are numbers, and the rule for combining numbers is addition, subtraction, multiplication or division.  In your precalculus and calculus courses, you encountered a situation where the objects were functions, and composition was the rule for combining two functions.

Binary Operations

The concept of a binary operation is a very general one, and need not be restricted to sets of numbers.  In fact, an operation can be specified on any finite set simply by presenting a table that shows how the operation is performed, when your are given two elements of the set.  For example, consider the set and an operation, denoted by *, defined by the following table:

We interpret this operation table in much the same way that we would interpret an addition table.  Using the operation symbol * as we would use + to mean addition, the table shows us, among other things, that
and so on.  The table summarizes 16 such calculations, telling us how to combine each of the four elements of A with each of the four elements.

Not All Operations Have the Same Properties

You should be familiar with various properties of the arithmetic operations on numbers.  Addition of numbers, for instance, is a commutative operation -- meaning that  for all numbers x and y.  The operation on the set A defined by the operation table above, however, is not commutative, and there are several instances of this lack of commutativity.  For instance,   since the table shows that .  In general, commutativity is a property of an operation, so it takes only one instance of lack of commutativity to spoil that property for the operation.  It is easy to check whether an operation defined by a table is commutative.  Sinply draw the diagonal line from upper left to lower right, and then look to see if the table is symmetric about this line.  In the illustration below, we see a lack of symmetry: the table entries colored yellow do not match, and the table entries colored blue do not match.

Either one of these mismatches would be sufficient to make the operation non-commutative.

Addition of numbers is an associative operation, meaning that   for all numbers x, y and z.  To check to see whether the operation * defined above is associative, however, is a somewhat tedious task.  We would need to compute all combinations of the form  in two ways -- once as shown, and then again in the form  -- and then check to see that they are equal.  This must be done for each selection of elements to fill the placeholders.  In the case of a 4-element set such as A above, there are  choices of the elements to be used, and each must be computed in two ways.  Thus, to verify that a binary operation on a 4-element set is associative, we would have to do 128 computations!  There is no easy shortcut as there is for checking commutativity.

On the other hand, if a given operation fails to be associative, all we need to do to verify this is to find one instance of the lack of associativity.  For the operation * defined on the set  above, we find that , while .  Thus , so the operation * is not associative.

Exercises

Identity Elements

An additional property that a binary operation may or may not have is the existence of an identity element.  Given a binary operation  on a set S, an element e of S is called an identity element for  if   for every element x of S.  (We are using the symbol to represent a generic binary operation here.)   As examples, 0 is an identity element for the operation of addition on the set of real numbers, and 1 is an identity element for the operation of multiplication on the set of real numbers.  For the operation * on the set A above, the element a is an identity element.

As another example, let denote the set of all functions from to  (where denotes the set of real numbers), and let  be the operation of composition of functions in .  Then  is an associative operation, since  for all functions f, g and h in .  But  is not a commutative operation; there are many examples of functions f and g for which .  (Can you find such an example?)

Does the operation  on have an identity element?  The function defined by f(x) = x for all real numbers x (which happens to be called the identity function) has the property that  for all functions g in , and therefore f is an identity element for the operation  on .

One easy fact about identity elements is that if an operation has an identity element, then that identity element must be unique -- that is, there is only one such identity element.  To see why this is true, we suppose that there are two identity elements for the operation on the set S, say e and .  Then consider the element .  Since is an identity, we have , and since e is an identity, we have .  Thus , so there is only one identity for .

Abstract Algebra

The field of mathematics in which binary operations and their properties are studied is called abstract algebra.  In abstract algebra, a semigroup is defined to be a set, along with a binary operation that is associative.  Examples of semigroups include the following:

Can you think of any other examples of semigroups?

Examples of sets that are not semigroups include

Other named algebraic structures are defined by varying the properties that the operation is required to satisfy.  Some of the more important types of algebraic structures that are studied in abstract algebra are groups, rings, fields and modules.  These algebraic structures show up repeatedly in many other branches of mathematics, and so they have attracted much attention over the years.  One example is the set of symmetries of the equilateral triangle, which was introduced in Vignette 8.  The set of symmetries of the triangle, with the operation of composition, is an example of a group -- a semigroup with an identity element, in which every element has an inverse element.  The set of 4th roots of 1, introduced in Vignette 10, is also an example of a group, with the operation of multiplication of complex numbers.

Further Exploration




Copyright © 2000 by Carl R. Spitznagel