Mathematics 243, section 3 – Algebraic Structures Solutions for 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 Solution: A′ is the complement of A in the universal set U, so A′ = {2, 4, 6, 8, 10}, and A′ ∩ C = {8, 10}.

b. A ∪ C′ Solution: Similarly, C′ = {1, 2, 3, 4, 5, 6, 11, 12} so A ∪ C′ = {1, 2, 3, 4, 5, 6, 7, 9, 11, 12} = U − {8, 10}.

c. A ∩ (B ∪ C)

Solution: B ∪ C = {4, 6, 7, 8, 9, 10} so A ∩ (B ∪ C) = {7, 9}. d. (A − B) ∪ (B − C)

Solution: A − B = {1, 3, 5, 7, 9, 11} = A since A ∩ B = ∅. Then, B − C = {4, 6}. So (A − B) ∪ (B − C) = {1, 3, 4, 5, 6, 7, 9, 11}.

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

a. List all elements of P(S) (the power set) Solution: There are 2^{4} = 16 subsets of S:

one of cardinality 0 : ∅
four of cardinality 1 : {a}, {b}, {c}, {d}
six of cardinality 2 : {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}
four of cardinality 3 : {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}
one of cardinality 4 : {a, b, c, d}

The power set P(S) is the set whose elements are these 16 subsets. b. Write out all of the partitions of S.

Solution: A partition is a collection of nonempty, pairwise disjoint subsets whose union is S. Up to the labeling of the individual subsets the possible partitions are

cardinalities 1,1,1,1 : {a}, {b}, {c}, {d}
cardinalities 1,1,2 : {a}, {b}, {c, d}

{a}, {c}, {b, d} {a}, {d}, {b, c} {b}, {c}, {a, d} {b}, {d}, {a, c} {c}, {d}, {a, b}

cardinalities 1,3 : {a}, {b, c, d}

{b}, {a, c, d} {c}, {a, b, d} {d}, {a, b, c}

cardinalities 2,2 : {a, b}, {c, d}

{a, c}, {b, d} {a, d}, {b, c}

cardinality 4 : {a, b, c, d}.

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

Solution: The table looks like this:

\begin{matrix}+ & ∅ & \{1\} & \{2\} & \{1, 2\} \\ ∅ & ∅ & \{1\} & \{2\} & \{1, 2\} \\ \{1\} & \{1\} & ∅ & \{1, 2\} & \{2\} \\ \{2\} & \{2\} & \{1, 2\} & ∅ & \{1\} \\ \{1, 2\} & \{1, 2\} & \{2\} & \{1\} & ∅ \end{matrix}

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)

Solution: f(A) = {a, c, e}. b. f(S) for S = {3, 4, 5} ⊂ A

Solution: f(S) = {f(3), f(4), f(5)} = {a, c, e} c. f^{−1}(f(S)) for S = {1, 2, 3} ⊂ A

Solution: We have f(S) = {a, c, e}, and f^{−1}(f(S)) = {1, 2, 3, 4, 5} since every image under f is contained in the set {a, c, e}.

d. f^{−1}(T) for T = {c, d, e} ⊂ B

Solution: f^{−1}(T) = {x ∈ A | f(x) ∈ T } = {2, 3, 5}.

e. f(f^{−1}(T)) for T = {a, b, c} ⊂ B

Solution: Since T = {a, b, c}, f^{−1}(T) = {1, 3, 4}. So f(f^{−1}(T)) = {f(1), f(3), f(4)} = {a, c}.

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.

Solution: To simplify the notation, we write → for the result of applying f. For instance, since 7 is odd, 7 → 3 · 7 + 1 = 22. Then since 22 is even, 22 → 11. Following this until something “interesting” happens:

7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 →
10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 ⋯

Note at this point the values will repeat the 4 → 2 → 1 cycle forever. Starting from 9, we have

9 → 28 → 14 → 7 → ⋯

so this continues with the pattern for f(7)–it also lands in the 4 → 2 → 1 → 4 cycle eventually. Comment: It is an open question whether that the same behavior will happen starting from any positive n. This means that there are lots of people who have worked on this but they have not been able to solve this problem yet. (Yes, there are unsolved problems in mathematics! A part of what mathematics professors do is to try to find solutions to these unsolved problems – this is what it means to do research in mathematics.) In this case, if you can prove that, starting from any n ∈ P, the function f always takes you into the 4 → 2 → 1 → 4 cycle eventually, you’ll be rich and famous (well famous, anyway!)

b. Show by example that f is not one-to-one.

