Composición de Relaciones y Relación Inversa

Definición 3   Si $R$ es una relación entre $A$ y $B$, y $S$ es una relación entre $B$ y $C$, definimos la composición de $R$ y $S$ como la siguiente relación entre $A$ y $C$:

$$S\circ R:=\{(a,c)\in A\times C\mid \;$$existe$$\; b\in B \;$$tal que$$\; aRb \;$$y$$\; bSc\}.$$

Notemos que la composición de relaciones en general no puede ser conmutativa, es decir, $S\circ R\neq R\circ S$. Sin embargo, sí es asociativa:

Teorema 4   Si $R$ es una relación entre $A$ y $B$, $S$ una relación entre $B$ y $C$, y $T$ una relación entre $C$ y $D$, entonces

$$T\circ (R\circ S)= (T\circ R)\circ S.$$

Definición 5   Si $R$ es una relación entre $A$ y $B$, definimos la inversa de $R$ como la siguiente relación entre $B$ y $A$:

$$R^{-1}:=\{(b,a)\in B\times A\mid aRb\}.$$

Notemos que si $X$ es un subconjunto de $A$, entonces la imagen directa de $X$ por $R$ es igual a la imagen inversa de $X$ por $R^{-1}$, es decir, $R(X)=(R^{-1})^{-1}(X)$. También, si $Y$ es un subconjunto de $B$, la imagen inversa de $Y$ por $R$ es igual a la imagen directa de $Y$ por $R^{-1}$, así que no hay confusión con la notación $R^{-1}(Y)$.

Daremos ahora dos teoremas que relacionan los conceptos de composición de relaciones y de relación inversa.

Teorema 6   La relación inversa de una composición de relaciones es igual a la composición inversa de las relaciones inversas, es decir, si $R$ es una relación entre $A$ y $B$, y $S$ una relación entre $B$ y $C$, entonces

$$(S\circ R)^{-1}=R^{-1}\circ S^{-1}$$

Teorema 7   Si $R$ es una relación entre $A$ y $B$, entonces

1. $\mathrm{id}_{D_R}\subseteq R^{-1}\circ R$.
2. $\mathrm{id}_{I_R}\subseteq R\circ R^{-1}$.