Mathematics 242 – Principles of Analysis Selected Solutions – Problem Set 2 September 20, 2004

Section 6/8. Let R be the relation on R^{2}, defined by

(a, b)R(c, d) ⇔ a + d = b + c

First, we show that R is an equivalence relation. First, it is reflexive since a + b = b + a implies (a, b)R(a, b) for all (a, b). Next, it is symmetric, since if (a, b)R(c, d) then a + d = b + c. Hence c + b = d + a so (c, d)R(a, b). Finally, it is transitive since if (a, b)R(c, d) and (c, d)R(e, f) then a + d = b + c and c + f = d + e. These equations imply that a + d + f = b + c + f = b + d + e, so a + f = b + e, which shows (a, b)R(e, f). The equivalence class of (7, 3) is the set of all (x, y) such that (x, y)R(3, 7), or x + 3 = y + 7. This is the line defined by the equation y = x − 7 in the plane.

Section 7/8. Note that the problem asks for functions f : N → N. This means that the domains and ranges must be subsets of the set of natural numbers N = {1, 2, 3, …}.

a) The function

f(n) = \{ \begin{matrix}1 & if n = 1 \\ n − 1 & if n ≥ 2 \end{matrix}

is not injective since f(1) = f(2) = 1. But it is surjective, since every natural number is in its range.

b) An injective, but not surjective function is f(n) = 2n. The range is the set of even natural numbers, so f is not surjective. But f is injective since f(n_{1}) = f(n_{2}) implies 2n_{1} = 2n_{2}, so n_{1} = n_{2}.

c) A function that is neither injective nor surjective is

f(n) = \{ \begin{matrix}n & if n is even \\ 2n & if n is odd \end{matrix}

The range is the set of even natural numbers, so f is not surjective. Moreover, f is not injective, since f(2) = f(1) = 2.

d) f(n) = n is bijective.

Section 7/10.

a) We want an example where f : A → B and f^{−1}(f(C)) ≠ C for some C ⊆ A. Let f(x) = x^{2}, and let C = {1}. We have f^{−1}(f(C)) = {x : x^{2} = 1} = {−1, 1}.

b) We want an example where f(f^{−1}(D)) ≠ D for some subset D ⊂ B. Let f(x) = x^{2} again, and take D = {−1}. Then f^{−1}(D) = {x : x^{2} = −1} = ∅ (as long as we take the domain of f to be the set of real numbers, or a subset of the reals). Hence f(f^{−1}(D)) = ∅ ≠ D.

c) We want an example where f(C_{1} ∩ C_{2}) ≠ f(C_{1}) ∩ f(C_{2}) for subsets C_{1}, C_{2} ⊂ A. Take f(x) = x^{2} again, and let C_{1} = {1}, C_{2} = {−1}. Then f(C_{1} ∩ C_{2}) = ∅, but f(C_{1}) = f(C_{2}) = {1}, so f(C_{1}) ∩ f(C_{2}) = {1}.

Section 7/12. Let f : A → B.

a) We want to show that f injective implies f^{−1}(f(C)) for all subsets C ⊂ A. We know C ⊆ f^{−1}(f(C)) for all mappings. Hence, we must show that f injective implies f^{−1}(f(C)) ⊆ C. Let x ∈ f^{−1}(f(C)). By definition, this means f(x) ∈ f(C), so f(x) = f(x′) for some x′ ∈ C. Since f is injective, this implies x = x′, so x ∈ C. We have shown f^{−1}(f(C)) ⊆ C.

b) Similarly, we want to show that f surjective implies that f(f^{−1}(D)) = D for all D ⊆ B. We know that f(f^{−1}(D)) ⊂ D for all mappings f and all D. So, we need to show that f surjective implies that D ⊆ f(f^{−1}(D)). So let y ∈ D. Since D ⊂ B and f is surjective, this means that y = f(x) for some x ∈ A. But then by definition, this implies that x ∈ f^{−1}(D), and y = f(x) ∈ f(f^{−1}(D)). This shows that D ⊆ f(f^{−1}(D)).

Section 7/13. We assume that f, g are injective. Let g(f(x)) = g(f(x′)). Since g is injective, f(x) = f(x′). But then, since f is injective, x = x′. This shows that the composition g ∘ f is injective also.

Section 7/20.

a) If f : A → B has a left inverse function g and f(x) = f(x′), then x = g(f(x)) = g(f(x′)) = x′. This implies that f is injective. Conversely, suppose f is injective. For each y ∈ B, y is either equal to f(x) for some x ∈ A or else y ≠ f(x) for all x ∈ A. In the first case, since f is injective, there is only one such x, so we can define g(y) = x, where x is the unique element of A for which f(x) = y. If y ≠ f(x) for all x ∈ A, then pick some a ∈ A arbitrarily and define g(y) = a. Doing this we get a function g : B → A, and g(f(x)) = x for all x ∈ A. Hence g is a left inverse of f.

b) If f : A → B has a right inverse function g, then f(g(y)) = y for all y ∈ B. This says that every y ∈ B is in the range of f, so f is surjective. Conversely, if f is surjective, then we must construct a right inverse function g. To do this, since f is surjective, for every y ∈ B, there exists (at least one) x ∈ A such that f(x) = y. For each y, pick any one such x and define g(y) = x. This gives a function g : B → A with f(g(y)) = y for all y ∈ B. Hence g is a right inverse for f.