Let f X Y be a function Define the following functions F P

Let f : X Y be a function. Define the following functions

F : P(X) P(Y )

G : P(Y ) P(X)

as, for A X and B Y ,

F(A) = {f(x)|x A}

G(B) = {x X|f(x) B}

That is, F(A) is the “image” of A under f, and G(B) is the “inverse image” of B under f.

(a) Prove that, for all subsets A of X, (G F)(A) A.

(b) Find an example of sets X and Y , a function f : X Y , and a subset A of X such that (G F)(A) 6= A. (Hint: try a function f : Z Z which is not 1 1.)

(c) Prove that, for all subsets B of Y , (F G)(B) B. (d) Find an example of sets X and Y , a function f : X Y , and a subset B of Y such that (F G)(B) 6= B. (Hint: try a function f : Z Z which is not onto.)

(e) Prove one of the following.

i. f is 1 1 if and only if F is 1 1.

ii. f is onto if and only if F is onto.

iii. f is 1 1 if and only if G is onto.

iv. f is onto if and only if G is 1 1.

(f) The previous exercise shows that F and G are both invertible if and only if f is. Prove that, if f is invertible, then in fact F and G are inverses of one another.

Solution