## A Book of Abstract Algebra, Second Edition (1982)

### Chapter 2. OPERATIONS

Addition, subtraction, multiplication, division—these and many others are familiar examples of operations on appropriate sets of numbers.

Intuitively, an operation on a set *A* is a way of combining any two elements of *A* to produce another element in the same set *A*.

Every operation is denoted by a symbol, such as +, ×, or ÷ In this book we will look at operations from a lofty perspective; we will discover facts pertaining to operations *generally* rather than to specific operations on specific sets. Accordingly, we will sometimes make up operation symbols such as * and to refer to arbitrary operations on arbitrary sets.

Let us now define formally what we mean by an *operation* on set *A*. Let *A* be *any set:*

*An operation * on A is a rule which assigns to each ordered pair* (*a*, *b*) *of elements of A exactly one element* *a* * *b* in *A*.

There are three aspects of this definition which need to be stressed:

1.*a* * *b* *is defined for every ordered pair* (a, *b*) *of elements of A*. There are many rules which look deceptively like operations but are not, because this condition fails. Often *a* * *b* is defined for all the obvious choices of *a* and *b*, but remains undefined in a few exceptional cases. For example, division does not qualify as an operation on the set of the real numbers, for there are ordered pairs such as (3, 0) whose quotient 3/0 is undefined. In order to be an operation on , division would have to associate a real number *alb* with *every* ordered pair (*a*, *b*) of elements of . No exceptions allowed!

2.*a* * *b* *must be uniquely defined*. In other words, the value of *a* * *b* must be given unambiguously. For example, one might attempt to define an operation □ on the set of the real numbers by letting *a* □ *b* be the number whose square is *ab*. Obviously this is ambiguous because 2 □ 8, let us say, may be either 4 or -4. Thus, □ does not qualify as an operation on !

3.*If a and b are in A, a * b must be in A*. This condition is often expressed by saying that *A* is *closed* under the operation *. If we propose to define an operation * on a set *A*, we must take care that *, when applied to elements of *A, does not take us out of A*. For example, division cannot be regarded as an operation on the set of the integers, for there are pairs of integers such as (3,4) whose quotient 3/4 is not an integer.

On the other hand, division does qualify as an operation on the set of all the *positive real numbers*, for the quotient of any two positive real numbers is a uniquely determined positive real number.

An operation is *any* rule which assigns to each ordered pair of elements of *A* a unique element in *A*. Therefore it is obvious that there are, in general, many possible operations on a given set *A*. If, for example, *A* is a set consisting of just two distinct elements, say *a* and *b*, each operation on *A* may be described by a table such as this one:

In the left column are listed the four possible ordered pairs of elements of *A*, and to the right of each pair (*x, y*) is the value of *x* * *y*. Here are a few of the possible operations:

Each of these tables describes a *different* operation on *A*. Each table has four rows, and each row may be filled with either an *a* or a *b;* hence there are 16 possible ways of filling the table, corresponding to *16 possible operations* on the set *A*.

We have already seen that any operation on a set *A* comes with certain “options.” An operation * may be *commutative*, that is, it may satisfy

*a* * *b* = *b* * *a*(1)

for any two elements *a* and *b* in *A*. It may be *associative*, that is, it may satisfy the equation

(*a* * *b*) * *c* = *a* * (*b* * *c*)(2)

for any three elements *a*, *b*, and *c* in *A*.

To understand the importance of the associative law, we must remember that an operation is a way of combining *two* elements; so if we want to combine *three* elements, we can do so in different ways. If we want to combine *a*, *b*, and *c without changing their order*, we may either combine *a* with the result of combining *b* and c, which produces *a* * (*b* * *c*); or we may first combine *a* with *b*, and then combine the result with *c*, producing (*a* * *b*) * *c*. The associative law asserts that these two possible ways of combining three elements (without changing their order) produce the same result.

For example, the addition of real numbers is associative because *a* + (*b* + *c*) = (*a* + *b*) + *c*. However, division of real numbers is *not* associative: for instance, 3/(4/5) is 15/4, whereas (3/4)/5 is 3/20.

If there is an element *e* in *A* with the property that

*e* * *a* = *a* and *a* * *e* = *a* *for every element a in A*(3)

then *e* is called an *identity* or “neutral” element with respect to the operation *. Roughly speaking, __Equation (3)__ tells us that when *e* is combined with any element *a*, it does not change *a*. For example, in the set of the real numbers, 0 is a neutral element for addition, and 1 is a neutral element for multiplication.

If *a* is any element of *A*, and *x* is an element of *A* such that

*a* * *x* = *e* and *x* * *a* = *e*(4)

