Αντιματροειδές

Στα  μαθηματικά, αντιματροειδές είναι ένα φορμαλιστικό σύστημα το οποίο περιγράφει διαδικασίες κατά τις οποίες ένα σύνολο κατασκευάζεται τοποθετώντας τα στοιχεία ένα τη φορά, και ένα στοιχείο, το οποίο έχει καταστεί διαθέσιμο ώστε να συμπεριληφθεί, παραμένει διαθέσιμο μέχρι να συμπεριληφθεί. Τα αντιματροειδή συνήθως ορίζονται αξιωματικά με δύο ισοδύναμους τρόπους, είτε σαν ένα σύστημα συνόλων το οποίο μοντελοποιεί τις πιθανές καταστάσεις μιας τέτοιας διαδικασίας, είτε σαν μια φορμαλιστική γλώσσα η οποία μοντελοποιεί τις διαφορετικές ακολουθίες στις οποίες τα στοιχεία μπορεί να συμπεριλαμβάνονται. Ο Dilworth (1940) ήταν ο πρώτος που μελέτησε τα αντιματροειδή, εφαρμόζοντας μία διαφορετική αξιωματική προσέγγιση βασισμένη στη θεωρία μερικώς διατεταγμένων συνόλων, και έχουν ανακαλυφθεί και σε άλλα πλαίσια: βλέπε Korte et al. (1991) για μια εκτενή έρευνα της θεωρίας αντιματροειδών με πλήθος πρόσθετων πηγών.
Τα αξιώματα που ορίζουν τα αντιματροειδή ως σύστημα συνόλων είναι παραπλήσια με τα αξιώματα των ματροειδών, αλλά ενώ τα ματροειδή ορίζονται μέσω ενός αξιώματος ανταλλαγής, τα αντιματροειδή ορίζονται μέσω ενός αξιώματος αντι-ανταλλαγής, από το οποίο πηγάζει και η ονομασία τους. Τα αντιματροειδή μπορούν να θεωρηθούν ως ειδική περίπτωση των greedoids και των ημισυναρμολογούμενων μερικώς διατεταγμένων συνόλων, και ως γενίκευση των μερικώς διατεταγμένων συνόλων και των επιμεριστικών μερικώς διατατεγμένων συνόλων. Τα αντιματροειδή είναι ισοδύναμα, μέσω της συμπλήρωσης, με τις κυρτές γεωμετρίες, μια αφηρημένη συνδυαστική θεώρηση των κυρτών συνόλων στη Γεωμετρία.
Τα αντιματροειδή έχουν χρησιμοποιηθεί για να μοντελοποιήσουν φραγμούς προτεραιότητας σε προβλήματα προγραμματισμού, πιθανές ακολουθίες γεγονότων σε προσομοιώσεις, σχεδιασμό εργασιών στην τεχνητή νοημοσύνη, και τις καταστάσεις της ανθρώπινης γνώσης.

Διαδρομές και βασικές λέξεις

