A function from set $A$ to set $B$ assigns each element of $A$ to exactly one element of $B$. But not all functions are created equal. There are three special properties a function can have:

Injective (one-to-one)

A function is injective if different inputs always give different outputs. No two elements of $A$ land on the same element of $B$.

$$f(a_1) = f(a_2) \implies a_1 = a_2$$

Example: $f(x) = 2x$ on the integers is injective — if $2a = 2b$, then $a = b$.

Non-example: $f(x) = x^2$ on the integers is not injective — $f(3) = f(-3) = 9$.

Surjective (onto)

A function is surjective if every element of $B$ is hit by at least one element of $A$. Nothing in $B$ is left out.

Example: $f(x) = x + 1$ from $\mathbb{Z}$ to $\mathbb{Z}$ is surjective — every integer is reachable (to hit $n$, start at $n - 1$).

Non-example: $f(x) = x^2$ from $\mathbb{Z}$ to $\mathbb{Z}$ is not surjective — no integer squares to give $3$.

Bijective (both)

A function that is both injective and surjective is called a bijection. It pairs up the elements of $A$ and $B$ perfectly: every element of $A$ goes to exactly one element of $B$, every element of $B$ is hit by exactly one element of $A$.

A bijection has an inverse — you can reverse all the arrows and get a well-defined function from $B$ back to $A$.

Why bijections matter

• Counting: Two sets have the same size if and only if there’s a bijection between them. This even works for infinite sets (Cantor’s insight).
• Permutations: A permutation is a bijection from a set to itself. That’s why every element goes somewhere, no two collide, and the rearrangement can always be undone.
• Isomorphism: In algebra, an isomorphism is a bijection that also preserves structure. Two groups are “the same” if there’s an isomorphism between them.