Kompletna krata - Complete lattice

W matematyce , A zakończeniu kratownica jest częściowy porządek , w którym wszystkie podzbiory mają zarówno supremum (przyłączenia) i infimum (spotkać). W szczególności każda niepusta skończona sieć jest kompletna. Pełne kraty pojawiają się w wielu zastosowaniach w matematyce i informatyce . Będąc szczególnym przykładem krat , są one badane zarówno w teorii porządku, jak i algebrze uniwersalnej .

Zupełnych krat nie należy mylić z całkowitymi rzędami częściowymi ( cpo s), które stanowią ściśle bardziej ogólną klasę zbiorów częściowo uporządkowanych. Bardziej szczegółowe pełne kraty to kompletne algebry Boole'a i kompletne algebry Heytinga (ustawienia regionalne ).

Definicja formalna

Częściowo uporządkowanym ( l , ≤) jest pełna kraty , jeżeli każdy podzbiór z L ma zarówno kres dolny (The infimum , zwany również spotykają ) i co najmniej górna granica (The Supremum , zwany również dołączyć ) w ( L , ≤).

Spotykają oznaczamy i dołącz przez . ${\ Displaystyle \ duży klin A}$${\ displaystyle \ bigvee A}$

W szczególnym przypadku, gdy jest zbiorem pustym , spotykają się z A będzie największym elementem z L . Podobnie, łączenie pustego zestawu daje najmniejszy element . Ponieważ definicja zapewnia również istnienie binarnych spotkań i złączeń, pełne sieci tworzą w ten sposób specjalną klasę ograniczonych krat .

Więcej implikacji powyższej definicji omówiono w artykule o właściwościach kompletności w teorii porządku.

Kompletne półkraty

W teorii porządku, arbitralne spotkania można wyrazić w postaci dowolnych połączeń i odwrotnie (szczegóły patrz kompletność (teoria porządku) ). W efekcie oznacza to, że wystarczy wymagać istnienia wszystkich połączeń lub wszystkich połączeń, aby uzyskać klasę wszystkich pełnych sieci.

W konsekwencji, niektórzy autorzy używają terminów pełne spotkanie-półksiężyc lub kompletne połączenie-półksiężyc jako inny sposób określania pełnych kratownic. Chociaż podobne w odniesieniu do obiektów, terminy pociągają za sobą różne pojęcia homomorfizmu , co zostanie wyjaśnione w poniższej sekcji poświęconej morfizmom.

Z drugiej strony, niektórzy autorzy nie mają pożytku z tego rozróżnienia morfizmów (zwłaszcza, że ​​wyłaniające się koncepcje „kompletnych morfizmów semilattice” można równie dobrze określić w kategoriach ogólnych). W związku z tym kompletne półfabrykaty są również definiowane jako te półfabrykaty, które są również kompletnymi częściowymi zamówieniami . Ta koncepcja jest prawdopodobnie „najbardziej kompletnym” pojęciem spotkania-półksiężyca, które nie jest jeszcze kratą (w rzeczywistości może brakować tylko górnego elementu). Dyskusję tę można również znaleźć w artykule na temat semilattices .

Kompletne podpartie

Podsieci krystalicznej M pełnego siatkowej L nazywa się całkowitą podsieci krystalicznej o L , jeśli dla każdego podzbioru A z M elementy i , jak określono w L , w rzeczywistości w M . ${\ Displaystyle \ duży klin A}$${\ displaystyle \ bigvee A}$

Jeśli powyższe wymagania jest mniejsza wymagać jedynie niepusty spotykają się i łączy się z L The podsieci krystalicznej M nazywany jest zamknięty podsieci krystalicznej o M .

Przykłady

