Σχέση (μαθηματικά)

Στα μαθηματικά, σχέση είναι μια συσχέτιση των στοιχείων ενός συνόλου με τα στοιχεία κάποιου άλλου. Η έννοια της σχέσης χρησιμοποιείται στα μαθηματικά για να μοντελοποιήσουμε έννοιες όπως μεγαλύτερο από, είναι ίσο με, είναι ισοδύναμο με κλπ. Η ίδια η έννοια της συνάρτησης ορίζεται ως μια σχέση ειδικού τύπου.

Αυστηρός ορισμός

Έστω $X$ και $Y$ δύο τυχαία σύνολα. Σχέση από το $X$ στο $Y$ ονομάζουμε κάθε υποσύνολο $R$ του καρτεσιανού γινομένου $X\times Y$:

$R\subseteq X\times Y=\lbrace (x,y)\mid x\in X,y\in Y\rbrace$.

Δηλαδή μια σχέση από ένα σύνολο $X$ σε ένα σύνολο $Y$ δεν είναι τίποτε άλλο από ένα σύνολο διατεταγμένων ζευγών. Το σύνολο $X$ ονομάζεται πεδίο ορισμού και το σύνολο $Y$ ονομάζεται σύνολο τιμών. Ειδικότερα αν $R$ είναι μια σχέση από το σύνολο $X$ στο σύνολο $X$, τότε λέμε ότι η $R$ είναι μια σχέση στο $X$. Η έκφραση $(x,y)\in R$ γράφεται διαφορετικά και ως εξής: $xRy$ ή $R(x,y)$ και λέμε ότι το $y$ σχετίζεται με το $x$ μέσω της σχέσης $R$ ή ακόμα ότι η σχέση $R$ ισχύει ανάμεσα στα στοιχεία $x$ και $y$. Το γράμμα $R$ μπορεί να αντικατασταθεί με οποιοδήποτε άλλο γράμμα, συχνά ακόμα και με σύμβολα όπως $<$, $>$, $+$, $=$ κ.α.

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

Για παράδειγμα αν για τα σύνολα $X$ και $Y$ έχουμε $X=\lbrace 1,2\rbrace$ και $Y=\lbrace 3,4,5\rbrace$, $R$ είναι μια σχέση στα σύνολα $X$ και $Y$ και $S$ είναι μια σχέση στο σύνολο $X$, τότε για την $R$ έχουμε:

$R\subseteq \lbrace (1,3),(1,4),(1,5),(2,3),(2,4),(2,5)\rbrace$

και για την $S$:

$S\subseteq \lbrace (1,2),(2,1),(1,1),(2,2)\rbrace$

Κλάσεις σχέσεων

Μερικές σημαντικές κλάσεις σχέσεων $R$, από ένα σύνολο $X$ σε ένα σύνολο $Y$ δίνονται παρακάτω:

• αριστερά ολική: για κάθε $x$ στο $X$ υπάρχει $y$ στο $Y$ τέτοιο ώστε $xRy$,
• επί ή δεξιά ολική: για κάθε $y$ στο $Y$ υπάρχει $x$ στο $X$ τέτοιο ώστε $xRy$,
• συναρτησιακή: για κάθε $x$ στο $X$ και $y,z$ στο $Y$ ισχύει ότι, αν $xRy$ και $xRz$ τότε $y=z$,
• ένα προς ένα: για κάθε $x$ και $z$ στο $X$ και για κάθε $y$ στο $Y$ ισχύει ότι αν $xRy$ και $zRy$ τότε $x=z$
• αμφιμονοσήμαντη: συναρτησιακή και αριστερά και δεξιά ολική

Σχέσεις σε ένα σύνολο

Ορισμένες σημαντικές κλάσεις διμελών σχέσεων σε ένα σύνολο X είναι οι εξής:

• ανακλαστική: για κάθε $x$ στο $X$ ισχύει $xRx$.
• συμμετρική: για κάθε $x,y$ στο $X$, αν ισχύει $xRy$ τότε ισχύει και yRx.
• αντισυμμετρική: για κάθε $x,y$ στο $X$, αν ισχύει $xRy$ και $yRx$ τότε $x=y$.
• ασυμετρική: για κάθε $x,y$ στο $X$, αν ισχύει $xRy$ τότε δεν ισχύει $yRx$.
• μεταβατική: για κάθε $x,y,z$ στο $X$, αν ισχύει $xRy$ και $yRz$ τότε $xRz$.
• ολική: για κάθε $x,y$ στο $X$, ισχύει $xRy$ ή $yRx$ ή και τα δύο.
• τριχοτομική: για κάθε $x,y$ στο $X$, ισχύει ακριβώς ένα από τα $xRy$, $yRx$ ή $x=y$.
• Ευκλείδεια: για κάθε $x,y,z$ στο $X$, αν ισχύει $xRy$ και $xRz$ τότε $yRz$ (και $zRy$).

Μια σχέση που είναι ανακλαστική, συμμετρική και μεταβατική ονομάζεται σχέση ισοδυναμίας. Μια σχέση που είναι ανακλαστική, αντισυμμετρική και μεταβατική ονομάζεται σχέση μερικής διάταξης. Μια σχέση μερικής διάταξης που είναι και ολική ονομάζεται σχέση ολικής διάταξης.

Η συνάρτηση ως σχέση

Έστω $X$ και $Y$ δύο μη κενά σύνολα. Μια σχέση $f$ από το σύνολο $X$ στο σύνολο $Y$ ονομάζεται συνάρτηση από το $X$ στο $Y$ αν:

• για κάθε $x$ στο $X$ υπάρχει $y$ στο $Y$ ώστε $xfy$
• αν $x$ ανήκει στο $X$, $y,z$ ανήκουν στο $Y$ και ισχύει $xfy$ και $xfz$ τότε $y=z$.

Επομένως, μια σχέση $f$ από το σύνολο $X$ στο σύνολο $Y$ ονομάζεται συνάρτηση από το $X$ στο $Y$ αν για κάθε $x$ στο $X$ υπάρχει μοναδικό $y$ στο $Y$ ώστε $xfy$. Με άλλα λόγια μια σχέση που είναι αριστερά ολική και συναρτησιακή, ονομάζεται συνάρτηση. Αν είναι μόνο συναρτησιακή τότε ονομάζεται μερική συνάρτηση.

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

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

Ιδιότητες

• Η σύνθεση σχέσεων είναι προσεταιριστική,
• Η αντίστροφη σχέση της $S\circ R$ είναι η σχέση $(S\circ R)^{-1}=R^{-1}\circ S^{-1}$,
• Η σύνθεση μερικών συναρτήσεων είναι μερική συνάρτηση,
• Η σύνθεση επί σχέσεων, είναι επί σχέση,
• Η σύνθεση ένα προς ένα σχέσεων, είναι ένα προς ένα.