Zakończenie Dedekinda-MacNeille'a

Diagram Hassego częściowo uporządkowanego zestawu (po lewej) i jego uzupełnienie Dedekinda – MacNeille'a (po prawej).

W matematyce , a konkretnie w teorii porządku , uzupełnienie częściowo uporządkowanego zbioru Dedekinda -MacNeille'a jest najmniejszą kompletną siecią , która go zawiera. Został nazwany na cześć Holbrooka Manna MacNeille'a , którego artykuł z 1937 roku po raz pierwszy go zdefiniował i skonstruował, oraz na cześć Richarda Dedekinda , ponieważ jego konstrukcja uogólnia cięcia Dedekinda użyte przez Dedekinda do skonstruowania liczb rzeczywistych z liczb wymiernych . Nazywa się to również uzupełnianiem przez cięcia lub uzupełnianie normalne .

Zamów zabudowy i uzupełnienia kratownicowe

Zbiór częściowo uporządkowany (poset) składa się ze zbioru elementów wraz z relacją binarną $x \leq y$ na parach elementów, która jest zwrotna ( $x \leq x$ dla każdego x ), przechodnia (jeśli $x \leq y$ i $y \leq z$ to $x \leq z$ ) i antysymetryczny (jeśli oba $x \leq y$ i $y \leq x$ są spełnione, to $x = y$ ). Zwykłe uporządkowania numeryczne liczb całkowitych lub rzeczywistych spełniają te właściwości; jednak w przeciwieństwie do uporządkowania liczb, porządek częściowy może mieć dwa elementy, które są nieporównywalne : nie zachodzi ani $x \leq y$ , ani $y \leq x .$ Innym znanym przykładem uporządkowania częściowego jest uporządkowanie inkluzji ⊆ na parach zbiorów.

Jeśli $S$ $jest$ zbiorem częściowo uporządkowanym, uzupełnienie S oznacza kompletną kratę $L$ z $osadzeniem$ porządku S w $L$ . Pojęcie pełnej sieci oznacza, że każdy podzbiór elementów $L$ ma infimum i supremum ; to uogólnia analogiczne właściwości liczb rzeczywistych . Pojęcie osadzania porządku wymusza wymagania, że różne elementy $S$ muszą być odwzorowywane na różne elementy $L$ oraz że każda para elementów w $S$ ma takie samo uporządkowanie w $L$ jak w $S$ . Rozszerzona oś liczb rzeczywistych (liczby rzeczywiste wraz z + ∞ i − ∞) jest w tym sensie uzupełnieniem liczb wymiernych: zbiór liczb wymiernych {3, 3,1, 3,14, 3,141, 3,1415, 3,14159, ...} nie nie ma wymiernej najmniejszej górnej granicy, ale w liczbach rzeczywistych ma najmniejszą górną granicę $π$ .

Dany częściowo uporządkowany zbiór może mieć kilka różnych uzupełnień. Na przykład jednym uzupełnieniem dowolnego częściowo uporządkowanego zbioru $S$ jest zbiór jego podzbiorów domkniętych w dół uporządkowanych przez inkluzję . $S$ jest osadzony w tej (pełnej) sieci poprzez odwzorowanie każdego elementu $x$ na niższy zestaw elementów, które są mniejsze lub równe $x$ . Rezultatem jest siatka rozdzielcza i jest używana w twierdzeniu Birkhoffa o reprezentacji . Jednak może mieć o wiele więcej elementów niż jest potrzebnych do utworzenia uzupełnienia $S$ . Spośród wszystkich możliwych uzupełnień sieci, uzupełnienie Dedekinda-MacNeille'a jest najmniejszą kompletną siecią z osadzonym w niej $S.$

Definicja

Dla każdego podzbioru $A$ częściowo uporządkowanego zbioru $S$ niech $Au oznacza$ zbiór górnych granic zbioru $A$ ; to znaczy, że element $x$ z $S$ należy do $Au,$ ilekroć $x$ jest większe lub równe każdemu elementowi z $A$ . Symetrycznie niech $Al w$ oznacza zbiór dolnych granic $A$ , elementów, które są mniejsze lub równe każdemu elementowi $A$ . Wtedy uzupełnienie $S$ Dedekinda-MacNeille'a składa się ze wszystkich podzbiorów $A$ dla których

