Relations and Functions

A relation pairs things up; a function is the disciplined kind where every input gets exactly one output. Models are functions, so the rules matter.

A function sends every input dot to exactly one output dot while a mere relation may split or strand inputs, and only the bijective pairing runs backwards

Why Does This Exist?

Every model you train is a function: features go in, a prediction comes out, and the same input always gives the same output. That last clause sounds trivial until a pipeline violates it, say a lookup that returns two different labels for one key, or a "function" that crashes on inputs nobody fenced out. The mathematics of relations and functions exists to say exactly which pairings behave and which do not.

A relation between sets $A$ and $B$ is any collection of pairs $(a, b)$ . No discipline required: one input can pair with many outputs, or with none. A function $f: A \to B$ is a relation with two rules: every $a$ in $A$ appears in some pair (totality), and no $a$ appears in two pairs with different outputs (single-valuedness). $A$ is the domain, $B$ the codomain, and the outputs actually reached form the range.

Why should you care which pairing you hold? Invertibility, the thing behind normalising flows, decoders and every "run it backwards" trick, needs a bijection: a function that is both injective (never merges two inputs) and surjective (reaches every output). Lose either property and the reverse trip is ambiguous or impossible.

The one idea you need first

A set is a collection of distinct things and the Cartesian product $A \times B$ is the set of all pairs $(a, b)$ . A relation is a subset of that product. The sets-and-logic overview in sets, logic and proofs covers the notation this page builds on.

Think of It Like This

A cloakroom with numbered hooks

A cloakroom has hooks (inputs) and coats (outputs). The attendant's ledger pairing each hook with the coat hung on it is a relation.

A well-run cloakroom is a function: every hook holds exactly one coat. No hook sits empty at closing time (totality), and no hook holds two coats at once (single-valuedness). An overstuffed cloakroom where two coats share a hook is a relation but not a function. A cloakroom with an empty hook is not a function either, at least not on the full set of hooks.

Now run it backwards: given a coat, find its hook. That works perfectly only if no two hooks share a coat (injective) and every coat hangs on some hook (surjective). Miss the first and two owners claim one coat; miss the second and someone's coat is on the floor. Bijections are cloakrooms with zero drama in either direction.

How It Actually Works

Three properties decide what a function can do:

Injective (one-to-one): $f(a_1) = f(a_2)$ forces $a_1 = a_2$ . Nothing merges. Squaring on all reals fails this ( $(-2)^2 = 2^2$ ); squaring on non-negatives passes.
Surjective (onto): every $b$ in $B$ equals $f(a)$ for some $a$ . The range fills the codomain. $f(x) = x^2$ from reals to reals fails (negatives unreachable); to non-negatives it passes.
Bijective: both at once. Exactly the functions with an inverse $f^{-1}$ satisfying $f^{-1}(f(a)) = a$ and $f(f^{-1}(b)) = b$ .

Composition chains functions: $(g \circ f)(x) = g(f(x))$ . A network layer stack is one long composition, and backpropagation differentiates through it with the chain rule. The codomain choice matters more than beginners expect: the "same formula" can be non-surjective or surjective depending on $B$ , which is why declaring output spaces (logits vs probabilities) is part of model design.

Worked example

Take $f(x) = 2x + 3$ with domain $\\{1, 2, 3\\}$ and codomain $\\{5, 7, 9\\}$ :

f(1) = 5, \quad f(2) = 7, \quad f(3) = 9

Every input appears exactly once, so $f$ is a function. Distinct inputs give distinct outputs ( $5 \ne 7 \ne 9$ ), so it is injective. Every codomain value is reached, so it is surjective. Both together: bijective, with inverse $f^{-1}(y) = (y - 3)/2$ . Check: $f^{-1}(7) = 2$ and $f(2) = 7$ . Round trip confirmed.

Code

The point is the check: test totality, single-valuedness and bijectivity on a finite mapping before trusting it.

1def is_bijection(mapping: dict[int, int], codomain: set[int]) -> bool:2    outs = list(mapping.values())3    injective = len(set(outs)) == len(outs)  # nothing merges4    surjective = set(outs) == codomain  # everything reached5    return injective and surjective6
7
8f = {1: 5, 2: 7, 3: 9}9print(is_bijection(f, {5, 7, 9}))  # -> True10print(is_bijection(f, {5, 7}))     # -> False

The second call fails on surjectivity: 9 is in the mapping but outside the declared codomain, so the range no longer matches. Same pairs, different verdict. The codomain is part of the claim.

Watch Out For

Treating a relation as a function in a lookup

A join key that appears twice in a label table pairs one feature row with two labels. Downstream code takes "the" label and gets whichever row the database returned first. The fix is a uniqueness check at the boundary: assert the key column has no duplicates before treating the table as a function. Silent many-to-one joins are a top-three source of training-serving skew.

Assuming invertibility from a formula alone

$f(x) = x^2$ looks invertible until you ask about the domain and codomain. On all reals it merges $\pm x$ , so no inverse exists; restricted to non-negatives it inverts cleanly to $\sqrt{y}$ . Whenever a method needs an inverse (change of variables, flow models, solving for inputs), verify bijectivity on the actual sets, not the formula in isolation.

The Quick Version

A relation is any set of input-output pairs; a function gives every input exactly one output.
Injective means nothing merges; surjective means everything is reached; bijective means both.
Only bijections have inverses, which is what makes running a model backwards possible.
Composition chains functions, and a layer stack is one long composition.
The codomain is part of the claim: the same formula can be bijective or not depending on it.