Further Reading: Functions

Annotated pointers for going deeper on functions, their three properties, composition and inverses, and the standard functions of computer science. Start with the textbook treatments, then follow whichever thread — proof technique, hashing, or the road to cardinality — pulls you. All sources are Tier-1 (canonical) or Tier-2 (a real, named idea you can look up).

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §2.3 — "Functions" The market-standard treatment of domain/codomain/range, one-to-one and onto, composition, inverses, and the floor and ceiling functions, with a large graded exercise bank and many worked classifications. If you want more drill on "prove this is/ isn't injective/surjective," this is the place to go first.

Epp, Discrete Mathematics with Applications (5th ed.), the functions chapter The gentlest careful development of the same material, with unusually explicit attention to the difference between a preimage and an inverse — the §9.2 pitfall this chapter flags — and to proving functions well-defined. Excellent if the formalism still feels slippery.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the chapters on functions, bijections, and counting Freely available. The most CS-flavored presentation: bijections are introduced as a counting and comparison tool (the "bijection rule"), which is exactly the use this book makes of them in Chapter 10. Read it to see why "find a bijection" is a working technique, not a definition you memorize.

On proof technique for functions

Velleman, How to Prove It (3rd ed.), the chapter on functions The standard companion for writing the proofs in this chapter's exercises. Its templates for proving injectivity ("assume $f(a_1)=f(a_2)$…"), surjectivity ("let $b$ be arbitrary…"), and that a function is well-defined match §9.3 line for line. Work its examples before Part B of the exercises.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the functions section Freely available. A free, readable alternative to Rosen with good problems on injections, surjections, and the counting of functions $A \to B$ — directly supporting this chapter's Interleaved exercises (9.27, 9.30).

On hashing and the CS payoff

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), the "Hash Tables" chapter The canonical reference for what §9.6 previews: why hash collisions are unavoidable (the pigeonhole argument made precise), and how chaining and open addressing handle the non-injectivity instead of pretending it away. This is the engineering sequel to case study 1; read it after Chapter 26.

Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.), §1.2.4 — "Integer Functions and Elementary Number Theory" The deep reference for floor, ceiling, and mod as functions: their identities, the division algorithm, and the algebra of $\lfloor \cdot \rfloor$ that powers the mixed-radix codec of case study 2. Dense, but the definitive source for the §9.5 toolkit.

The road ahead: bijections and the sizes of infinity

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the chapter on infinite sets and countability Freely available. This is where §9.3's finite theorem gets its sequel: drop the equal-size hypothesis and use bijections to compare infinite sets. The cleanest free lead-in to Chapter 10 and the "there are more problems than programs" punchline; pairs perfectly with this chapter's Deep Dive exercises (9.30, 9.31).

Sipser, Introduction to the Theory of Computation (3rd ed.), the section on diagonalization and countability The classic treatment of how bijections (and their absence) separate the countable from the uncountable, leading to undecidability. Save it for after Chapter 10, but know it's where the bijection-as-measuring-instrument idea ultimately points.

Suggested order

  1. Read Rosen §2.3 (or Epp's functions chapter) alongside §§9.1–9.4 here for the core definitions and more worked classifications.
  2. Work Velleman's functions chapter before attempting Part B and Part D of the exercises — it drills the exact proof and error-spotting templates.
  3. Read the MIT 6.042 functions/bijections chapter for the CS framing of bijections as a counting tool; it directly motivates Chapter 10.
  4. Save CLRS's hash-table chapter and Knuth §1.2.4 for after Chapters 26 and 23 respectively, when the §9.5–9.6 ideas become full topics.
  5. Read the MIT 6.042 countability chapter last, as a bridge into Chapter 10's surprises.