53984 - Ανακατασκευή Δομών

Ν. Λυγερός

Έστω μια δομή που χαρακτηρίζεται ως σύνολο μερικής διάταξης.
Έστω η ομάδα αυτομορφισμών αυτής της δομής.
Ορίζουμε ως επίθεση κατά της δομής την αφαίρεση της κoρυφής του συνόλου μερικής διάταξης.
Ορίζουμε ως ακολουθία επιθέσεων όλες τις δυνατές διαφορετικές επιθέσεις κατά της δομής.
Ορίζουμε ερείπιο τη δομή που έχει υποστεί επίθεση.
Ορίζουμε ερείπια την ακολουθία που αποτελείται από όλα τα διαφορετικά δεδομένα κάθε ερειπίου.
Ορίζουμε ανακατασκευή δομής τη διαδικασία που αρχίζει από τα ερείπια και κατασκευάζει την αρχική δομή.
Ορίζουμε δείκτη το πλήθος των εμφανίσεων του ίδιου ερειπίου.
Ξέρουμε ότι υπάρχουν 5 σύνολα μερικής διάταξης τάξης 3.
Τα ερείπια τους είναι αναγκαστικά υποσύνολα του συνόλου των συνόλων μερικής διάταξης τάξης 2.
Η γνώση των ερειπίων τάξης 2 δεν επαρκεί για να ανακατασκευάσουμε με μοναδικό τρόπο.
Αυτό οφείλεται στο γεγονός ότι υπάρχουν δύο σύνολα μερικής διάταξης που είναι δυϊκά.
Για τα σύνολα μερικής διάταξης τάξης 4, μπορούμε να αποδείξουμε το εξής:
Θεώρημα Α: Είναι δυνατόν η ανακατασκευή της δομής τάξης 4 με μοναδικό τρόπο χάρη στα ερείπια και τους δείκτες.
Θεώρημα Β: Οι δείκτες δεν είναι απαραίτητοι για το αποτέλεσμα του θεωρήματος Α.
Απόδειξη: Βλέπε Opus 53983.