Mathematics 243, section 1 – Algebraic Structures Solutions for Exam 1 – October 10, 2003

I. A) (15) Show that the following proposition is true for all combinations of truth values

of p, q, r:

(p ⇒ (q ∨ r)) ⇔ ((p∧ ∼ q) ⇒ r)

You may use a truth table or any other applicable method.

Solutions: Method 1 (truth table)

\begin{matrix}p & q & r & q ∨ r & p ⇒ (q ∨ r) & (p∧ ∼ q) & (p∧ ∼ q) ⇒ r \\ T & T & T & T & T & F & T \\ T & T & F & T & T & F & T \\ T & F & T & T & T & T & T \\ T & F & F & F & F & T & F \\ F & T & T & T & T & F & T \\ F & T & F & T & T & F & T \\ F & F & T & T & T & F & T \\ F & F & F & F & T & F & T \end{matrix}

The fifth and last columns are the same so the two propositions have the same truth value and ⇔ will always yield T.

Method 2 (use another logical equivalence p ⇒ q ⇔∼ p ∨ q (twice):

(p ⇒ (q ∨ r)) ⇔∼ p ∨ (q ∨ r)
⇔ (∼ p ∨ q) ∨ r assoc. of ∨
⇔∼ (p∧ ∼ q) ∨ r DeMorgan
⇔ (p∧ ∼ q) ⇒ r

B) (15) Let A, B be any two subsets of a universal set U. Show that (A ∩ B)′ = A′ ∪ B′ (where X′ is the complement of X).

Solution: We will show (A ∩ B)′ = A′ ∪ B′ by showing (A ∩ B)′ ⊆ A′ ∪ B′ and A′ ∪ B′ ⊆ (A ∩ B)′. For the first inclusion, let x ∈ (A ∩ B)′. Then x ∉ A ∩ B by the definition of the complement. By the definition of the intersection and DeMorgan’s Law for negating an “and” statement, this says x ∉ A or x ∉ B. That is, x ∈ A′ or x ∈ B′, so x ∈ A′ ∪ B′ by the definition of union. This shows (A ∩ B)′ ⊆ A′ ∪ B′.

For the other inclusion, let x ∈ A′ ∪ B′. Then x ∈ A′ or x ∈ B′ by the definition of union. As a result, x ∉ A or x ∉ B. Using the same DeMorgan Law as in the previous part, but “in reverse”, x ∉ A ∩ B. Hence x ∈ (A ∩ B)′. This shows A′ ∪ B′ ⊆ (A ∩ B)′.

II. Consider the following statement, where A is a nonempty set. “If f : A → A is a one-to-one mapping, then for all a ∈ A, the set f^{−1}({a}) has at most one element.” A) (10) Give the contrapositive form of this statement.

Solution: If for some a ∈ A the set f^{−1}({a}) has more than one element, then f is not a one-to-one mapping.

B) (10) Give the converse of the statement. Is the converse true or false? Explain.

Solution: Converse: If for all a ∈ A the set f^{−1}({a}) has at most one element, then f is a one-to-one mapping. This statement is true because it says that if f(x) = f(y) = a (so x, y ∈ f^{−1}({a})), then x = y.

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

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

A) (10) Let S = {1, 2, 3} and T = {0, 3, 6}. What is g^{−1}(T) ∩ f(S)?

Solution: f(S) = {0, 2, 5}. g^{−1}(T) = {x|g(x) ∈ T } = {1, 2, 7, 13}. So the intersection is {2}.

B) (10) What is the mapping f ∘ g?

Solution: To find f(g(x)) you must take the parity (i.e. evenness or oddness) of g(x) into account. For instance, if x is even then g(x) = x + 1 is odd. Hence we must use that part of the definition of f: If x is even f(g(x)) = (x + 1) − 1 = x. If x is odd, though, then g(x) can be even or odd. If x is odd and g(x) is odd, then f(g(x)) = \frac{x−3}{2}. If x is odd and g(x) is even, then f(g(x)) = x.

IV. Let M be the set of all 2×2 matrices with integer entries, and write Q = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ∈ M.

Define a relation R on M by saying A R B if and only if the matrix product QAQ is equal to B. A) (5) Show that

( \begin{matrix}4 & 7 \\ 2 & 3 \end{matrix} ) R ( \begin{matrix}3 & 2 \\ 7 & 4 \end{matrix} )

is true. (Hint: The matrix product is associative.)

Solution: Multiplying out the matrix product

QAQ = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}4 & 7 \\ 2 & 3 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}2 & 3 \\ 4 & 7 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}3 & 2 \\ 7 & 4 \end{matrix} ) = B

B) (10) For which matrices A is ARA true?

Solution: The general pattern you can see from the above computation is that if A =

( \begin{matrix}a & b \\ c & d \end{matrix} ), then

QAQ = ( \begin{matrix}d & c \\ b & a \end{matrix} )

This equals A again only when a = d and b = c. The general matrix A for which ARA is true looks like:

A = ( \begin{matrix}a & b \\ b & a \end{matrix} )

where a, b are any integers.

V. (15) Prove by mathematical induction: If n ∈ Z^{+}, then

a + (a + d) + (a + 2d) + ⋯ + (a + (n − 1)d) = \frac{n}{2}(2a + (n − 1)d).

Solution: The base case is n = 1, where the left hand side is just one term a, and the right hand side is \frac{1}{2}(2a + 0d) = a. Hence the base case is true.

Now, assume we know the formula for n = k:

a + (a + d) + (a + 2d) + ⋯ + (a + (k − 1)d) = \frac{k}{2} (2a + (k − 1)d),

consider the sum on the left for n = k + 1, and use the induction hypothesis on the first part of the sum:

a + (a + d) + (a + 2d) + ⋯ + (a + (k − 1)d) + (a + kd) = \frac{k}{2} (2a + (k − 1)d) + (a + kd)

= ka + \frac{k(k − 1)}{2}d + a + kd

= (k + 1)a + \frac{k^{2} − k + 2k}{2} d

= (k + 1)a + \frac{k(k + 1)}{2}d

= \frac{(k + 1)}{2}(2a + kd)

which is what we wanted to show.