Injective, Surjective, and Bijective Functions

Math for CS · Axiom Academy

Injective, Surjective, Bijective Classifying functions by how they map elements Intuition: No two arrows point to the same target. Each output is hit by at most one input. f(x) = 2x is injective (different inputs give different doubles) f(x) = x^2 on is NOT injective ( f(-3) = f(3) = 9 ) f(x) = x^2 on _ 0 IS injective (restricted to non-negatives) Two standard proof strategies: Intuition: Every target gets hit by at least one arrow. No element of B is "left out." f: , f(x) = 2x + 1 is surjective (for any b , solve x = (b-1)/2 ) f: , f(x) = x^2 is NOT surjective (negative numbers are never output) f: _ 0 , f(x) = x^2 IS surjective (with codomain restricted) Bijections establish a perfect pairing between A and B . A bijection from A to B implies |A| = |B| A bijection from a finite set to itself is a permutation Injective: Primary keys in databases (no two rows share the same key) Surjective: A hash function onto its range (every bucket is used) Bijective: Encryption (reversible, one-to-one correspondence between plaintext and ciphertext) This last fact is powerful: for finite sets of equal size, you only need to prove one direction!

This is the written version of the interactive lesson above. See the full Math for CS course.