• Każda niepusta, skończona sieć jest trywialnie kompletna.
• Zestaw moc danego zestawu, uporządkowane według włączenia . Supremum jest nadawane przez związek, a dolne przez przecięcie podzbiorów.
• Przedział jednostkowy [0,1] i rozszerzony zbiór liczb rzeczywistych , przy znanej całkowitej porządku i zwykłą Suprema i Infima . Rzeczywiście, całkowicie uporządkowany zbiór (z jego topologią porządku ) jest zwarty jako przestrzeń topologiczna, jeśli jest kompletny jako krata.
• Nieujemne liczby całkowite , uporządkowane według podzielności . Najmniejszym elementem tej sieci jest liczba 1, ponieważ dzieli każdą inną liczbę. Być może zaskakujące jest to, że największym elementem jest 0, ponieważ można go podzielić przez dowolną inną liczbę. Wyższość zbiorów skończonych jest określona przez najmniejszą wspólną wielokrotność, a dolne przez największy wspólny dzielnik . W przypadku zbiorów nieskończonych, najwyższe zawsze będzie równe 0, podczas gdy dolne może być większe od 1. Na przykład zbiór wszystkich liczb parzystych ma 2 jako największy wspólny dzielnik. Jeśli 0 zostanie usunięte z tej struktury, pozostaje kratą, ale przestaje być kompletne.
• Podgrupy dowolnej włączanej grupy. (Podczas gdy infimum jest tutaj zwykłym przecięciem teorii mnogości, supremum zbioru podgrup jest podgrupą wygenerowaną przez sumę podgrup w teorii mnogości, a nie samą unię teorii mnogości). Jeśli e jest tożsamością G , wtedy trywialna grupa { e } jest minimalną podgrupą G , a maksymalna podgrupą jest sama grupa G .
• Podmoduły modułu uporządkowane według włączenia. Najwyższe jest sumą podmodułów, a dolną przez przecięcie.
• Te idee o pierścieniu , uporządkowane według włączenia. Supremum jest sumą ideałów i dolnego punktu przecięcia.
• Otwarte zbiory przestrzeni topologicznej uporządkowane według inkluzji. Supremum jest wynikiem połączenia zbiorów otwartych i dolnego końca przez wnętrze przecięcia.
• Te wypukłe podzbiory o rzeczywistej lub zespolonej przestrzeni wektorowej , zamówił przez włączenia. Dolinę daje przecięcie zbiorów wypukłych i supremum wypukłym kadłubem zrostu.
• W topologii na zbiorze, zamówił przez włączenia. Punkt dolny jest określony przez przecięcie topologii, a górny przez topologię wygenerowaną przez sumę topologii.
• Krata wszystkich relacji przechodnich na zbiorze.
• Siatka wszystkich podzbiorów multizbioru .
• Sieć wszystkich relacji równoważności na zbiorze; relacja równoważności ~ jest uważana za mniejszą (lub „drobniejszą”) niż ≈ jeśli x ~ y zawsze implikuje x ≈ y .
• Krata rzutów samosprzężonych (znanych również jako rzuty ortogonalne) algebry von Neumanna.

Lokalnie skończone pełne kraty

O kompletnej sieci L mówi się, że jest lokalnie skończona, jeśli supremum dowolnego nieskończonego podzbioru jest równe 1 lub równoważnie, zbiór jest skończony dla dowolnego . Sieć ( N , |) jest lokalnie skończona. Zauważ, że w tej sieci element ogólnie oznaczony jako „0” to w rzeczywistości 1 i na odwrót. ${\ Displaystyle \ {y \ w L ~ | ~ y \ leq x \} \ \!}$${\ displaystyle 1 \ neq x \ w L}$

Morfizmy pełnych krat

Tradycyjne morfizmy między pełnymi sieciami to kompletne homomorfizmy (lub pełne homomorfizmy kratowe ). Są one scharakteryzowane jako funkcje, które zachowują wszystkie połączenia i wszystkie spotkania. Oznacza to wyraźnie , że funkcja f: L→M pomiędzy dwiema pełnymi kratami L i M jest pełnym homomorfizmem, jeśli

• ${\ displaystyle f \ lewo (\ bigwedge A \ prawej) = \ bigwedge \ {f (a) \ mid a \ in A \}}$ i
• ${\ displaystyle f \ lewo (\ bigvee A \ prawej) = \ bigvee \ {f (a) \ środkowy a \ w A \}}$,

dla wszystkich podzbiorów A o L . Takie funkcje są automatycznie monotoniczne , ale warunek bycia całkowitym homomorfizmem jest w rzeczywistości znacznie bardziej szczegółowy. Z tego powodu przydatne może być rozważenie słabszych pojęć morfizmów, które są wymagane tylko do zachowania wszystkich złączeń (podając kategorię Sup ) lub wszystkich spełnia (podając kategorię Inf ), które są rzeczywiście nierównymi warunkami. Pojęcie to można traktować jako homomorfizm, odpowiednio, kompletnych półksiężyców łączonych lub kompletnych półlatych złączonych.

Ponadto morfizmy, które zachowują wszystkie połączenia, są równoważnie scharakteryzowane jako dolna część sprzężona unikalnego połączenia Galois . Każdy z nich wyznacza unikalne połączenie górne w odwrotnym kierunku, które zachowuje wszystkie styki. Stąd rozważanie pełnych krat z kompletnymi morfizmami semilattice sprowadza się do uznania połączeń Galois za morfizmy. Daje to również wgląd w to, że wprowadzone morfizmy zasadniczo opisują tylko dwie różne kategorie pełnych sieci kratowych: jedną z całkowitymi homomorfizmami i jedną z funkcjami zachowującymi spotkania (górne sprzężenie), podwójną do tej z odwzorowaniami zachowującymi łączenie (dolnymi łącznikami).