(ZA u) l = ZA

;

jest uporządkowany przez włączenie: $A \leq B$ do uzupełnienia wtedy i tylko wtedy, gdy $A \subseteq B$ jako zestawy.

Element $x$ z $S$ osadza się w uzupełnieniu jako jego główny ideał , zbiór $↓ x$ elementów mniejszych lub równych $x$ . Wtedy $(↓ x) u$ jest zbiorem elementów większych lub równych $x$ , a $((↓ x) u) l = ↓ x$ , co pokazuje, że $↓ x$ rzeczywiście należy do uzupełnienia. Odwzorowanie od $x$ do $↓ x$ jest osadzeniem porządku.

Czasami używana jest alternatywna definicja uzupełnienia Dedekinda-MacNeille'a, która bardziej przypomina definicję cięcia Dedekinda. W zbiorze częściowo uporządkowanym $S$ zdefiniuj przekrój jako parę zbiorów $(A, B)$ dla których $A u = B$ i $A = B l$ . Jeśli $(A, B)$ jest przecięciem, to $A, Au) A spełnia$ równanie ( $(Au) l = A i$ odwrotnie, jeśli $(A u) l = A$ wtedy jest przecięciem. Dlatego zbiór przekrojów, częściowo uporządkowany przez inkluzje na dolnym zbiorze przekrojów (lub odwrotność relacji inkluzji na górnym zbiorze), daje równoważną definicję uzupełnienia Dedekinda-MacNeille'a.

W definicji alternatywnej zarówno operacje łączenia, jak i łączenia całej sieci mają opisy symetryczne: jeśli $(A i, B i)$ są przekrojami w dowolnej rodzinie przekrojów, to spotkanie tych przekrojów jest przecięciem $(L, L u)$ gdzie $L = \cap ja ZA ja$ , a połączeniem jest przecięcie $(U l, U)$ gdzie $U = \cap ja B ja$ .

Przykłady

Jeśli jest zbiorem liczb wymiernych $,$ postrzeganym jako całkowicie uporządkowany zbiór ze zwykłym porządkiem liczbowym, to każdy element uzupełnienia Dedekinda-MacNeille'a z $\ displaystyle \ mathbb {Q}}$ można postrzegać jako cięcie Dedekinda , a uzupełnienie Dedekinda-MacNeille'a $całkowite$ uporządkowanie liczb rzeczywistych wraz z dwiema dodatkowymi wartościami ${\ displaystyle \ pm \ infty}$ .

Jeśli $S$ jest antyłańcuchem (zbiorem elementów, z których żadne dwa nie są porównywalne), to uzupełnienie $S przez Dedekinda-MacNeille'a$ składa się z samego $S$ wraz z dwoma dodatkowymi elementami, elementem dolnym, który znajduje się poniżej każdego elementu w $S$ i elementem górnym, który jest ponad każdym elementem w $S$ .

Jeśli $O$ jest dowolnym skończonym zbiorem obiektów, a $A$ jest dowolnym skończonym zbiorem jednoargumentowych atrybutów obiektów w $O$ , to można utworzyć porządek częściowy o wysokości dwa, w którym elementami porządku częściowego są przedmioty i atrybuty, a w który $x \leq y$ gdy $x$ jest obiektem, który ma atrybut $y$ . W przypadku tak zdefiniowanego porządku częściowego uzupełnienie $S przez Dedekinda-MacNeille'a$ jest znane jako siatka pojęciowa i odgrywa centralną rolę w dziedzinie formalnej analizy pojęciowej .

Nieruchomości

Uzupełnienie Dedekinda-MacNeille'a częściowo uporządkowanego zbioru $S$ jest najmniejszą kompletną siecią z osadzonym w niej $S w tym sensie, że jeśli$ $L$ jest dowolnym uzupełnieniem sieci $S$ , to uzupełnienie Dedekinda-MacNeille'a jest częściowo uporządkowanym podzbiorem $L$ . Kiedy $S$ jest skończone, jego uzupełnienie jest również skończone i ma najmniejszą liczbę elementów spośród wszystkich skończonych kompletnych krat zawierających $S$ .

