Discrete Mathematics for Computer Science

The Pigeon-Hole Principle 257 Since F(xl) = F(x 2 ), F(xl) and F(x 2 ) account for one element in range(F). The elements F(x 3 ) ...

258 CHAPTER 4 Functions Study the example for finding the decimal expansion of the rational number 3/7, as shown in Figure 4.24, ...

The Pigeon-Hole Principle 259 r = 0.4579909909909909... 909909... with repeating block of digits 909. It is easier to work with ...

260 CHAPTER 4 Functions have the same remainder r when divided by m. That is, there are integers c, d, and r such that al +a2 +' ...

The Pigeon-Hole Principle 261 To appreciate these two results, it is helpful to experiment with some subsets of a set, say (1, 2 ...

262 CHAPTER 4 Functions The goal is to find either a four-element increasing subsequence or a four-element de- creasing subseque ...

Exercises 263 Prove that in any class of more than 101 students, at least two must receive the same grade for an exam with grad ...

264 CHAPTER 4 Functions Construct a sequence of 16 integers that has no increasing or decreasing subsequence of five elements. ...

Countable and Uncountable Sets 265 cardinality of finite sets more precisely. In Section 1.5.1, we gave a provisional definition ...

266 CHAPTER 4 Functions Theorem 1. (Properties of Cardinalities) Let X, Y, and Z be sets. (a) IXI < IXI. (b) If IXlI<lIY I ...

Countable and Uncountable Sets 267 JR to JR was given that is not onto, and an onto function from R to R was given that is not 1 ...

268 CHAPTER 4 Functions Now, show that the set of primes is countably infinite. List the primes in increasing order: 2,3,5,7, 11 ...

Countable and Uncountable Sets 269 positive integer. For I p I + q = 1 and 2, we have 0 Ip p +q=l -1 1 Then, for I p + q = 3, we ...

270 CHAPTER 4 Functions Set G(n) to be the nth rational number on the list above. Then, by the discussion above, G : N --* Q is ...

Countable and Uncountable Sets 271 (c) If real numbers x and y have the same decimal expansion, they are equal. (d) If a real nu ...

272 CHAPTER 4 Functions Proof. It is enough to show that (0, 1) is uncountable, since clearly, 1 (0, 1) 1 < I R 1. (See Exerc ...

Exercises 273 States) showed that the continuum hypothesis is neither provable nor disprovable from the standard axioms for set ...

274 CHAPTER 4 Functions (a) Prove that if X and Y are countable sets, so are X U Y, X fl Y, X - Y, and X x Y, (Caution: Countab ...

Chapter Review 275 (b) Show that the set of all infinite sequences of elements of the two element set {o, 1 has the same cardina ...

276 CHAPTER^4 Functions codomain injection collision resolution strategy injective function decreasing mapped to decrypt one-to- ...