Residuation in $Rel(X)$

15 Views Asked by At

Following the definition from residuated lattice, then we have that for any $R$, $S$ and $T$ in $Rel(X)$ (all the binary relations on a set $X$): $$ R ; S \subseteq T \iff S \subseteq R\backslash T \iff R \subseteq T/S\,. $$ where $;$ is the composition of relations and where, if $A,B \in Rel(X)$, then $$ A \backslash B = (A;B^-)^- $$ and $$ B/A = (B^-;A^-)^- $$ where with $A^-$ we mean the complement of the relation (see also).

Now I wanted to get a feeling of what these subsets of $X\times X$ are by considering an example, but I there is something wrong in what I am doing.

Take $X = \{1,2,3\}$, and let:

  • $R = \{(1,1),(2,2),(3,3),(2,1),(3,2)\}$ and
  • $S = \{(1,2),(1,3),(2,2),(3,1),(3,2),(3,3)\}$.

Then we have that $R;S = \{(1,2),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3)\}$.

Take $T = (R;S) \cup \{(1,1)\}$, so that $R;S \subseteq T$.

Then we have $T^- = \{(2,1)\}$ and thus $R;T^- = \{(2,1),(3,1)\}$.

But now we have that: $$ S\not\subseteq R\backslash T=(R;T^-)^- = \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)\} $$ as $\{(3,1)\} \in S$ but $\{(3,1)\}\notin R\backslash T$.

If we choose to add $\{(2,1)\}$ to $R;S$ to form $T$ then I see things work out fine.