1
A relation is just a set of pairs
No condition at all. {(1,1), (2,5)} is a relation on {1,2,5}, and so is the empty set.
Lesson · Sets, Relations, and Functions · Relations
Binary Relations
Any subset of A × B is a relation. Three ways to present one — as pairs, as a matrix, as a directed graph — and the operations of inverse and composition.
R ⊆ A × B a relation FROM A TO B
a R b means (a, b) ∈ R
R⁻¹ = {(b, a) : (a, b) ∈ R} the inverse
S ∘ R = {(a, c) : ∃b. aRb and bSc} composition
Pairs, and what you can do with them
Core ideas
What this lesson establishes
The definition is deliberately weak: any set of pairs qualifies. The interesting relations are the ones with extra properties, from “Properties of Relations” on.
2
Three presentations, one object
The pair list, the boolean matrix and the directed graph carry identical information. Each makes different properties obvious.
3
Composition is not commutative
S ∘ R follows R then S. Reversing the order generally gives a different relation, and often an empty one.
The material
Relations and their presentations
The definition, three ways to draw it, and two operations.
Definition · Binary relation
A relation from A to B is a subset R ⊆ A × B. A relation on A is a subset of A × A. We write a R b for (a, b) ∈ R.
The definition permits everything. ∅ is a relation (nothing is related), and A × A is a relation (everything is related to everything). Between those extremes there are 2^(n²) relations on an n-element set — 512 on a three-element set, and over thirty-three million on a five-element one.
Three presentations
- As pairs. R = {(1,2), (2,3), (3,1)}. Complete and unreadable beyond a handful.
- As a matrix. An n × n grid with a 1 in row a, column b when a R b. Reflexivity is the diagonal, symmetry is the matrix equalling its transpose.
- As a directed graph. A dot per element, an arrow from a to b when a R b. Transitivity becomes "every two-step path has a one-step shortcut", which is the reading Graphs and Trees uses.
The matrix is what the lab shows, because the four properties of “Properties of Relations” are all visible in it: the diagonal, the transpose, and the presence of both (a,b) and (b,a) for distinct a, b.
Definition · Inverse relation
R⁻¹ = {(b, a) : (a, b) ∈ R} — every pair reversed. As a matrix this is the transpose.
Definition · Composition
For R ⊆ A × B and S ⊆ B × C, S ∘ R = {(a, c) : ∃b ∈ B with (a,b) ∈ R and (b,c) ∈ S}. Read right to left: apply R first, then S.
The right-to-left order is chosen to match function composition, where (g ∘ f)(x) = g(f(x)). It is a convention and some texts reverse it; what matters is being consistent and saying which you mean.
Example · Composing two relations
On {1,2,3}, let R = {(1,2), (2,3)} and S = {(2,1), (3,3)}. Then S ∘ R = {(1,1), (2,3)}: from 1, R reaches 2 and S takes 2 to 1; from 2, R reaches 3 and S takes 3 to 3. Meanwhile R ∘ S = {(2,2)} — a different relation.
Theorem · Composition and matrices
If M_R and M_S are the boolean matrices of R and S, then the matrix of S ∘ R is the boolean product M_R M_S, where multiplication is ∧ and addition is ∨.
That is the same computation as counting walks of length 2 in “Graph Representations” in Graphs and Trees, with ∨ in place of +. Composition of relations and paths in a directed graph are the same idea.
Interactive
Relation properties
Decided by checking, not by name
Method
Reading a relation
Choose the presentation that makes your question easy.
1
Write it as pairs when it is small
Nothing is clearer than the list for four or five pairs, and the list is what the definition actually is.
2
Use the matrix to check properties
Reflexive is a full diagonal; symmetric is equal to its transpose. Both are one glance in matrix form and tedious in list form.
3
Use the digraph to trace paths
Transitivity and the transitive closure are statements about paths, and arrows make paths visible.
4
Compose right to left
S ∘ R means R first. Pick each a, follow R to every b, then S to every c, and collect the pairs (a, c).
Relations
Score 0 / 0Choose the answer you can justify.
Composing with itself
On {1,2,3,4}, let R = {(1,2), (2,3), (3,4)} — the successor relation.
R ∘ R (two steps):
1 → 2 → 3 gives (1, 3)
2 → 3 → 4 gives (2, 4)
3 → 4 → ? 4 has no outgoing pair — nothing
R ∘ R = {(1,3), (2,4)}
R ∘ R ∘ R (three steps): {(1,4)}
R⁴ = ∅ no path of length 4 exists in a 4-element chain
R ∪ R² ∪ R³ = {(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)} = the
relation "a < b", which is the transitive closure of R.
The last line is “Properties of Relations”'s transitive closure computed by hand: the union of all powers of R is exactly the pairs joined by a path of any length. Warshall's algorithm in the lab does this without enumerating the powers.
Common mistakes
1
Composing in the wrong orderS ∘ R applies R first. Getting this backwards produces a different relation, usually a different size, and the error is silent.
2
Assuming a relation must be meaningfulAny set of pairs qualifies. Most relations have no description shorter than their pair list, which is why properties rather than names are what matter.
3
Confusing R⁻¹ with a complementThe inverse reverses each pair; the complement takes the pairs not in R. They are unrelated operations.
Check your understanding
✓
Finish when you can move between all three presentations.
Take R = {(1,1),(1,2),(2,3),(3,1)} on {1,2,3}, write its matrix, sketch its digraph, and compute R ∘ R in whichever presentation is easiest. Then check the answer in a second presentation.
Note: Relations need not be on one set: R ⊆ A × B with A ≠ B is a bipartite relation, and “Functions”'s functions are exactly the relations from A to B in which every element of A appears exactly once as a first coordinate.