Fill-in-the-blanks 1. Let f : X -> Y and g : Y -> Z be functions. Complete the following proofs about surjectivity of the function composition g ◦ f : X -> Z. Claim (a): If both f and g are surjective, then g ◦f is also surjective. Proof of (a). Assume that f : X -> Y and g : Y -> Z are surjective. To prove surjectivity of g ◦f, we must show that for every z in Z there exists x in such that (g ◦ f)(x) = z. So let z in Z. Then by surjectivity of , there exists some y in Y such that g(y) = z. Fix some such y. Then by surjectivity of f : X -> Y , there exists some x in such that f(x) = y. For such an x, we have (g ◦ f)(x) def = g f(x) = g = , and we have thus proven the surjectivity of g ◦ f : X -> Z. Claim (b): If g ◦ f is surjective, then g is also surjective. Proof of (b). Assume g ◦ f : X -> Z is surjective. To prove the surjectivity of g : Y -> Z, we must show that for every z in Z there exists a such that g = z. So let z in Z. By surjectivity of g ◦ f : X -> Z, there exists some x in X such that (g ◦ f)(x) = z. Fix some such x. If we then set y = f(x), then we have g = = (g ◦ f)(x) = z , and we have thus proven the surjectivity of g : Y -> Z. The following are not a part of this exercise, but they are important to understand. (c) Assuming g ◦ f is surjective, is it possible to prove that f is also surjective? What about the corresponding statements about injectivity? (a’) Assuming f and g are injective, is it possible to prove that g ◦ f is injective? (b’) Assuming g ◦ f is injective, is it possible to prove that g is injective? (c’) Assuming g ◦ f is injective, is it possible to prove that f is inject Fill-in-the-blanks 2. Complete the following proof of the squeeze theorem (sandwich principle, lemma of two policemen). Claim: If three sequences (an)n in N, (bn)n in N, and (cn)n in N of real numbers satisfy an <= bn <= cn starting from some index, and if lim n->\infty an = lim n->\infty cn = \beta in R, then the sequence (bn)n in N also converges, and limn->\infty bn = \beta . Proof. Since the beginning of a sequence affects neither the convergence nor the limit of the sequence, we may assume that an <= bn <= cn holds for all n in N. We will show that limn->\infty bn = \beta . Let \epsi > 0. We must show that |bn − \beta | < \epsi from some index on. Idea: the expression bn − \beta has to be estimated from both directions; one relying on the sequence (an)n in N, and the other on the sequence (cn)n in N. (Draw a figure!) Since limn->\infty an = \beta and \epsi > 0, there exists an n 0 \epsi in N such that for all n >= n 0 \epsi . Since limn->\infty cn = \beta and \epsi > 0, there exists an n 00 \epsi in N such that for all . Now choose n\epsi = . With this choice, for any n >= n\epsi we have n >= n 0 \epsi . Therefore we get \beta − bn <= \beta − an <= |\beta − an| < (the leftmost inequality holds by virtue of the assumption an <= bn). Similarly, for n >= n\epsi we have n >= n 00 \epsi , so we get bn − \beta <= cn − \beta <= < (the leftmost inequality holds by virtue of the assumption bn <= cn). The above inequalities imply that |bn − \beta | < for all n >= n\epsi . We have thus proved the claim.