﻿ ﻿OPERATIONS - A Book of Abstract Algebra

## 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 ab 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 al. (The symbol al 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 .

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

# 3a * b is a root of the equation x2a2b2 = 0, on the set .

4Subtraction, on the set .

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

6a * b = |ab, 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.)

1x * y = x + 2y + 4 (i)x * y = x + 2y + 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.

2x * y = x + 2yxy 3x * y = |x + y| 4x * y = |xy| 5x * y = xy + 1 6x * 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}.

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

Label these operations 0l to 016. Then:

2Identify which of the operations 0l to 016 are commutative.

# 3Identify which operations, among 0l to 016, are associative.

4For which of the operations 0l to 016 is there an identity element?

5For which of the operations 0l to 016 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 = a1a2. . . an and b = blb2bm, then

ab = a1a2anbb2. . .bm

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.

1Prove that the operation defined above is associative.

2Explain why the operation is not commutative.

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

﻿