Mathematics 243, section 1 – Algebraic Structures Exam 1 – October 8, 2003

Directions

Do all the problems below in the blue exam booklet. Do not place anything you want to have considered for credit on the exam sheet. There are 100 regular points and 10 Extra Credit points.

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. 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).

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. B) (10) Give the converse of the statement. Is the converse true or false? Explain.

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)? B) (10) What is the mapping f ∘ g?

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.) B) (10) For which matrices A is ARA true?

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).

Extra Credit (10) Refer to question IV above. Show that R is a symmetric relation.