Σύνθεση σχέσεων

Παράδειγμα δύο σχέσεων από το $A$ στο $B$, και από το $B$ στο $C$.

Η σχέση από το $A$ στο $C$ που είναι η σύνθεση των δύο παραπάνω. Παρατηρήστε ότι $(a,c_{)}$ αν υπάρχει ένα μονοπάτι από το $a$ στο $c$ (μέσω κάποιου στοιχείου στο $B$.

Στα μαθηματικά, η σύνθεση σχέσεων είναι ένας τρόπος με τον οποίο σχηματίζουμε μια νέα σχέση από δύο δεδομένες σχέσεις $R$ και $S$ και την οποία συμβολίζουμε με $S\circ R$. Ειδική κατηγορία σύνθεσης σχέσεων είναι η σύνθεση συναρτήσεων.

Ορισμός

Αν $R\subseteq X\times Y$ και $S\subseteq Y\times Z$ είναι δύο διμελείς σχέσεις, τότε η σύνθεση τους $S\circ R$ είναι η σχέση:

$S\circ R=\{(x,z)\in X\times Z\mid \exists y\in Y:(x,y)\in R,(y,z)\in S\}\subseteq X\times Z$.

Με άλλα λόγια η σχέση $S\circ R$ είναι η σχέση στην οποία ανήκουν όλα τα διατεταγμένα ζεύγη $(x,z)$ για τα οποία ισχύει το εξής: υπάρχει $y$ στο $Y$ τέτοιο ώστε το $(x,y)$ να ανήκει στη $R$ και το $(y,z)$ να ανήκει στη $S$.

Παραδείγματα

Θεωρούμε τα σύνολα $A=\{a_{1},a_{2},a_{3},a_{4}\}$, $B=\{b_{1},b_{2},b_{3},b_{4},b_{5}\}$ και $C=\{c_{1},c_{2},c_{3},c_{4}\}$. Έστω οι σχέσεις $R\subseteq A\times B$ με

$R=\{(a_{1},b_{2}),(a_{1},b_{4}),(a_{2},b_{1}),(a_{2},b5),(a_{3},b_{4}),(a_{3},b_{5}),(a_{4},b_{5})\}$,

και $S\subseteq B\times C$ με

$S=\{(b_{1},c_{1}),(b_{2},c_{3}),(b_{2},c_{4}),(b_{3},c_{1}),(b_{3},c_{2}),(b_{4},c_{4})\}$.

Η σύνθεση αυτών των δύο είναι η σχέση

$S\circ R=\{(a_{1},c_{3}),(a_{1},c_{4}),(a_{2},c_{1}),(a_{3},c_{4})\}$.

Ιδιότητες

Η σύνθεση σχέσεων ικανοποιεί τις παρακάτω ιδιότητες:

• Είναι προσεταιριστική, δηλαδή $(R_{1}\circ R_{2})\circ R_{3}=R_{1}\circ (R_{2}\circ R_{3})$.

Απόδειξη  

Έστω ότι έχουμε τρεις σχέσεις $R_{1}\subseteq W\times X$, $R_{1}\subseteq X\times Y$ και $R_{3}\subseteq Y\times Z$. Τότε για κάθε $w\in W$ και $z\in Z$ ισχύει ότι:

${\begin{aligned}w((R_{1}\circ R_{2})\circ R_{3})z&\Leftrightarrow \exists y\in Y.w(R_{1}\circ R_{2})y\wedge yR_{3}z\\&\Leftrightarrow \exists y\in Y.\exists x\in X.wR_{1}x\wedge xR_{2}y\wedge yR_{3}z\\&\Leftrightarrow \exists x\in X.wR_{1}x\wedge \exists y\in Y.xR_{2}y\wedge yR_{3}z\\&\Leftrightarrow \exists x\in X.wR_{1}x\wedge x(R_{2}\circ R_{3})z\\&\Leftrightarrow w(R_{1}\circ (R_{2}\circ R_{3}))z.\end{aligned}}$

Επομένως, οι δύο σχέσεις είναι ίσες.

• Η αντίστροφη σχέση της $S\circ R$ είναι η σχέση $(S\circ R)^{-1}=R^{-1}\circ S^{-1}$.

Απόδειξη  

Για μία σχέση $S$ και την αντίστροφή της $S^{-1}$ ισχύει ότι:

$S\circ S^{-1}=S^{-1}\circ S=I$,

όπου $I$ είναι η ταυτοτική σχέση (και για την οποία ισχύει $S\circ I=I\circ S=S$). Επομένως, αρκεί να επιβεβαιώσουμε τις δύο ισότητες. Χρησιμοποιώντας ότι η σύνθεση σχέσεων είναι προσεταιριστική, έχουμε ότι

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

Παρομοίως,

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

• Η σύνθεση μερικών συναρτήσεων είναι μερική συνάρτηση.
• Η σύνθεση επί σχέσεων, είναι επί σχέση.
• Η σύνθεση ένα προς ένα σχέσεων, είναι ένα προς ένα.