Mathematics 243, section 3 – Algebraic Structures Solutions for Problem Set 2 due: September 14, 2012

‘A’ Section

1. Let f : ℤ → ℤ and g : ℤ → ℤ be the indicated functions. In each case, say whether f, g, f ∘ g, g ∘ f are one-to-one (injective) or onto (surjective), both, or neither. Justify your answers.

a. f(x) = 3x, g(x) = 4 − x Solution: f is one-to-one since f(x) = 3x = 3x′ = f(x′) implies 3(x−x′) = 0 in ℤ. Hence x − x′ = 0, so x = x′. f is not onto because, for instance, there is no x ∈ ℤ such that f(x) = 3x = 1. g is one-to-one since 4 − x = 4 − x′ implies x = x′. g is also onto, since given any integer y, g(x) = 4 − x = y when x = 4 − y. (f ∘ g)(x) = 3(4 − x) = 12 − 3x. This is one-to-one since 12 − 3x = 12 − 3x′ implies 3(x − x′) = 0, so x = x′ as before. This function is not onto since there is no integer x such that (f ∘ g)(x) = 12 − 3x = 1 (for instance). Finally g ∘ f is the function (g ∘ f)(x) = 4 − 3x. This is one-to-one and not onto for reasons similar to those given for f ∘ g.

b. f(x) = |x|, g(x) = \begin{cases}x & if x is even \\ x − 1 & if x is odd \end{cases} .

Solution: f is neither one-to-one nor onto, because f(x) = f(−x) and f takes only nonnegative values. g is neither one-to-one nor onto. For instance g(2) = 2 = g(3) so g is not one-to-one. g is not onto either because it takes only even values. (f ∘ g)(x) =

\begin{cases}|x| & if x is even \\ |x − 1| & if x is odd \end{cases} is neither one-to-one nor onto since g is not one-to-one and f is

not onto. (g ∘ f)(x) = \begin{cases}|x| & if x is even \\ |x| − 1 & if x is odd \end{cases} is neither one-to-one nor onto since f is

not one-to-one and g is not onto.

2. Consider the binary operation on ℤ given by

x ∗ y = x + y + 5

a. Is ∗ commutative? Why or why not? Solution: Yes, since by commutativity of addition in ℤ, y∗x = y+x+5 = x+y+5 = x∗y is true for all x, y ∈ ℤ.

b. Is ∗ associative? Why or why not?

Solution: We have

(x ∗ y) ∗ z = (x + y + 5) ∗ z = (x + y + 5) + z + 5 = x + y + z + 10.

On the other hand,

x ∗ (y ∗ z) = x ∗ (y + z + 5) = x + (y + z + 5) + 5 = x + y + z + 10.

Since these are the same for all x, y, z ∈ ℤ, the operation is associative. c. Is there an identity element for ∗. What is the identity, or why not?

Solution: Yes, e = −5 acts as an identity since x ∗ (−5) = x + (−5) + 5 = x and (−5) ∗ x = (−5) + x + 5 = x for all x ∈ ℤ.

d. Are there any elements of ℤ that have inverses under this operation? What are they, and what are the inverses? Solution: The inverse of x for this operation is the integer y that satisfies x ∗ y = −5 (the identity from part c). Given x, x + y + 5 = −5 when y = −x − 10. so −x − 10 is the inverse of x under this operation.

3. Let A = {x, y, z, w} and let ∗ be the binary operation on A given by the following table:

\begin{matrix}∗ & x & y & z & w \\ x & x & y & z & w \\ y & y & y & w & w \\ z & z & w & z & w \\ w & w & w & w & w \end{matrix}

a. Explain how you can tell this operation is commutative. Solution: The table is symmetric about the “main diagonal” from upper left to lower right. This means that a ∗ b = b ∗ a for all a, b ∈ A, so the operation is commutative.

b. Explain why x is an identity element for ∗.

Solution: From the table, a ∗ x = x ∗ a = a for all a ∈ A. c. Which elements have inverses and what are the inverses?

Solution: x is the only element with an inverse, and the inverse is x itself. d. What is (y ∗ z) ∗ z? Is that the same as y ∗ (z ∗ z)?

Solution: (y ∗ z) ∗ z = w ∗ z = w. That is the same as y ∗ (z ∗ z) = y ∗ z = w. (This, by itself, does not say that ∗ is associative, though. Do you see why not?)

‘B’ Section

1. Let f : A → B and g : B → A be mappings. Prove that if f ∘ g is onto and g ∘ f is one-to-one, then f is one-to-one and onto.

Solution: If f ∘ g is onto, then for every b ∈ B, there is some x ∈ B such that (f ∘ g)(x) = b. But that says f(g(x)) = b, so for every b ∈ B, there is some element in A (namely g(x)) such that f(g(x)) = b. This shows f is onto. For the other part we will prove the contrapositive form – If f is not one-to-one, then g ∘ f is not one-to=one either. If f is not one-to-one, then there exist a ≠ a′ in A such that f(a) = f(a′). But then g(f(a)) = g(f(a′)) too, so g ∘ f is not one-to-one either.

