278 RELATIONS: FUNCTIONS AND MAPPINGS Chapter 8
Justification for the name "numerical equivalence" is provided by the
following result.
THEOREM 1
z is an equivalence relation on the collection of all subsets of any given universal
set U.Proof (Reflexive) Let A be any set. Clearly A z A, since I,: A -, A is one
to one and onto, by Exercise 6(a)(i), Article 8.2.
(Symmetric) Assume that A and B are sets with A z B. Let f: A -P B
be a bijection. Then f -': B + A is a bijection, by Exercise 6(a)(ii), Ar-
ticle 8.2, so that B r A.
(Transitive) Suppose A, B, and C are sets with A z B and B s C.
Let f: A + B and g: B + C be bijections. We must provide a bijection
h: A + C. Let h = g 0 f. By (a) of the corollary to Theorem 2, Article
8.2, h is a bijection. Hence A z C, as desired. Cl
In view of Theorem 1, we know from Article 7.3 that any collection of
sets is partitioned into equivalence classes, with any two sets in the same
class numerically equivalent and two sets in different classes numerically
nonequivalent. Let us agree to say that two numerically equivalent sets
have the same cardinal number. In subsequent paragraphs we will see that
a cardinal number is essentially a symbol associated with sets in an equiva-
lence class of numerically equivalent sets. Before developing this idea, let
us look at some examples to illustrate numerical equivalence.
EXAMPLE 1 Let A = (1,2,3,4} and X = (a, b, c, d}. The mapping f:
A + X given by f(1) = c, f (2) = a, f (3) = d, f(4) = b, is clearly a bijection
between A and X, so that A r X. 0Note that the function f in Example 1 is by no means the only bijection
between A and X; in fact (recalling the topic of permutations from Article
IS), there are as many bijections between A and X as there are arrange-
ments of the letters a, b, c, and d; that is, P(4,4) = 4! = 24.
EXAMPLE 2 Let B = (1,2, 3) and X = (a, b, c, d}. Then there are precisely
P(4,3) = 4! = 24 one-to-one mappings of B into X. One example is
f (1) = a, f (2) = b, f (3) = c. Clearly none of these mappings is onto. No
bijection exists between B and X, so that B $ X. 0You should verify (by an indirect argument) that the sets A and B in
the preceding examples are not numerically equivalent. (What conclusion
could we derive if it were true that B r A?) This result is satisfying to our
intuition since B, after all, is a proper subset of A and, surely, it would seem,
no set should be in one-to-one correspondence with a proper subset of itself.
If you agree with the statement following "surely" you will be enlightened,
although perhaps slightly disoriented, by the next result.