402
Relations, Functions, and Matrices
Then y either is or is not a member of X. If y [ X , then by the definition of X,
y o f ( y), but since f ( y) = X , then y o X . On the other hand, if y o X , then since
X = f ( y), y o f ( y), and by the definition of X, y [ X . In either case, there is a
contradiction, and our original assumption is incorrect. Therefore S and `(S ) are
not equivalent. End of Proof
The proof of Cantor’s theorem depends on the nature of set X, which was carefully constructed to provide the crucial contradiction. In this sense, the proof is
similar to the diagonalization method (see Example 23 in Chapter 4) used to prove
the existence of an uncountable set. Indeed, the existence of an uncountable set
can be shown directly from Cantor’s theorem.
exeRcISeS 5.4
1. The accompanying figure represents a function.
5
6
4
7
8
8
9
10
11
a. What is the domain? What is the codomain? What is the range?
b. What is the image of 5? of 8?
c. What are the preimages of 9?
d. Is this an onto function? Is it one-to-one?
example 43
The set N is, of course, a denumerable set. By Cantor’s theorem, the set `(N) is
not equivalent to N and is therefore not a denumerable set, although it is clearly
infinite.
S e c t I o n 5 . 4 Review
technIQueS
• Test whether a given relation is a function.
• Test a function for being one-to-one or onto.
• Find the image of an element under function composition.
• Write permutations of a set in array or cycle
form.
• Count the number of functions, one-to-one functions,
and onto functions from one finite set to another.
maIn IDeaS
• The concept of function, especially bijective
function, is extremely important.
• Composition of functions preserves bijectiveness.
• The inverse function of a bijection is itself a bijection.
• Permutations are bijections on a set.
W
W