Solution: For instance, f(1) = 4 and f(8) = 4. Since 1 ≠ 8, this says f is not one-to-one. (There are infinitely many other cases like this as well, one for each odd positive integer. For instance, f(3) = 10 = f(20), etc. c. Explain why f is onto.

Solution: f is an onto mapping since if n ∈ P is any positive integer, f(x) = n if x = 2n. Note that 2n is always an even number so that f(2n) = (2n)/2 = n.

’B’ Section

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

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

Solution: Let x ∈ (A ∩ B)′. This means that x ∉ A ∩ B, so x ∉ A or x ∉ B. But by definition of set union that implies x ∈ A′ ∪ B′. Hence (A ∩ B)′ ⊆ A′ ∪ B′. Conversely, suppose x ∈ A′ ∪ B′. Then x ∈ A′ or x ∈ B′, or equivalently: x ∉ A or x ∉ B. This implies that x ∉ A ∩ B so x ∈ (A ∩ B)′. We have A′ ∪ B′ ⊆ (A ∩ B)′ Because of the two containments, A′ ∪ B′ = (A ∩ B)′ follows.

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

Solution: By definition of the set difference, (A ∪ B) − (A ∩ B) = (A ∪ B) ∩ (A ∩ B)′. By part a of this problem, this is the same as (A ∪ B) ∩ (A′ ∪ B′). By the distributive laws for intersection over union and commutative laws for intersections, we have

(A ∪ B) ∩ (A′ ∪ B′) = (A ∩ A′) ∪ (B ∩ A′) ∪ (B ∩ A′) ∪ (B ∩ B′)
= ∅ ∪ (A′ ∩ B) ∪ (A ∩ B′) ∪ ∅
= (A′ ∩ B) ∪ (A ∩ B′).

This is what we wanted to show.

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.

Solution: Write the elements in A as A = {a_{1}, a_{2}, …, a_{m}}. So B must contain the set {f(a_{1}), …, f(a_{m})}. But these cannot be distinct in B since B contains only n < m distinct elements. Therefore f(a_{i}) = f(a_{j}) for some i ≠ j and as a result f is not one-to-one.

b. Show that if n > m, there are no onto mappings f : A → B.

Solution: Write A = {a_{1}, …, a_{m}} again. By definition, f(A) = {f(a_{1}), …, f(a_{m})}. There are at most m distinct elements of this set, and n > m elements in B. There is no way f(A) = B can hold since there are at least n − m elements of B that are not images of elements in A. Therefore, f is not onto.

c. Assume n ≥ m. How many different one-to-one mappings f : A → B are there? Prove your assertion.

Solution: Write A = {a_{1}, …, a_{m}} again. There are n different possibilities for f(a_{1}). Once that element of B is determined, there are n − 1 different possibilities for f(a_{2}) ≠ f(a_{1}), and therefore n · (n − 1) possible choices for those two images. Then once f(a_{1}), f(a_{2}) are determined, there are n − 2 possibilities for f(a_{3}) ≠ f(a_{1}), f(a_{2}), and n(n − 1)(n − 2) possible choices for those three images. Continuing in the same way, we see there are

n(n − 1)(n − 2) · · · · · (n − (m − 1))

different one-to-one mappings f : A → B.

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.

Solution: If f is not one-to-one, there are a_{1} ≠ a_{2} ∈ A such that f(a_{1}) = f(a_{2}) = b. So let S = {a_{1}}. We have f(S) = {b}, but now a_{1}, a_{2} ∈ f^{−1}(f(S)), so 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.

Solution: It is true by definition that S ⊆ f^{−1}(f(S)) for all subsets S ⊆ A. So what we must show is that if f is one-to-one, then f^{−1}(f(S)) ⊆ S, since that will then imply f^{−1}(f(S)) = S. Suppose t ∈ f^{−1}(f(S)). Then by definition, this means that f(t) = f(s) for some s ∈ S. Since f is assumed to be one-to-one, this implies s = t, so t ∈ S. This shows that f^{−1}(f(S)) ⊆ S, and this concludes the proof.

c. Show that if f is not onto, then there is some T ⊆ B such that f(f^{−1}(T)) ≠ T.

Solution: If f is not onto, there is some y ∈ B such that y ≠ f(x) for all x ∈ A. Take T = {y}. Then f^{−1}(T) = ∅ and f(f^{−1}(T)) = ∅, so f(f^{−1}(T)) ≠ T.

d. Conversely, show that if f is onto, then f(f^{−1}(T)) = T for all T ⊆ B.

Solution: By the definitions, f(f^{−1}(T)) ⊆ T holds for all T ⊆ B. So what we must show is that if f is onto, then T ⊆ f(f^{−1}(T)) for all T, since that will imply f(f^{−1}(T)) = T. So assuming that f is onto, consider any subset T. For each y ∈ T, there exists x ∈ A such that f(x) = y, and each of these x is in f^{−1}(T). But then, f(f^{−1}(T)) contains every y in T, since we have f(x) = y for some x ∈ f^{−1}(T). It follows that T ⊆ f(f^{−1}(T)). This concludes the proof.