Στη θεωρητική αξιωματικοποίηση ενός αντιματροειδούς μέσω συνόλων υπάρχουν συγκεκριμένα ειδικά σύνολα που ονομάζονται διαδρομές, τα οποία καθορίζουν όλο το αντιματροειδές, υπό την έννοια ότι τα σύνολα του αντιματροειδούς είναι οι ενώσεις των διαδρομών. Αν S είναι οποιοδήποτε εφικτό σύνολο του αντιματροειδούς, ένα στοιχείο x το οποίο μπορεί να μετακινηθεί από το S για να σχηματίσει ένα άλλο εφικτό σύνολο ονομάζεται καταληκτικό σημείο του  S, και ένα εφικτό σύνολο το οποίο έχει ένα μόνο καταληκτικό σημείο ονομάζεται διαδρομή του αντιματροειδούς. Η οικογένεια των διαδρομών μπορεί να είναι μερικώς διατεταγμένη κατά σειρά ένταξης, σχηματίζοντας τη μερικώς διατεταγμένη διαδρομή του αντιματροειδούς.
Για κάθε εφικτό σύνολο S του αντιματροειδούς, και κάθε στοιχείο x του S, ένα μπορεί να βρεθεί μια διαδρομή υποσύνολο του S για την οποία το x είναι καταληκτικό σημείο: για να γίνει αυτό, μετακινήστε ένα τη φορά σημεία εκτός του x μέχρι καμία τέτοια μετακίνηση να αφήσει ένα εφικτό υποσύνολο. Ως εκ τούτου, κάθε εφικτό σύνολο σε ένα αντιματροειδές είναι η ένωση των διαδρομών υποσυνόλων του. Αν S δεν είναι διαδρομή, κάθε υποσύνολο σε αυτήν την ένωση είναι αυστηρό υποσύνολο του S. Αλλά, αν το S  είναι το ίδιο μια διαδρομή με καταληκτικό σημείο x, κάθε αυστηρό υποσύνολο του S το οποίο ανήκει στο αντιματροειδές εξαιρεί το x. Ως εκ τούτου, οι διαδρομές ενός αντιματροειδούς είναι ακριβώς τα σύνολα τα οποία δεν είναι ίσα με τις ενώσεις των αυστηρών τους υποσυνόλων στο αντιματροειδές. Ισοδύναμα, μια δοθείσα οικογένεια συνόλων P σχηματίζει το σύνολο των διαδρομών ενός αντιματροειδούς αν και μόνον αν, για κάθε S που ανήκει στο P, η ένωση των υποσυνόλων των S του P έχει ένα λιγότερο στοιχείο από το ίδιο το S. Αν συμβαίνει αυτό, το ίδιο το F είναι η οικογένεια των ενώσεων των υποσυνόλων των P.
Στην φορμαλιστική γλώσσα φορμαλισμό ενός αντιμαστροειδούς μπορούμε επίσης να προσδιορίσουμε ένα υποσύνολο λέξεων που καθορίζουν όλη τη γλώσσα, τις βασικές λέξεις. Οι μεγαλύτερες συμβολοσειρές της L ονομάζονται βασικές λέξεις, κάθε βασική λέξη σχηματίζει μια μετάθεση ολόκληρου του αλφαβήτου. Για παράδειγμα οι βασικές λέξεις ενός μερικώς διατεταγμένου αντιματροειδούς είναι οι γραμμικές επεκτάσεις της δοθείσας μερικής διάταξης. Αν B είναι ένα σύνολο βασικών λέξεων, η L μπορεί να οριστεί από το B ως το σύνολο των προθεμάτων των λέξεων του B. Είναι συχνά βολικό να ορίζουμε αντιματροειδή από βασικές λέξεις με αυτόν τον τρόπο, αλλά δεν είναι απλό να γράψουμε έναν αξιωματικό ορισμό των αντιματροειδών σε όρους των βασικών λέξεων.

Υπερεπιλύσιμα αντιματροειδή

Ωθούμενος από ένα πρόβλημα ορισμού μερικής διάταξης στα στοιχεία μίας ομάδας Coxeter, ο Armstrong (2007) μελέτησε αντιματροειδή τα οποία είναι επίσης υπερεπιλύσιμα πλέγματα. Ένα υπερεπιλύσιμο αντιματροειδές προσδιορίζεται από μία ολικά διατεταγμένη συλλογή από στοιχεία, και μία οικογένεια συνόλων από αυτά τα στοιχεία. Η οικογένεια πρέπει να περιέχει το κενό σύνολο. Επιπρόσθετα, πρέπει να έχει την ιδιότητα ότι αν δύο σύνολα A και B ανήκουν στην οικογένεια, η συνολο-θεωρητική διαφορά B \ A είναι μη κενό, και το x είναι το μικρότερο στοιχείο του  B \ A, τότε το A ∪ {x} επίσης ανήκει στην οικογένεια. Όπως παρατήρησε ο Armstrong, κάθε οικογένεια συνόλων διαμορφώνει ένα αντιματροειδές. Ο Armstrong επίσης παρέχει ένα πλέγμα-θεωρητικό χαρακτηρισμό των αντιματροειδών τον οποίο αυτή η δομή μπορεί να δημιουργήσει.