Częściowo uporządkowany zbiór $S$ jest gęsto połączony i gęsty w uzupełnieniu Dedekinda-MacNeille'a; to znaczy każdy element uzupełnienia jest połączeniem jakiegoś zestawu elementów $S$ , a także jest spotkaniem jakiegoś zestawu elementów w $S$ . Uzupełnienie Dedekinda – MacNeille'a charakteryzuje się wśród uzupełnień $S$ tą właściwością.

algebry Boole'a przez Dedekinda-MacNeille'a jest kompletną algebrą Boole'a ; wynik ten jest znany jako twierdzenie Glivenko-Stone'a , po Valery Ivanovich Glivenko i Marshall Stone . Podobnie, uzupełnienie Dedekinda-MacNeille'a resztkowej sieci jest kompletną resztkową siatką. Jednak uzupełnienie sieci dystrybucyjnej samo w sobie nie musi być dystrybucyjne, a uzupełnienie sieci modułowej może nie pozostać modułowe.

Uzupełnienie Dedekinda – MacNeille'a jest samodualne: uzupełnienie podwójnego porządku częściowego jest tym samym, co podwójne uzupełnienie.

$S$ przez Dedekinda-MacNeille'a ma ten sam wymiar porządku , co samo $S.$

W kategorii częściowo uporządkowanych zbiorów i funkcji monotonicznych między częściowo uporządkowanymi zbiorami, kompletne kraty tworzą obiekty iniekcyjne dla osadzania porządku , a dopełnienie $S$ Dedekinda-MacNeille'a jest iniekcyjnym kadłubem $S$ .

Algorytmy

Kilku badaczy zbadało algorytmy konstruowania uzupełnienia Dedekinda-MacNeille'a skończonego, częściowo uporządkowanego zbioru. Uzupełnienie Dedekinda-MacNeille'a może być wykładniczo większe niż porządek częściowy, z którego pochodzi, a granice czasowe dla takich algorytmów są generalnie określane w sposób wrażliwy na dane wyjściowe , w zależności zarówno od liczby $n$ elementów wejściowego rzędu częściowego, jak i od liczba $c$ elementów jego uzupełnienia.

Konstruowanie zbioru przekrojów

Ganter i Kuznetsov (1998) opisują algorytm przyrostowy, w którym częściowy porządek wejściowy jest tworzony przez dodawanie jednego elementu na raz; na każdym etapie realizacja mniejszego porządku częściowego jest rozszerzana, tworząc uzupełnienie większego porządku częściowego. W ich metodzie zakończenie jest reprezentowane przez wyraźną listę cięć. Każdy przekrój rozszerzonego rzędu częściowego, z wyjątkiem tego, którego dwa zbiory przecinają się w nowym elemencie, jest albo przekrojem z poprzedniego rzędu częściowego, albo jest tworzony przez dodanie nowego elementu do jednej lub drugiej strony przecięcia z poprzedniego porządek częściowy, więc ich algorytm potrzebuje tylko par testowych zbiorów tej postaci, aby określić, które z nich są cięciami. Czas użycia ich metody do dodania pojedynczego elementu do zakończenia częściowego porządku wynosi $O (cnw)$ , gdzie $w$ jest szerokością częściowego porządku, czyli rozmiarem jego największego antyłańcucha . Dlatego czas do obliczenia zakończenia danego porządku częściowego wynosi $O (cn 2 w) = O (cn 3)$ .

