Σχέση διάταξης

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

Κίνητρο

Η διάταξη είναι συνηθισμένη έννοια, με την οποία δουλεύουμε και στην καθημερινή ζωή. Πολλά πράγματα μπορούμε να τα διατάξουμε με κάποιον τρόπο – λέξεις με αλφαβητική σειρά, μαθητές στο σχολείο ανάλογα με το ύψος, εμπορεύματα ανάλογα με την τιμή. Όλα αυτά τα περιγράφει η σχέση διάταξης, που τη συμβολίζουμε συνήθως με το σύμβολο ≤. Σχετικά σύμβολα είναι: <, >, ≥. Η σημασία τους είναι προφανής.

Τι θα περιμέναμε από μια τέτοια σχέση; Ήδη από το σύμβολο είναι σαφές ότι στη σχέση διάταξης θα υπάρχουν στοιχεία που είναι ίδια – μας ενδιαφέρει δηλαδή να ορίσουμε τις ιδιότητες της σχέσης «μικρότερο ή ίσο». Μια τέτοια σχέση θα έπρεπε λοιπόν να είναι ανακλαστική. Πρέπει να ισχύει a ≤ a.

Τι άλλο; Σίγουρα δεν θα ισχύει η συμμετρία – αν έχουμε διάταξη ως προς την τιμή, τότε αν το αυτοκίνητο είναι φθηνότερο από το ψωμί, σίγουρα δεν θα είναι ταυτόχρονα το ψωμί φθηνότερο από το αυτοκίνητο. Τι θα περιμέναμε γενικά αν συνέβαινε a ≤ b και ταυτόχρονα b ≤ a; Θα είχε ποτέ νόημα αυτό; Ναι, αν ίσχυε a = b. Η μοναδική περίπτωση όπου η σειρά των στοιχείων που βάζουμε στη σχέση δεν έχει σημασία είναι όταν αυτά τα στοιχεία είναι ίδια – η διάταξη είναι λοιπόν αντισυμμετρική.

Τέλος, αν ξέρουμε ότι το αυτοκίνητο είναι ακριβότερο από το ψωμί και το αεροπλάνο είναι ακόμη ακριβότερο από το αυτοκίνητο, τότε περιμένουμε ότι το αεροπλάνο θα είναι σίγουρα ακριβότερο από το ψωμί. Αυτό περιγράφει η μεταβατικότητα.

Μερική διάταξη

Αυτό που ορίσαμε πριν από λίγο είναι στην πραγματικότητα μόνο μερική διάταξη, όχι ολική. Γιατί δεν είναι ολική; Ας δοκιμάσουμε να ορίσουμε διάταξη στα σύνολα. Με ποιον τρόπο θα μπορούσαμε να συγκρίνουμε δύο σύνολα;

Λέμε ότι το σύνολο A είναι μικρότερο ή ίσο από το σύνολο B, αν A ⊆ B, δηλαδή αν το A είναι υποσύνολο του B. Έχει νόημα, επειδή αν έχουμε A = {1, 2} και B = {1, 2, 3}, για το A θα μπορούσαμε να πούμε ότι είναι μικρότερο – το B περιέχει τα ίδια στοιχεία με το A και επιπλέον περιέχει τον αριθμό τρία. Έτσι για παράδειγμα θα ισχύει:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

Το πρόβλημα όμως είναι όταν θέλουμε να συγκρίνουμε αυτά τα σύνολα: A = {a, b} και B = {a, c}. Ποιο από αυτά είναι μικρότερο ή μεγαλύτερο; Το πρόβλημα είναι ότι, μολονότι και τα δύο σύνολα περιέχουν το στοιχείο a, το δεύτερο στοιχείο τους είναι διαφορετικό. Κανένα σύνολο δεν είναι υποσύνολο του άλλου, άρα δεν ισχύει ούτε A ≤ B ούτε B ≤ A. Τέτοια σύνολα είναι με βάση τη διάταξή μας μη συγκρίσιμα.

Γι' αυτό ένα σύνολο το λέμε ολικά διατεταγμένο ή αλλιώς αλυσίδα, αν κάθε δύο στοιχεία του συνόλου είναι συγκρίσιμα. Τέτοια σύνολα είναι για παράδειγμα τα αριθμητικά σύνολα με την κλασική διάταξη. Για κάθε δύο πραγματικούς αριθμούς a, b μπορείς να αποφασίσεις αν a ≤ b ή b ≤ a.

Παραδείγματα από τη ζωή

