ALGEBRAIC STRUCTURES: DISCRETE MATH

In exercise 11.2.3 :

i. Items (b), (d), (e), and (f) are groups. For each, show what the identity is, and what the inverse of atypical element is.

ii. Item (a) is not a group. Why not?

iii. Item (g) is not a group. Why not?

iv. Item (c) does not even specify an operator. Why not

EX: 11.2.3 :

3. Which of the following are groups? ( do not answer this; this is the reference for the above question)

(a) B with concatenation (see Subsection 11.2.1).

(b) M₂₃(R) with matrix addition. (c) M₂₃(R) with matrix multiplication.

(d) The positive real numbers, R+,with multiplication.

(e) The nonzero real numbers, R, with multiplication.

(f) {1,1} with multiplication.

(g) The positive integers with the operation M defined by aMb = the larger of a and b.

REFERENCE: Subsection 11.2.1

11.2.1 Monoids at Two Levels

Consider the following two examples of algebraic systems.

(a) Let B be the set of all finite strings of 0's and 1's including the null (or empty) string, . An algebraic system is obtained by adding the operation of concatenation. The concatenation of two strings is simply the linking of the two strings together in the order indicated. The concatenation of strings a with b is denoted a+b. For example, 01101+101 = 01101101 and + 100 = 100. Note that concatenation is an associative operation and that is the identity for concatenation. A note on notation: There isn't a standard symbol for concatenation. We have chosen + to be consistent with the notation used in Python and Sage for the concatenation.

(b) Let M be any nonempty set and let be any operation on M that is associative and has an identity in M. Our second example might seem strange, but we include it to illustrate a point. The algebraic system [B;+] is a special case of [M;]. Most of us are much more comfortable with B than with M. No doubt, the reason is that the elements in B are more concrete. We know what they look like and exactly how they are combined. The description of M is so vague that we don't even know what the elements are, much less how they are combined. Why would anyone want to study M? The reason is related to this question: What theorems are of interest in an algebraic system? Answering this question is one of our main objectives in this chapter. Certain properties of algebraic systems are called algebraic properties, and any theorem that says something about the algebraic properties of a system would be of interest. The ability to identify what is algebraic and what isn't is one of the skills that you should learn from this chapter. Now, back to the question of why we study M. Our answer is to illustrate the usefulness of M with a theorem about M.

Theorem 11.2.1 A Monoid Theorem. If a, b are elements of M and ab = ba, then (ab)(ab) = (aa)(bb). Proof. (ab)(ab) = a(b(ab)) Why? = a((ba)b) Why? = a((ab)b) Why? = a(a(bb)) Why? = (aa)(bb) Why? The power of this theorem is that it can be applied to any algebraic system that M describes. Since B is one such system, we can apply Theorem 11.2.1 to any two strings that commute. For example, 01 and 0101. Although a special case of this theorem could have been proven for B, it would not have been any easier to prove, and it would not have given us any insight into other special cases of M. Example 11.2.2 Another Monoid. Consider the set of 2 2 real matrices, M₂₂(R), with the operation of matrix multiplication. In this context, Theorem 11.2.1 can be interpreted as saying that if AB = BA, then (AB)² = A²B². One

pair Of matrices that this theorem applies to is:

( 2 1 1 2 ) and( 3 4 4 3 ).