Bridge to Abstract Mathematics: Mathematical Proof and Structures

8.3 CARDINAL NUMBER OF A SET 283

element x in (0, 1) can be represented by a decimal expansion, say, x =

d,d,d,.... We can guarantee that each such expansion is uniquely

determined by x if we agree to dispense with the usual convention in-

volving infinite strings of nines. It is normally understood that any ter-

minating decimal (like .168) is also represented by a decimal involving

an infinite string of nines (.I67999... in this case), thus providing a

situation in which two different decimal expansions correspond to the

same number. We hereby, and for the course of the current proof,

disallow that understanding by outlawing the use of decimals ending in

an infinite string of nines.

So, let us assume that the elements of (0, 1) have been listed in se-

quence x,, x,, x,,... , where

We now proceed to construct a decimal corresponding to a real number

between 0 and 1 that cannot possibly be on the list. Let us denote this

number y = .b,b,b, ... , where b, = 4, if a,, # 4 and b, = 7, if a,, = 4.

Clearly y # x,, because the decimal expansion of y differs from that of

x, in the first place. In general, let bi = 4, if a,, # 4 and b, = 7, if a,, = 4.

Note that, for each i = 1,2,3,... , we have y # xi, because the decimal

expansion of y differs from that of xi in the ith place. We have con-

structed a new decimal, different from any of those listed, contradicting

the assumption that a listing of all such decimals is possible.

And so we see that there are at least two levels of infinite cardinality,
or two infinite cardinal numbers. It can be proved (see Exercise 1) that
(0, 1) r R, so that the "level of infinity" uncovered in Theorem 3 is actually
that of the real number system. Following convention, let us now agree
to denote the cardinal number of N (and of Z, Q+, and Q) by the symbol
KO (pronounced "aleph-null"; "aleph" is the first letter of the Hebrew al-
phabet). The cardinal number of R [and of (0, l) and C] is denoted by c
and is called the cardinal number of the continuum. We introduce some
standard terminology in the following definition.

DEFINITION 3

A set that is numerically equivalent to N is said to be countably infinite or de-

numerable. Any set that is either finite or countably infinite is said to be count-

able. An infinite set that is not countable is said to be uncountable.

The sets {1,2,3,... , 100), N, Z, Q+, and Q are all countable sets; the
latter four are countably infinite. The sets R, C, and (0, I), and indeed any