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 2A to 2B; i.e., f : 2A -> 2B, 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 : 2B -> 2A, 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 : 2A -> 2B, 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 : 2B -> 2A.
  1. For any subsets C1,C2 of A, show that f(C1\cap C2) is a subset of f(C1)\cap f(C2), where \cap means "intersect". Give an example to show that f(C1\cap C2) = f(C1)\cap f(C2) can fail.
  2. For any subsets D1,D2 of B, show that f -1(D1\cap D2) = f -1(D1)\cap f(D2).
  3. 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.
  4. 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.