then *x* is called an *inverse* of *a*. Roughly speaking, __Equation (4)__ tells us that when an element is combined with its inverse it produces the neutral element. For example, in the set of the real numbers, −*a* is the inverse of *a* with respect to addition; if *a* ≠ 0, then 1/*a* is the inverse of *a* with respect to multiplication.

The inverse of *a* is often denoted by the symbol *a*^{−}^{l}. (The symbol *a*^{−}^{l} is usually pronounced “*a* inverse.”)

**EXERCISES**

Throughout this book, the exercises are grouped into exercise sets, each set being identified by a letter A, B, C, etc, and headed by a descriptive title. Each exercise set contains six to ten exercises, numbered consecutively. *Generally, the exercises in each set are independent of each other and may be done separately*. However, when the exercises in a set are related, with some exercises building on preceding ones so that they must be done in sequence, this is indicated with a symbol t in the margin to the left of the heading.

The symbol # next to an exercise number indicates that a partial solution to that exercise is given in the Answers section at the end of the book.

**A. Examples of Operations**

Which of the following rules are operations on the indicated set? ( designates the set of the integers, the rational numbers, and the real numbers.) For each rule which is not an operation, explain why it is not.

**Example** , on the set .

Solution This is not an operation on . There are integers *a* and *b* such that {*a* + *b*)/*ab* is not an integer. (For example,

is not an integer.) Thus, is not closed under *.

**1**, on the set .

**2***a** *b* = *a* ln *b*, on the set {*x* ∈ : *x >* 0}.

# __3__*a* * *b* is a root of the equation *x*^{2} − *a*^{2}*b*^{2} = 0, on the set .

**4**Subtraction, on the set .

**5**Subtraction, on the set {*n* ∈ : *≥*0}.

**6***a* * *b* = |*a* − *b*, *on* the set {*n* ∈ : *≥*0}.

**B. Properties of Operations**

Each of the following is an operation * on *U*. Indicate whether or not

(i)it is commutative,

(ii)it is associative,

(iii) has an identity element with respect to *,

(iv)every *x* ∈ has an inverse with respect to *.

**Instructions** For (i), compute *x* * *y* and *y* * *x*, and verify whether or not they are equal. For (ii), compute *x* * (*y* * *z*) and (*x* * *y*) * *z*, and verify whether or not they are equal. For (iii), first solve the equation *x* * *e* = *x* for *e*; if the equation cannot be solved, there is no identity element. If it *can* be solved, it is still necessary to check that *e* * *x* = *x** *e* = *x* for any *x*. If it checks, then *e* is an identity element. For (iv), first note that if there is no identity element, there can be no inverses. If there *is* an identity element *e*, first solve the equation *x* * *x*′ = *e* for *x′* if the equation cannot be solved, *x* does not have an inverse. If it *can* be solved, check to make sure that *x* * *x′* = *x′* * *x* = *x′* * *x* = *e*. If this checks, *x′* is the inverse of *x*.

**Example** *x* * *y* = *x* + *y* + 1

(i)*x* * *y* = *x* + *y* + 1; *y* * *x* = *y* + *x* + 1 = *x* + *y* + 1.

(*Thus, * is commutative*.)

(ii)*x**(*y* * *z*) = *x**(*y* + *z* + l) = *x* + (*y* + *z* + l) + l = *x* + *y* + *z* + 2.

(*x* * *y*) * *z* = (*x* + *y* + 1) * *z* = (*x* + *y* + 1) + *z* + 1 = *x* + *y* + *z* + 2.

(** is associative*.)

(iii)Solve *x** *e* = *x* for *e*: *x* * *e* = *x* + *e* + 1 = *x;* therefore, *e* = −1.

Check: *x* * (−1) = *x* + (−1) + 1 = *x*; (−1) * *x* = (−1) + *x* + 1 = *x*.

Therefore, −1 is the identity element.

(** has an identity element*.)

(iv)Solve *x* * *x′* = −1 for *x′*: *x* **x′* = *x* + *x′* + 1 = −1; therefore *x′* = −*x* − 2. Check: *x* * (−*x* − 2) = *x* + (−*x* − 2) + 1 = −1; (−*x* − 2) * *x* = (−*x* −2) + *x* + l = −l. Therefore, −*x* − 2 is the inverse of *x*.

(*Every element has an inverse*.)

**1***x* * *y* = *x* + 2*y* + 4

(i)*x* * *y* = *x* + 2*y* + 4; *y* * *x* =

(ii)*x**(*y* * *z*) = *x**() =

(*x* * *y*) * *z* = () * *z* =

(iii)Solve *x* * *e* = *x* for *e*. Check.

(iv)Solve *x* * *x′* = *e* for *x′*. Check.

**2***x* * *y* = *x* + 2*y* − *xy*

**3***x* * *y* = |*x* + *y*|

**4***x* * *y* = |*x* − *y*|

**5***x* * *y* = *xy* + 1

**6***x* * *y* = max {*x*, *y*} = the larger of the two numbers *x* and *y*

# ** 7** (on the set of positive real numbers)

**C. Operations on a Two-Element Set**

Let *A* be the two-element set *A* = {*a*, *b*}.

**1**Write the tables of all 16 operations on *A*. (Use the format explained on page 20.)

Label these operations 0_{l} to 0_{16}. Then:

**2**Identify which of the operations 0_{l} to 0_{16} are commutative.

# ** 3**Identify which operations, among 0

_{l}to 0

_{16}, are associative.

**4**For which of the operations 0_{l} to 0_{16} is there an identity element?

**5**For which of the operations 0_{l} to 0_{16} does every element have an inverse?

**D. Automata: The Algebra of Input/Output Sequences**

Digital computers and related machines process information which is received in the form of input sequences. An *input sequence* is a finite sequence of symbols from some alphabet *A*. For instance, if *A* = {0,1} (that is, if the alphabet consists of only the two symbols 0 and 1), then examples of input sequences are 011010 and 10101111. If *A* = {*a*, *b*, *c*}, then examples of input sequences are *babbcac* and *cccabaa. Output sequences* are defined in the same way as input sequences. The set of all sequences of symbols in the alphabet *A* is denoted by *A**.

There is an operation on *A** called *concatenation:* If **a** and **b** are in *A**, say **a** = *a*_{1}*a*_{2}. . . *a _{n}* and

**b**=

*b*

_{l}

*b*

_{2}…

*b*, then

_{m}**ab** = *a*_{1}*a*_{2} … *a _{n}bb*

_{2}. . .

*b*

_{m}In other words, the sequence **ab** consists of the two sequences **a** and **b** end to end. For example, in the alphabet *A* = {0,1}, if **a** = 1001 and **b** = 010, then **ab** = 1001010.

The symbol λ denotes the empty sequence.

**1**Prove that the operation defined above is associative.

**2**Explain why the operation is not commutative.

**3**Prove that there is an identity element for this operation.