π

x=

–

2

π

x= –

–

2

cardinality 61

instance, it is not possible to place the set of all real

numbers in a list, and so, in some well-defined sense,

the set of real numbers is “more infinite” than the set

of counting numbers or the rationals. Cantor denoted

the cardinality of the set of real numbers c, for “contin-

uum.” We have:

ℵ0< c

In general, the cardinality of one set Ais said to be less

than the cardinality of another set Bif it is possible to

match each element of Awith a unique element of B,

but not vice versa. (Thus Ais equipotent with a proper

subset of Bbut not equipotent with Bitself.) For exam-

ple, the cardinality of {Jane, Lashana, Kabeer}, which we

denote as 3, is less than the cardinality of the set {Rover,

Fido, Spot, Tess, Rue, Tucker, Jet}, which we denote as

7. Although we can match the owners with distinct

dogs, we cannot match the dogs with distinct owners.

An infinite set has the property that it is equipotent

with a proper subset of itself. (This is usually taken as

the definition of what it means for a set to be infinite.)

For example, since the set of integers is equipotent with

the subset of counting numbers, the set of integers is

indeed an infinite set. The graph of the tangent function

y= tan xbetween and shows that each

point on the y-axis is matched with a unique point on

the x-axis in the interval , and vice versa.

Thus the set of all points on the entire number line (the

y-axis) has the same cardinality as the set of all points

just in a finite interval. The set of all real numbers is

indeed an infinite set.

The set of all subsets of a set Ais called the “power

set” of A, denoted P(A).For example, the power set

of {a,b,c,} is the set of eight elements: {Ø,{a},

{b},{c},{a,b},{a,c},{b,c},A}. (In general, the power set of

a set with nelements has 2nelements.) In some sense,

the power set of the set of all counting numbers A=

{1,2,3,…} matches precisely with the set of all real

numbers between zero and one. This can be seen as

follows:

Given a subset Bof counting numbers, let xbe

the real number written as a decimal in base

two whose kth digit is 1 if kbelongs to B, and

0 otherwise. (Thus, for instance, the subset of

odd counting numbers yields the real number x

= .1010101… .) And conversely, given a real

number xbetween zero and one, create a sub-

set Bof counting numbers as dictated by the

placement of 1s in its binary expansion. (Thus,

for instance, the real number x= .010000…

corresponds to the subset {2}.)

(There is one technical difficulty with this correspon-

dence. The numbers 0.01000… and 0.001111…, for

instance, represent the same real number, yet corre-

spond to different subsets of the counting numbers.

Mathematicians have shown that this difficulty can be

obviated.) We have:

P(N) = R

where Ndenotes the set of natural numbers and Rthe

set of real numbers.

The cardinality of the counting numbers is ℵ0, and

the above argument shows that the cardinality of its

power set is c. This suggests, as for finite sets, that the

power set of a set is always of “larger” cardinality than

the original set. Cantor used the following argument to

prove that this is indeed the case:

Let A be a set and consider its power set P(A).

Since every element a of A gives rise to the ele-

ment {a} of P(A), we can certainly match the

elements A with distinct elements of P(A). We

now show, however, that it is not possible to

reverse the process and match the elements of

P(A) with distinct elements of A.

Suppose, to the contrary, we have speci-

fied a way to associate with each subset of A

a distinct element of A. For example, the sub-

set {a,b,c} might be matched with the element

a, and the subset {a,c,e,g,…} with b. Notice

that the first subset contains the element a

with which it is matched, but the second sub-

set does not contain the element bwith which

it is matched.

Let Ube the set of all elements of Athat

are used in the above correspondence, but are

not elements of the subsets to which they are

assigned. (For instance, babove is an element

of U, but ais not.) The subset Umust be

assigned some element of A, call it u. Now ask:

Is ua member of U? The set Ucannot contain

uby the very definition of U.

But in that case usatisfies the definition

of being in U. So by not being in U, u must