Bridge to Abstract Mathematics: Mathematical Proof and Structures

272 RELATIONS: FUNCTIONS AND MAPPINGS Chapter 8

f - '( f (M)) c M. Let x E f - '( f (M)). Then f (x) E f (M) so that f (x) =

f(m) for some m E M. Since f is one to one, we conclude x = m. Since

m E M and x = m, we conclude x E M, as desired.

(d) This is left as an exercise for you [Exercise 8(c)].

In the example preceding Theorem 5 we noted that M is a proper sub-

set of f - '( f (M)), while f (f - '(N)) is a proper subset of N. In view of (c)

and (d) of Theorem 5, these conclusions are consistent with the evident fact

that the mapping in that example is neither one to one nor onto. Also, in

attempting the proof of the "only if" part of (d), you should keep in mind

that the "only if" part of the proof of (c) employed a clever application of

the specialization technique, namely, an appropriate choice M = {x,) of

a set M.

In our next theorem we consider how image and inverse image interact

with the set operations of union and intersection. As we will see, inverse

image is slightly "better behaved" than image.

THEOREM 6

Let f: A -, 6. Then:

(a) f-'(N, u N,) = f-'(N,) u f-'(N,) and f-.'(~, n N,) =f-l(~,) n f-'(N,)

for any subsets N, and N, of 6.

(b) f(Ml u M,) = f(M,) u f(M,) for any subsets M1 and M, of A.

(c) f(M, n M,) E f(M,) n f(M,) for any subsets M, and M, of A.

(d) f(M, n M,) = f(M,) n f(M,) for any subsets MI and M, of A if and only if f is

injective.

Partial proof Let us consider (c) and the "if" part of (d). The remaining

parts are left to you in Exercise 9. For (c), let MI and M, be subsets

of A and let y E f(M1 n M,). Then y = f(m) for some m E MI n M,.

Since m~ MI, then YE f(M1). Since m~ M,, then YE f(M2). Hence

y E f (M ') n f (M,), as desired.

As for (d), assume f is one to one and let y E f (M ') n f (MJ. To

show y E f(Ml n M,), we must show there exists m E Ml n M2 such

that y = f (m). Now since y E f (M then y = f (m,) for some m, E MI.

Since y E f(M2), then y = f(m,) for some m, E M,. Since f(ml) = y =

f(m,) and since f is one to one, we may conclude m, = m,. Let the de-

sired m equal the common value of m, and m,, noting that y = f(m) and

m~ M1 n M, (since m= m, E M1 and m = m,~ M,), as desired.

In view of (d) of Theorem 6, a mapping for which the containment in
(c) is proper cannot be injective. You should supply an example off, MI,
and M, to illustrate this case. The results in (a) through (c) of Theorem 6
may be generalized to any finite number of sets, using an induction argu-
b ment (Exercise 10) and also to infinite collections of sets indexed by N
I
(Exercise 11).