2. Let ∗ be an associative binary operation on a set A and assume there is an identity element e for ∗. If a ∈ A has inverses b_{1} and b_{2}, show that b_{1} = b_{2}. Hint: Consider the “product” (b_{1} ∗ a) ∗ b_{2}.

Solution: If b_{1} is an inverse for ∗, then (b_{1} ∗ a) ∗ b_{2} = e ∗ b_{2} = b_{2}. But on the other hand, if ∗ is associative we also have (b_{1} ∗ a) ∗ b_{2} = b_{1} ∗ (a ∗ b_{2}). Then since b_{2} is also an inverse for a, this equals b_{1} ∗ e = b_{1}. Two things that are equal to the same thing are equal to one another, so b_{1} = b_{2}.

3. Let A be a set and let P(A) be the power set of A as defined in §1 of the text and on Problem Set 1. Let ∗ be the binary operation on P(A) defined by S ∗ T = S ∪ T. Answer the following questions and prove your assertions.

a. Is ∗ associative? Is ∗ commutative? Solution: Yes to both. Commutativity just says S ∗ T = S ∪ T = T ∪ S = T ∗ S and that follows from the definition of set union. Similarly, ∗ is associative since for any subsets S, T, U of A, (S ∗ T) ∗ U = (S ∪ T) ∪ U. This is the set of all elements of A, that are in S, or in T, or in U, which is the same as S ∪ (T ∪ U) = S ∗ (T ∗ U).

b. Is there an identity element in P(A) for this operation?

Solution: Yes, ∅ (the empty subset of A) is an identity element, since ∅ ∪ S = S ∪ ∅ = S for all S ⊆ A.

c. What elements of P(A) have inverses for this operation? Solution: If S = ∅, then let T = ∅ too. Then S ∪ T = ∅ = T ∪ S. Therefore S = ∅ does have an inverse. Now, we claim that this is the only subset of A that does have an inverse for this operation: if S does have an inverse, then S = ∅. We will show the contrapositive form. Let S ≠ ∅. An inverse for S would be a subset T such that S ∪ T = ∅. But S ⊆ S ∪ T for all T, so S ∪ T ≠ ∅. Therefore S = ∅ is the only S that does have an inverse.

d. Make a table like the one in problem 3 of the ‘A’ section for the operation in this problem, when A = {a, b}. List the elements of P(A) in this order on the borders of the table:

∅, {a}, {b}, {a, b}.

Do you notice something? Solution: The table is:

\begin{matrix}∗ & ∅ & \{a\} & \{b\} & \{a, b\} \\ ∅ & ∅ & \{a\} & \{b\} & \{a, b\} \\ \{a\} & \{a\} & \{a\} & \{a, b\} & \{a, b\} \\ \{b\} & \{b\} & \{a, b\} & \{b\} & \{a, b\} \\ \{a, b\} & \{a, b\} & \{a, b\} & \{a, b\} & \{a, b\} \end{matrix}

The thing you should notice is that this table has exactly the same “pattern” as the table from problem 3 in the ‘A’ section. If you replace ∅ ↦ x, {a} ↦ y, {b} ↦ z, {a, b} ↦ w, then you get exactly the other table.

4. Let × : ℝ^{3} × ℝ^{3} → ℝ^{3} be the vector cross product from multivariable calculus (MATH 241). Recall that this operation is defined by the following formula:

(a_{1}, a_{2}, a_{3}) × (b_{1}, b_{2}, b_{3}) = (a_{2}b_{3} − a_{3}b_{2}, −(a_{1}b_{3} − a_{3}b_{1}), a_{1}b_{2} − a_{2}b_{1}).

a. Show that × is not associative and not commutative. Solution: To show an operation does not have these properties, it suffices to find specific cases where they do not hold (negation of a “for all” statement is a “there exists” statement). Let a = (1, 0, 0), b = (0, 1, 0), c = (1, 1, 0) We have a × b = (0, 0, 1), but b × a = (0, 0, −1), so × is not commutative. Also,

(a × b) × c = (0, 0, 1) × (1, 1, 0) = (−1, 1, 0).

But

a × (b × c) = (1, 0, 0) × (0, 0, 1) = (0, −1, 0).

Hence × is not associative. b. Show that × does satisfy the Jacobi identity:

(a × b) × c = a × (b × c) + b × (c × a)

for all a, b, and c in ℝ^{3}. The + in this formula means the vector sum in R^{3}, defined for vectors d = (d_{1}, d_{2}, d_{3}) and e = (e_{1}, e_{2}, e_{3}) by the rule

d + e = (d_{1}, d_{2}, d_{3}) + (e_{1}, e_{2}, e_{3}) = (d_{1} + e_{1}, d_{2} + e_{2}, d_{3} + e_{3}).

Solution: Since this is a “for all” statement, it does not suffice just to give an example where the equation is true. Instead, we must show that the equation holds for all choices of vectors a, b, and c in ℝ^{3}. To see this, we compute as follows:

