.
Θεωρία Διάταξης είναι ένας κλάδος των μαθηματικών που ερευνά τη διαισθητική έννοια της διάταξης στο δυαδικό σύστημα σχέσεων. Παρέχει ένα επίσημο πλαίσιο για την περιγραφή των καταστάσεων, όπως "αυτό είναι μικρότερο από αυτό" ή "αυτό προηγείται εκείνου". Το άρθρο αυτό εισάγει το πεδίο και παρέχει τους βασικούς ορισμούς. Μια λίστα θεωρητικών διατάξεων μπορεί να βρεθεί στο γλωσσάριο της θεωρητικής διάταξης.
Ιστορικό και κίνητρα
Οι διατάξεις είναι παντού στα μαθηματικά και σε συναφείς τομείς όπως η επιστήμη των υπολογιστών. Η πρώτη διάταξη γίνεται συχνά αντικείμενο συζήτησης στο δημοτικό σχολείο που είναι η βάση για τους φυσικούς αριθμούς, π.χ. "το 2 είναι μικρότερο από το 3", "το 10 είναι μεγαλύτερο από το 5", ή "Ο Tom έχει λιγότερα μπισκότα από τη Sally;". Αυτή η διαισθητική έννοια μπορεί να επεκταθεί και σε διατάξεις σε άλλα σύνολα αριθμών, όπως στους ακέραιους και στους πραγματικούς αριθμούς. Η ιδέα ότι κάποιος αριθμός είναι μεγαλύτερος ή μικρότερος από έναν άλλο αριθμό συνιστά μία από τις βασικές διαισθητικές προσεγγίσεις των συστημάτων αρίθμησης (σύγκρινε με τα συστήματα αρίθμησης) γενικότερα (αν και συνήθως το ενδιαφέρον εστιάζεται στην πραγματική διαφορά δύο αριθμών, η οποία δεν δίνεται από τη σειρά ). Ένα άλλο γνωστό παράδειγμα διάταξης είναι η λεξικογραφική σειρά των λέξεων σε ένα λεξικό.
Οι παραπάνω τύποι εντολών έχουν μια ειδική ιδιότητα: κάθε στοιχείο μπορεί να συγκριθεί με οποιοδήποτε άλλο στοιχείο, δηλαδή είναι μεγαλύτερο, μικρότερο ή ίσο. Ωστόσο, αυτή δεν είναι πάντα η επιθυμητή απαίτηση. Για παράδειγμα, σκεφτείτε το υποσύνολο στη διάταξη των συνόλων. Εάν ένα σύνολο Α περιλαμβάνει όλα τα στοιχεία του συνόλου Β, τότε το Β λέγεται ότι είναι μικρότερο από ή ίσο με το Α. Ωστόσο, υπάρχουν ορισμένα σύνολα, που δεν μπορούν να συσχετιστούν με αυτό τον τρόπο. Οπότε όταν ένα σύνολο περιέχει ορισμένα στοιχεία που δεν βρίσκονται στο άλλο, τα δύο σύνολα δεν μπορούν να συσχετιστούν με τη διάταξη του υποσυνόλου. Ως εκ τούτου, το υποσύνολο είναι μόνο μια μερική διάταξη, σε αντίθεση με το σύνολο των διατάξεων που δόθηκε προηγουμένως.
Η θεωρία διάταξης συλλαμβάνει τη διαίσθηση των διατάξεων που προκύπτει από τέτοια παραδείγματα σε ένα γενικότερο περιβάλλον. Αυτό επιτυγχάνεται με τον καθορισμό ιδιοτήτων που μια σχέση ≤ πρέπει να είναι μια μαθηματική σειρά. Αυτή η πιο αφηρημένη προσέγγιση έχει νόημα, επειδή μπορεί κανείς να αντλήσει πολλά θεωρήματα από το γενικό περιβάλλον, χωρίς να επικεντρώνεται στις λεπτομέρειες κάποιας συγκεκριμένης διάταξης. Αυτές οι ιδέες μπορούν να μεταφερθούν εύκολα σε πολλές , λιγότερο αφηρημένες εφαρμογές.
Καθοδηγούμενες από την ευρεία πρακτική χρήση των διατάξεων, πολλές ειδικές μορφές διατεταγμένων συνόλων έχουν οριστεί, μερικές από τις οποίες έχουν αναπτυχθεί σε μαθηματικούς τομείς. Επιπλέον, η θεωρία δεν περιορίζεται στις διάφορες κατηγορίες της διάταξης σχέσεων, αλλά θεωρεί επίσης σκόπιμο τις αρμοδιότητες μεταξύ τους. Ένα απλό παράδειγμα μιας θεωρητικής διάταξης για τις συναρτήσεις προέρχεται από την ανάλυση, όπου τακτικά βρίσκεται η μονοτονία των συναρτήσεων.
Βασικοί ορισμοί
Αυτή η ενότητα παρουσιάζει διατεταγμένα σύνολα που είναι βασισμένα πάνω στις έννοιες της θεωρίας συνόλων, στην αριθμητική, και στις διμελείς σχέσεις.
Μερικώς διατεταγμένα σύνολα
Οι διατάξεις είναι ειδικές δυαδικές σχέσεις. Ας υποθέσουμε ότι το P είναι ένα σύνολο και ότι αυτή ≤ είναι μια σχέση στο P. Τότε η σχέση ≤ είναι μια μερική διάταξη, αν είναι ανακλαστική, αντισυμμετρική και μεταβατική, δηλαδή, για κάθε a, b και c που ανήκουν στο P, έχουμε ότι:
a ≤ a (ανακλαστική)
αν a ≤ b and b ≤ a τότε a = b (αντισυμμετρική)
αν a ≤ b and b ≤ c τότε a ≤ c (μεταβατική).
Ένα σύνολο με μερική διάταξη, ονομάζεται μερικώς διατεταγμένο σύνολο ή απλά διατεταγμένο σύνολο. Με τον έλεγχο αυτών των ιδιοτήτων, αμέσως καταλαβαίνει κανείς ότι οι γνωστές διατάξεις για τους φυσικούς, ακέραιους, ρητούς και πραγματικούς αριθμούς, βασίζονται όλες στην παραπάνω έννοια. Ωστόσο, έχουν την επιπλέον ιδιότητα να είναι πλήρη, δηλαδή, για κάθε a και b που ανήκουν στο σύνολο P, έχουμε ότι:
a ≤ b ή b ≤ a (ολότητα).
Αυτές οι διατάξεις μπορούν επίσης να ονομαστούν γραμμικές διατάξεις ή αλυσίδες. Ενώ οι περισσότερες κλασσικές διατάξεις είναι γραμμικές, η διάταξη υποσύνολο σε ένα σύνολο, αποτελεί ένα παράδειγμα, που δεν ανήκει σε αυτήν την περίπτωση. Ένα άλλο παράδειγμα δίνεται από τη σχέση διαιρετότητας "|". Για δύο φυσικούς αριθμούς n και m, γράφουμε n | m, εάν ο n διαιρεί τον m χωρίς να αφήνει υπόλοιπο. Εύκολα διαπιστώνει κανείς ότι αυτή η σχέση δίνει μια μερική διάταξη. Η ταυτοτική σχέση = για οποιοδήποτε σύνολο είναι επίσης μια μερική διάταξη, με την οποία κάθε δύο διακριτά στοιχεία είναι ασύγκριτα. Είναι επίσης η μόνη σχέση που είναι ταυτόχρονα και μερική διάταξη και σχέση ισοδυναμίας. Πολλές από τις προηγμένες ιδιότητες των μερικά διατεταγμένων συνόλων είναι ενδιαφέρουσες κυρίως για τις μη γραμμικές διατάξεις.
Απεικόνιση ενός μερικά διατεταγμένου συνόλου
Διάγραμμα Hasse για το σύνολο {x,y,z}
Τα διαγράμματα Hasse μπορούν να αναπαραστήσουν οπτικά τα στοιχεία και τις σχέσεις μιας μερικής διάταξης. Σε ένα τέτοιο διάγραμμα, κάθε στοιχείο του συνόλου συμβολίζεται με μια κορυφή και η σχέση διάταξης υποδεικνύεται από τις δύο άκρες και τη σχετική τοποθέτηση των κορυφών. Οι διατάξεις απεικονίζονται από κάτω προς τα πάνω: αν ένα στοιχείο x είναι μικρότερο από (προηγείται) y τότε υπάρχει ένα μονοπάτι από το x στο y που κατευθύνεται προς τα πάνω. Συχνά είναι απαραίτητο για τη σύνδεση των άκρων κάποια στοιχεία να διασταυρώνονται μεταξύ τους, αλλά δεν πρέπει ποτέ να βρίσκονται στοιχεία μέσα σε ένα άκρο. Για παράδειγμα να σχεδιάσετε το διάγραμμα Hasse για το σύνολο των φυσικών αριθμών που είναι μικρότεροι από ή ίσοι με το 13, με εντολή | (τη σχέση διαιρεί).
Ακόμη και ορισμένα άπειρα σύνολα μπορούν να απεικονιστούν με την υπέρθεση αποσιωπητικών (...) σε ένα πεπερασμένο υποσύνολο. Αυτό λειτουργεί καλά για τους φυσικούς αριθμούς, αλλά αποτυγχάνει για τους πραγματικούς, όπου δεν υπάρχει ο αμέσως επόμενος διάδοχος του 0. Ωστόσο, αρκετά συχνά μπορεί κανείς να αποκτήσει μια διαίσθηση που σχετίζεται με διαγράμματα παρόμοιου είδους.
Ειδικά στοιχεία μέσα σε μια διάταξη
Σε ένα μερικώς διατεταγμένο σύνολο μπορεί να υπάρχουν κάποια στοιχεία που παίζουν έναν ιδιαίτερο ρόλο. Το πιο βασικό παράδειγμα δίνεται από το ελάχιστο στοιχείο ενός μερικά διατεταγμένου συνόλου. Για παράδειγμα, το 1 είναι το ελάχιστο στοιχείο των θετικών ακεραίων και το κενό σύνολο είναι το ελάχιστο στοιχείο από όλα τα σύνολα σύμφωνα με την διάταξη του υποσυνόλου. Τυπικά, ένα στοιχείο m είναι το ελάχιστο στοιχείο, εφόσον:
m ≤ a, για κάθε στοιχείο a που ανήκει στη διάταξη.
Ο συμβολισμός 0 χρησιμοποιείται συχνά για να εκφράσει το ελάχιστο στοιχείο, ακόμα και όταν δεν υπάρχουν αριθμοί. Ωστόσο, σε διατάξεις για σύνολα αριθμών, αυτή η σημειογραφία μπορεί να είναι ακατάλληλη ή ασαφής, δεδομένου ότι ο αριθμός μηδέν δεν είναι πάντα το ελάχιστο. Ένα παράδειγμα δίνεται από την παραπάνω σχέση διαιρετότητας |, όπου το 1 είναι το ελάχιστο στοιχείο, δεδομένου ότι διαιρεί όλους τους άλλους αριθμούς. Αντίθετα, το 0 είναι ο αριθμός που διαιρείται από όλους τους άλλους αριθμούς. Ως εκ τούτου είναι το μέγιστο στοιχείο της διάταξης. Άλλες συχνές συνθήκες για τα ελάχιστα και μέγιστα στοιχεία είναι το κάτω και το πάνω ή το μηδέν και η μονάδα.
Ελάχιστα και μέγιστα στοιχεία μπορεί να μην υπάρχουν, όπως δείχνει το παράδειγμα των πραγματικών αριθμών. Αλλά αν υπάρχουν, είναι πάντα μοναδικά. Αντίθετα, θεωρούμε τη σχέση διαιρετότητας | στο σύνολο {2,3,4,5,6}. Παρά το γεγονός ότι αυτό το σύνολο δεν έχει ούτε άνω ούτε κάτω φράγμα, τα στοιχεία 2, 3, και 5 δεν έχουν στοιχεία από κάτω τους, ενώ τα στοιχεία 4, 5, και 6 δεν έχουν κανένα στοιχείο από πάνω τους. Τέτοια στοιχεία ονομάζονται ελάχιστα και μέγιστα, αντίστοιχα. Τυπικά, ένα στοιχείο το m είναι ελάχιστο, αν:
a ≤ m συνεπάγεται a = m, για κάθε στοιχείο a της διάταξης.
Η αλλαγή του ≤ με το ≥ δίνει τον ορισμό του μέγιστου. Όπως δείχνει το παράδειγμα, μπορεί να υπάρχουν πολλά μέγιστα στοιχεία και ορισμένα στοιχεία μπορεί να είναι και μέγιστα και ελάχιστα (π.χ. 5 από το προηγούμενο παράδειγμα). Ωστόσο, αν υπάρχει ένα ελάχιστο στοιχείο, τότε είναι το μόνο ελάχιστο στοιχείο της διάταξης. Και πάλι, στις άπειρες σχέσεις μερικής διάταξης δεν υπάρχουν πάντα μέγιστα στοιχεία - το σύνολο όλων των πεπερασμένων υποσυνόλων ενός άπειρου συνόλου, με διάταξη το υποσύνολο, παρέχει ένα από τα πολλά αντιπαραδείγματα. Ένα σημαντικό εργαλείο για τη διασφάλιση της ύπαρξης μέγιστων στοιχείων υπό ορισμένες συνθήκες είναι το Λήμμα του Zorn. Τα υποσύνολα μερικώς διατεταγμένων συνόλων, διατηρούν την ίδια διάταξη. Αυτό το έχουμε ήδη εφαρμόσει θεωρώντας το υποσύνολο {2,3,4,5,6} των φυσικών αριθμών με την επαγόμενη διατεταγμένη διαιρετότητα. Τώρα υπάρχουν επίσης στοιχεία ενός συνόλου που είναι ειδικά, σε σχέση με κάποιο υποσύνολο της διάταξης. Αυτό οδηγεί στον ορισμό των άνω φραγμάτων. Λαμβάνοντας υπόψη ένα υποσύνολο S κάποιου μερικώς διατεταγμένου συνόλου P, ένα άνω φράγμα του S είναι ένα στοιχείο b του P που είναι πάνω από όλα τα στοιχεία του S. Τυπικά, αυτό σημαίνει ότι
s ≤ b, για όλα τα s του συνόλου S.
Τα κάτω φράγματα και πάλι καθορίζονται αντιστρέφοντας τη διάταξη. Για παράδειγμα, -5 είναι ένα κάτω φράγμα των φυσικών αριθμών ως ένα υποσύνολο του συνόλου των ακεραίων. Λαμβάνοντας υπόψη ένα σύνολο συνόλων, ένα άνω φράγμα για αυτά τα σύνολα βρίσκεται από τα διατεταγμένα υποσύνολά τους και είναι η ένωση αυτών.Στην πραγματικότητα, αυτό το ανώτατο όριο είναι πολύ ιδιαίτερο: αυτό είναι το μικρότερο σύνολο που περιέχει όλα τα σύνολα. Ως εκ τούτου, έχουμε βρει το ελάχιστο άνω φράγμα του συνόλου των συνόλων. Αυτή η έννοια ονομάζεται επίσης supremum ή join, και για ένα σύνολο S συμβολίζεται ως sup(S) ή vS για το ελάχιστο άνω φράγμα της. Αντίθετα, το μέγιστο κάτω φράγμα είναι γνωστό ως infimum ή meet και συμβολίζεται inf(S) ή ^S. Αυτές οι έννοιες διαδραματίζουν σημαντικό ρόλο σε πολλές εφαρμογές της θεωρίας διάταξης. Για δύο στοιχεία x και y, μπορεί να συμβολίσει κανείς x v y και x ^ y για το sup({x,y}) και το inf({x,y}), αντίστοιχα.
Για ένα άλλο παράδειγμα, σκεφτείτε ξανά τη σχέση | σχετικά με τους φυσικούς αριθμούς. Το ελάχιστο άνω φράγμα τουλάχιστον δύο αριθμών είναι ο μικρότερος αριθμός που διαιρείται και με τους δύο, δηλαδή το ελάχιστο κοινό πολλαπλάσιο των αριθμών. Τα μέγιστα κάτω φράγματα με τη σειρά τους, δίνονται από τον μέγιστο κοινό διαιρέτη.
Δυαδικότητα
Στους προηγούμενους ορισμούς, είχαμε επισημάνει ότι μια έννοια μπορεί να ορίζεται απλά αντιστρέφοντας τη διάταξη σε ένα πρώην ορισμό. Αυτή είναι η περίπτωση που έχουμε "μικρότερο" και "μεγαλύτερο", "ελάχιστο" και "μέγιστο", "ανώτερο φράγμα" και "κατώτερο φράγμα", και ούτω καθεξής. Αυτή είναι μια γενική ιδιότητα της θεωρίας διάταξης ώστε: Μια δεδομένη διάταξη μπορεί να αντιστραφεί μόνο από την αλλαγή της κατεύθυνσης του συμβόλου διάταξης, εικονογραφικά έχουμε την αναστροφή του διαγράμματος Hasse από πάνω προς τα κάτω. Αυτό υποκύπτει στη λεγόμενη διπλή αντιστροφή, ή αντίθετη διάταξη. Κάθε θεωρητικός ορισμός της διάταξης έχει διπλή λειτουργία: περιλαμβάνει και την έννοια που αποκτά κανείς με την εφαρμογή του ορισμού στην αντίστροφη διάταξη. Δεδομένου ότι όλες οι έννοιες είναι συμμετρικές, αυτό το εγχείρημα διατηρείται και στα θεωρήματα της μερικής διάταξης. Για ένα δεδομένο μαθηματικό αποτέλεσμα, μπορεί κανείς απλά να αντιστρέψει τη διάταξη και να αντικαταστήσει όλους τους ορισμούς από τους αντίστροφους τους, αποκομίζοντας με αυτόν τον τρόπο ακόμα ένα έγκυρο θεώρημα. Αυτό είναι σημαντικό και χρήσιμο, επειδή κάποιος αποκτά δύο θεωρήματα που πηγάζουν από ένα. Περισσότερες λεπτομέρειες και παραδείγματα μπορούν να βρεθούν στο άρθρο Δυαδικότητα στη θεωρία διάταξης.
Κατασκευή νέων σχέσεων διάταξης
Υπάρχουν πολλοί τρόποι για να κατασκευαστούν οι σχέσεις διάταξης που προκύπτουν από άλλες σχέσεις διάταξης. Η διπλή έννοια της διάταξης είναι ένα παράδειγμα. Μία άλλη σημαντική κατασκευή αποτελεί το καρτεσιανό γινόμενο δύο μερικώς διατεταγμένων συνόλων, που λαμβάνεται ως αποτέλεσμα της διάταξης στα ζεύγη των στοιχείων τους. Η διάταξη ορίζεται από τη σχέση (a, x) ≤ (b, y) αν (και μόνο αν) a ≤ b και x ≤ y. (Παρατηρήστε προσεκτικά ότι υπάρχουν τρεις διαφορετικές σημασίες για το σχετικό σύμβολο ≤ στον ορισμό αυτό). Η ασυνεχής ένωση δύο μερικώς διατεταγμένων συνόλων είναι ένα άλλο χαρακτηριστικό παράδειγμα της κατασκευής σχέσεων διάταξης ,όπου η νέα σχέση διάταξης αποτελεί την (ασυνεχή) ένωση των αρχικών διατάξεων. Κάθε μερική διάταξη ≤ αναδεικνύει τη λεγόμενη αυστηρή διάταξη <, ορίζοντας a < b αν a ≤ b και όχι b ≤ a. Αυτός ο μετασχηματισμός μπορεί να αναστραφεί θέτοντας a ≤ b αν a < b ή a = b. Οι δύο έννοιες είναι ισοδύναμες, και σε ορισμένες περιπτώσεις κρίνεται αναγκαίο να μπορεί να διακρίνει κανείς με ποια από τις δύο είναι πιο βολικό να εργαστεί.
Συναρτήσεις με διατάξεις
Είναι λογικό να εξεταστούν οι συναρτήσεις μεταξύ μερικώς διατεταγμένων συνόλων που έχουν ορισμένες πρόσθετες ιδιότητες οι οποίες σχετίζονται με τις σχέσεις διάταξης των δύο συνόλων. Ο πιο θεμελιώδης όρος που εμφανίζεται σε αυτό το συγκείμενο είναι αυτός της μονοτονίας. Μία συνάρτηση f από ένα μερικώς διατεταγμένο σύνολο P σε ένα μερικώς διατεταγμένο σύνολο Q είναι μονότονη, ή διατηρεί την σχέση διάταξής της, αν a ≤ b στο P συνεπάγεται f(a) ≤ f(b) στο Q (Επισημαίνοντας ότι, οι δύο σχέσεις εδώ είναι αυστηρά διαφορετικές, δεδομένου ότι εφαρμόζονται σε διαφορετικά σύνολα.). Το αντίστροφο αυτού εμμέσως οδηγεί σε συναρτήσεις που είναι ανακλαστικές ως προς τη διάταξη, δηλαδή συναρτήσεις f όπως η παραπάνω για τις οποίες f(a) ≤ f(b) συνεπάγεται a ≤ b. Από την άλλη πλευρά, μια συνάρτηση μπορεί επίσης να είναι διάταξη αναστροφής ή μη-μονότονη, αν a ≤ b συνεπάγεται f(b) ≤ f(a).
Μία διάταξη παρεμβολής είναι μία συνάρτηση f μεταξύ των διατάξεων που ταυτοχρόνως διατηρεί την διάταξη και είναι ανακλαστική ως προς αυτή. Παραδείγματα για τους ορισμούς αυτούς βρίσκονται εύκολα. Για παράδειγμα, η συνάρτηση που απεικονίζει ένα φυσικό αριθμό στον αμέσως επόμενό του, είναι σαφώς μονότονη ως προς τη συνήθη διάταξη. Κάθε λειτουργία από μια διακριτή διάταξη, δηλαδή από ένα σύνολο κατά την ταυτοτική διάταξη "=", είναι επίσης μονότονη. Η απεικόνιση κάθε φυσικού αριθμού στον αντίστοιχο πραγματικό αριθμό δίνει ένα παράδειγμα διάταξης παρεμβολής. Το συμπλήρωμα συνόλου σε ένα μερικώς διατεταγμένο σύνολο αποτελεί ένα παράδειγμα μη -μονότονης συνάρτησης.
Σημαντικό ερώτημα συνιστά το παρακάτω: πότε δύο διατάξεις είναι "ουσιαστικά ίσες", δηλαδή πότε εκφράζουν την ίδια σχέση με μετονομασία των στοιχείων τους. Οι Ισομορφισμοί διατάξεων αποτελούν συναρτήσεις που καθορίζουν μια τέτοια μετονομασία. Μια διάταξη-ισομορφισμός είναι μία μονότονη αμφιμονοσήμαντη ,δηλαδή μία "ένα προς ένα" και επί, συνάρτηση της οποίας η αντίστροφη συνάρτηση είναι επίσης μονότονη. Αυτό είναι ισοδύναμο με το να είναι μία επί διάταξη παρεμβολής. Ως εκ τούτου, η εικόνα f(P) μιας διάταξης-παρεμβολής είναι πάντα ισομορφική στο P, γεγονός το οποίο δικαιολογεί τον όρο «παρεμβολή». Ένας πιο περίτεχνος τύπος συναρτήσεων δίνεται από τις λεγόμενες σχέσεις Galois.Η μονοτονία των σχέσεων Galois μπορεί να θεωρηθεί ως μια γενίκευση των ισομορφισμών των διατάξεων, αφού αποτελούν ένα ζεύγος δύο συναρτήσεων με αντίστροφη κατεύθυνση, η οποία δεν είναι αυστηρά αντίστροφη μεταξύ τους, αλλά οι σχέσεις μεταξύ αυτών παραμένουν στενές.
Ένας άλλος ειδικός τύπος της αυτο-απεικόνισης πάνω σε ένα μερικώς διατεταγμένο σύνολο είναι οι ταυτοτική απεικόνιση, οι οποίες δεν είναι μόνο μονότονες, αλλά και ταυτοτικές, δηλαδή f(x) = f(f(x)), και εκτεταμένες , δηλαδή x ≤ f(x). Αυτά έχουν πολλές εφαρμογές σε όλα τα είδη "κλειστότητας" που εμφανίζονται στα μαθηματικά.
Πέραν του ότι είναι συμβατές με τις απλές σχέσεις διάταξης, συναρτήσεις μεταξύ μερικώς διατεταγμένων συνόλων μπορεί επίσης να συμπεριφέρονται καλά σε σχέση με ειδικά στοιχεία και κατασκευές. Για παράδειγμα, όταν μιλάμε για μερικώς διατεταγμένα σύνολα με ελάχιστο στοιχείο, μπορεί να φαίνεται λογικό να θεωρηθούν μονότονες μόνο οι συναρτήσεις που διατηρούν αυτό το στοιχείο, δηλαδή αυτές οι οποίες απεικονίζουν τα ελάχιστα στοιχεία σε ελάχιστα στοιχεία. Εάν υπάρχει το μέγιστο κάτω φράγμα ^, τότε ως μία λογική ιδιότητα μπορεί κανείς να απαιτήσει f(x^y) = f(x)^f(y), για κάθε x και y. Όλες αυτές οι ιδιότητες, και μάλιστα πολλές περισσότερες, μπορούν να καταρτιστούν με την ετικέτα της διατήρηση ορίου συναρτήσεων. Τέλος, μπορεί κανείς να αναστρέψει την άποψη, η μετάβαση από τις συναρτήσεις των διατάξεων στις διατάξεις των συναρτήσεων. Πράγματι, οι συναρτήσεις ανάμεσα σε δύο μερικώς διατεταγμένα σύνολα P και Q μπορούν να διαταχθούν μέσω της σημειακής διάταξης. Για δύο συναρτήσεις f και g, έχουμε f ≤ g αν f(x) ≤ g(x) για όλα τα στοιχεία x του P. Αυτό συμβαίνει για παράδειγμα στην θωρία πεδίων, όπου οι συναρτήσεις διαστημάτων διαδραματίζουν σημαντικό ρόλο.
Ειδικοί τύποι διατάξεων
Πολλές από τις δομές που μελετήθηκαν στη θεωρία διάταξης, απασχολούν τις σχέσεις διάταξης με επιπλέον ιδιότητες. Στην πραγματικότητα, ακόμη και κάποιες σχέσεις που δεν εντάσσονται στις σχέσεις μερικής διατάξης έχουν ιδιαίτερο ενδιαφέρον. Κυρίως η έννοια της μερικής διάταξης κρίνεται αναγκαίο να αναφερθεί.Μία σχέση μερικής διάταξης είναι μια σχέση που είναι ανακλαστική και μεταβατική, αλλά όχι κατ 'ανάγκη αντισυμμετρική. Κάθε σχέση μερικής διάταξης δημιουργεί μια σχέση ισοδυναμίας μεταξύ των στοιχείων, όπου a είναι ισοδύναμο με το b, αν a ≤ b και b ≤ a. Σχέσεις μερικής διάταξης μπορούν να μετατραπούν σε σχέσεις διάταξης με τον εντοπισμό όλων των στοιχείων που είναι ισοδύναμα όσον αφορά τη σχέση αυτή. Διάφοροι τύποι των σχέσεων διάταξης μπορούν να οριστούν από αριθμητικά δεδομένα σχετικά με τα στοιχεία της διάταξης: μια ολική διάταξη προέρχεται ως αποτέλεσμα της τοποθέτησης διακριτών πραγματικών αριθμών σε κάθε στοιχείο και της χρήσης αριθμητικών συγκρίσεων για να διαταχθούν τα στοιχεία. Αντ’ αυτού, εάν τα διακριτά στοιχεία επιτρέπεται να έχουν ίση αριθμητική αξία, κάποιος αποκτά μία αδύναμη ως προς την αυστηρότητα διάταξη. Η απαίτηση δύο αριθμητικές αξίες να διαχωρίζονται από ένα σταθερό όριο πριν μπορέσουν να συγκριθούν, οδηγεί στην έννοια της ημι-διάταξης, στην οποία επιτρέπεται παράλληλα στο όριο να ποικίλει ανάλογα με το είδος της βάσης που παράγει ένα διατεταγμένο διάστημα. Μία επιπρόσθετη απλή αλλά χρήσιμη ιδιότητα οδηγεί στα λεγόμενα καλά-διατεταγμένα σύνολα,των οποίων όλα τα μη κενά υποσύνολα έχουν ένα ελάχιστο στοιχείο. Γενικεύοντας τα καλά-διατεταγμένα σύνολα από γραμμικά σε μερικώς διατεταγμένα, ένα σύνολο ορίζεται να είναι καλά-μερικώς διατεταγμένοεάν όλα τα μη κενά υποσύνολα του έχουν πεπερασμένο αριθμό ελάχιστων στοιχείων.
Πολλοί άλλοι τύποι διατάξεων προκύπτουν όταν η ύπαρξη κάτω και άνω φραγμάτων ορισμένων συνόλων είναι εγγυημένη. Εστιάζοντας σε αυτή την πτυχή, η οποία συνήθως αναφέρεται ως η πληρότητα των διατάξεων, παίρνουμε:
Οριοθετημένα Σύνολα, δηλαδή σύνολα με ένα ελάχιστο και ένα μέγιστο στοιχείο (τα οποία είναι ακριβώς τα άνω και κάτω φράγματα του κενού υποσυνόλου),
Πλέγματα, στα οποία κάθε μη κενό πεπερασμένο σύνολο έχει άνω και κάτω φράγμα,
Πλήρη Πλέγματα, όπου κάθε σύνολο έχει άνω και κάτω φράγμα, και
Σύνολα Μερικής Διάταξης, που εγγυώνται την ύπαρξη άνω φράγματος σε όλα τα μερικής διάταξης υποσύνολα του, τα οποία μελετούνται στη θεωρία πεδίων.
Σύνολα μερικής διάταξης με συμπληρώματα [1] είναι δυναμοσύνολα S που έχουν ένα μοναδικό ελάχιστο στοιχείο 0∈S , μαζί με μια ανάστροφη διάταξη, έτσι ώστε a\leq a^{*} \Rightarrow a=0.
Ωστόσο, μπορεί κανείς να πάει ακόμα παραπέρα: αν υπάρχουν όλα τα μη κενά πεπερασμένα σύνολα με κάτω φράγματα, τότε ∧ μπορεί να θεωρηθεί ως μία διμελής πράξη κατά την έννοια της καθολικής άλγεβρας. Ως εκ τούτου, σε ένα πλέγμα, δύο πράξεις ∧ και ∨ είναι διαθέσιμες, και μπορεί κανείς να ορίσει με αυτές νέες ιδιότητες, δίνοντας ταυτότητες, όπως
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z), για κάθε x, y, και z.
Η κατάσταση αυτή ονομάζεται επιμεριστική ιδιότητα και προκαλεί πλέγματα στα οποία αυτή ισχύει. Υπάρχουν κάποιοι άλλοι σημαντικοί κανόνες της επιμεριστικής που συζητούνται στο άρθρο σχετικά με την επιμεριστικότητα στη θεωρία διάταξης. Μερικές πρόσθετες δομές της διάταξης που συχνά καθορίζονται μέσω των αλγεβρικών πράξεων και τον καθορισμό των ταυτοτήτων είναι
Άλγεβρα Heyting και
Άλγεβρα Boole
που και οι δύο εισάγουν μια νέα λειτουργία που ονομάζεται ~ άρνηση. Και οι δύο δομές παίζουν ένα ρόλο στη μαθηματική λογική και ιδιαίτερα η άλγεβρα Boule έχει σημαντικές εφαρμογές στην επιστήμη των υπολογιστών. Τέλος, διάφορες δομές στα μαθηματικά συνδυάζουν τις διατάξεις με ακόμη περισσότερες αλγεβρικές λειτουργίες, όπως στην περίπτωση των μερικής διατάξεως αλγεβρικών δομών, που επιτρέπουν τον καθορισμό μιας ακόμα πράξης.
Υπάρχουν πολλές άλλες σημαντικές ιδιότητες των μερικά διατεταγμένων συνόλων. Για παράδειγμα, ένα μερικά διατεταγμένο σύνολο είναι τοπικά πεπερασμένο αν κάθε κλειστό διάστημα [α, β] σε αυτό είναι πεπερασμένο. Τοπικά πεπερασμένα σύνολα μερικής διάταξης οδηγούν στην αύξηση της άλγεβρας προσπτώσεων η οποία με τη σειρά της μπορεί να χρησιμοποιηθεί για να καθορίσει τη χαρακτηριστική συνάρτηση Euler των πεπερασμένων οριοθετούμενων συνόλων μερικής διάταξης.
Υποσύνολα φραγμένων συνόλων
Σε ένα διατεταγμένο σύνολο, μπορεί κάποιος να ορίσει πολλούς τύπους υποσυνόλων βασισμένων σε συγκεκριμένη διάταξη. Ένα απλό παράδειγμα είναι τα άνω σύνολα, δηλαδή σύνολα που περιλαμβάνουν όλα τα στοιχεία τα οποία είναι μεγαλύτερα από αυτά στη διάταξη. Επισήμως, η άνω κλειστότητα ενός συνόλου S σε μερικώς διατεταγμένο σύνολο P δίνεται από το σύνολο {x in P | υπάρχει κάποιο y στο S με y ≤ x}. Ένα σύνολο που είναι ισοδύναμο με την άνω κλειστότητα του ονομάζεται άνω σύνολο. Το Κάτω σύνολο ορίζεται διττά.
Πιο περίπλοκα κάτω υποσύνολα είναι τα ιδεώδη, τα οποία έχουν την επιπλέον ιδιότητα ότι κάθε δύο από τα στοιχεία τους έχουν ένα άνω όριο μέσα στο ιδεώδες. Τα δυϊκά σχήματα δίνονται από τα φίλτρα. Μια σχετική έννοια είναι αυτή του διατεταγμένου υποσυνόλου, που σαν το ιδεώδες περιλαμβάνει άνω φράγματα πεπερασμένων υποσυνόλων, όμως δεν πρέπει να είναι ένα κάτω σύνολο. Επιπλέον είναι συχνά γενικευμένη σαν προδιάταξη. Ένα υποσύνολο το οποίο είναι - ως ένα μερικώς διατεταγμένο υποσύνολο -γραμμικά διατεταγμένο, ονομάζεται αλυσίδα . Η αντίθετη έννοια, αντι-αλυσίδα, είναι ένα υποσύνολο που δεν περιέχει δύο συγκρίσιμα στοιχεία, δηλαδή που έχει μια διακριτή διάταξη.
Σχετικές μαθηματικές περιοχές
Αν και οι περισσότερες μαθηματικές περιοχές χρησιμοποιούν διατάξεις με τον έναν ή τον άλλο τρόπο, υπάρχουν επίσης μερικές θεωρίες ότι υπάρχουν σχέσεις οι οποίες υπερβαίνουν κατά πολύ την απλή εφαρμογή. Μαζί με τα σημαντικά σημεία επαφής τους με την θεωρία διάταξης, κάποια από αυτά παρουσιάζονται παρακάτω.
Καθολική Άλγεβρα
Όπως έχει ήδη αναφερθεί, οι μέθοδοι και οι φορμαλισμοί της καθολικής άλγεβρας είναι ένα σημαντικό εργαλείο για πολλά θεωρητικά ζητήματα διάταξης. Εκτός από τον φορμαλισμό της διάταξης σε όρους των αλγεβρικών δομών που ικανοποιούν συγκεκριμένες ταυτότητες, μπορεί κάποιος επίσης να δημιουργήσει άλλες συνδέσεις με την άλγεβρα. Ένα παράδειγμα δίνεται από την αντιστοιχία μεταξύ της άλγεβρας Boole και τους δακτυλίους Boole. Άλλα θέματα που αφορούν την ύπαρξη ελεύθερων κατασκευών, όπως τα ελεύθερα πλέγματα που βασίζονται σε ένα δεδομένο σύνολο γεννητριών. Επιπρόσθετα, η κλειστότητα των τελεστών είναι σημαντική στη μελέτη της καθολικής άλγεβρας.
Τοπολογία
Στην τοπολογία, οι διατάξεις παίζουν ένα πολύ σημαντικό ρόλο. Στην πραγματικότητα, το σύνολο των ανοικτών συνόλων παρέχει ένα κλασικό παράδειγμα ενός πλήρους πλέγματος, ακριβέστερα την πλήρη άλγεβρα Heyting (Το σύστημα όλων των ανοικτών συνόλων ενός δεδομένου τοπολογικού χώρου με εντολή ένταξης). Τα φίλτρα και τα δίκτυα είναι έννοιες στενά συνδεδεμένες με τη θεωρία διάταξης και η κλειστότητα των τελεστών των συνόλων μπορεί να χρησιμοποιηθεί για να ορίσει την τοπολογία. Πέρα από αυτές τις σχέσεις, η τοπολογία μπορεί να εξεταστεί μόνο σε σχέση με τα ανοιχτά πλέγματα, τα οποία οδηγούν στη μελέτη της άσκοπης τοπολογίας. Επιπλέον, μια φυσική προδιάταξη των στοιχείων του αντίστοιχου συνόλου ενός τοπολογικού χώρου δίνεται από την αποκαλούμενη εξειδικευμένη διάταξη, που στην πραγματικότητα είναι μια μερική διάταξη αν η τοπολογία είναι [[T0]].
Αντίθετα, στην θεωρία διάταξης, κάποιος κάνει συχνά χρήση των αποτελεσμάτων της τοπολογίας. Υπάρχουν διάφοροι τρόποι για να ορίσει κανείς τα υποσύνολα μιας διάταξης τα οποία μπορούν να θεωρηθούν ως ανοιχτά σύνολα μιας τοπολογίας. Ειδικά, είναι ενδιαφέρον να θεωρήσει τις τοπολογίες πάνω σε ένα μερικώς διατεταγμένο σύνολο (X, ≤) που καθιστά την ≤ ως την εξιδεικευμένη τους διάταξη. Το καλύτερο όταν η τοπολογία είναι η Alexandrov τοπολογία, δίνεται παίρνοντας όλα τα άνω σύνολα ως ανοιχτά. Αντίθετα, η αδύναμητοπολογία που περιέχει την εξιδεικευμένη διάταξη είναι η άνω τοπολογία, έχοντας τα συμπληρώματα από τα κύρια ιδεώδη (δηλαδή σύνολα της μορφής{y in X | y ≤ x} για κάποιο x) σαν μια υπόβαση(σε έναν τοπολογικό χώρο X με τοπολογία T είναι η συλλογή B της T που παράγει την T, με την προϋπόθεση ότι η T είναι η μικρότερη τοπολογία που περιέχει την B). Επιπλέον, μια τοπολογία με εξιδεικευμένη διάταξη ≤ μπορεί να είναι μια σταθερή διάταξη (μη αντιφατική), πράγμα που σημαίνει ότι τα ανοικτά τους σύνολα είναι "απρόσιτα από το διατεταγμένο άνω φράγμα" (με σεβασμό στην ≤). Η καλύτερη σταθερή διατεταγμένη τοπολογία είναι η Scott τοπολογία, η οποία είναι πιο αδύναμη από αυτή του Alexandrov . Μια τρίτη σημαντική τοπολογία είναι η Lawson τοπολογία. Υπάρχουν στενές συνδέσεις ανάμεσα σε αυτές τις τοπολογίες και έννοιες της θεωρίας διάταξης. Για παράδειγμα, μια συνάρτηση που διατηρεί διατεταγμένο άνω φράγμα αν και μόνο αν είναι συνεχής με σεβασμό στην τοπολογία του Scott (για αυτό το λόγο αυτή η θεωρητική διάταξη καλείται και συνέχεια του Scott).
Η θεωρία των κατηγοριών
Η οπτικοποίηση της διάταξης με διαγράμματα Hasse έχει μια απλή γενίκευση: αντί να εμφανίσει μικρότερα στοιχεία κάτω από τα μεγαλύτερα, η κατεύθυνση της διάταξης μπορεί επίσης να αναπαρασταθεί δίνοντας κατευθύνσεις στα άκρα του γραφήματος. Με αυτόν τον τρόπο, κάθε διάταξη φαίνεται να είναι ισοδύναμη με ένα κατευθυνόμενο μη κυκλικό γράφημα, όπου οι κόμβοι είναι τα στοιχεία του μερικώς διατεταγμένου συνόλου και υπάρχει μια κατευθυντήρια γραμμή από το α στο β αν και μόνο αν α ≤ β. Έχοντας την απαίτηση να είναι μη κυκλικό, ένα μπορεί να λάβει και όλες τις προηγούμενες διατάξεις.
Όταν τα διαγράμματα είναι εξοπλισμένα με τη μεταβατική ιδιότητα, τότε αυτά αποτελούν μια ειδική κατηγορία, όπου τα στοιχεία είναι αντικείμενα και κάθε σύνολο από μορφισμούς ανάμεσα σε δύο στοιχεία είναι το πολύ μονοσύνολο. Οι συναρτήσεις των διατάξεων γίνονται παράγοντες μεταξύ των κατηγοριών. Είναι ενδιαφέρων, ότι πολλές ιδέες της θεωρίας διάταξης είναι απλά μικρότερες έννοιες της θεωρίας κατηγοριών. Για παράδειγμα, ένα κάτω φράγμα είναι απλά ένα αντικείμενο μιας κατηγορίας (το προϊόν ή αντικείμενο μιας οικογένειας από αντικείμενα είναι το πιο γενικό αντικείμενο που δέχεται ένα μορφισμό για κάθε ένα από τα δοσμένα αντικείμενα). Πιο γενικά, κάποιος μπορεί να συλλάβει το κάτω και άνω φράγμα κάτω από την αφηρημένη έννοια του κατηγορηματικού ορίου. Σε έναν άλλο χώρο όπου υπάρχουν κατηγορηματικές ιδέες είναι στις συνδέσεις Galois, όπου είναι το ίδιο με ένα ζευγάρι συζυγών παραγόντων.
Αλλά η θεωρία των κατηγοριών έχει επίσης επιπτώσεις στην θεωρία διάταξης σε μεγαλύτερη κλίμακα. Τάξεις από δυναμοσύνολα με κατάλληλες λειτουργίες όπως συζητήθηκε σε παραπάνω ενδιαφέρουσες κατηγορίες. Συχνά μπορεί κάποιος να φτιάξει κατασκευές από τη διάταξη, όπως η κανονική διάταξη στο χώρο (σε δύο σύνολα Α και Β, μπορεί κανείς να ορίσει το καρτεσιανό γινόμενο A × B. Είναι κανονική διάταξη αν όταν δίνονται δύο ζευγάρια (α1,β1) and (α2,β2) στο A × B, τότε ισχύει (α1,β1) ≤ (α2,β2) αν και μόνο αν α1 ≤ α2 and β1 ≤ β2),από την άποψη των κατηγοριών. Περαιτέρω ιδέες προκύπτουν όταν οι κατηγορίες των διατάξεων είναι κατηγορηματικά ισοδύναμες με τις άλλες κατηγορίες, για παράδειγμα των τοπολογικών χώρων. Αυτή η γραμμή της έρευνας οδηγεί σε διάφορα θεωρήματα αναπαράστασης, συχνά συγκεντρωμένα κάτω από την ετικέτα της Stone δυαδικότητας.
Ιστορία
Όπως εξηγήθηκε πριν, οι διατάξεις είναι πανταχού παρούσες στα μαθηματικά. Ωστόσο, οι πρώτες ρητές ερμηνείες της μερικής διάταξης έναι πιθανόν να μην βρέθηκε πριν από τον 19ο αιώνα. Στο πλαίσιο αυτό, η δουλειά του George Boole έχει πολύ μεγάλη σημασία. Επιπλέον, η δουλειά των Charles Sanders Peirce, Richard Dedekind, και Ernst Schröder επίσης έδωσαν σημασία στη θεωρία διάταξης. Βεβαίως, υπάρχουν και άλλοι για να κατονομαστούν για αυτό το ζήτημα και σίγουρα υπάρχει πιο λεπτομερές υλικό στην ιστορία της θεωρίας διάταξης.
Ο όρος poset ως μια συντομογραφία για το μερικώς διατεταγμένο σύνολο επινοήθηκε από τον Garrett Birkhoff στην δεύτερη έκδοση του βιβλίου του Θεωρία Πλεγμάτων.[2][3]
Δείτε επίσης:
Κυκλική διάταξη
Ιεραρχία
Επιπτωτική άλγεβρα
Σημαντικές δημοσιεύσεις για τη θεωρία διάταξης
Σχέση μεταξύ αιτίας και αποτελέσματος στα σύνολα
Παραπομπές
Roller, Martin A. (1998), Poc sets, median algebras and group actions. An extended study of Dunwoody's construction and Sageev's theorem, Southampton Preprint Archive
Birkhoff 1948, p.1
Earliest Known Uses of Some of the Words of Mathematics
Παραπομπές
Birkhoff, Garrett (1940). Lattice Theory 25 (3rd Revised ed.). American Mathematical Society. ISBN 978-0-8218-1025-5.
Burris, S. N.; Sankappanavar, H. P. (1981). A Course in Universal Algebra. Springer. ISBN 978-0-387-90578-5.
Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. ISBN 0-521-78451-4.
Gierz, G.; Hofmann, K. H.; Keimel, K.; Mislove, M.; Scott, D. S. (2003). Continuous Lattices and Domains. Encyclopedia of Mathematics and its Applications 93. Cambridge University Press. ISBN 978-0-521-80338-0.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
