282 RELATIONS: FUNCTIONS AND MAPPINGS Chapter 80 f(i) -f(i) f(2) -f(2) fi3) -f(3) f(4)
Figure 8.7 Write down an explicit rule defining the
correspondence pictured here.rationals, lined up as in Figure 8.6a, we simply skip over any quotient
of integers corresponding to a rational number that has already been
accounted for. Thus we have f (1) = 1, f (2) = 3, f (3) = 2, f (4) = 4, f (5) =
3, f(6) = i, and so on. Note that we have skipped over $ in defining
f(5), since $ = 1, and 1 has already been accounted for, having been first
in the array.
With the equivalence of N and Q+ established, we may conclude
N E Q by showing Q+ z Q (What property of z is the key to this con-
clusion?). This we may do as follows. Let Q + = { f (1), f (2), f (3),... }
and let us set up the correspondence in Figure 8.7. This mapping is
clearly onto since every nonzero rational number is either equal to or
is the negative of a positive rational number.At this point, you may think you have figured out all there is to know
about the equivalence classes induced by numerical equivalence. First, we
know already that there are equivalence classes (consisting of all the n ele-
ment subsets of U) corresponding to each positive integer n. We should
represent each such class by the appropriate n and call n the cardinal num-
ber of any set in its class. Second, based on Theorem 2, you may be ready
to conclude that any two infinite sets are numerically equivalent, and in
particular, are equivalent to N, as we have just witnessed for Q. We might
then say that all such sets have cardinal number oo and be done with it,/
secure in the belief that the list 1,2,3,... , oo accounts for all possible
equivalence classes of numerically equivalent sets, or in other words, all
possible cardinal numbers. Those who believe all of this are only half-right.
The statements about finite sets are correct, as we had seen earlier; every-
thing else ("Second, you may.. .") is a gross oversimplification. Assuming
U is sufficiently large, there are infinite sets in U with cardinality different
from that of N. A familiar example of such a set is provided in our next
result.
THEOREM 3
The open unit interval (0, 1) is not numerically equivalent to N.
Proof (Cantor) In fact, we will show that every one-to-one mapping of N
into (0, 1) must fail to be onto; that is, every listing of the elements of
(0, 1) must leave out some element of (0, 1). It is a known fact that every