270 RELATIONS: FUNCTIONS AND MAPPINGS Chapter 8
for Article 8.3, let us take an informal look at possibilities for injections,
surjections, and bijections between pairs of finite sets.
Suppose A and B are finite sets with n(A) = m and n(B) = n. Suppose
there exists an injection f from A to B; What can we can say about the
relationship between m and n? Every element of A is mapped to an element
of B and there is no "doubling up." Hence B must have at least as many
elements as A; that is, m 5 n. On the other hand, if there exists a surjection
from A to B, then every element of B is mapped into by at least one element
of A. Since again, there is no "doubling up" (the definition of function
forbids it) in this direction, A must have at least as many elements as B.
We conclude rn 2 n in this case. Finally, suppose there is a bijection f
between A and B. Since f is injective, we have m n. Since f is surjective,
m 2 n. The result of our informal considerations is the conclusion m = n.
Two finite sets having rn and n elements are in one-to-one correspondence
if and only if m = n.
IMAGE AND INVERSE IMAGE
DEFINITION 3
Let f: A --+ B be a mapping, and let M c A and N c B. Then we define(a) The image f(M) of M under f by f(M) = {f(m) lm E M}
(b) The inverse image f- '(N) of IV under f by f-'(N) = {x E A1 f(x) E N)Image and inverse image are useful tools for expressing many ideas in ad-
vanced mathematics; we provide several examples of their uses in the exer-
cises (e.g., Exercise 15). But our primary goal now is to introduce you to
the two concepts and to study a number of their elementary properties.
Let us begin with some basic facts. Note first that f (M) and f - '(N) are
sets; f(M) is a subset of B, whereas f -'(N) is a subset of A. Note also that
P(N) is a separate entity from the inverse relation f - and, in particular,
is always defined, even when the relation f - is not a function.
Here is an important and useful fact about f(M). An element y E B is
contained in f(M) if and only if y = f(m) for some rn E M. Hence proofs
of theorems about f (M) usually involve the techniques studied in Article
6.1. It is generally easier to prove theorems whose conclusion involves in-
verse image. If x E A, we-may prove x E f - l(N) simply by proving f (x) E N.
A few other elementary properties of image and inverse image are com-
bined in the following result, most of whose proof is left to you in Exercise
8(a).
THEOREM 4
Let f: A -* B. Then: