
π
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
−
ππ
22
,