# 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.

<br>

> *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$.

<br>

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

$$
\begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1\end{pmatrix}
$$

<br>

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.

<br>

> *Lemma*: let $R$ be an equivalence relation on a set $S$. If $b \in [a]_R$, then $[b]_R = [a]_R$.

??? note "*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$. 

<br>

> *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$.

<br>

> *Theorem*: let $R$ be an equivalence relation on a set $S$. Then the set $S/R$ of $R$-equivalence classes partitions the set $S$. 

??? note "*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$.

<br>

> *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.

??? note "*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.

??? note "*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$. 

??? note "*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](#composition-of-relations), $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}.
    $$