Functions: One-to-One and Onto

A function is simply a rule that takes each input and hands back exactly one output, like a vending machine where each button gives you one specific snack. All we're asking in this lesson is two questions about that rule. The formulas look heavy, but they're short sentences: the first says "if two inputs give the same output, they were really the same input" (that's one-to-one, since each output comes from just one input), and the second says "every output $b$ comes from some input $a$" (that's onto, since the function covers all of $B$). Here $f$ is the rule, $a_1$ is an input and $b$ is an output. That's all there is to the symbols.

A function $f: A \to B$ takes each element of the domain $A$ to one element of the codomain $B$. The range is the set of outputs actually hit, which can be smaller than $B$.

• One-to-one (injective): no two inputs share an output. This is only possible if $|A| \le |B|$, since each input needs its own output.
• Onto (surjective): the range is all of $B$. This is only possible if $|A| \ge |B|$, since you need at least one input per output.
• Bijection: both. Then every output comes from exactly one input, so you can run the function backwards, the inverse $f^{-1}$ exists, and $|A| = |B|$.

Bijections are how mathematicians count: to show two sets have the same size, pair their elements up perfectly. Remember the power set from the last lesson? Subsets of $\{1, \dots, n\}$ correspond to bit strings of length $n$ (bit $i$ says whether $i$ is in), which is exactly why there are $2^n$ of each.

Counting functions. Each of the $|A|$ inputs gets to pick any of the $|B|$ outputs on its own, so there are $|B|^{|A|}$ functions. For one-to-one functions, each input has to avoid the outputs already used: the first has $|B|$ choices, the next $|B| - 1$, and so on, giving $|B|(|B| - 1)\cdots$, a falling product with $|A|$ factors.

A common mistake. It's tempting to decide whether $f$ is onto by looking only at the formula. But being onto depends on the codomain too. $f(n) = 2n$ isn't onto the integers, yet the very same rule is onto the even integers. Always ask "onto what?"

Hash functions squeeze many inputs into few outputs, so they can't be one-to-one; encryption has to be a bijection, or some messages couldn't be decrypted.