Jak zauważają Jourdan, Rampon i Jard (1994) , problem wyliczenia wszystkich cięć w zbiorze częściowo uporządkowanym można sformułować jako szczególny przypadek prostszego problemu wyliczenia wszystkich maksymalnych antyłańcuchów w innym zbiorze częściowo uporządkowanym. Jeśli $P$ jest jakimkolwiek częściowo uporządkowanym zbiorem, niech $Q$ będzie porządkiem częściowym, którego elementy zawierają dwie kopie $P$ : dla każdego elementu $x$ z $P$ , $Q$ zawiera dwa elementy $x 0$ i $x 1$ , gdzie $x i < y j$ wtedy i tylko wtedy, gdy $x < y$ $i < j$ ja . Wtedy cięcia w $P$ odpowiadają jeden do jednego maksymalnym antyłańcuchom w $Q$ : elementy w dolnym zestawie cięcia odpowiadają elementom z indeksem dolnym 0 w antyłańcuchu, a elementy w górnym zestawie cięcia odpowiadają elementy z indeksem dolnym 1 w antyłańcuchu. Jourdana i in. opisz algorytm znajdowania maksymalnych antyłańcuchów, który zastosowany do problemu wyliczenia wszystkich cięć w $P$ , wymaga czasu $O (c (nw + w 3) )$ , ulepszenie algorytmu Gantera i Kuzniecowa (1998), gdy szerokość $w$ jest mały. Alternatywnie, maksymalny antyłańcuch w $Q$ jest tym samym, co maksymalny niezależny zbiór na grafie porównywalności Q lub maksymalna klika w dopełnieniu grafu porównywalności, więc algorytmy dla $problemu$ kliki lub problemu zbioru niezależnego można również zastosować do ta wersja problemu uzupełniania Dedekinda-MacNeille'a.

Konstruowanie grafu pokrywającego

Przechodnia redukcja lub wykres pokrycia uzupełnienia Dedekinda-MacNeille'a w zwięzły sposób opisuje relację porządku między jego elementami: każdy sąsiad przekroju musi usunąć element pierwotnego porządku częściowego z górnego lub dolnego zestawu przekroju, więc każdy wierzchołek ma co najwyżej $n$ sąsiadów. Zatem graf pokrywający ma $c$ wierzchołków i co najwyżej $cn /2$ sąsiadów, liczbę, która może być znacznie mniejsza niż $c 2$ wpisów w macierzy, która określa wszystkie porównania parami między elementami. Nourine i Raynaud (1999) pokazują, jak efektywnie obliczyć ten pokrywający wykres; bardziej ogólnie, jeśli $B$ jest jakąkolwiek rodziną zbiorów, pokazują one, jak obliczyć wykres pokrywający kratę sumy podzbiorów $B$ . W przypadku sieci Dedekinda-MacNeille'a $B$ można przyjąć jako rodzinę dopełnionych zbiorów ideałów głównych, a sumy podzbiorów $B$ są dopełnieniami niższych zbiorów przekrojów. Główną ideą ich algorytmu jest stopniowe generowanie sum podzbiorów $B$ (dla każdego zbioru w $B$ , tworząc jego sumę ze wszystkimi poprzednio wygenerowanymi sumami), reprezentowanie wynikowej rodziny zbiorów w trie i użycie reprezentacji trie do testowania pewnych kandydujące pary zbiorów na sąsiedztwo w relacji obejmującej; wymaga czasu $O (cn 2)$ . W późniejszych pracach ci sami autorzy wykazali, że algorytm może być w pełni przyrostowy (zdolny do dodawania elementów do częściowego porządku pojedynczo) z tym samym całkowitym ograniczeniem czasowym.

Notatki

