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.
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:
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.
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.
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 .
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:
Examples of sets that are not semigroups include