Algebraic Systems
1 INTRODUCTION
This Appendix investigates some of the major algebraic systems in mathematics: semigroups, groups, rings, and ?elds. We also de?ne the notion of a homomorphism and the notion of a quotient structure. We begin with the formal de?nition of an operation, and discuss various types of operations.
2 OPERATIONS
The reader is familiar with the operations of addition and multiplication of numbers, union and intersection of sets, and the composition of functions. These operations are denoted as follows:
a + b = c, a · b = c, A ? B = C, A ? B = C, g o f = h.
In each situation, an element (c, C, or h) is assigned to an original pair of elements. We make this notion precise.
De?nition 1: Let S be a nonempty set. An operation on S is a function ? from S × S into S. In such a case, instead of ? (a, b), we usually write
a ? b or sometimes ab
The set S and an operation ? on S is denoted by (S, ?) or simply S when the operation is understood.
Remark: An operation ? from S × S into S is sometimes called a binary operation. A unary operation is a function from S into S. For example, the absolute value |n| of an integer n is a unary operation on Z, and the
complement AC of a set A is a unary operation on the power set P (X) of a set X. A ternary (3-ary) operation is a function from S × S × S into S. More generally, an n-ary operation is a function from S × S × ··· × S (n factors)
into S. Unless otherwise stated, the word operation shall mean binary operation. We will also assume that our underlying set S is nonempty.
Suppose S is a ?nite set. Then an operation ? on S can be presented by its operation (multiplication) table where the entry in the row labeled a and the column labeled b is a ?
Suppose S is a set with an operation ?, and suppose A is a subset of S. Then A is said to be closed under ?
if a ? b belongs to A for any elements a and b in A.
EXAMPLE 1 Consider the set N of positive integers.
(a) Addition (+) and multiplication (×) are operations on N. However, subtraction (?) and division (/) are not operations on N since the difference and the quotient of positive integers need not be positive integers.
For example, 2 ? 9, and 7/3 are not positive integers.
(b) Let A and B denote, respectively, the set of even and odd positive integers. Then A is closed under addition and multiplication since the sum and product of any even numbers are even. On the other hand, B is closed
under multiplication but not addition since, for example, 3 + 5 = 8 is even.
EXAMPLE 2 Let S = {a, b, c, d }. The tables in Fig. 1 de?ne operations ? and · on S. Note that ? can be de?ned by the following operation where x and y are any elements of S:
x ? y = x
Fig. 1
Next we list a number of important properties of our operations.
Associative Law:
An operation ? on a set S is said to be associative or to satisfy the Associative Law if, for any elements a, b,
c in S, we have
(a ? b) ? c = a ? (b ? c)
Generally speaking, if an operation is not associative, then there may be many ways to form a product. For example, the following shows ?ve ways to form the product abcd:
((ab)c)d , (ab)(cd ), (a(bc))d , a((bc)d ), a(b(cd ))
If the operation is associative, then the following theorem (proved in Problem 4) applies.
Theorem 1: Suppose ? is an associative operation on a set S. Then any product a1 ? a2 ? ··· ? an requires no parentheses, that is, all possible products are equal.
Commutative Law:
An operation ? on a set S is said to be commutative or satisfy the Commutative Law if, for any elements a,
b in S,
a ? b = b ? a
EXAMPLE 3
(a) Consider the set Z of integers. Addition and multiplication of integers are associative and commutative. On the other hand, subtraction is nonassociative. For example,
(8 ? 4) ? 3 = 1 but 8 ? (4 ? 3) = 7
Moreover, subtraction is not commutative since, for example, 3 ? 7 = 7 ? 3.
(b) Consider the operation of matrix multiplication on the set M of n-square matrices. One can prove that matrix multiplication is associative. On the other hand, matrix multiplication is not commutative. For example,