Bridge to Abstract Mathematics: Mathematical Proof and Structures

8.2 MORE ON FUNCTIONS AND MAPPINGS 267

assumption, then (g 0 f )(x) = (h 0 f )(x) so that g( f (x)) = h( f (x)). Since

y = f(x), we conclude g(y) = h(y), as desired. We may express the latter

argument in the form of a proof by transitivity by the string g(y) =

g(f(x)) = (g O f )(x) = (h O f )(x) = h(f(4) = 4~)-

e As in the "if" part of the proof of Theorem 4, Article 8.1, we are

motivated by the relatively complex form of the hypothesis to attempt

an indirect proof. Suppose f is not surjective. Our goal is to contradict

the hypothesis by producing a set Z and distinct mappings g and h of

Y into Z such that g 0 f = h 0 f. Now since f is not onto, there exists

yo E Y such that yo 4 rng f. Let xo EX (which we have assumed to be

nonempty) and note that yo # f(xo), since yo4rng f. It is now time

that we define Z, g, and h. Let Z = Y, let g: Y + Z be the identity map-

ping, and let h: Y + Z be defined by the rule h(y) = y if y # yo and h(y) =

f(xo) if y = yo. Since yo # f(xo), then g and h are clearly distinct map-

pings from Y to Z. Finally, if x is any element of X, we have

(g 0 f )(x) = g( f (x)) = f (x) = h( f (x)) = (h 0 f )(x), so that the mappings

g 0 f and h 0 f are identical, as required.

In the string of equations at the conclusion of the proof of Theorem 1,
the key assertion f(x) = h( f(x)) is valid because h is the identity mapping
except at yo. By our construction, we know f(x) does not equal yo for any
x E X SO that our conclusion h( f (x)) = f (x) is warranted.
Theorem 1 asserts that onto mappings are precisely the mappings with
a sort of "right-cancellation" property, analogous to the left-cancellation
property of one-to-one mappings derived in Theorem 4 of Article 8.1.
In the following theorem we combine several results relating the injective
and surjective properties to composition of mappings. As we will see, it is
possible to view the proofs of these properties as applications of Theorem
1 and Theorem 4, Article 8.1.

THEOREM 2

Let f: X 4 Y and g: Y Z, so that g 0 f: X -+ Z. Then:

(a) If f and g are injective, g 0 f is injective.

(b) If f and g are surjective, g 0 f is surjective.

(c) If g 0 f is injective, then f is injective.

(d) If g 0 f is surjective, then g is surjective.

Partial proof Each of these results may be proved directly from the defini-

tions involved. Let us consider (d). To prove g is surjective, let z E Z be

given. We must show there exists y E Y such that g(y) = z. Now since

g 0 f maps X onto Z, by hypothesis, then corresponding to this z (using

specialization), there is an element x E X such that z = (g 0 f)(x). Since

(g 0 f)(x) = g( f(x)) and since f(x) E Y, our choice of the desired y is now

clear. Let y = f(x). We reiterate that y E Y and note that g(y) =

g( f(x)) = z, as desired. The proof of (d) is complete.