Συνδετική πράξη και κυρτή διάσταση

Αν A και B είναι δύο αντιματροειδή, τα οποία περιγράφονται ως οικογένεια συνόλων, και αν τα μέγιστα σύνολα των A και B είναι ίσα, μπορούμε να σχηματίσουμε ένα άλλο αντιματροειδές, τη σύνδεση των A και B, ως εξής: 
Αυτή είναι μια διαφορετική πράξη από τη σύνδεση που θεωρείται στον πλεγματο-θεωρητικό χαρακτηρισμό των αντιματροειδών: συνδυάζει δύο αντιματροειδή για να δημιουργήσει ένα άλλο αντιματροειδές και όχι δύο σύνολα ενός αντιματροειδούς για να δημιουργήσει ένα άλλο σύνολο. Η οικογένεια όλων των αντιματροειδών τα οποία έχουν ένα δοθέν μέγιστο σύνολο δημιουργεί ένα ημιπλέγμα με αυτή τη συνδετική πράξη.
Οι συνδέσεις συσχετίζονται άμεσα με μια απεικόνιση κλειστότητας η οποία απεικονίζει φορμαλιστικές γλώσσες σε αντιματροειδή, όπου η κλειστότητα μιας γλώσσας L είναι η τομή όλων των αντιματροειδών που περιέχουν την L ως υπογλώσσα. Αυτή η κλειστότητα έχει ως τα εφικτά της σύνολα τις ενώσεις των προθεμάτων των συμβολοσειρών της L. Σε όρους αυτής της απεικόνισης κλειστότητας, η σύνδεση είναι η κλειστότητα της ένωσης των γλωσσών A και B.
Κάθε αντιματροειδές μπορεί να αναπαρασταθεί ως η σύνδεση μιας οικογένειας αντιματροειδών αλυσίδες, ή ισοδύναμα ως η κλειστότητα ενός συνόλου βασικών λέξεων: η κυρτή διάσταση ενός αντιματροειδούς A είναι ο ελάχιστος αριθμός των αντιματροειδών αλυσίδες (ή ισοδύναμα ο ελάχιστος αριθμός βασικών λέξεων) σε μια τέτοια αναπαράσταση. Αν F είναι μια οικογένεια αντιματροειδών αλυσίδες των οποίων όλες οι βασικές λέξεις ανήκουν στο A, τότε η F παράγει το A αν και μόνον αν τα εφικτά σύνολα της F περιέχουν όλες τις διαδρομές του A. Οι διαδρομές του Α που ανήκουν σε ένα αντιματροειδές αλυσίδα πρέπει να σχηματίζουν μια αλυσίδα στη διαδρομή μερικώς διατεταγμένων συνόλων του Α, έτσι η κυρτή διάσταση ενός αντιματροειδούς ισούται με τον ελάχιστο αριθμό των αλυσίδων που χρειάζονται για να καλύψουν τη διαδρομή μερικώς διατεταγμένων συνόλων, ο οποίος από το Θεώρημα Dilworth ισούται με το εύρος των διαδρομών μερικώς διατεταγμένων συνόλων.
Αν κάποιος έχει μία αναπαράσταση ενός αντιματροειδούς ως την κλειστότητα ενός συνόλου από d βασικές λέξεις, τότε αυτή η αναπαράσταση μπορεί να χρησιμοποιηθεί για να απεικονίσει τα εφικτά σύνολα του αντιματροειδούς σε έναν d-διάστατο Ευκλείδειο χώρο: ορίζει μια συντεταγμένη για κάθε βασική λέξη w, και ορίζει την τιμή της συντεταγμένης ενός εφικτού συνόλου S να είναι το μήκος του μεγαλύτερου προθέματος της w που είναι υποσύνολο του S. Με αυτή την ενσωμάτωση, το S είναι υποσύνολο του Τ αν και μόνον αν οι συντεταγμένες για το S είναι όλες μικρότερες ή ίσες των αντίστοιχων συντεταγμένων του T. Επομένως, η διάσταση διάταξης της διάταξης ένταξης των εφικτών συνόλων είναι το πολύ ίση με τη κυρτή διάσταση του αντιματροειδούς. Ωστόσο, γενικά αυτές οι δύο διαστάσεις ενδέχεται να διαφέρουν: υπάρχουν αντιματροειδή με διάσταση διάταξης τρία αλλά αυθαίρετα μεγάλη κυρτή διάσταση.

