Mathematics 243, section 3 – Algebraic Structures Solutions for Exam 1 – September 28, 2012

I. Let A, B, C be any subsets of a universal set U. A) Show that if A ⊆ B, then A ∩ C ⊆ B ∩ C.

Solution: Let x ∈ A ∩ C. Then x ∈ A and x ∈ C. It follows from A ⊆ B and x ∈ A that x ∈ B as well. Hence x ∈ B and x ∈ C, so x ∈ B ∩C. This shows A∩C ⊆ B ∩C.

B) Is it true that A − B = A − C implies B = C? If you think the statement is true, illustrate with a Venn diagram. If you think the statement is false, give a counterexample. Solution: This statement is false because A−B = A∩B′ and A−C = A∩C′. To make a counterexample, we just need to think of sets B and C whose complements intersect A in the same set, but which have different elements. Here’s a simple example. In U = {1, 2, 3}, let A = {1}, B = {2, 3} and C = {2}. Then B′ = {1} = A ∩ B′ and C′ = {1, 3}, so A ∩ C′ = {1}. But clearly B ≠ C.

II. Consider the following statement, where A is a nonempty set. “If f : A → B is an onto mapping, then for all b ∈ B, the set f^{−1}({b}) is nonempty.” Give the contrapositive form of this statement. Are the given statement and its contrapositive true or false? Explain.

Solution: The contrapositive form is: “If for some b ∈ B the set f^{−1}({b}) is empty, then f is not an onto mapping.” This statement and the original form are equivalent and both true. By definition, f is onto if for all b ∈ B, there exist a ∈ A such that f(a) = b. Those a are precisely the elements of f^{−1}({a}), so that set must be nonempty. That is the given form of the statement.

III. Let f, g : Z → Z be the mappings given by

f(x) = \{ \begin{matrix}2x − 1 & if x is even \\ x + 1 & if x is odd \end{matrix} g(x) = \{ \begin{matrix}x & if x is even \\ x + 1 & if x is odd \end{matrix}

A) Let S = {1, 2, 3} and T = {0, 3, 6}. What is g^{−1}(T) ∩ f(S)? Solution: We have f(S) = {f(1), f(2), f(3)} = {2, 3, 4}. Then g^{−1}(T) = {x ∈ Z | g(x) ∈ T } = {0, −1, 6, 5}. (Note that g(x) is even for all x, so there are no x that map to 3 ∈ T.) So g^{−1}(T) ∩ f(S) = ∅.

B) What is the mapping f ∘ g?

Solution: By the observation about g, given in the previous part, in computing (f ∘ g)(x), we never use the part of the definition of f for odd x, and:

(f ∘ g)(x) = \{ \begin{matrix}2x − 1 & if x is even \\ 2(x + 1) − 1 = 2x + 1 & if x is odd \end{matrix}

IV. Consider the binary operation on Z defined by x ∗ y = x + xy + y. A) Is ∗ associative?

Solution: Let x, y, z be any three integers. We have

(x ∗ y) ∗ z = (x + xy + y) ∗ z
= x + xy + y + (x + xy + y)z + z
= x + y + z + xy + xz + yz + xyz

On the other hand, we have

x ∗ (y ∗ z) = x ∗ (y + yz + z)
= x + x(y + yz + z) + y + yz + z
= x + y + z + xy + xz + yz + xyz

These are always the same, so ∗ is associative. B) There is an identity element for ∗. Find it and justify your claim.

Solution: By inspection e = 0 acts as an identity for ∗.

V. (15) Let A ∈ M_{2×2}(Z) be the matrix A = (a_{ij}) defined by a_{ij} = i − j, and let B ∈ M_{3×2}(Z) be the matrix B = (b_{ij}) defined by b_{ij} = i + 2j. Which of the two products AB, BA are defined? Compute the one(s) that are defined.

Solution: By the given information,

A = ( \begin{matrix}0 & −1 \\ 1 & 0 \end{matrix} )  and  B = ( \begin{matrix}3 & 5 \\ 4 & 6 \\ 5 & 7 \end{matrix} )

The sizes match to multiply only for BA and

BA = ( \begin{matrix}5 & −3 \\ 6 & −4 \\ 7 & −5 \end{matrix} )

Extra Credit Which x ∈ Z have inverses for the binary operation ∗ from question IV?

Solution: x has an inverse y when x + xy + y = 0 (using the identity from part B) of IV. This says y = \frac{−x}{x+1}. But this formula gives integer values only when x = 0 and x = −2. The inverse of 0 is 0 and the inverse of −2 is −2.