Relations and their properties
A relation describes how elements of sets are connected: 'is less than', 'is a friend of', 'has the same remainder as'. Their properties determine what we can do with them.
What a relation is
A relation \(R\) from set \(A\) to set \(B\) is a subset of \(A \times B\); we write \(a\,R\,b\) when \((a, b) \in R\). A relation on a set \(A\) relates elements of \(A\) to each other. Functions are special relations where each input relates to exactly one output.
Reflexive, symmetric, transitive
A relation on \(A\) is reflexive if every element relates to itself (\(a\,R\,a\)); symmetric if \(a\,R\,b\) implies \(b\,R\,a\); transitive if \(a\,R\,b\) and \(b\,R\,c\) imply \(a\,R\,c\). Equality has all three. 'Is a sibling of' is symmetric but not reflexive. 'Is less than' is transitive but neither reflexive nor symmetric.
Antisymmetry
A relation is antisymmetric if \(a\,R\,b\) and \(b\,R\,a\) together force \(a = b\). The relation \(\le\) is antisymmetric: if \(a \le b\) and \(b \le a\), then \(a = b\). Antisymmetric is not the opposite of symmetric; a relation can be both (like equality) or neither.
Representing relations
Relations on finite sets can be shown as matrices (a 1 in row \(a\), column \(b\) when \(a\,R\,b\)) or as directed graphs with an arrow from \(a\) to \(b\). In the matrix, reflexive means the diagonal is all 1s, and symmetric means the matrix equals its transpose.
Closures
The transitive closure of \(R\) adds the minimum pairs needed to make it transitive. If \(R\) is 'there is a direct flight from \(a\) to \(b\)', its transitive closure is 'you can fly from \(a\) to \(b\), possibly with connections'. Warshall's algorithm computes transitive closures efficiently.
Composition and inverse
Composing relations, \(S \circ R\), relates \(a\) to \(c\) when \(a\,R\,b\) and \(b\,S\,c\) for some \(b\). 'Parent of a parent' is 'grandparent'. The inverse relation \(R^{-1}\) reverses every pair: the inverse of 'is a parent of' is 'is a child of'.
Worked example
On \(A = \{1, 2, 3\}\), let \(R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}\). It is reflexive (all \((a, a)\) present), symmetric (\((1,2)\) and \((2,1)\) both present), and transitive (no chain leaves the set). So \(R\) is an equivalence relation, grouping \(\{1, 2\}\) together and \(\{3\}\) alone.
Relations in databases
A relational database table is literally a relation: a set of tuples. Joins compose relations, selecting combines them with conditions, and keys enforce function-like uniqueness. Edgar Codd's relational model, built on this mathematics, underlies SQL databases.
Key takeaways
Relations are subsets of Cartesian products. Key properties are reflexive, symmetric, antisymmetric, and transitive. Matrices and directed graphs represent them. Closures add missing pairs, composition chains relations, and relational databases apply these ideas directly.
Flashcard
A subset of A \times B
Check your understanding
The relation 'is less than' on the integers is: