Bijections

Set Theory · Axiom Academy

Perfect pairing: one-to-one correspondences and invertible functions A function f: A → B is a bijection (or bijective function ) if it is both injective and surjective: Injective: Different inputs produce different outputs Surjective: Every element of B is hit by some input Bijective: Both properties hold—a perfect one-to-one correspondence Alternative characterization: f is bijective if every element of B has exactly one pre-image in A. This means bijections create a perfect "matching" between sets—no element is left out, and no element is counted twice. 2. Inverse Functions and Bijections The most important property of bijections: they have inverses! Theorem: A function f: A → B has an inverse function f⁻¹: B → A if and only if f is bijective. The inverse f⁻¹ satisfies: f⁻¹(f(a)) = a for all a ∈ A, and f(f⁻¹(b)) = b for all b ∈ B. Why both properties are needed: Injectivity ensures f⁻¹ is well-defined (no ambiguity about which input produced an output) Surjectivity ensures f⁻¹ has domain B (every element of B can be "reversed") Example: f(x) = 2x + 3 is bijective on ℝ, with inverse f⁻¹(y) = (y - 3)/2 3. Bijections and Set Cardinality Bijections provide the foundation for comparing sizes of sets: Definition: Two sets A and B have the same cardinality (written |A| = |B|) if there exists a bijection f: A → B. For finite sets, this matches our intuitive notion of "same size"—a bijection pairs up elements perfectly. For infinite sets, bijections reveal surprising equivalences:

This is the written version of the interactive lesson above. See the full Set Theory course.