Relations are one of the most basic structures in mathematics. They formalize when and how elements of one set are connected to elements of another set.
Definition
Let \(A\) and \(B\) be sets. A subset \(R\subseteq A\times B\) is called a relation from \(A\) to \(B\).
The cartesian product \(A\times B\) contains all possible ordered pairs \((a,b)\) with \(a\in A\), \(b\in B\). The relation \(R\) selects the pairs that are considered "related".
The notation for cartesian products and subsets follows set theory.
Reading and Notation
If \((a,b)\in R\), we often write
\[ a\,R\,b. \]
If \((a,b)\notin R\), we write \(a\not R b\).
Informally, a relation can be represented as a table of pairs. This is the conceptual source of the term relational database.
Domain, Codomain, Image
For \(R\subseteq A\times B\):
\[ \operatorname{dom}(R):=\{a\in A:\exists b\in B,(a,b)\in R\}, \]
\[ \operatorname{im}(R):=\{b\in B:\exists a\in A,(a,b)\in R\}. \]
The codomain is \(B\), while \(\operatorname{im}(R)\subseteq B\) is the actual set of reached values.
Inverse and Composition of Relations
Inverse Relation
The inverse relation \(R^{-1}\subseteq B\times A\) is
\[ R^{-1}:=\{(b,a):(a,b)\in R\}. \]
It flips every pair.
Composition
If \(R\subseteq A\times B\) and \(S\subseteq B\times C\), then
\[ S\circ R:=\{(a,c):\exists b\in B, (a,b)\in R\land(b,c)\in S\}. \]
Composition connects two relation steps into one.
Relations on One Set
If \(R\subseteq A\times A\), then \(R\) is a relation on \(A\). Important properties are:
- Reflexive: \(\forall a\in A: aRa\).
- Symmetric: \(aRb\Rightarrow bRa\).
- Antisymmetric: \(aRb\land bRa\Rightarrow a=b\).
- Transitive: \(aRb\land bRc\Rightarrow aRc\).
- Total (connex): \(\forall a,b\in A: aRb\lor bRa\).
Two Important Classes
Equivalence Relations
A relation that is reflexive, symmetric, and transitive is an equivalence relation.
Example on integers:
\[ a\equiv b\pmod m \iff m\mid(a-b). \]
This relation is central in modulo arithmetic.
Order Relations
A relation that is reflexive, antisymmetric, and transitive is a partial order.
If it is also total, it is a total order. On \(\mathbb{R}\), \(\le\) is a total order.
From Relations to Functions
A function is a special relation with additional uniqueness and existence conditions. Concretely, \(f:A\to B\) is a relation \(f\subseteq A\times B\) such that:
- for every \(a\in A\), there exists a \(b\in B\) with \((a,b)\in f\),
- for every \(a\in A\), this \(b\) is unique.
This is exactly the additional structure that turns a general relation into a function.
Common Pitfalls
- Confusing codomain with image.
- Assuming every relation is a function.
- Forgetting uniqueness in the definition of functions.
- Mixing up inverse relation \(R^{-1}\) with inverse function \(f^{-1}\).