s
Section 5.4 Functions
401
equivalent Sets
DefInItIonS equivalent SetS and caRdinality
A set S is equivalent to a set T if there exists a bijection f : S S T . Two sets that
are equivalent have the same cardinality.
The notion of equivalent sets allows us to extend our definition of cardinality
from finite to infinite sets. The cardinality of a finite set is the number of elements
in the set. If S is equivalent to T, then all the members of S and T are paired off
by f in a one-to-one correspondence. If S and T are finite sets, this pairing off can
happen only when S and T are the same size. With infinite sets, the idea of size
gets a bit fuzzy, because we can sometimes prove that a given set is equivalent to
what seems to be a smaller set. The cardinality of an infinite set is therefore given
only in a comparative sense; for example, we may say that an infinite set A has (or
does not have) the same cardinality as the set N.
PRaCtiCe 39 Describe a bijection f : Z S N, thus showing that Z is equivalent to N (Z and N have the
same cardinality) even though N ( Z.
■
If we have found a bijection between a set S and N, we have established a one-toone correspondence between the members of S and the nonnegative integers. We
can then name the members of S according to this correspondence, writing s 0 for
the value of S associated with 0, s 1 for the value of S associated with 1, and so on.
Then the list
s 0 , s 1 , s 2 , …
includes all the members of S. Since this list constitutes an enumeration of S, S is
a denumerable set. Conversely, if S is denumerable, then a listing of the members
of S exists and can be used to define a bijection between S and N. Therefore a set
is denumerable if and only if it is equivalent to N.
For finite sets, we know that if S has n elements, then `(S ) has 2
n
elements.
Of course, 2
n
> n, and we cannot find a bijection between a set with n elements
and a set with 2
n
elements. Therefore S and `(S ) are not equivalent. This result is
also true for infinite sets.
theoRem cantoR’S tHeoReM
For any set S, S and `(S ) are not equivalent.
Proof : We will do a proof by contradiction and assume that S and `(S ) are equivalent. Let f be the bijection between S and `(S ). For any member s of S, f (s) is a
member of `(S ), so f (s) is a set containing some members of S, possibly containing s itself. Now we define a set X = 5x [ S 0 x o f (x)6. Because X is a subset of
S, it is an element of `(S ) and therefore must be equal to f ( y) for some y [ S.
Section 5.4 Functions
401
equivalent Sets
DefInItIonS equivalent SetS and caRdinality
A set S is equivalent to a set T if there exists a bijection f : S S T . Two sets that
are equivalent have the same cardinality.
The notion of equivalent sets allows us to extend our definition of cardinality
from finite to infinite sets. The cardinality of a finite set is the number of elements
in the set. If S is equivalent to T, then all the members of S and T are paired off
by f in a one-to-one correspondence. If S and T are finite sets, this pairing off can
happen only when S and T are the same size. With infinite sets, the idea of size
gets a bit fuzzy, because we can sometimes prove that a given set is equivalent to
what seems to be a smaller set. The cardinality of an infinite set is therefore given
only in a comparative sense; for example, we may say that an infinite set A has (or
does not have) the same cardinality as the set N.
PRaCtiCe 39 Describe a bijection f : Z S N, thus showing that Z is equivalent to N (Z and N have the
same cardinality) even though N ( Z.
■
If we have found a bijection between a set S and N, we have established a one-toone correspondence between the members of S and the nonnegative integers. We
can then name the members of S according to this correspondence, writing s 0 for
the value of S associated with 0, s 1 for the value of S associated with 1, and so on.
Then the list
s 0 , s 1 , s 2 , …
includes all the members of S. Since this list constitutes an enumeration of S, S is
a denumerable set. Conversely, if S is denumerable, then a listing of the members
of S exists and can be used to define a bijection between S and N. Therefore a set
is denumerable if and only if it is equivalent to N.
For finite sets, we know that if S has n elements, then `(S ) has 2
n
elements.
Of course, 2
n
> n, and we cannot find a bijection between a set with n elements
and a set with 2
n
elements. Therefore S and `(S ) are not equivalent. This result is
also true for infinite sets.
theoRem cantoR’S tHeoReM
For any set S, S and `(S ) are not equivalent.
Proof : We will do a proof by contradiction and assume that S and `(S ) are equivalent. Let f be the bijection between S and `(S ). For any member s of S, f (s) is a
member of `(S ), so f (s) is a set containing some members of S, possibly containing s itself. Now we define a set X = 5x [ S 0 x o f (x)6. Because X is a subset of
S, it is an element of `(S ) and therefore must be equal to f ( y) for some y [ S.