Bridge to Abstract Mathematics: Mathematical Proof and Structures

8.2 MORE ON FUNCTIONS AND MAPPINGS 269

are both one to one and onto. The latter combination is of sufficient im-
portance to warrant special designation:

DEFINITION 2

A mapping f: A -+ B is called a one-to-one correspondence, or a bijection,

between A and B if and only if it is both one to one and onto.

The two parts of the next result follow from Theorem 2.

COROLLARY

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

(a) If f and g are bijections, then g 0 f is a bijection.

(b) If g 0 f is a bijection, then f is injective and g is surjective.

Formal verification of (a) and (b) are left to you [Exercise 4(a)], as are

the simple proofs of parts (a) and (b) of the next theorem.

THEOREM 3

Given sets A and B.

(a) The identity mapping I,: A -+ A on A is a bijection.

(b) If f: A -P 6 is a bijection, so is f-': B + A.

(c) If f: A + B is a bijection, then f-' 0 f = I, and f 0 f-' = I,.

Proof of (c) Since f is a one-to-one mapping of A onto B, then by (b), f -'

is a bijection from B to A. Hence by (a) of the corollary to Theorem 2,

f - ' 0 f is a bijection from A to A, while f 0 f - ' is a bijection from

B to B. To show f-' 0 f = I,, let x E A; we need only show that

(f - ' 0 f)(x) = x; that is, f - '( f (x)) = x, or the ordered pair (f (x), x) E f - ',

which is equivalent to (x, f (x)) E f, evidently a true statement. To show

f 0 f - ' = I,, let y E B. We claim that f (f - '(y)) = y. For this, we need

only that (f - ' (y), y) E f. The latter is true since (y, f - '(y)) E f - '. The

proofs of parts (a) and (b) are the content of Exercise 6(a).

The idea of a one-to-one correspondence between sets is the basis of the
theory of cardinal numbers, a study of the "relative size" of sets. As we
will see in Article 8.3, this theory is of primary interest in relation to infinite
sets, providing as it does a means of distinguishing between "relatively
small" and "relatively large" infinite sets. The starting point in our brief
glimpse at cardinality of sets will be the concept of numerical equivalence
of sets; in brief, two sets A and B are said to be numerically equivalent if
and only if there exists a bijection from one to the other. In preparation