A relation can be defined between elements of set \(A\) and elements of another set \(B\).
Relations may also be defined between elements of the same set.
The letter \(\mathcal R\) is used to refer to relation.
Let \(A\) and \(B\) be two sets, and \(x \in A\), \(y \in B\). Given some \(\mathcal R\) linking these, it can be stated that \(x\) is related to \(y\) with respect to the relation \(\mathcal R\). This may be more succinctly expressed as \(x\ \mathcal R\ y\).
Relations within or between bounded sets be shown via a boolean matrix. For two sets \(A\) and \(B\) this is then shown as a matrix of order \(|A| \times |B|\).
For example, given \(A = \{1,2,3,4,5\}\) the relation \(\mathcal R_< = \{(a,b) \in A^2\ |\ a < b\}\) may be noted as \[ M_{\mathcal R_<} = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \]
Equivalently, a directed graph that expresses this as an adjacency matrix may also be shown.
| Term | Bi-condition | Digraph | Matrix |
|---|---|---|---|
| reflexivity | \(x \mathcal R x\) | loop on every node | \(M_{i,i} = 1\) |
| symmetry | \(a \mathcal R b \iff b \mathcal R a\) | parallel edges on all connected nodes | \(M_{i,j} = M_{j,i}\) |
| anti-symmetry | \(a \mathcal R b \land b \mathcal R a \implies a = b\) | no parallel edges | \(M_{i,j} \neq 0 \implies M_{j,i} = 0\) |
| transitivity | \(a \mathcal R b \land b \mathcal R c \implies a \mathcal R c\) | direct paths between any two connected nodes | \(M^2_{i,j} \neq 0 \implies M_{i,j} \neq 0\) |
If a relation is reflexive, symmetric, and transitive it is termed an Equivalence relation.
A relation that is reflexive, anti-symmetric, and transitive is a partial order.
A relation is a total order if satisfies the properties of a partial order and \(\forall a,b \in S\) either \(a \mathcal R b\) or \(b \mathcal R a\). That is, all elements of \(S\) must be comparable under \(\mathcal R\).