8.3 CARDINAL NUMBER OF A SET 279EXAMPLE 3 Prove that the set N of all positive integers is in one-to-one
correspondence with 2N, the set of all positive even integers.Solution The mapping f: N -, 2N given by f(n) = 2n is clearly a bijection
between N and 2N. First, f is one to one, because if f(n,) = f(n,), then
2n, = 2n2 so that n, = n,. Second, f is onto, because if m is an arbitrary
element of 2N, then m is an even integer so that m = 2n for some n E N.
Clearly m = 2n = f (n), so that m E rng f. Since m was arbitrarily chosen
from 2N, we conclude rng f = 2N, as desired. Cl
Example 3 shows that a set can be in one-to-one correspondence with
a proper subset of itself. Focusing for the moment on this phenomenon,
we notice that the example in which it occurred was one in which both
sets involved were infinite, unlike the sets in Examples 1 and 2. In fact,
the underlined property can be taken as the formal definition of an infinite
set.
DEFINITION 2
A set A is said to be infinite if and only if there exists a proper subset B of A such
that B z A. A set that is not infinite is said to be finite.It can be proved (we do not do so in this text) that a nonempty set A is
finite if and only if A is numerically equivalent to the set F,, = (1,2,3,... , n}
for some positive integer n. It is easy to show that 0 is finite, and you are
asked to do so in Exercise 2(a). It can be proved furthermore that, for
positive integers m and n, F, z F, if and only if m = n. Thus we may asso-
ciate with each finite set A a unique nonnegative integer n(A), called the
number of elements in A. If n(A) = k, we say that A hasjnite cardinal num-
ber k. We usually denote a generic finite set A having k elements by such
notation as A = (a,, a,,... , a,}.
In Examples 1 and 2, A and X were both sets with four elements and
were numerically equivalent. All sets in the equivalence class they share
have cardinal number 4. The set B from Example 2 lies in a different equiv-
alence class from A and X and has the cardinal number 3. Once again,
the cardinal number of a finite set is simply the number of elements in that
set, in the usual sense. Two finite sets with same number of elements, in
the usual sense, have the same cardinal number; two finite sets with different
numbers of elements, in the usual sense, have different cardinal numbers.
As seen thus far, the relation of numerical equivalence between sets is
applicable to any two sets, finite or infinite, and in addition, agrees with
the familiar "same number of elements as" relation in the finite case. Let
us reflect for a moment on why this relation "seems right" as a measure of
the comparative sizes of infinite sets. Why, to begin with, is it difficult to
measure the size of an infinite set? The answer lies in a realization of what
we actually do when counting the elements of a finite set S. Using the set
N as our point of reference, we associate with each element of S a unique