Session 7: Functions, Cardinality & Diagonalization

Overview

Functions as objects in their own right, and the first results about the sizes of infinite sets.

Lecturer

Ali Ibrahim (MECH + Mathematics)

Session Information

• Date and Time: Monday 12 October 2026 — 17:30-19:30
• Place: (to be announced)
• Online Meeting Link
• Session Recording

Core Concepts

• Functions as relations; domains, codomains, and images
• Injectivity, surjectivity, and bijectivity (with proofs in both directions)
• Composition; inverses; left and right inverses and their relationship to injectivity and surjectivity
• Function spaces B^A; functions as first-class objects
• Countability (with proofs): ℕ, ℤ, and ℚ
• Cantor’s diagonalization argument (i.e. ℝ is uncountably infinite); |P(A)| > |A|

Slides

Session 7 Slides: Download PDF

Readings

• Book of Proof (Hammack), Ch. 12, 13, 14

Exercises & Extra Steps

• Practice (not collected): prove f is injective iff it has a left inverse (nonempty domain)
• Practice (not collected): write out both directions of the currying bijection and verify they are mutually inverse
• Practice (not collected): prove there is no surjection A → P(A)

Navigation

• ← Previous: S6: Sets, Relations, Orders, Closures
• Back to Course Overview
• Next: S8: Induction I — Naturals and Strong Induction →

Questions? Reach out on the course WhatsApp!