Math 74 Homework 7Due Monday, October 13thOctober 5, 20081. Recall that for X and Y sets and f : X → Y a function, we defined afunction P (f) : P (X) → P (Y ) by P (f)(A) = {f (a) | a ∈ A}. Let X,Y , and Z be sets and let f : X → Y and g : Y → Z be functions.(a) Show that P (1X) = 1P (X).(b) Show that P (g ◦ f) = P (g) ◦ P (f ).(c) Use (a) and (b) to show that if f : X → Y is a bijection, then sois P (f ) : P (X) → P (Y ).[Note: parts (a) and (b) say that P is what is called a functor.]2. Recall that for each set X and natural number k, we defined the setPk(X) := {A ∈ P (X) | |A| = k}. Let X and Y be sets and letf : X → Y be a bijection.(a) Show that if A ∈ Pk(X), then P (f)(A) ∈ Pk(Y ).(b) Use (a) and problem 1 to show that P (f) restricts to a bijectionfrom Pk(X) to Pk(Y ).(c) Using what we proved in class about An, show that if |X| = n,then |Pk(X)| =nk.3. Let Q stand for the rational numbers (these are real numbers whichcan be written as fractionsabwith a, b ∈ Z and b 6= 0). Define afunction f : N → Q inductively as follows: let f(0) = 1, and for n > 0,let f (n) =6·f(n−1)+5f(n−1)+2. Prove that:(a) For all n ∈ N, f(n) > 0, and(b) For all n ∈ N, f(n) < 5.14. Show thatPnk=0nk= 2nfor all n ∈ N.5. Show that |Pk(An)| = |Pn−k(An)| for all n, k ∈ N with 0 ≤ k ≤ n by:(a) Computing the numbers on both sides of the equation, and(b) Writing down an explicit bijection f : Pk(An) → Pn−k(An).6. Let X be a set, and suppose there is an injective function f : N → X.Prove by contradiction that X is not a finite