and
an operation, denoted by *, defined by the following table:
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:
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.
Exercises
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:
(with the operation
+)(with the operation
of function composition)Examples of sets that are not semigroups include
Further Exploration
