Contents
xi
CHAPTER 4
Functions
219
4.1 Basic Definitions 219
4.1.1 Functions as Rules 221
4.1.2 Functions as Sets 222
4.1.3 Recursively Defined Functions 224
4.1.4 Graphs of Functions 225
4.1.5 Equality of Functions 226
4.1.6 Restrictions of Functions 228
4.1.7 Partial Functions 229
4.1.8 1-1 and Onto Functions 231
4.1.9 Increasing and Decreasing Functions 237
4.2 Exercises 239
4.3 Operations on Functions 243
4.3.1 Composition of Functions 243
4.3.2 Inverses of Functions 245
4.3.3 Other Operations on Functions 248
4.4 Sequences and Subsequences 248
4.5 Exercises 251
4.6 The Pigeon-Hole Principle 253
4.6.1 k to 1 Functions 254
4.6.2 Proofs of the Pigeon-Hole Principle 255
4.6.3 Application: Decimal Expansion of Rational Numbers 257
4.6.4 Application: Problems with Divisors and Schedules 259
4.6.5 Application: Two Combinatorial Results 260
4.7 Exercises 262
4.8 Countable and Uncountable Sets 264
4.8.1 Countably Infinite Sets 266
4.8.2 Cantor's First Diagonal Argument 268
4.8.3 Uncountable Sets and Cantor's Second Diagonal Argument 270
4.8.4 Cardinalities of Power Sets 273
4.9 Exercises 273