Mathematics 243, section 3 – Algebraic Structures Problem Set 1 due: September 7, 2012

’A’ Section

1. Let

U = {1, 2, 3, …, 12}
A = {1, 3, 5, 7, 9, 11}
B = {4, 6, 8}
C = {7, 8, 9, 10}

Find each of the following sets:

a. A′ ∩ C

b. A ∪ C′

c. A ∩ (B ∪ C)

d. (A − B) ∪ (B − C)

2. Let S = {a, b, c, d}

a. List all elements of P(S) (the power set)

b. Write out all of the partitions of S.

3. Let A = {1, 2}. For each pair of subsets S, T ⊂ A (including the cases where S or T is ∅ or A itself), define S +T = (S ∪T)−(S ∩T). Make a chart with rows labeled with the possibilities for S, columns labeled with the possibilities for T, and entries showing which subset of A is produced as S + T. (For example, in the row for S = {1} and the column for T = {1, 2}, your chart will contain the entry S + T = {1, 2} − {1} = {2}.)

4. Let A = {1, 2, 3, 4, 5}, B = {a, b, c, d, e} and let f : A → B be defined by f(1) = a, f(2) = e, f(3) = c, f(4) = a, and f(5) = e. Find the following:

a. f(A)

b. f(S) for S = {3, 4, 5} ⊂ A

c. f^{−1}(f(S)) for S = {1, 2, 3} ⊂ A d. f^{−1}(T) for T = {c, d, e} ⊂ B e. f(f^{−1}(T)) for T = {a, b, c} ⊂ B

5. Let P be the set of positive integers and let f : P → P be defined by

f(x) = \begin{cases}3x + 1 & if x is odd \\ x/2 & if x is even \end{cases}

a. Compute f(7), f(f(7)), f(f(f(7))), etc. What happens eventually if you continue this

long enough? Try the same thing with f(9), f(f(9)), f(f(f(9))), etc. b. Show by example that f is not one-to-one. c. Explain why f is onto.

’B’ Section

1. Let A, B be any two subsets of a universal set U.

a. Prove that (A ∩ B)′ = A′ ∪ B′. b. Prove that (A ∪ B) − (A ∩ B) = (A ∩ B′) ∪ (A′ ∩ B).

2. Let A and B be finite sets with |A| = m and |B| = n.

a. Show that if m > n, there are no one-to-one mappings f : A → B. b. Show that if n > m, there are no onto mappings f : A → B. c. Assume n ≥ m. How many different one-to-one mappings f : A → B are there? Prove

your assertion.

3. Refer back to Problem 4 in the ’A’ section for some examples of the patterns described in

this exercise. a. Show that if f is not one-to-one, then there is some S ⊂ A such that f^{−1}(f(S)) ≠ S. b. Conversely, show that if f is one-to-one, then f^{−1}(f(S)) = S for all S ⊂ A. c. Show that if f is not onto, then there is some T ⊂ B such that f(f^{−1}(T)) ≠ T d. Conversely, show that if f is onto, then f(f^{−1}(T)) = T for all T ⊂ B.