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

 (a) For any subsets C_{1},C_{2} of A, show that f(C_{1}\cup C_{2}) = f(C_{1})\cup f(C_{2}),
where \cup means "union".
 (b) For any subsets D_{1},D_{2} of B, show that f^{ 1}(D_{1}\cup D_{2}) = f^{ 1}(D_{1})\cup f(D_{2}).
 For any subsets C_{1},C_{2} of A, show that f(C_{1}\cap C_{2}) is a subset of f(C_{1})\cap f(C_{2}),
where \cap means "intersect".
Give an example to show that f(C_{1}\cap C_{2}) = f(C_{1})\cap f(C_{2}) can fail.
 For any subsets D_{1},D_{2} of B, show that f^{ 1}(D_{1}\cap D_{2}) = f^{ 1}(D_{1})\cap f(D_{2}).
 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.
 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.