(a × b) × c = (a_{2}b_{3} − a_{3}b_{2}, −(a_{1}b_{3} − a_{3}b_{1}), a_{1}b_{2} − a_{2}b_{1}) × (c_{1}, c_{2}, c_{3})  (1)
= ((a_{3}b_{1} − a_{1}b_{3})c_{3} − (a_{1}b_{2} − a_{2}b_{1})c_{2}, (a_{3}b_{2} − a_{2}b_{3})c_{3} + (a_{1}b_{2} − a_{2}b_{1})c_{1},
(a_{2}b_{3} − a_{3}b_{2})c_{2} + (a_{1}b_{3} − a_{3}b_{1})c_{1})
= (a_{3}b_{1}c_{3} − a_{1}b_{3}c_{3} − a_{1}b_{2}c_{2} + a_{2}b_{1}c_{2}, a_{3}b_{2}c_{3} − a_{2}b_{3}c_{3} + a_{1}b_{2}c_{1} − a_{2}b_{1}c_{1},
a_{2}b_{3}c_{2} − a_{3}b_{2}c_{2} + a_{1}b_{3}c_{1} − a_{3}b_{1}c_{1}).

Similarly,

a × (b × c) = (a_{1}, a_{2}, a_{3}) × (b_{2}c_{3} − b_{3}c_{2}, −(b_{1}c_{3} − b_{3}c_{1}), b_{1}c_{2} − b_{2}c_{1})  (2)
= (a_{2}(b_{1}c_{2} − b_{2}c_{1}) + a_{3}(b_{1}c_{3} − b_{3}c_{1}), −a_{1}(b_{1}c_{2} − b_{2}c_{1}) + a_{3}(b_{2}c_{3} − b_{3}c_{2}),
− a_{1}(b_{1}c_{3} − b_{3}c_{1}) − a_{2}(b_{2}c_{3} − b_{3}c_{2}))
= (a_{2}b_{1}c_{2} − a_{2}b_{2}c_{1} + a_{3}b_{1}c_{3} − a_{3}b_{3}c_{1}, −a_{1}b_{1}c_{2} + a_{1}b_{2}c_{1} + a_{3}b_{2}c_{3} − a_{3}b_{3}c_{2},
− a_{1}b_{1}c_{3} + a_{1}b_{3}c_{1} − a_{2}b_{2}c_{3} + a_{2}b_{3}c_{2})

and

b × (c × a) = (b_{1}, b_{2}, b_{3}) × (c_{2}a_{3} − c_{3}a_{2}, −(c_{1}a_{3} − c_{3}a_{1}), c_{1}a_{2} − c_{2}a_{1})  (3)
= (b_{2}(c_{1}a_{2} − c_{2}a_{1}) + b_{3}(c_{1}a_{3} − c_{3}a_{1}), −b_{1}(c_{1}a_{2} − c_{2}a_{1}) + b_{3}(c_{2}a_{3} − c_{3}a_{2}),
− b_{1}(c_{1}a_{3} − c_{3}a_{1}) − b_{2}(c_{2}a_{3} − c_{3}a_{2}))
= (a_{2}b_{2}c_{1} − a_{1}b_{2}c_{2} + a_{3}b_{3}c_{1} − a_{1}b_{3}c_{3}, −a_{2}b_{1}c_{1} + a_{1}b_{1}c_{2} + a_{3}b_{3}c_{2} − a_{2}b_{3}c_{3},
− a_{3}b_{1}c_{1} + a_{1}b_{1}c_{3} − a_{3}b_{2}c_{2} + a_{2}b_{2}c_{3})

Adding a × (b × c) + b × (c × a), we see from Eqs. (2), (3) that there are cancellations in every component of the vectors on the right side. What is left is

(a_{2}b_{1}c_{2} + a_{3}b_{1}c_{3} − a_{1}b_{2}c_{2} − a_{1}b_{3}c_{3}, a_{1}b_{2}c_{1} + a_{3}b_{2}c_{3} − a_{2}b_{1}c_{1} − a_{2}b_{3}c_{3},
+ a_{1}b_{3}c_{1} + a_{2}b_{3}c_{2} − a_{3}b_{1}c_{1} − a_{3}b_{2}c_{2}),

which is the same as (1). This proves the Jacobi identity.

c. Extra Credit In a sense, the additional term b × (a × c) on the right in the Jacobi identity measures the failure of associativity. Using that idea, is a × (b × c) ever equal to (a × b) × c when all three of the vectors are nonzero? Explain. Hint: One way to approach this is to think about the geometric conditions on the three vectors under which it will be true that

b × (c × a) = 0.

Solution: One condition under which associativity will hold is this: The cross product of the two vectors c and c is the zero vector (c × a) = (0, 0, 0)) when c and a point along the same line. If that is true then the associative law does hold for those c and a with any b. There are other situations too, for instance if b points along the same line as a × c.