Απαρίθμηση

Ο αριθμός των δυνατών αντιματροειδών πάνω σε ένα σύνολο στοιχείων μεγαλώνει ταχέως όσο αυξάνεται ο αριθμός των στοιχείων του συνόλου. Για σύνολα του ενός, των δύο, τριών, κλπ. στοιχείων, ο αριθμός των διακεκριμένων αντιματροειδών είναι:
1, 3, 22, 485, 59386, 133059751, ...(ακολουθία A119770 στην OESIS)

Εφαρμογές

Οι περιορισμοί προτεραιότητας και χρόνου αποδέσμευσης στον βασικό συμβολισμό για θεωρητικά προβλήματα προγραμματισμού μπορούν να μοντελοποιηθούν από αντιματροειδή. Οι Boyd & Faigle (1990) χρησιμοποιούν αντιματροειδή για να δημιουργήσουν τον άπληστο αλγόριθμο του Eugene Lawler για την βέλτιστη επίλυση προγραμματιστικών προβλημάτων μονού επεξεργαστή με περιορισμούς προτεραιότητας όπου ο στόχος είναι να ελαχιστοποιηθεί η μέγιστη ποινή που επιβάλλεται από τον αργό προγραμματισμό μιας εργασίας.
Οι Glasserman & Yao (1994) χρησιμοποιούν αντιματροειδή για να μοντελοποιήσουν την διάταξη των γεγονότων σε συστήματα διακριτής προσομοίωσης γεγονότων.
Ο Parmar (2003) χρησιμοποιεί αντιματροειδή για να μοντελοποιήσει την πρόοδο ενός στόχου σε προβλήματα σχεδίασης στην τεχνητή νοημοσύνη.
Στη μαθηματική ψυχολογία, τα αντιματροειδή έχουν χρησιμοποιηθεί για να περιγράψουν τις εφικτές καταστάσεις της γνώσης ενός ανθρώπινου όντος. Κάθε στοιχείο του αντιματροειδούς αναπαριστά μία έννοια η οποία είναι να κατανοηθεί από τον μαθητή, ή μια κλάση προβλημάτων την οποία ενδέχεται να μπορεί να λύσει αυτός/αυτή, και τα σύνολα των στοιχείων τα οποία σχηματίζουν το αντιματροειδές αναπαριστούν πιθανά σύνολα εννοιών οι οποίες μπορούν να γίνουν αντιληπτές από έναν άνθρωπο. Τα αξιώματα που ορίζουν ένα αντιματροειδές μπορούν να εκφραστούν ανεπίσημα θέτοντας ότι η εκμάθηση μιας έννοιας δεν εμποδίζει ποτέ τον μαθητή από την εκμάθηση μιας άλλης, και ότι οποιαδήποτε εφικτή κατάσταση γνώσης μπορεί να επιτευχθεί μαθαίνοντας μια έννοια την φορά. Ο στόχος του συστήματος εκτίμησης γνώσης είναι να συμπεράνει το σύνολο των γνωστών εννοιών για έναν μαθητή με το να αναλύει τις αντιδράσεις του/της σε ένα μικρό και καλώς διαλεγμένο σύνολο προβλημάτων. Σε αυτό το πλαίσιο τα αντιματροειδή έχουν επίσης ονομαστεί "κενά μάθησης" και "καλώς διαβαθμισμένα κενά γνώσης".