Appearance
8.4 — Relations and Functions
"Is older than", "is a parent of", "divides", "is equal to", "connects to" — every one is a statement relating pairs of things. Mathematics handles all of them with one construction, and it is built from Chapter 8.1's Cartesian product.
A relation from A to B is any subset of A\times B — that is, any collection of ordered pairs. That is the entire definition. It seems almost too permissive, and its power is exactly that it imposes nothing: whatever you mean by "related", the set of pairs that satisfy it is the relation.
We write a\,R\,b to mean the pair (a,b) is in the relation.
And this is why relational databases are called relational. A table is a set of rows, each row an ordered tuple, so a table is a relation in this precise sense. Codd's 1970 paper that founded the field is built directly on this, and Volume I, 7.1 covers the database consequences.
1. Properties a relation can have
Four properties, which between them classify almost every relation worth naming.
Reflexive: a\,R\,a for every a. "Is equal to" is reflexive; "is older than" is not.
Symmetric: if a\,R\,b then b\,R\,a. "Is a sibling of" is symmetric; "is a parent of" is emphatically not.
Antisymmetric: if a\,R\,b and b\,R\,a then a = b. "Less than or equal to" is antisymmetric — two numbers each at most the other must be equal.
Transitive: if a\,R\,b and b\,R\,c then a\,R\,c. "Less than" is transitive. "Is a friend of" is not, which is the entire reason social networks are interesting.
2. Equivalence relations: sorting things into groups
A relation that is reflexive, symmetric and transitive is an equivalence relation, and it captures the idea of "the same in some respect".
Examples: equality itself; "has the same birthday as"; "is congruent modulo 5" from Chapter 1.6; "has the same remainder"; "is the same shape as" for triangles.
The reason this matters: an equivalence relation splits its set into non-overlapping groups called equivalence classes, and every element lands in exactly one. That splitting is called a partition, and it is automatic — you do not have to arrange it.
Congruence modulo 5 splits the integers into exactly five classes: the numbers leaving remainder 0, 1, 2, 3 and 4. Every integer is in one and no integer is in two. Chapter 1.6's "residue classes" are these.
The idea underneath: an equivalence relation is how mathematics deliberately forgets a distinction it does not care about. Fractions are a good example. \frac12 and \frac24 are different pairs of integers and the same rational number, because "the rationals" are defined as the equivalence classes of pairs under the relation \frac ab \sim \frac cd when ad = bc. Chapter 1.3's "many names for one number" is exactly this construction.
You use it in software constantly. Comparing two objects for equality means deciding which differences to ignore — is a User with the same ID but a different last-login timestamp the same user? Every equals method you write defines an equivalence relation, and the three properties are what makes it behave sensibly. A comparison that is not transitive will break sorting and caching in ways that are extremely hard to debug.
3. Order relations: arranging things
A relation that is reflexive, antisymmetric and transitive is a partial order.
"Less than or equal to" on numbers is one. So is "divides" on the integers, and "is a subset of" on sets.
Why "partial": some pairs may be incomparable. Under "divides", neither 4 nor 6 divides the other, so they simply are not ordered relative to one another. Under "subset", \{1,2\} and \{2,3\} are incomparable.
A total order is one where every pair is comparable — the ordinary ordering of numbers.
Partial orders are everywhere in practice, and the reason is that dependencies are naturally partial. Task B depends on task A; task C depends on A; B and C are independent of each other and can happen in either order or simultaneously.
Topological sorting is the operation of extending a partial order to a total one — producing some valid sequence consistent with all the dependencies. It is what a build system does to decide compilation order, what a package manager does to install dependencies, and what a project scheduler does. Volume I, 4.7 gives the algorithm.
Version control history is a partial order too. Two commits on separate branches have no order between them until they are merged, which is why distributed version control needs a merge operation rather than just a sequence. Volume I, 14.1 covers Git's model, and the commit graph is a partial order in exactly this sense.
4. Functions
A function from A to B is a relation where every element of A is paired with exactly one element of B.
f: A\to B
A is the domain (the allowed inputs), B is the codomain (where outputs may live), and the range or image is the set of outputs actually produced. The range can be smaller than the codomain, and keeping them distinct matters for the definitions below.
Two requirements, both worth stating explicitly. Every input must produce an output (nothing may be undefined), and no input may produce two different outputs. The second is what fails for the "relation" x^2+y^2=1, since x=0 gives both y=1 and y=-1 — a circle is a relation and not a function, which is why Chapter 3.4 had to split it into two halves.
5. Injective, surjective, bijective
Injective (one-to-one): different inputs give different outputs. Nothing collides.
f(a) = f(b) \implies a = b
f(x) = 2x is injective. f(x) = x^2 is not, since 2 and -2 both give 4.
Surjective (onto): every element of the codomain is actually produced. The range fills the codomain.
f:\mathbb{R}\to\mathbb{R}, f(x)=x^3 is surjective — every real is some cube. f(x)=x^2 is not, because negatives are never produced.
Bijective: both. A perfect pairing with nothing missed and nothing doubled.
A function has an inverse exactly when it is bijective. If it is not injective, the inverse would have to choose between two possible answers; if it is not surjective, the inverse would be undefined somewhere.
This is why \sqrt{\;} is defined as the non-negative root (Chapter 1.4): squaring is not injective on all the reals, so it must be restricted to the non-negatives before it can be inverted. The same reason forces \arcsin to return values only between -90° and 90°, which Chapter 3.5 noted causes real trouble in programming.
And bijection is how Chapter 1.7 compared infinite sets. Two sets have the same size when a bijection between them exists — the shepherd's pebbles, made precise.
6. Composition
(g\circ f)(x) = g(f(x))
Apply f first, then g. The order looks backwards and is not — it matches the nesting of the brackets, and it is the same right-to-left convention as matrix multiplication in Chapter 4.2, for the same reason.
Composition is associative: (h\circ g)\circ f = h\circ(g\circ f). It is not commutative: doubling then adding one is not adding one then doubling.
Where composition is the whole idea. Function composition is the foundation of functional programming — pipelines, middleware chains, transformations applied in sequence. A Unix pipeline cat file | grep x | sort is composition. An Express middleware stack is composition. A neural network is composition of layers, which is exactly why the chain rule of Chapter 5.3 is what trains it.
7. Cardinality, revisited
With bijections defined, Chapter 1.7's results can be stated cleanly.
Two sets have the same cardinality when a bijection exists between them.
A set is countable when there is a bijection with \mathbb{N}. The integers and the rationals are countable; the reals are not.
A set is infinite exactly when it has a bijection with a proper subset of itself. This is Dedekind's definition, and it turns Chapter 1.7's "strange result" into the actual definition — the strangeness is infinity.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
Relations and functions
A relation on a set can have these properties:
| Property | Meaning |
|---|---|
| Reflexive | aRa for all a |
| Symmetric | aRb \Rightarrow bRa |
| Antisymmetric | aRb and bRa force a=b |
| Transitive | aRb and bRc give aRc |
Equivalence relation = reflexive + symmetric + transitive. Its effect is to carve the set into equivalence classes: disjoint groups where everything inside is related and nothing across is. "Has the same remainder modulo 5" splits the whole numbers into exactly five classes, which is precisely what 1.6 is about.
Partial order = reflexive + antisymmetric + transitive. Think of "divides" or "is a subset of": some pairs are comparable, others are not, and that is what makes it partial.
Functions.
\text{Injective (one-to-one)}: f(a)=f(b)\Rightarrow a=b
\text{Surjective (onto)}: \text{every target value is hit}
\text{Bijective}: \text{both, so an inverse exists}
(f\circ g)^{-1} = g^{-1}\circ f^{-1}
The reversal is the same "socks and shoes" logic as matrix inverses in 4.4 — determinants and inverses.
Counting functions between finite sets, |A| = m and |B|=n:
\text{all functions } A\to B: n^m, \qquad \text{injections}: \frac{n!}{(n-m)!}, \qquad \text{bijections (if } m=n): n!
The first is the multiplication principle: each of the m inputs independently picks one of n outputs.
8. Where this shows up in your life
Every database. Tables are relations, keys enforce functional dependencies, joins combine relations, and normalisation is about eliminating redundant functional dependencies. Volume I, 7.1.
Every build system, package manager and CI pipeline. Partial orders and topological sort.
Every equals and hashCode you write. An equivalence relation, and the contract that equal objects must hash equally is what makes hash tables work. Volume I, 4.4.
Every sort you perform. A comparator must define a total order, and one that is not transitive causes sorting algorithms to produce garbage or crash — a real and well-documented failure mode in Java's sort.
Every URL shortener, every ID generator, every hash function. Injectivity, or the acceptance of collisions when it is impossible. Volume I, 11.1 and 11.5.
Every function you have ever written. The definitions here are what "function" means, and a function that returns different results for the same input is not one — which is why pure functions are easier to reason about, cache and parallelise.
Relations and functions describe structure. The next chapter counts it: how many arrangements, how many paths, how many steps — which is where discrete mathematics meets algorithm analysis.