Relations
Binary relations
Definition: a binary relation \(R\) between the sets \(S\) and \(T\) is a subset of the Cartesian product \(S \times T\).
- If \((a,b) \in R\) then \(a\) is in relation \(R\) to \(b\), denoted by \(aRb\).
- The set \(S\) is called the domain of the relation \(R\) and the set \(T\) the codomain.
- If \(S=T\) then \(R\) is a relation on \(S\).
- This definition can be expanded to n-ary relations.
Definition: let \(R\) be a relation from a set \(S\) to a set \(T\). Then for each element \(a \in S\) we define \([a]_R\) to be the set
\[ [a]_R := \{b \in T \;|\; aRb\}. \]This set is called the (\(R\)-) image of \(a\).
For \(b \in T\) the set
\[ _R[b] := \{a \in S \;|\; aRb\} \]is called the (\(R\)-) pre-image of \(B\) or \(R\)-fiber of \(b\).
Relations between finite sets can be described using matrices.
Definition: if \(S = \{s_1, \dots, s_n\}\) and \(T = \{t_1, \dots, t_m\}\) are finite sets and \(R \subseteq S \times T\) is a binary relation, then the adjacency matrix \(A_R\) of the relation \(R\) is the \(n \times n\) matrix whose rows are indexed by \(S\) and columns by \(T\) defined by
\[ A_{s,t} = \begin{cases} 1 &\text{ if } (s,t) \in R, \\ 0 &\text{ otherwise}. \end{cases} \]
For example, the adjacency matrix of relation \(\leq\) on the set \(\{1,2,3,4,5\}\) is the upper triangular matrix
Some relations have special properties
Definitions: let \(R\) be a relation on a set \(S\). Then \(R\) is called
- Reflexive if \(\forall x \in S\) there is \((x,x) \in R\).
- Irreflexive if \(\forall x \in S\) there is \((x,x) \notin R\).
- Symmetric if \(\forall x,y \in S\) there is that \(xRy \implies yRx\).
- Antisymmetric if \(\forall x,y \in S\) there is that \(xRy \land yRx \implies x = y\).
- Transitive if \(\forall x,y,z \in S\) there is that \(xRy \land yRz \implies xRz\).
Equivalence relations
Definition: a relation \(R\) on a set \(S\) is called an equivalence relation on \(S\) if and only if it is reflexive, symmetric and transitive.
Lemma: let \(R\) be an equivalence relation on a set \(S\). If \(b \in [a]_R\), then \([b]_R = [a]_R\).
Proof:
Suppose \(b \in [a]_R\), therefore \(aRb\). If \(c \in [b]_R\), then \(bRc\) and as \(aRb\) there is transitivity \(aRc\). In particular \([b]_R \subseteq [a]_R\). By symmetry of \(R\), \(aRb \implies bRa\) and hence \(a \in [b]_R\), obtaining \([a]_R \subseteq [b]_R\).
Definition: let \(R\) be an equivalence relation on a set \(S\). Then the sets \([s]_R\) where \(s \in S\) are called the \(R\)-equivalence classes on \(S\). The set of \(R\)-equivalence classes is denoted by \(S/R\).
Theorem: let \(R\) be an equivalence relation on a set \(S\). Then the set \(S/R\) of \(R\)-equivalence classes partitions the set \(S\).
Proof:
Let \(\Pi_R\) be the set of \(R\)-equivalence classes. Then by reflexivity of \(R\) we find that each element \(a \in S\) is inside the class \([a]_R\) of \(\Pi_R\). If an element \(a \in S\) is in the classes \([b]_R\) and \([c]_R\) of \(\Pi_R\), then by the previous lemma we find \([b]_R = [a]_R\) and \([c]_R = [a]_R\). Then \([b]_R = [c]_R\), therefore each element \(a \in S\) is inside a unique member of \(\Pi_R\), which therefore is a partition of \(S\).
Composition of relations
If \(R_1\) and \(R_2\) are two relations between a set \(S\) and \(T\), new relations can be formed between \(S\) and \(T\) by taking the intersection \(R_1 \cap R_2\), the union \(R_1 \cup R_2\) or the complement \(R_1 \backslash R_2\). Furthermore a relation \(R^\top\) from \(T\) to \(S\) can be considered as the relation \(\{(t,s) \in T \times S \;|\; (s,t) \in R\}\) and the identity relation from \(T\) to \(S\) is given by \(I = \{(s, t) \in S \times T \;|\; s = t\}\)
Another way of making new relations out of existing ones is by taking the composition.
Definition: if \(R_1\) is a relation between \(S\) and \(T\) and \(R_2\) is a relation between \(T\) and \(U\) then the composition \(R = R_1;R_2\) is the relation between \(S\) and \(U\) defined by \(sRu\) for \(s \in S\) and \(u \in U\), if and only if there is a \(t \in T\) with \(sR_1t\) and \(tR_2u\).
Proposition: suppose \(R_1\) is relation from \(S\) to \(T\), \(R_2\) a relation from \(T\) to \(U\) and \(R_3\) a relation from \(U\) to \(V\). Then \(R_1;(R_2;R_3) = (R_1;R_2);R_3\). Composing relations is associative.
Proof:
Suppose \(s \in S\) and \(v \in V\) with \(sR_1;(R_2;R_3)v\). Then a \(t \in T\) with \(sR_1t\) and \(t(R_2;R_3)v\) can be found. Then there is also a \(u \in U\) with \(tR_2u\) and \(uR_3v\). For this \(u\) there is \(sR_1;R_2u\) and \(uR_3v\) and hence \(s(R_1;R_2);R_3v\).
Similarly, if \(s \in S\) and \(v \in V\) with \(s(R_1;R_2);R_3v\). Then a \(u \in U\) with \(s(R_1;R_2)u\) and \(uR_3v\) can be found. Then there is also a \(t \in T\) with \(sR_1t\) and \(tR_2u\). For this \(t\) there is \(tR_2;R_3u\) and \(sR_1t\) and hence \(sR_1;(R_2;R_3)v\).
Transitive closure
Lemma: let \(\ell\) be a collection of relations \(R\) on a set \(S\). If all relations \(R\) in \(\ell\) are transitive, reflexive or symmetric then the relation \(\bigcap_{R \in \ell} R\) is also transitive, reflexive or symmetric respectively.
Proof:
Let \(\bar R = \bigcap_{R \in \ell} R\). Suppose all members of \(\ell\) are transitive. Then for all \(a,b,c \in S\) with \(a \bar R b\) and \(b \bar R c\) there is \(aRb\) and \(bRc\) for all \(R \in \ell\). Thus by transitivity of each \(R \in \ell\) there is also \(aRc\) for each \(R \in \ell\). Thus there is \(a \bar R c\). Hence \(\bar R\) is also transitive.
Proof for symmetric relation will follow.
Proof for reflexive relation will follow.
The above lemma makes it possible to define the reflexive, symmetric or transitive closure of a relation \(R\) on a set \(S\). It is the smallest reflexive, symmetric or transitive relation containing \(R\).
For example suppose \(R = \{(1,2), (2,2), (2,3), (5,4)\}\) is a relation on \(S = \{1, 2, 3, 4, 5\}\).
: The reflexive closure of \(R\) is then the relation
$$
\big\{(1,1), (1,2), (2,2), (2,3), (3,3), (4,4), (5,5), (5,4) \big\},
$$
the symmetric closure of $R$ is then the relation
$$
\big\{ (1,2), (2,1), (2,2), (2,3), (3,2), (4,5), (5,4) \big\},
$$
and the transitive clusure of $R$ is then the relation
$$
\{(1,2), (1,3), (2,2), (2,3), (5,4)\}.
$$
It may be observed that the reflexive closure of \(R\) equals the relation \(I \cup R\) and the symmetric closure equals \(R \cup R^\top\). For the transitive closure there is:
Proposition: \(\bigcup_{n > 0} R^n\) is the transitive closure of the relation \(R\) on a set \(S\).
Proof:
Define \(\bar R = \bigcup_{n>0} R^n\), to show that \(\bar R\) is the least transitive relation containing \(R\), \(\bar R\) must contain \(R\), must be transitive and must be the smallest set with both of those properties.
Since \(R \subseteq \bar R\), \(\bar R\) contains all of the \(R^i, i \in \mathbb{N}\), so in particular \(\bar R\) contains \(R\).
If \((s_1, s_2), (s_2, s_3) \in \bar R\), then \((s_1, s_2) \in R^j\) and \((s_2, s_3) \in R^k\) for some \(j,k\). Since composition is associative, \(R^{j+k} = R^j ; R^k\) and hence \((s_1, s_3) \in R^{j+k} \subseteq \bar R\).
We claim that if \(T\) is any transitive relation containing \(R\), then \(\bar R \subseteq T\). By taking \(R^n \subseteq \bar R \subseteq T \; \forall n \in \mathbb{N}\) .
: We first check for \(n=1\)
$$
R^1 = R \subseteq T.
$$
: Now suppose that for some \(k \in \mathbb{N}\) we have \(R^k \subseteq T\). Then by assumption \(R^{k+1} \subseteq T\). Let \((s_1, s_3) \in R^{k+1} = R^k ; R\), then \((s_1, s_2) \in R\) and \((s_2, s_3) \in R^k\) for some \(s_2\). Hence \((s_1, s_2), (s_2, s_3) \in T\) and by transitivity of \(T\), \((s_1, s_3) \in T\).
Hence if the claim holds for some \(k \in \mathbb{N}\) then it also holds for \(k+1\). The principle of natural induction implies now that \(\forall n \in \mathbb{N}\) we have \(R^n \subseteq \bar R \subseteq T\).
Suppose a relation \(R\) on a finite set \(S\) of size \(n\) is given by its adjacency matrix \(A_R\). Then Warshall's algorithm is an method for finding the adjacency matrix of the transitive closure of the relation \(R\).
Algorithm - Warshall's algoritm: for an adjacency matrix \(A_R = M_0\) of relation \(R\) on \(n\) elements there will be \(n\) steps taken to obtain the adjacency matrix of the transitive closure of the relation \(R\). Let \(R_i\) and \(C_i\) be the \(i\)th row and column of \(A_R\). In each step a new matrix \(M_i\) is obtained with \(C_i \times R_i\) added to \(M_{i-1}\). After \(n\) steps \(A_{\bar R}\) is obtained.
For example let \(R\) be an relation on \(S = \{1,2,3,4\}\) with \(R = \{(2,1), (2,3), (3,1), (3,4), (4,1), (4,3)\}\), determining the transitive closure \(\bar R\) of \(R\) with Warshall's algorithm.
: The adjacency matrix of the relation \(R\) is given by
$$
A_R = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}.
$$
We have $C_1 = \{2,3,4\}$ and $R_1 = \varnothing$, therefore $C_1 \times R_1 = \varnothing$ and no additions will be made, $M_1 = A_R$.
We have $C_2 = \varnothing$ and $R_2 = \{1,3\}, therefore $C_2 \times R_2 = \varnothing$ and no additions will be made, $M_2 = M_1$.
We have $C_3 = \{2,4\}$ and $R_3 = \{1,4\}$, therefore $C_3 \times R_3 = \{(2,1), (2,4), (4,1), (4,4)\}$ obtaining the matrix
$$
M_3 = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1\end{pmatrix}.
$$
We have $C_4 = \{2,3,4\} and $R_4 = \{1,3,4\}, therefore $C_4 \times R_4 = \{(2,1), (2,3), (2,4), (3,1), (3,3), (3,4), (4,1), (4,3), (4,4)\}$ obtaining the final matrix
$$
M_4 = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1\end{pmatrix} = A_{\bar R}.
$$