156 Chapter 13
has constructed a specific real number that is not algebraic. So Cantor’s proof is construc-
tive. Furthermore, by simply varying the manner of choosing the diagonal real (by using
different digits than we had chosen before, or by slightly changing the enumeration of the
algebraic numbers) we can construct an enormous variety of specific distinct transcenden-
tal numbers.
13.5 Equinumerosity
Let us now develop a little more of Cantor’s theory of the transfinite. One of the funda-
mental concepts is that of the equinumerosity relation, aimed at expressing the idea that
two sets have the same size. What does it mean precisely to say that two sets have the same
size?
Definition 114. We say that sets A and B are equinumerous, written A B, if they can be
placed into one-to-one correspondence with each other. In other words, A B if there is a
bijection f : A → B, a one-to-one onto function from A to B.
There is a natural partial order underlying equinumerosity, namely, A B if there is a
one-to-one function f : A → B, not necessarily onto. In exercises 13.9 and 13.10, the
reader will verify that the equinumerosity relation is an equivalence relation and that
is a partial preorder.
The equinumerosity concept is evidently a more primitive notion of “same size” than the
idea of counting the number of elements of the set. We can see easily without counting,
for example, that the set of people in the classroom has the same size as the set of noses
in the classroom, simply because every person in the room has one nose and there are not
any extra noses. So we have constructed a one-to-one correspondence between the set of
people and the set of noses, and we have done so without counting these sets.
The equinumerosity concept provides a notion of same size that is fruitfully applicable
even to infinite sets.
Theorem 115. Every countable set is either finite or equinumerous with the whole set of
natural numbers N.
Proof. Since every countable set is equinumerous with a set of natural numbers, it suffices
to consider only sets of natural numbers A ⊆ N.IfA is infinite, then we may associate the
number n with the nth element of A, and this will be a one-to-one correspondence between
N and A, and so A is equinumerous with N. So every set of natural numbers is either finite
or equinumerous with the whole set of natural numbers.
We say that a set is countably infinite if it is countable and infinite, which by theorem 115,
is equivalent to being equinumerous with N. Let us now push a little harder with Cantor’s
idea, extending higher into the transfinite realm.