Chapter Review 275(b) Show that the set of all infinite sequences of elements of the two element set {o, 1
has the same cardinality as P(N).
(c) Challenge: Show that the set of all infinite sequences of elements of N has the
same cardinality as 'P(N).rnChapter Review
Functions describe the transition from input information to output information. Functions
are a special class of relations, and they can be defined and studied in that context. Func-
tions can also be defined either as sets or as rules of correspondence. In addition, the rules
of correspondence can either give the value of the function directly from the input value
or recursively, in terms of other values of the function. There are even rules of corre-
spondence that do not always give an output value for each possible input value. These
correspondences are called partial function. Partial functions are especially important in
describing the behavior of programs.
Two key properties that a function may possess are being 1-1 and/or being onto. The
notion of functions being 1-1 and onto leads to two major topics. The first focuses on
functions that are 1-1 or measures how far a function is from being 1-1. The principles
introduced are the Pigeon-Hole Principle and the Generalized Pigeon-Hole Principle. Op-
erations such as composition and taking inverses are also defined on functions, and the class
of function called sequences is described formally. The second topic deals with counting
the elements of a set. The notion of cardinality makes precise what it means for two sets to
have the same number of elements. Infinite sets, such as Q and R, are shown to have dif-
ferent number of elements. Various relationships between other infinite sets are explored.
Two important tools for studying the cardinality of a set are Cantor's first diagonal argu-
ment and Cantor's second diagonal argument. The class of function called sequences are
described formally.
Among the applications discussed with this material is a characterization of the prop-
erties of inverse and of composition of functions when the properties of the functions are
given. It is also shown how boolean functions can be realized by combinatorial networks.
The Pigeon-Hole Principle and the Generalized Pigeon-Hole Principle can be applied in
such diverse settings as determining what competitive schedules must look like and guaran-
teeing that a set of integers contains at least two with a common divisor. Rational numbers
are shown to have repeating decimal representations. Both N, Z, and Q are shown to have
the same number of elements.4.10.1 Terms, Theorems, and Algorithms
4.1 SummaryTERMS1-1 and onto function bijective function
1-1 correspondence binary function
bijection ceiling