Παράδειγμα όπου συμφέρει να μη συγκρίνουμε θα μπορούσε να είναι η διάταξη ως προς την ομορφιά, όπου η σχέση < θα σήμαινε «είναι πιο άσχημος». Ίσως θα έπρεπε να το ορίσουμε αντίστροφα, το > ως «είναι πιο όμορφος», για να είμαστε πιο ορθοί :-). Μάλλον έχει νόημα να συγκρίνουμε μεταξύ τους δύο γυναίκες, για παράδειγμα «Μαρίνα» < «Αγάθη» με την έννοια ότι η Αγάθη είναι πιο όμορφη από τη Μαρίνα. Ή δύο άντρες: «Γιώργος» < «Νίκος» με την έννοια ότι ο Νίκος είναι πιο όμορφος από τον Γιώργο.

Το πρόβλημα είναι ότι δύσκολα μπορούμε να συγκρίνουμε την ομορφιά ενός άντρα και μιας γυναίκας. Είναι πιο όμορφη η Αγάθη ή ο Νίκος; Είναι πιο άσχημη η Μαρίνα ή ο Γιώργος; Καλύτερα να μην το ψάξουμε…

Αν στο τελευταίο παράδειγμα περιοριστούμε για παράδειγμα μόνο στις γυναίκες, μπορούμε να πούμε ότι έχουμε ολικά διατεταγμένο σύνολο, επειδή μπορούμε να συγκρίνουμε την ομορφιά όλων των γυναικών.

Ελαχιστικό και μεγιστικό στοιχείο, ελάχιστο και μέγιστο στοιχείο

Αν έχουμε ένα διατεταγμένο σύνολο M, το στοιχείο min ∈ M το ονομάζουμε ελαχιστικό, αν δεν υπάρχει x ∈ M τέτοιο ώστε x < min. Δηλαδή δεν μπορούμε να βρούμε στοιχείο που να είναι μικρότερο από το στοιχείο min.

Το στοιχείο max ∈ M το ονομάζουμε μεγιστικό, αν δεν υπάρχει x ∈ M τέτοιο ώστε x > max. Δηλαδή δεν μπορούμε να βρούμε στοιχείο που να είναι μεγαλύτερο.

Οι δύο προηγούμενες έννοιες διαφέρουν από τις έννοιες ελάχιστο και μέγιστο.

Το στοιχείο a ∈ M το ονομάζουμε ελάχιστο, αν για όλα τα x ∈ M ισχύει a ≤ x. Δηλαδή το ελάχιστο στοιχείο a είναι μικρότερο ή ίσο από όλα τα άλλα στοιχεία του συνόλου M.

Το στοιχείο b ∈ M το ονομάζουμε μέγιστο, αν για όλα τα x ∈ M ισχύει b ≥ x. Το μέγιστο στοιχείο b είναι μεγαλύτερο ή ίσο από όλα τα άλλα στοιχεία του συνόλου M.

Ποια είναι η διαφορά ανάμεσα στο μέγιστο και στο μεγιστικό στοιχείο; Μεγιστικά στοιχεία μπορεί να υπάρχουν περισσότερα, επειδή το σύνολο δεν είναι απαραίτητα ολικά διατεταγμένο. Αν επιστρέψουμε στο παράδειγμα της σύγκρισης ανθρώπων με βάση την εμφάνιση, μπορούμε να πούμε ότι η Αγάθη είναι η πιο όμορφη γυναίκα και ο Νίκος ο πιο όμορφος άντρας. Αυτά τα δύο πρόσωπα όμως δεν μπορούμε πια να τα συγκρίνουμε μεταξύ τους, δεν ξέρουμε αν είναι πιο όμορφη η Αγάθη ή ο Νίκος.

Και τα δύο στοιχεία είναι λοιπόν μεγιστικά. Δεν μπορούμε να βρούμε πρόσωπο που να είναι πιο όμορφο από τον Νίκο – ο Νίκος είναι πιο όμορφος από όλους τους άλλους άντρες και με τις γυναίκες δεν μπορούμε να τον συγκρίνουμε. Παρόμοια για την Αγάθη – αυτή είναι πιο όμορφη από όλες τις γυναίκες και με τους άντρες δεν μπορούμε να τη συγκρίνουμε.

Κανένας από τους δύο όμως δεν είναι μέγιστος, με αυτή την έννοια ο πιο όμορφος. Επειδή για να είναι ο Νίκος ο πιο όμορφος/μέγιστος, θα έπρεπε να είναι πιο όμορφος από όλα τα πρόσωπα, και από όλες τις γυναίκες. Αλλά είπαμε ήδη ότι με τις γυναίκες δεν μπορούμε να τον συγκρίνουμε, γι' αυτό δεν μπορεί να είναι ο πιο όμορφος άνθρωπος, είναι μόνο, στην ορολογία της θεωρίας διάταξης, μεγιστικός.

Μάλλον εύκολα φαίνεται ότι αν ένα σύνολο έχει μέγιστο στοιχείο, τότε αυτό το στοιχείο είναι ταυτόχρονα και μεγιστικό. Αν το στοιχείο a είναι μεγαλύτερο από όλα τα άλλα στοιχεία του συνόλου (ορισμός του μέγιστου στοιχείου), τότε σίγουρα δεν θα βρούμε στοιχείο που να είναι ακόμη μεγαλύτερο (ορισμός του μεγιστικού στοιχείου).

