Bridge to Abstract Mathematics: Mathematical Proof and Structures

8.1 FUNCTIONS AND MAPPINGS 263

We conclude this article with a rather abstract result that relates the con-
cept of one to one to the composition of mappings. This theorem, which
states that one-to-one mappings are precisely those mappings having a sort
of "left-cancellation" property, is typical of a number of statements that can
be proved about mappings and on which we focus in the next article. For
our purposes, the proofs of these theorems are as important as the results
themselves. We will try to strike a balance between proofs detailed in the
text and others left as exercises. You should pay particular attention to
these proofs.

THEOREM 4

Let f: X -, Y be a mapping. Then f is injective if and only if for any set W and

for any mappings g: W -+ X and h: W -+ X such that f 0 g = f 0 h, we have g = h.

Sketch of proof - Assume f is one to one; let W be a set, and let g: W -, X
and h: W -, X be mappings such that f 0 g = f 0 h. We claim that g = h.
Since g and h both have domain W, we need only show g(w) = h(w) for
all w E W. SO let w E W be given. Now, by assumption, f 0 g = f 0 h so
that, in particular, (f 0 g)(w) = (f 0 h)(w). Hence f (g(w)) = f (h(w)). Since
f is one to one, we conclude g(w) = h(w), as desired.
e The proof in this direction is more difficult. We have a hypothesis
whose form is quite complicated and a relatively simple desired conclu-
sion, namely, "f is injective." In Article 6.2 we noted that, in such cir-
cumstances, it is often best to try a proof by contrapositive. In such a
proof we must begin by assuming f is not one to one. If we are to prove
the negation of the hypothesis, we must note carefully what that negation
says. It states that there exists a set W and mappings g: W + X and
h: W -, X such that f 0 g = f 0 h, but g # h. We give several hints from
here, and leave the completion of the proof as an exercise. Since f is not
one to one, there exist distinct elemknts x,, x, E X such that f(x,) =
f (x,). Our job is to produce a set W and distinct mappings g and h of
W into X such that f 0 g = f 0 h. Our key hint is this: Let W = (x,, x,).
In Exercise 10(a) you are to produce the required mappings g and h.
0

Exercises

1. (a) Find the domain and range of each of the relations in Example 1.
   (6) Determine which of the relations in Example 1, Article 7.1, are functions.
   (c) Show that each of the following relations is not a function:

(i) r, = {(x, y) E R x R 14x2 + 9y2 = 108)

*(ii) r, = ((x,y)~R x R(x3y+ xy3 =0)

(iii) r,={(x,y)~RxRly=xf 3)

fiv) r,= {(x,y)eR x Rlx= lyl)

(d) Find all functions having the set (1,2,3) as domain and the set (w, z) as range.