Functions

Rules That Assign

A function $f: A \to B$ assigns to each element of the domain $A$ exactly one element of the codomain $B$. It is a special kind of relation — the "exactly one output per input" requirement is what distinguishes a function from a general relation. The image (or range) is the set of outputs actually hit.

Three properties describe how a function maps:

• Injective (one-to-one) — different inputs give different outputs: $f(a) = f(a')$ forces $a = a'$. No two inputs collide.
• Surjective (onto) — every element of the codomain is hit by some input: the image is all of $B$.
• Bijective — both injective and surjective: a perfect one-to-one pairing between $A$ and $B$.

Bijections are special because they are exactly the invertible functions — a bijection $f$ has an inverse $f^{-1}$ that undoes it. They also formalize "same size": two sets have the same cardinality precisely when a bijection exists between them, which is how we compare even infinite sets.

Functions compose: given $f: A \to B$ and $g: B \to C$, the composition $g \circ f: A \to C$ applies $f$ first, then $g$ — note the right-to-left order. Composition is central everywhere in computing, since a program is essentially a composition of functions transforming data.

Common pitfall: mixing up injective and surjective, and misreading composition order. Injective is about inputs not colliding (one-to-one); surjective is about the codomain being fully covered (onto) — a function can be one without the other. And $g \circ f$ means "$f$ then $g$" — the function written on the right is applied first, which looks backwards until you get used to it.

A domain column and codomain column of dots with arrows; a collision (two arrows into one target) flashes in accent to fail injectivity and an unhit target flashes to fail surjectivity.

$$f(a) = f(a') \Rightarrow a = a'$$