Παράδειγμα συνόλου που έχει μέγιστο και ελάχιστο στοιχείο είναι το κλειστό διάστημα [0, 1]. Αν επιλέξουμε το ίδιο διάστημα, αλλά ανοικτό, δεν θα είχε ούτε μέγιστο ούτε ελάχιστο στοιχείο: (0, 1).

Αν θέλαμε άπειρα ελαχιστικά στοιχεία, θα μπορούσαμε να ορίσουμε τη διάταξη R ως εξής. Πρώτα ορίζουμε βοηθητικά σύνολα M_x. Τα σύνολα θα έχουν την εξής μορφή: για όλα τα x από το διάστημα (0, 1) ορίζουμε το σύνολο M_x = {y | y = x + n}, όπου n ακέραιος μη αρνητικός αριθμός. Έτσι παίρνουμε για παράδειγμα τέτοια σύνολα:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Σε κάθε σύνολο M_x ορίζουμε την κλασική διάταξη, που τη συμβολίζουμε R_x. Στο τέλος απλώς ενώνουμε αυτές τις διατάξεις: R = ∪ R_x. Σε αυτή τη διάταξη μπορούμε λοιπόν να συγκρίνουμε πάντα μόνο μέσα στις αρχικές αλυσίδες. Έτσι μπορούμε να βρούμε αν 0,5 ≤ 2,5, αλλά δεν μπορούμε να βρούμε αν 0,5 ≤ 2,7, επειδή αυτοί οι αριθμοί δεν βρίσκονταν στο ίδιο σύνολο M_x και έτσι η μεταξύ τους σχέση δεν είναι ορισμένη.

Σε αυτή τη σχέση διάταξης ισχύει λοιπόν ότι κάθε στοιχείο του διαστήματος (0, 1) είναι ελαχιστικό στοιχείο.

Διαγράμματα Hasse

Τα διατεταγμένα σύνολα μπορούμε να τα σχεδιάσουμε με τη βοήθεια διαγράμματος Hasse. Πρόκειται για γράφημα στο οποίο οι κορυφές παριστάνουν τα στοιχεία του συνόλου και η ακμή ανάμεσα στις κορυφές (a, b) μας λέει ότι a < b και ταυτόχρονα δεν υπάρχει c τέτοιο ώστε a < c < b. Δηλαδή ανάμεσα στα στοιχεία a και b δεν υπάρχει πια κανένα άλλο στοιχείο. Επιπλέον πρέπει στο γράφημα η κορυφή a να είναι χαμηλότερα από την κορυφή b. Παράδειγμα διαγράμματος Hasse:

Αυτό το διάγραμμα Hasse παριστάνει το διατεταγμένο σύνολο {A, B, C, D, E, F}. Ισχύει: A < B, B < E, και φυσικά ισχύει και A < E, αλλά ανάμεσα σε αυτές τις κορυφές δεν υπάρχει ακμή, επειδή υπάρχει η κορυφή B, για την οποία ισχύει A < B < E. Τα στοιχεία E και D είναι μη συγκρίσιμα, επειδή κανένα δεν βρίσκεται πάνω ή κάτω από το άλλο.

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

Άλλο παράδειγμα μπορεί να είναι το σύνολο: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Αυτοί είναι οι φυσικοί διαιρέτες του αριθμού 60. Η διάταξη ως προς τη διαιρετότητα μπορεί να απεικονιστεί ως εξής:

Η διάταξη ως προς τη διαιρετότητα σημαίνει ότι (a, b) ∈ R αν και μόνο αν το a διαιρεί το b. Από το διάγραμμα μπορούμε να παρατηρήσουμε ότι κάθε αριθμός έχει πάνω από αυτόν τους αριθμούς που διαιρεί. Για παράδειγμα πάνω από τον αριθμό 6 βρίσκονται οι αριθμοί 12, 30 και 60. Πάνω από τον αριθμό 4 βρίσκονται οι αριθμοί 12, 20 και 60. Κ.ο.κ. Αντίθετα ο αριθμός 3 δεν έχει πάνω από αυτόν τον αριθμό 10, επειδή δεν τον διαιρεί – προσοχή, ο αριθμός 10 βρίσκεται οπτικά πάνω από τον αριθμό 3, αλλά δεν οδηγεί σε αυτόν καμία γραμμή «από κάτω προς τα πάνω». Αν από τον αριθμό 3 κινηθούμε μόνο προς τα πάνω, μπορούμε να πάμε στους αριθμούς 15 και 6 και από αυτούς στον αριθμό 30. Στον αριθμό 10 θα φτάναμε μόνο αν κατεβαίναμε πάλι κάτω, κάτι που δεν επιτρέπεται.