Relations & functions

A foreign key, a dictionary lookup, a JOIN, a type signature, a GROUP BY — these feel like four or five separate tools you happen to have learned. Underneath, they are one idea seen from different angles. All of them are talking about relations: which things go with which other things. Set theory builds that idea from almost nothing, and the payoff is that once you see the shape, you recognise it everywhere.

Ordered pairs and the Cartesian product

Sets are unordered: {a, b} and {b, a} are the same set. But relationships usually have direction — “Alice manages Bob” is not “Bob manages Alice”. So we need a construct that remembers order. That is the ordered pair (a, b), defined by the rule that (a, b) = (c, d) exactly when a = c and b = d. Hence (1, 2) and (2, 1) are different objects, even though {1, 2} and {2, 1} are not.

Collect every possible pair and you get the Cartesian product:

A × B = { (a, b) : a ∈ A and b ∈ B }

If A has 4 elements and B has 3, then A × B has 12. This is not an abstraction you have to imagine — it is a CROSS JOIN:

SELECT * FROM users CROSS JOIN roles;  -- every user paired with every role

Four users, three roles, twelve rows. The database is computing A × B literally.

A relation is just a subset

Here is the definition that does the heavy lifting: a relation from A to B is any subset of A × B. Nothing more. To say “x is less than y” over the integers is to name the set of pairs (x, y) where the first is smaller than the second. To say which users hold which roles is to name a subset of users × roles — which is exactly what a join table stores, one row per pair.

And an inner join is that same move in query form: take the full product, keep the pairs satisfying a condition.

SELECT * FROM users u JOIN roles r ON u.role_id = r.id;

Conceptually, form every pairing, then filter. (Real engines use indexes so they never materialise the product, but the meaning is unchanged.) A join is a relation, picked out of a Cartesian product by a predicate.

Properties: reflexive, symmetric, transitive

For a relation R on a single set A — pairs drawn from A × A — three properties come up constantly.

• Reflexive: every element relates to itself. For all a, the pair (a, a) is in R. Equality is reflexive; strict less-than is not.
• Symmetric: if (a, b) is in R then so is (b, a). “Is a sibling of” is symmetric; “is the parent of” is emphatically not.
• Transitive: if (a, b) and (b, c) are in R, so is (a, c). Less-than is transitive, as is “is an ancestor of”. “Is a friend of” usually isn’t, which is why social graphs are hard.

A relation with all three is an equivalence relation, and it does something remarkable.

Equivalence relations carve a set into classes

An equivalence relation is a formalisation of “same in the way I currently care about”. Same remainder mod 3. Same country of residence. Same normalised email address.

The theorem worth remembering: every equivalence relation on a set partitions that set into disjoint equivalence classes whose union is the whole set. Each element lands in exactly one class, everything in a class is equivalent to everything else in it, and nothing is left out.

Partitioning by an equivalence relation is what GROUP BY does. GROUP BY country says “treat two rows as the same when their countries match” — reflexive, symmetric, transitive — and hands you back one bucket per class. Deduplication is the same operation, keeping one representative per class.

This is also why “same” is a design decision, not a fact. Case-sensitive or not? Trimmed or not? Each choice is a different equivalence relation and therefore a different partition.

Functions: the special relations

Now impose one extra condition. A relation f from A to B is a function when every element of A is the first component of exactly one pair — one output per input, never zero, never two.

That is the whole definition, and it is precisely why lookups work. A hash map stores pairs; storing a key twice overwrites rather than keeping both, which enforces single-valuedness. Ask for a key and there is one answer. A structure that permits a key to carry several values — a multimap, or a many-to-many join table — has dropped that condition and is a general relation again.

Three sets come attached to every function:

• the domain, the legal inputs;
• the codomain, the declared set outputs are drawn from;
• the range (or image), the values actually produced.

The range is always a subset of the codomain, and often a proper one. A type signature declares domain and codomain; it says nothing about the range.

function parseAge(s: string): number | null
// domain: string    codomain: number | null
// range: whatever this actually returns — perhaps only 0..130 and null

Mathematics calls a function pure by construction: same input, same output, no hidden state. That property programmers work to preserve is simply what a function is set-theoretically.

Injective, surjective, bijective

Three labels describe how a function maps its domain onto its codomain.

Injective (one-to-one): distinct inputs give distinct outputs, so f(a) = f(b) forces a = b. Nothing collapses, nothing is lost. A hash function with no collisions would be injective — impossible whenever there are more keys than buckets, which is the pigeonhole principle in one line.

Surjective (onto): every element of the codomain is hit, so range equals codomain. Note that this depends on the codomain you declared. Doubling is surjective onto the even integers, not onto all integers.

Bijective: both at once — a perfect pairing. Bijections matter because they are exactly the invertible functions. Reverse every pair and the result is still a function, giving f⁻¹ with f⁻¹(f(a)) = a. Lossless encodings are bijections; lossy ones (hashing, truncation, downcasing) are not, and no amount of cleverness will invert them.

Composition

Finally, functions chain. (g ∘ f)(x) = g(f(x)): apply f, then g. The condition is that the range of f fits inside the domain of g — otherwise g receives something it cannot handle, which is exactly the error a type checker raises when you pipe one function into the next.

const slugify = compose(hyphenate, lowercase, trim);

Every pipeline, middleware stack, and chain of .map() calls is composition. And composition is associative but not commutative: f ∘ g is generally not g ∘ f, as anyone who has trimmed after lowercasing instead of before can confirm.