Bezpłatna budowa i ukończenie

Bezpłatne „pełne półlaty”

Jak zwykle, konstrukcja swobodnych obiektów zależy od wybranej klasy morfizmów. Rozważmy najpierw funkcje, które zachowują wszystkie sprzężenia (tj. Dolne sprzężenia połączeń Galois), ponieważ ten przypadek jest prostszy niż sytuacja dla pełnych homomorfizmów. Używając wyżej wymienionej terminologii, można to nazwać swobodnym pełnym zespoleniem półprzewodnikowym .

Używając standardowej definicji z algebry uniwersalnej , dowolna pełna sieć nad zbiorem generującym S jest pełną siecią L wraz z funkcją i : S → L , tak że każda funkcja f od S do podstawowego zbioru jakiejś pełnej sieci M może być czynnik czynnikowy jednoznacznie poprzez morfizm f ° od L do M . Inaczej mówiąc, dla każdego elementu s z S okazuje się, że f ( s ) = f ° ( i ( s )) i że f ° jest jedynym morfizmem z tą własnością. Warunki te sprowadzają się w zasadzie do stwierdzenia, że ​​istnieje funktor z kategorii zbiorów i funkcji do kategorii pełnych krat i funkcji zachowujących złączenia, który jest połączony z funktorem zapominalskim od pełnych krat do ich zbiorów bazowych.

Swobodne pełne sieci w tym sensie mogą być skonstruowane bardzo łatwo: pełna sieć generowana przez pewien zbiór S jest po prostu zbiorem potęgowym 2 ^S , tj. zbiorem wszystkich podzbiorów S , uporządkowanym przez włączenie podzbioru . Wymagana jednostka i : S → 2 ^S odwzorowuje dowolny element s z S na zbiór singletonów { s }. Biorąc pod uwagę odwzorowanie f jak powyżej, funkcja f °: 2 ^S → M jest zdefiniowana przez

${\ displaystyle f ^ {\ circ} (X) = \ bigvee \ {f (s) | s \ in X \}}$.

Następnie f ° przekształca związki w suprema, a tym samym zachowuje połączenia.

Nasze rozważania dają również swobodną konstrukcję dla morfizmów, które zachowują połączenia zamiast połączeń (tj. Górne sprzężenia połączeń Galois). W rzeczywistości musimy jedynie dualizować to, co zostało powiedziane powyżej: wolne obiekty są podane jako powersets uporządkowane przez inkluzję odwrotną, tak że set union zapewnia operację spełniania, a funkcja f ° jest zdefiniowana w kategoriach spełnia zamiast złączeń. Rezultat tej konstrukcji można nazwać swobodnym kompletnym spotkaniem semilattice . Należy również zauważyć, w jaki sposób te konstrukcje swobodne rozszerzają te, które są używane do uzyskania półsieci swobodnych , gdzie musimy tylko uwzględnić zbiory skończone.

Darmowe kompletne kraty

Sytuacja dla pełnych krat z całkowitymi homomorfizmami jest oczywiście bardziej skomplikowana. W rzeczywistości wolne kompletne kraty generalnie nie istnieją. Oczywiście można sformułować problem tekstowy podobny do tego dla krat , ale zbiór wszystkich możliwych słów (lub "wyrażeń") w tym przypadku byłby właściwą klasą , ponieważ arbitralne spotkania i łączenia zawierają operacje na argumenty -zestawy o każdej liczności .

Własność ta sama w sobie nie stanowi problemu: jak pokazuje powyższy przypadek zupełnych swobodnej półsieci, równie dobrze może być tak, że rozwiązanie zadania tekstowego pozostawia tylko zbiór klas równoważności. Innymi słowy, możliwe jest, że odpowiednie klasy wszystkich terminów mają to samo znaczenie i są w ten sposób identyfikowane w konstrukcji swobodnej. Jednak klasy równoważności dla zadania tekstowego z całkowitymi sieciami są „zbyt małe”, tak że wolna pełna krata nadal byłaby właściwą klasą, co jest niedozwolone.

Nadal można mieć nadzieję, że istnieją przydatne przypadki, w których zestaw generatorów jest wystarczająco mały, aby istniała wolna, kompletna sieć. Niestety limit rozmiaru jest bardzo niski i mamy następujące twierdzenie:

