Functions

A coat check gives every coat a ticket number. That’s a function: each coat gets exactly one number. A good coat check also never gives two coats the same number (that would end badly at closing time). In math words, its function is one-to-one.

Now picture a theater where every seat must be filled for a show to start. Assigning people to seats so that no seat is empty is an onto function. Do both at once (everyone gets their own seat, and no seat is empty) and you have a bijection: a perfect pairing.

These ideas sound abstract, but you use them all the time. A password hash should be “almost one-to-one” (F04 lesson 15). A database key must be one-to-one, or two people get each other’s records. And bijections are how we know two sets have the same size without counting them, which leads to the surprising lesson about infinity coming up next.

The real words

• A function $f: A \to B$ assigns to every $a \in A$ exactly one $f(a) \in B$.
  • $A$ is the domain, $B$ the codomain. The range (or image) is the set of outputs actually used.
  • Every input needs an arrow, and no input may have two. A Python dictionary is a function from its keys to its values.
• One-to-one and onto:
  • Injective (one-to-one): $f(a_1) = f(a_2)$ only when $a_1 = a_2$. No output is shared. Then $|A| \le |B|$.
  • Surjective (onto): every $b \in B$ equals $f(a)$ for some $a$. The range is all of $B$. Then $|A| \ge |B|$.
• A bijection is both. Then $|A| = |B|$, and it can be reversed: the inverse $f^{-1}: B \to A$ sends each output back to its input.
• Composition: $(g \circ f)(x) = g(f(x))$, “do $f$, then $g$”. Exactly like calling one Python function on the result of another.