Banaszewski, B.; Bruns, G. (1967), „Kategoryczna charakterystyka zakończenia MacNeille'a”, Archiv der Mathematik , 18 (4): 369–377, doi : 10.1007 / BF01898828 , MR 0221984 , S2CID 121216988 .
Birkhoff, Garrett (1995), „VI.9 Zakończenie przez cięcia”, Lattice Theory , Colloquium Publications, tom. 25 (wyd. 3), Amerykańskie Towarzystwo Matematyczne, s. 126–128, ISBN 978-0-8218-1025-5 .
Biskup, Alan A. (1978), „Uniwersalna charakterystyka odwzorowania uzupełniania przez cięcia”, Algebra Universalis , 8 (3): 349–353, doi : 10.1007/bf02485405 , MR 0469839 , S2CID 121624631 .
Cameron, Kathie (1985), „Sekwencje antyłańcuchowe”, Order , 2 (3): 249–255, doi : 10.1007 / BF00333130 , MR 0824698
Cotlar, Mischa (1944), „Metoda konstrukcji struktur i jej zastosowanie do przestrzeni topologicznych i arytmetyki abstrakcyjnej”, Univ. Nac. Tucuman. Revista A. , 4 : 105–157, MR 0014062 .
Davey, BA; Priestley, Hilary A. (2002), „7.38 Zakończenie Dedekinda – MacNeille'a” , Wprowadzenie do krat i porządku (wyd. 2), Cambridge University Press , s. 166, ISBN 978-0-521-78451-1 , Zbl 1002.06001 .
Funayama, Nenosuke (1944), „O zakończeniu cięć krat dystrybucyjnych”, Proceedings of the Imperial Academy, Tokio , 20 : 1–2, doi : 10.3792/pia/1195573210 , MR 0014063 , Zbl 0063.01484 .
Gabbay, Dow M .; Shehtman, Valentin; Skvortsov, Dimitrij (2009), „3.4.12 Zakończenie Dedekinda – MacNeille'a resztkowej sieci”, Quantification in Nonclassical Logic, tom 1 , Studies in logic and the fundations of matematyki, tom. 153, Elsevier, s. 177–178, ISBN 978-0-444-52012-8 , Zbl 1211.03002 .
Ganter, Bernhard; Kuznetsov, Sergei O. (1998), „Stopniowa budowa zakończenia Dedekinda-MacNeille'a”, Proc. 6. Int. konf. Struktury pojęciowe: teoria, narzędzia i zastosowania (ICCS98) , notatki z wykładów z informatyki, tom. 1453, Springer-Verlag, s. 295–302, doi : 10.1007/BFb0054922 , MR 1673860 , Zbl 0928.06004 .
Jourdan, Guy-Vincent; Rampon, Jean-Xavier; Jard, Claude (1994), „Obliczanie on-line kraty maksymalnych antyłańcuchów pozycji” (PDF) , Order , 11 (3): 197–210, doi : 10.1007 / BF02115811 , MR 1308475 , S2CID 120755660 , Zbl 0814.0600 4 .
MacNeille, HM (1937), "Zestawy częściowo uporządkowane", Transactions of the American Mathematical Society , 42 (3): 416–460, doi : 10.2307/1989739 , JFM 63.0833.04 , JSTOR 1989739 , MR 1501929 , Zbl 0017.3390 4 .
Nourine, Lhouari; Raynaud, Olivier (1999), „Szybki algorytm do budowania sieci” , Information Processing Letters , 71 (5–6): 199–204, doi : 10.1016 / S0020-0190 (99) 00108-8 , MR 1726978 , Zbl 0998.06005 .
Nourine, Lhouari; Raynaud, Olivier (2002), „Szybki algorytm przyrostowy do budowania krat”, Journal of Experimental and Theoretical Artificial Intelligence , 14 (2): 217–227, doi : 10.1080/09528130210164152 , S2CID 38160433 , Zbl 1022.68027 .
Novak, Vítězslav (1969), "Über eine Eigenschaft der Dedekind-MacNeilleschen Hülle", Mathematische Annalen , 179 : 337–342, doi : 10.1007/BF01350778 , MR 0240010 , S2CID 120963245 .
O'Leary, Michael L. (2015), Pierwszy kurs logiki matematycznej i teorii mnogości , John Wiley & Sons, s. 276, ISBN 978-0-470-90588-3
Roman, Steven (2007), Advanced Linear Algebra , Graduate Texts in Mathematics, tom. 135 (wyd. 3), Springer, s. 10–11, ISBN 978-0-387-72831-5
Schmidt, Jürgen (1956), "Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Hülle", Archiv der Mathematik (w języku niemieckim), 7 : 241–249, doi : 10.1007/BF01900297 , MR 0084484
Schröder, Bernd SW (2003), „5.3 Osadzone / Zakończenie Dedekind / MacNeille”, Zamówione zestawy: wprowadzenie , Birkäuser, s. 119–122, ISBN 978-1-4612-6591-7 .

Linki zewnętrzne