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

Στα μαθηματικά, η σύνθεση σχέσεων είναι ένας τρόπος με τον οποίο σχηματίζουμε μια νέα σχέση από δύο δεδομένες σχέσεις $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$.

Ιδιότητες

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

• Είναι προσεταιριστική, δηλαδή $(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$.

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