280 RELATIONS: FUNCTIONS AND MAPPINGS Chapter 8positive integer, starting with 1 and ending with some n. We then designate
n by a symbol such as n(S) or #(S) and call it the number of elements in
S. For a finite set T, we might go through the same process and arrive at
a positive integer m. We then answer the question whether S and T are
the same size by asking whether n equals m.
The problem, of course, in dealing with infinite sets is that we never ex-
haust the elements; there is no positive integer m we can associate with
such a set. So how can we reasonably compare the size of two such sets?
The answer lies in considering how the sizes of finite sets might be com-
pared if no set N is available. Imagine living in a situation, be it a primitive
culture today or perhaps in a prehistoric time, in which systems of naming
(possibly any but the smallest) counting numbers do not exist. How could
we then determine, for instance, whether we have more pegs or more holes
in a Peg-Board? With luck, the most intelligent or creative among us might
think of putting pegs into holes until the supply of one or the other is ex-
hausted. In so doing, we are clearly setting up a one-to-one mapping be-
tween pegs and holes. Only if both pegs and holes run out simultaneously,
could that mapping be onto and would we then judge the two sets to be
of the same size, that is, numerically equivalent. We would not, at this
stage, have in mind any measure of the common size of the two sets (with
counting numbers unavailable); rather, we would have only the knowledge
that the two sets are the same size.
The genius of Cantor consisted partially in his realization that this 2
proach does not depend on exhausting the elements in the set for its effec-
tiveness. Given any two sets, both infinite, one finite and one infinite, or
both finite, we can ask whether they are numerically equivalent, that is,
can we discover a one-to-one correspondence between them or prove that
none exists? This is not to say that the question will be easy to answer in
all cases, or that we won't run into surprises and challenges to our intuition
once this genie is out of the bottle. One such surprise is the possibility of
a one-to-one correspondence between a set S and one of its proper subsets
P. This is (by our formal definition as well as by intuition) out of the ques-
tion in the finite case. In that case, as we try to match elements in P with
those in S, we will clearly run out of elements in P, so that our mapping
is doomed to fail to be onto. This "running out of elements" is precisely
what will not happen in the infinite case. Clearly the inclusion mapping
i,: P --+ S is not the desired one-to-one correspondence (never onto when
P is a proper subset of S), but some other mapping may be. Realizing this
possibility, we must rise above the limitations on our intuition imposed by
overexposure to the simplest and most familiar case, that is, finite sets.
Returning to Example 3, we find a more bizarre situation than this
example suggests. You should verify that the sets S = {n21n E NJ =
(1,4,9,16,25,... ) (of all perfect squares) and M = lo6 N = {lo6, 2 x lo6,
3 x lo6,.. .) (of all integral multiples of "one million") are in one-to-one
I 4 correspondence with N. As sparsely distributed as these sets may be within