M417 Homework 3 Spring 2004

Instructions : Be prepared to discuss and present in class on Wed., February 4. Written solutions are due Fri., February 6.

For this problem set, let A and B be sets, and let f : A -> B be a mapping. Recall that we get a mapping, also denoted f, but now mapping from 2^A to 2^B; i.e., f : 2^A -> 2^B, defined for any subset C of A as f(C) = { f(c) : c in C}. The subset f(C) of B is called the image of C. We also get f ^-1 : 2^B -> 2^A, defined for any subset D of B as f ^-1(D) = { c in A : f(c) in D}. The subset f ^-1(D) of A is called the inverse image of D. Be careful not to confuse the two meanings, f : A -> B and f : 2^A -> 2^B, of f; you have to use context to tell which is meant. Note also that f ^-1 has two meanings. It can either mean the inverse function f ^-1 : B -> A, although this exists only when f is bijective, or it can mean the inverse image function f ^-1 : 2^B -> 2^A.

1. • (a) For any subsets C₁,C₂ of A, show that f(C₁\cup C₂) = f(C₁)\cup f(C₂), where \cup means "union".
   • (b) For any subsets D₁,D₂ of B, show that f ^-1(D₁\cup D₂) = f ^-1(D₁)\cup f(D₂).
2. For any subsets C₁,C₂ of A, show that f(C₁\cap C₂) is a subset of f(C₁)\cap f(C₂), where \cap means "intersect". Give an example to show that f(C₁\cap C₂) = f(C₁)\cap f(C₂) can fail.
3. For any subsets D₁,D₂ of B, show that f ^-1(D₁\cap D₂) = f ^-1(D₁)\cap f(D₂).
4. Show that C is a subset of f ^-1(f(C)) for every subset C of A, and that equality always holds if and only if f is injective.
5. Show that f(f ^-1(D)) is a subset of D for every subset D of B, and that equality always holds if and only if f is surjective.