Swobodna pełna sieć na trzech generatorach nie istnieje; to jest właściwa klasa .

Dowód na to oświadczenie podaje Johnstone; oryginalny argument przypisywany jest Alfredowi W. Halesowi ; zobacz także artykuł o swobodnych kratach .

Ukończenie

Jeśli z danego posetu, użytego w miejsce rozpatrywanego powyżej zestawu generatorów, generowana jest dowolna sieć , to mówi się o uzupełnieniu posetu. Definicja wyniku tej operacji jest podobna do powyższej definicji obiektów swobodnych, gdzie "zbiory" i "funkcje" są zastąpione przez "posety" i "odwzorowania monotoniczne". Podobnie proces uzupełniania można opisać jako funktor z kategorii posetów z funkcjami monotonicznymi do pewnej kategorii pełnych krat z odpowiednimi morfizmami, które są w odwrotnym kierunku połączone z funktorem zapominalskim.

Tak długo, jak uważa się funkcje chroniące spotkania lub połączenia za morfizmy, można to łatwo osiągnąć poprzez tak zwane uzupełnienie Dedekinda-MacNeille'a . W tym procesie elementy posetu są mapowane do (Dedekind-) cięć , które następnie mogą być mapowane do leżących poniżej posetów dowolnych kompletnych sieci w podobny sposób, jak w przypadku zestawów i swobodnych kompletnych (semi-) sieci powyżej.

Wspomniany wynik, że nie istnieją swobodne pełne kraty, powoduje, że nie jest również możliwa zgodna swobodna konstrukcja z posetu. Można to łatwo zauważyć, rozważając pozy w dyskretnym porządku, w którym każdy element odnosi się tylko do siebie. To są dokładnie wolne posety na podstawowym zbiorze. Gdyby istniała swobodna konstrukcja kompletnych krat z posetów, to obie konstrukcje mogłyby być złożone, co przeczy powyższemu negatywnemu wynikowi.

Reprezentacja

Już książka G. Birkhoffa o teorii krat zawiera bardzo przydatną metodę reprezentacji. Wiąże kompletną sieć z dowolną relacją binarną między dwoma zestawami, konstruując połączenie Galois z relacji, co następnie prowadzi do dwóch podwójnie izomorficznych systemów domknięć . Systemy zamknięć to rodziny zbiorów zamknięte przez przecięcie. Po uporządkowaniu przez relację podzbioru ⊆ są one kompletnymi kratami.

Szczególny przykład konstrukcji Birkhoffa rozpoczyna się od dowolnego pozy (P,≤) i konstruuje połączenie Galois z relacji porządku ≤ między P a nim samym. Otrzymana kompletna sieć jest dopełnieniem Dedekinda-MacNeille'a . Kiedy to uzupełnienie zostanie zastosowane do posetu, który już jest kompletną siatką, wówczas wynik jest izomorficzny z pierwotnym. W ten sposób od razu stwierdzamy, że każda kompletna sieć jest reprezentowana przez metodę Birkhoffa, aż do izomorfizmu.

Konstrukcja jest wykorzystywana w formalnej analizie pojęć , w której dane są reprezentowane przez rzeczywiste słowa za pomocą relacji binarnych (zwanych kontekstami formalnymi ) i wykorzystuje się powiązane pełne kraty (zwane kratami pojęciowymi ) do analizy danych. Matematyką stojącą za formalną analizą pojęć jest zatem teoria sieci pełnych.

Inną reprezentację uzyskuje się w następujący sposób: podzbiór pełnej sieci jest sam w sobie kompletną siecią (gdy jest uporządkowana w kolejności indukowanej) wtedy i tylko wtedy, gdy jest obrazem rosnącej i idempotentnej (ale niekoniecznie rozległej) mapy własnej. Mapowanie tożsamości ma oczywiście te dwie właściwości. W ten sposób występują wszystkie pełne sieci.

Dalsze wyniki

Oprócz poprzednich wyników reprezentacji, istnieją inne stwierdzenia, które można sformułować na temat pełnych krat lub które w tym przypadku przybierają szczególnie prostą formę. Przykładem jest twierdzenie Knastera-Tarskiego , które stwierdza, że ​​zbiór punktów stałych funkcji monotonicznej na pełnej sieci jest ponownie pełną siecią. Można to łatwo zauważyć jako uogólnienie powyższej obserwacji na temat obrazów funkcji rosnących i idempotentnych, ponieważ są to przykłady twierdzenia.

Zobacz też

• krata (zamówienie) .

Bibliografia