Relations describe links between objects: "x is less than y", "user u belongs to group g", "page p links to page q". Discrete mathematics studies them abstractly and finds that a handful of properties is enough to classify them. Recognising those properties tells you at once what kind of structure you are dealing with and which algorithms you can use.
Definition
A binary relation R from a set A to a set B is a subset of the Cartesian product A × B. If the pair (a, b) belongs to R we write a R b and say that a is related to b. When A = B we speak of a relation on A.
Example: on A = {1, 2, 3, 4}, the relation "divides" contains the pairs (a, b) where a divides b:
R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
Three ways to represent it
- List of pairs, as above.
- Boolean matrix: a table with rows and columns indexed by the elements, with 1 where the pair is in the relation.
- Directed graph: one node per element, an arrow from a to b for each pair (a, b).
The matrix of the "divides" relation on {1, 2, 3, 4}:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 1 |
The fundamental properties
Reflexive
R is reflexive if every element is related to itself: a R a for every a. In the matrix, the diagonal is all 1s; in the graph, every node has a loop. "Divides" is reflexive, because every number divides itself. "Less than" is not.
Symmetric
R is symmetric if a R b implies b R a. The matrix equals its transpose; in the graph every arrow has a return arrow. "Being siblings" is symmetric (edge cases aside), and so is "being connected in an undirected network". "Divides" is not: 2 divides 4 but 4 does not divide 2.
Antisymmetric
R is antisymmetric if a R b and b R a together imply a = b. In other words, between two distinct elements there is at most one of the two arrows. "Divides" on the positive integers is antisymmetric, as is "≤".
Careful: antisymmetric does not mean "not symmetric". Equality is both symmetric and antisymmetric. A relation can also be neither.
Transitive
R is transitive if a R b and b R c imply a R c. In the graph: whenever there is a path of two arrows, there is also a direct arrow. "Divides" is transitive, and so is "≤". "Being friends with" generally is not.
Summary on a few examples
| Relation | Refl. | Symm. | Antisymm. | Trans. |
|---|---|---|---|---|
| = on ℤ | yes | yes | yes | yes |
| ≤ on ℤ | yes | no | yes | yes |
| < on ℤ | no | no | yes | yes |
| divides on ℤ⁺ | yes | no | yes | yes |
| same remainder mod 5 | yes | yes | no | yes |
| differ by 1 | no | yes | no | no |
Checking the properties in code
With the relation stored as a set of pairs, the checks are direct translations of the definitions:
def reflexive(R, A):
return all((a, a) in R for a in A)
def symmetric(R):
return all((b, a) in R for (a, b) in R)
def transitive(R):
return all((a, d) in R
for (a, b) in R for (c, d) in R if b == c)
The transitivity check examines every pair of pairs, so it is expensive on large relations; for those, matrix representations and dedicated algorithms are used.
Closures
If a relation lacks a property, you can add the minimum number of pairs needed to give it that property. The result is called a closure.
- Reflexive closure: add every pair (a, a).
- Symmetric closure: for each (a, b), add (b, a).
- Transitive closure: add pairs until every path has its shortcut.
The transitive closure has a very concrete interpretation: if R says "module a directly imports module b", its transitive closure says "a depends, directly or indirectly, on b". The same goes for "group g is a member of group h" in permission management systems: working out who inherits what means computing a transitive closure. In a permissions audit, that is often exactly where you discover access that nobody assigned explicitly. Warshall's algorithm computes it on an n × n matrix with three nested loops, in time proportional to n³.
In short
- A binary relation is a set of ordered pairs, representable as a matrix or a directed graph.
- Reflexive: full diagonal; symmetric: the matrix equals its transpose.
- Antisymmetric does not mean not symmetric: equality is both.
- Transitive: every two-step path has a direct shortcut.
- The transitive closure answers questions about dependencies and inherited permissions.
