Krata (zamówienie) - Lattice (order)

Kratownica jest abstrakcyjne struktury badanej w matematycznych subdyscyplin teorii zlecenia i algebry abstrakcyjnej . Składa się z częściowo uporządkowanego zestawu, w którym każda para elementów ma unikalną wartość supremum (zwaną również najmniejszą granicą górną lub złączeniem ) i unikalną granicę (zwaną również największą dolną granicą lub spotkaniem ). Przykładem jest przez zestaw zasilania zestawu częściowo uporządkowane przez włączenie , których Supremum jest związek i infimum jest przecięcie . Innym przykładem są liczby naturalne , częściowo uporządkowane według podzielności , dla których supremum jest najmniejszą wspólną wielokrotnością, a dolna jest największym wspólnym dzielnikiem .

Kraty można również scharakteryzować jako struktury algebraiczne spełniające pewne tożsamości aksjomatyczne . Ponieważ obie definicje są równoważne, teoria krat czerpie zarówno z teorii rzędów, jak i algebry uniwersalnej . Półsieci obejmują kraty, które z kolei zawierają algebry Heytinga i Boole'a . Wszystkie te struktury przypominające kraty dopuszczają opisy zarówno teoretyczne, jak i algebraiczne.

Kraty jako zestawy częściowo uporządkowane

Jeśli jest częściowo uporządkowanym (poset) i jest dowolna podgrupa, po czym element jest mówi się, że górna granica w jeśli dla każdego zestawu A może posiadać wiele górnych granic, lub wcale. Mówi się, że górne ograniczenie z jest jego dolnym górnym ograniczeniem , albo join , albo supremum , jeśli dla każdego górnego ograniczenia zbioru A nie musi mieć górnego ograniczenia, ale nie może mieć więcej niż jedno. Podwójnie , to mówi się, że dolna granica od jeśli dla każdego dolną granicę stanowi mówi się, że jej kres dolny , lub spotkać lub infimum , jeśli dla każdej dolną granicę stanowi Zestaw może mieć wiele niższe granice, albo wcale , ale może mieć co najwyżej jedną największą dolną granicę. ${\displaystyle (L,\leq)}$${\displaystyle S\subseteq L}$${\displaystyle u\wl}$${\displaystyle S}$${\displaystyle s\leq u}$${\displaystyle s\w S.}$${\ Displaystyle u}$${\displaystyle S}$${\displaystyle u\leq x}$${\displaystyle x}$${\ Displaystyle S.}$${\displaystyle l\wl}$${\displaystyle S}$${\displaystyle l\leq s}$${\displaystyle s\w S.}$${\displaystyle l}$${\displaystyle S}$${\displaystyle x\leql}$${\displaystyle x}$${\ Displaystyle S.}$

Częściowo uporządkowany zbiór nazywany jest półzbiorem złączenia jeśli każdy dwuelementowy podzbiór ma złącze (tzn. najmniejsze ograniczenie górne, oznaczone przez ) i jest nazywany spotkaniem półprzyczepy jeśli każdy podzbiór dwóch elementów ma spotkanie (tzn. największe ograniczenie dolne , oznaczony przez ). nazywa się kratą, jeśli jest zarówno połączeniem, jak i spotkaniem semilattyki. Ta definicja tworzy i operacje binarne . Obie operacje są monotonne w stosunku do podanej kolejności: i implikuje, że i${\displaystyle (L,\leq)}$${\ Displaystyle \ {a, b \} \ podseteq L}$${\displaystyle a\vee b}$${\displaystyle a\klin b}$${\displaystyle (L,\leq)}$${\displaystyle \,\klin \,}$${\displaystyle \,\vee \,}$ ${\displaystyle a_{1}\leq a_{2}}$${\displaystyle b_{1}\leq b_{2}}$${\displaystyle a_{1}\vee b_{1}\leq a_{2}\vee b_{2}}$${\displaystyle a_{1}\klin b_{1}\leq a_{2}\klin b_{2}.}$

Z argumentu indukcyjnego wynika, że ​​każdy niepusty skończony podzbiór sieci ma najmniejszą górną granicę i największą dolną granicę. Przy dodatkowych założeniach możliwe są dalsze wnioski; zobacz Kompletność (teoria porządku), aby uzyskać więcej dyskusji na ten temat. W artykule tym omówiono również, w jaki sposób można przeformułować powyższą definicję pod kątem istnienia odpowiednich powiązań Galois między powiązanymi częściowo uporządkowanymi zbiorami — podejście szczególnie interesujące dla podejścia teorii kategorii do krat i formalnej analizy pojęć .

Ograniczonym, krata jest kratownica, że dodatkowo ma największą elementu (zwany również maksymalną lub górną elementu, a oznaczony przez 1, lub ) oraz co najmniej elementem (zwany również minimalne lub dolna , oznaczone przez 0 lub po ), które spełniają ${\displaystyle \\top}$${\displaystyle \\bot}$

Każda sieć może być osadzona w ograniczonej sieci przez dodanie największego i najmniejszego elementu, a każda niepusta skończona sieć jest ograniczona, biorąc połączenie (odpowiednio spotkanie) wszystkich elementów, oznaczone przez (odpowiednio ) gdzie${\ Displaystyle \ Bigvee L = a_ {1} \ Lor \ cdots \ Lor a_ {n} = 1}$${\ Displaystyle \ bigwedge L = a_ {1} \ ziemia \ cdots \ ziemia a_ {n} = 0}$${\ Displaystyle L = \ lewo \ {a_ {1} \ ldots, a_ {n} \ po prawej \}.}$

Częściowo uporządkowany zbiór jest ograniczoną kratą wtedy i tylko wtedy, gdy każdy skończony zbiór elementów (włącznie ze zbiorem pustym) ma sprzężenie i spotkanie. Dla każdego elementu posetu jest bezsensownie prawdą, że i dlatego każdy element posetu jest zarówno górnym, jak i dolnym ograniczeniem zestawu pustego. Oznacza to, że złączenie zbioru pustego jest najmniejszym elementem, a spotkanie zbioru pustego największym elementem Jest to zgodne z asocjatywnością i przemiennością zbioru spotkaj i złącz: złączenie zbioru skończonych zbiorów jest równe złączeniu z łączy z zestawów, a podwójnie, spotykają się z unii zbiorów skończonych jest równa spotykają się z spotyka się z zestawów, czyli ,, dla skończonych podzbiorów o poset${\displaystyle x}$${\displaystyle {\tekst{dla wszystkich}}a\in \varnic, x\leq a}$${\displaystyle {\tekst{dla wszystkich}}a\in \varnic,a\leq x,}$${\ Displaystyle \ Bigvee \ Varnic = 0,}$${\ Displaystyle \ bigwedge \ varnothing = 1.}$${\displaystyle A{\tekst{i}}B}$${\ Displaystyle L}$

oraz trzymać. Biorąc B za pusty zestaw, oraz

co jest zgodne z faktem, że ${\ Displaystyle A \ filiżanka \ varnothing = A.}$

Mówi się, że element sieciowy pokrywa inny element, jeśli nie istnieje taki, że Tutaj oznacza i${\displaystyle y}$${\displaystyle x}$${\displaystyle y>x}$${\displaystyle z}$${\displaystyle y>z>x.}$${\displaystyle y>x}$${\displaystyle x\leq y}$${\displaystyle x\neq y.}$

Krata nazywana jest graded , czasami klasyfikowana (ale zobacz Pozycja rankingowa dla alternatywnego znaczenia), jeśli może być wyposażona w funkcję rangi czasami do ℤ, kompatybilną z kolejnością (więc kiedykolwiek ) tak, że kiedykolwiek obejmuje to Wartość rangi funkcja dla elementu kratowego nazywana jest jego rangą . ${\displaystyle (L,\leq)}$ ${\ Displaystyle r: L \ do \ mathbb {N} }$${\displaystyle r(x)<r(y)}$${\displaystyle x<y}$${\displaystyle y}$${\displaystyle x}$${\ Displaystyle r (y) = r (x) + 1.}$

Biorąc podzbiór Krata, spotykają się i dołącz ograniczać do funkcji częściowych - są niezdefiniowane, jeżeli ich wartość nie jest w podgrupie Uzyskana struktura na nazywana jest${\displaystyle H\subseteq L}$${\ Displaystyle H.}$${\ Displaystyle H}$ częściowa sieć . Oprócz tej zewnętrznej definicji jako podzbioru jakiejś innej struktury algebraicznej (kraty), częściowa krata może być również wewnętrznie zdefiniowana jako zbiór z dwoma częściowymi operacjami binarnymi spełniającymi pewne aksjomaty.

Kraty jako struktury algebraiczne

Ogólna krata

Algebraiczna struktura , składająca się z zestawu oraz dwóch binarnych, przemiennych i asocjacyjnych operacji i na to kraty , jeżeli następujące tożsamości aksjomatyczne trzymać dla wszystkich elementów czasami zwane prawa absorpcji . ${\displaystyle (L,\vee,\klin)}$${\ Displaystyle L}$ ${\displaystyle \,\vee \,}$${\displaystyle \,\klin,}$${\ Displaystyle L}$${\displaystyle a,b\wl,}$

Następujące dwie tożsamości są również zwykle uważane za aksjomaty, mimo że wynikają z dwóch praw absorpcji wziętych razem. Są to tak zwane prawa idempotentne .

Te aksjomaty zakładają , że oba i są półsieciami . Prawa absorpcji, jedyne powyższe aksjomaty, w których zarówno spotykają się, jak i łączą, odróżniają sieć od arbitralnej pary struktur półsieciowych i zapewniają, że dwie półsieci oddziałują odpowiednio. W szczególności każda półsieć jest podwójną drugą. Prawa absorpcji mogą być postrzegane jako wymóg, aby półsieci stykały się i łączyły określały ten sam porządek częściowy . ${\displaystyle (L,\vee)}$${\ Displaystyle (L, \ klin)}$

Ograniczona krata

Ograniczonym, krata jest algebraiczna konstrukcja formy , tak że jest kratownica, (dolnej kraty'S) jest element neutralny dla operacji łączenia i (górna kratownica'S) jest element identyfikacyjny operacji spotykają${\displaystyle (L,\vee,\klin ,0,1)}$${\displaystyle (L,\vee,\klin)}$${\ Displaystyle 0}$${\displaystyle \,\vee,\,}$${\ Displaystyle 1}$${\displaystyle\,\klin.}$

Zobacz semilattice w celu uzyskania dalszych szczegółów.

Połączenie z innymi strukturami algebraicznymi

Kraty mają pewne powiązania z rodziną grupopodobnych struktur algebraicznych . Ponieważ spotykają się i dołączają zarówno do dojeżdżania, jak i kojarzenia, kratę można postrzegać jako składającą się z dwóch przemiennych półgrup mających tę samą domenę. Dla sieci ograniczonej te półgrupy są w rzeczywistości monoidami przemiennymi . Prawo absorpcji to jedyna definiująca tożsamość, która jest charakterystyczna dla teorii sieci.

Przez przemienność, asocjatywność i idempotentność można myśleć o łączeniu i spotykaniu jako o operacjach na niepustych zbiorach skończonych, a nie na parach elementów. W ograniczonej sieci można również zdefiniować sprzężenie i spotkanie pustego zbioru (jako i odpowiednio). To sprawia, że ​​kraty ograniczone są nieco bardziej naturalne niż kraty ogólne, a wielu autorów wymaga, aby wszystkie kraty były ograniczone. ${\ Displaystyle 0}$${\displaystyle 1,}$

Interpretacja algebraiczna krat odgrywa zasadniczą rolę w algebrze uniwersalnej .

Związek między dwiema definicjami

Zlecenie-teoretyczny kratownica skłania do dwóch operacji binarnych i od czasu przemienne, łączność i absorpcji można łatwo zweryfikować dla tych operacji, robią w kratę w sensie algebraicznym. ${\displaystyle \,\vee \,}$${\displaystyle\,\klin.}$${\displaystyle (L,\vee,\klin)}$

Odwrotność też jest prawdziwa. Mając algebraicznie zdefiniowaną sieć, można zdefiniować porządek częściowy na przez ustawienie ${\displaystyle (L,\vee,\klin),}$${\displaystyle \,\leq \,}$${\ Displaystyle L}$

dla wszystkich elementów Prawa absorpcji zapewniają, że obie definicje są równoważne: ${\displaystyle a,b\wl.}$

${\displaystyle a=a\klin b{\tekst{implikuje}}b=b\vee (b\klin a)=(a\klin b)\veeb=a\veeb}$

i podwójnie dla drugiego kierunku.

Można teraz sprawdzić, czy wprowadzona w ten sposób relacja ≤ definiuje częściowe uporządkowanie, w którym binarne spotyka się i łączy się poprzez oryginalne operacje i${\displaystyle \,\vee \,}$${\displaystyle\,\klin.}$

Ponieważ obie definicje sieci są równoważne, można swobodnie powoływać się na aspekty obu definicji w dowolny sposób, który odpowiada zamierzonemu celowi.

Przykłady

• 

  Fotka. 1: Podgrupy pod zadanej włączenia . Nazwę „krata” sugeruje forma przedstawiającego ją diagramu Hassego . ${\displaystyle \{x,y,z\}}$

• 

  Fotka. 2. Krata dzielników całkowitych 60, zamawianych przez „ dzieli ”.

• 

  Fotka. 3: Krata partycji z zamówionych przez „ uszlachetnia ”. ${\ Displaystyle \ {1,2,3,4 \},}$

• 

  Fotka. 4: Krata liczb całkowitych dodatnich, uporządkowana według${\displaystyle \,\leq,}$

• 

  Fotka. 5: Krata nieujemnych par liczb całkowitych, uporządkowana składowo.

• W przypadku każdego zestawu zbierania wszystkich podzbiorów (zwany zestaw mocy z ) można zamówić przez włączenie podzbioru uzyskać siatkę ograniczony siebie i pustego zestawu. Ustaw przecięcie i ustaw związek interpretuj odpowiednio spotkaj i połącz (patrz rys. 1).${\displaystyle A}$${\ Displaystyle A}$${\ Displaystyle A}$${\ Displaystyle A}$
• Dla dowolnego zbioru zbiór wszystkich skończonych podzbiorów uporządkowanych przez inkluzję jest również kratą i będzie ograniczony wtedy i tylko wtedy, gdy jest skończony.${\displaystyle A}$${\displaystyle A}$${\ Displaystyle A}$
• Dla dowolnego zbioru Zbiór wszystkich partycjach z zamówionych przez wyrafinowania , jest kratownica (patrz Rys. 3).${\displaystyle A}$${\displaystyle A}$
• Te dodatnie liczby całkowite w zwykłej celu utworzenia siatki, na operacji „min” i „max.” 1 to dół; nie ma góry (patrz rys. 4).
• Kartezjański kwadratowy z liczb naturalnych, tak uporządkowane, że jeśli Para jest dolna część; nie ma góry (patrz rys. 5).${\displaystyle (a,b)\leq (c,d)}$${\displaystyle a\leq c{\text{i}}b\leq d.}$${\ Displaystyle (0,0)}$
• Liczby naturalne tworzą również siatkę w wyniku operacji brania największego wspólnego dzielnika i najmniejszej wspólnej wielokrotności , z podzielnością jako relacją porządku: jeśli dzielenie jest dolne; jest na szczycie. Fotka. 2 przedstawia skończoną podsieć.${\displaystyle a\leq b}$${\displaystyle a}$${\displaystyle b.}$ ${\ Displaystyle 1}$${\ Displaystyle 0}$
• Każda kompletna siatka (patrz również poniżej ) jest (raczej specyficzną) ograniczoną siecią. Ta klasa daje początek szerokiej gamie praktycznych przykładów .
• Zestaw zwartych elementów z z arytmetycznego kompletnej siatki jest kratownica z elementem, w którym co najmniej kratownica operacje są kolejno ograniczenie odpowiednich operacji arytmetycznych kraty. Jest to specyficzna właściwość, która odróżnia kraty arytmetyczne od krat algebraicznych , dla których zwarte tworzą jedynie sprzężenie-semilattykę . Obie te klasy kompletnych sieci są badane w teorii domen .

Dalsze przykłady sieci podano dla każdej z dodatkowych właściwości omówionych poniżej.

Przykłady nie-krat

Fotka. 8: Non-kratownica poset: i mają wspólne dolne granice i ale żaden z nich nie jest kres dolny .${\displaystyle a}$${\displaystyle b}$${\displaystyle 0,d,g,h,}$${\displaystyle ja,}$

Fotka. 7: Non-kratownica poset: i mają wspólne górne granice i ale żaden z nich nie jest kresem górnym .${\displaystyle b}$${\displaystyle c}$${\displaystyle d,e}$${\displaystyle f}$

Fotka. 6: Poset bez siatki: i nie mają wspólnej górnej granicy.${\displaystyle c}$${\displaystyle d}$

Większość częściowo uporządkowanych zestawów nie jest kratami, w tym następujące.

• Poset dyskretny, co oznacza poset taki, który implikuje, jest kratą wtedy i tylko wtedy, gdy ma co najwyżej jeden element. W szczególności dwuelementowa dyskretna poset nie jest siatką.${\displaystyle x\leq y}$${\displaystyle x=y}$
• Chociaż zbiór częściowo uporządkowany według podzielności jest kratą, tak uporządkowany zbiór nie jest kratą, ponieważ w parze 2, 3 brakuje złączenia; podobnie 2, 3 brakuje spotkania w${\ Displaystyle \ {1,2,3,6 \}}$${\ Displaystyle \ {1,2,3 \}}$${\ Displaystyle \ {2,3,6 \}.}$
• Zbiór częściowo uporządkowany przez podzielność nie jest kratą. Każda para elementów ma ograniczenie górne i dolne, ale para 2, 3 ma trzy ograniczenia górne, mianowicie 12, 18 i 36, z których żaden nie jest najmniejszym z tych trzech w ramach podzielności (12 i 18 nie dzielą wzajemnie). Podobnie para 12, 18 ma trzy dolne granice, a mianowicie 1, 2 i 3, z których żadna nie jest największa z tych trzech w ramach podzielności (2 i 3 nie dzielą się nawzajem).${\ Displaystyle \ {1,2,3,12,18,36\}}$

Morfizmy krat

Odpowiednie pojęcie morfizmu między dwiema kratami łatwo wypływa z powyższej definicji algebraicznej. Biorąc pod uwagę dwie kraty i kraty homomorfizm od L do M jest funkcją tak, że dla wszystkich${\ Displaystyle \ lewo (L \ Vee _ {L} \ klin _ {L} \ po prawej)}$${\ Displaystyle \ lewo (M \ Vee _ {M} \ klin _ {M} \ po prawej)}$${\displaystyle f:L\do M}$${\displaystyle a,b\wl:}$

Tak więc jest homomorfizm dwóch leżących poniżej półsieci . Gdy rozważane są sieci o większej strukturze, morfizmy również powinny „szanować” dodatkową strukturę. W szczególności homomorfizm o ograniczonej sieci (zwykle nazywany po prostu „homomorfizmem sieci”) między dwiema granicami sieci i powinien mieć również następującą właściwość: ${\displaystyle f}$${\displaystyle f}$${\ Displaystyle L}$${\ Displaystyle M}$

W ujęciu teorii rzędów warunki te po prostu stwierdzają, że homomorfizm krat jest funkcją zachowującą spełnienie i złączenia binarne. Dla sieci ograniczonych zachowanie najmniejszych i największych elementów jest tylko zachowaniem sprzężenia i spotkania pustego zbioru.

Każdy homomorfizm krat jest z konieczności monotonny w odniesieniu do powiązanej relacji porządkującej; zobacz Funkcja zachowywania limitów . Odwrotność nie jest prawdą: monotoniczność w żadnym wypadku nie implikuje wymaganego zachowania spotkań i złączeń (patrz rys. 9), chociaż bijekcja z zachowaniem porządku jest homomorfizmem, jeśli jego odwrotność jest również z zachowaniem porządku.

Biorąc pod uwagę standardową definicję izomorfizmów jako odwracalnych morfizmów, izomorfizm sieci jest po prostu bijektywnym homomorfizmem sieci. Podobnie endomorfizm sieci jest homomorfizmem sieci od sieci do siebie, a automorfizm sieci jest bijektywnym endomorfizmem sieci. Kraty i ich homomorfizmy tworzą kategorię .

Niech i będą dwiema kratami z 0 i 1 . Homomorfizmem od się nazywa 0,1 - rozdzielania , wtedy i tylko wtedy, gdy ( oddziela 0 ) i ( oddziela 1). ${\ Displaystyle \ mathbb {L} }$${\ Displaystyle \ mathbb {L} '}$${\ Displaystyle \ mathbb {L} }$${\ Displaystyle \ mathbb {L} '}$ ${\ Displaystyle f ^ {-1} \ {f (0) \} = \ {0 \}}$${\displaystyle f}$${\ Displaystyle f ^ {-1} \ {f (1) \} = \ {1 \}}$${\displaystyle f}$

Podsieci

Podsieci krystalicznej z siatki jest podzbiorem to kratownicy z tej samej operacji łączenia i spotykają się w Oznacza to, że jeśli jest siatkową i jest podzbiorem , że dla każdej pary elementów obu i są następnie jest podsieci krystalicznej${\ Displaystyle L}$${\ Displaystyle L}$${\ Displaystyle L.}$${\ Displaystyle L}$${\ Displaystyle M}$${\ Displaystyle L}$${\displaystyle a,b\w m}$${\displaystyle a\klin b}$${\displaystyle a\vee b}$${\displaystyle M}$${\ Displaystyle M}$${\ Displaystyle L.}$

Podsieci krystalicznej z siatki jest wypukła podsieci krystalicznej z jeśli i sugeruje, że należy do wszystkich elementów${\ Displaystyle M}$${\ Displaystyle L}$${\ Displaystyle L}$${\displaystyle x\leq z\leq y}$${\displaystyle x,y\wm}$${\displaystyle z}$${\displaystyle M}$${\displaystyle x,y,z\wl.}$

Właściwości sieci

Wprowadzamy teraz szereg ważnych właściwości, które prowadzą do interesujących specjalnych klas sieci. Jedna, granica, została już omówiona.

Kompletność

Poset nazywa się pełną kratą, jeśli wszystkie jego podzbiory mają zarówno złącze, jak i spotkanie. W szczególności każda pełna sieć jest siecią ograniczoną. Podczas gdy ograniczone homomorfizmy sieci ogólnie zachowują tylko skończone złączenia i spotkania, pełne homomorfizmy sieci są wymagane do zachowania dowolnych złączeń i spotkań.

Każdy poset będący kompletną półsiecią jest również kompletną kratą. Z tym wynikiem wiąże się interesujące zjawisko polegające na tym, że istnieją różne konkurujące ze sobą pojęcia homomorfizmu dla tej klasy pozów, w zależności od tego, czy są one postrzegane jako pełne kraty, pełne sprzężenia-semilattyki, pełne spotkania-semilattyki, czy też jako kompletne lub pełne złączeń. kompletne kraty.

Zauważ, że „częściowa sieć” nie jest przeciwieństwem „pełnej sieci” – raczej „częściowa sieć”, „sieć” i „pełna sieć” są coraz bardziej restrykcyjnymi definicjami.

Warunkowa kompletność

Warunkowo zakończeniu kratownica jest kratownica, w której każdy niepusty podzbiór które górna granica musi łączyć (to jest co najmniej górna granica). Takie ogrodzenia zapewniają najbardziej bezpośrednie uogólnienie aksjomatu kompletności tych liczb rzeczywistych . Warunkowo pełna sieć jest albo pełną siecią, albo pełną siecią bez elementu maksymalnego, elementu minimalnego lub obu. ${\displaystyle 1,}$${\displaystyle 0,}$

Dystrybucja

Fotka. 11: Najmniejsza niemodularna (a więc niedystrybucyjna) sieć N 5 . Oznaczone elementy naruszają równanie rozdzielności, ale spełniają jego dualizm${\ Displaystyle c \ klin (a \ vee b) = (c \ klin a) \ vee (c \ klin b)}$${\ Displaystyle c \ vee (a \ klin b) = (c \ vee a) \ klin (c \ vee b).}$

Fotka. 10: Najmniejsza niedystrybucyjna (ale modułowa) sieć M 3 .

Ponieważ kraty mają dwie operacje binarne, naturalne jest pytanie, czy jedna z nich rozkłada się na drugą, to znaczy czy jedno lub drugie z następujących praw dualnych obowiązuje dla każdych trzech elementów : ${\displaystyle a,b,c\wl,}$

Dystrybucja ponad${\displaystyle \,\vee \,}$${\displaystyle \,\klin \,}$

Dystrybucja ponad${\displaystyle \,\klin \,}$${\displaystyle \,\vee \,}$

Krata, która spełnia pierwszy lub równoważnie (jak się okazuje) drugi aksjomat, nazywana jest kratą rozdzielczą . Jedyne sieci niedystrybucyjne zawierające mniej niż 6 elementów nazywają się M ₃ i N ₅ ; pokazano je odpowiednio na rysunkach 10 i 11. Sieć jest dystrybutywna wtedy i tylko wtedy, gdy nie ma izomorficznej podsieci z M ₃ lub N ₅ . Każda rozdzielcza krata jest izomorficzna z kratą zbiorów (z sumą i przecięciem jako odpowiednio połącz i spotkaj).

Aby zapoznać się z przeglądem silniejszych pojęć rozdzielności, które są odpowiednie dla pełnych sieci i które są używane do definiowania bardziej specjalnych klas sieci, takich jak ramy i sieci całkowicie rozdzielcze , zobacz teoria rozdzielności w porządku .

Modułowość

W przypadku niektórych zastosowań warunek rozdzielności jest zbyt silny i często przydatna jest następująca słabsza właściwość. Krata jest modularna, jeśli dla wszystkich elementów zachodzi następująca identyczność: ( Tożsamość modularna ) Warunek ten jest równoważny następującemu aksjomatowi: implikuje ( Prawo modularności ) Krata jest modularna wtedy i tylko wtedy, gdy nie ma podsieci izomorficznej z N ₅ (pokazano na rys. 11). Poza siatkach dystrybucyjnych przykłady siatek modułowych Krata dwustronnych idei o pierścieniu , kraty podmodułów o module i krata normalnych podgrupy o grupie . Zestaw warunków pierwszego rzędu z zamawiania „jest bardziej szczegółowy niż” jest organizacją non-modułowy kraty stosowane w zautomatyzowanym rozumowania . ${\displaystyle (L,\vee,\klin)}$${\displaystyle a,b,c\wl,}$${\ Displaystyle (a \ klin c) \ vee (b \ klin c) = ((a \ klin c) \ vee b) \ klin c.}$
${\displaystyle a\leq c}$${\ Displaystyle a \ vee (b \ klin c) = (a \ vee b) \ klin c.}$

Semimodularność

Sieć skończona jest modularna wtedy i tylko wtedy, gdy jest zarówno górna, jak i dolna semimodularna . W przypadku sieci stopniowanej (górna) semimodularność jest równoważna następującemu warunkowi funkcji rang${\displaystyle r:}$

${\ Displaystyle r (x) + r (y) \ geq r (x \ klin y) + r (x \ vee y).}$

Innym równoważnym (dla stopniowanych krat) warunkiem jest warunek Birkhoffa :

dla każdego i w przypadku i obu pokrywa to obejmuje zarówno i${\displaystyle x}$${\displaystyle y}$${\ Displaystyle L}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\klin y}$${\displaystyle x\vee y}$${\displaystyle x}$${\ Displaystyle y.}$

Krata nazywana jest niższym semimodularnym, jeśli jej dual jest semimodularny. W przypadku skończonych sieci oznacza to, że poprzednie warunki są spełnione i zamienione, „pokrywy” zamienione na „jest objęte”, a nierówności odwrócone. ${\displaystyle \,\vee \,}$${\displaystyle \,\klin \,}$

Ciągłość i algebraiczność

W teorii domen naturalne jest dążenie do przybliżenia elementów w porządku częściowym przez „znacznie prostsze” elementy. Prowadzi to do klasy posetów ciągłych , składającej się z posetów, w których każdy element może być uzyskany jako supremum skierowanego zestawu elementów, które są znacznie poniżej elementu. Jeśli można je dodatkowo ograniczyć do zwartych elementów posetu w celu uzyskania tych skierowanych zbiorów, to poset jest nawet algebraiczny . Obie koncepcje można zastosować do sieci w następujący sposób:

• Sieć ciągła to pełna sieć, która jest ciągła jako poset.
• Algebraiczne kratownica jest kompletnym kratownica to algebraiczne jako poset.

Obie te klasy mają ciekawe właściwości. Na przykład sieci ciągłe można scharakteryzować jako struktury algebraiczne (z operacjami nieskończoności) spełniające określone tożsamości. Chociaż taka charakterystyka nie jest znana dla krat algebraicznych, można je opisać „syntaktycznie” za pomocą systemów informacyjnych Scotta .

Uzupełnienia i pseudouzupełnienia

Niech będzie kratą ograniczoną z największym elementem 1 i najmniejszym elementem 0. Dwa elementy i z są dopełnieniami siebie wtedy i tylko wtedy, gdy: ${\ Displaystyle L}$${\displaystyle x}$${\displaystyle y}$${\ Displaystyle L}$

Ogólnie rzecz biorąc, niektóre elementy sieci ograniczonej mogą nie mieć dopełnienia, a inne mogą mieć więcej niż jedno dopełnienie. Na przykład zestaw ze swoim zwykłym uporządkowaniem jest ograniczoną siatką i nie ma dopełnienia. W ograniczonym kraty N ₅ , element posiada dwa dopełnienia, a mianowicie. i (patrz rys. 11). Krata ograniczona, dla której każdy element ma dopełnienie, nazywana jest siecią uzupełnioną . ${\ Displaystyle \ {0,1/2,1 \}}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

Uzupełnioną kratą, która jest również dystrybutywna, jest algebra Boole'a . W przypadku sieci rozdzielczej dopełnienie tego, kiedy istnieje, jest wyjątkowe. ${\displaystyle x}$

W przypadku dopełnieniem jest wyjątkowy, piszemy ¬ x = y i równoważnie ¬ y = x . Odpowiednia jednoargumentowa operacja nad zwaną komplementacją wprowadza analogię logicznej negacji do teorii krat. ${\ Displaystyle L}$

Algebry Heytinga są przykładem krat rozdzielczych, w których niektórym członom może brakować dopełnień. Każdy element z algebry Heytinga ma, z drugiej strony, A na pseudo-dopełniacza , oznaczany także ¬ x . Pseudouzupełnienie jest największym elementem tak, że Jeśli pseudouzupełnienie każdego elementu algebry Heytinga jest w rzeczywistości dopełnieniem, to algebra Heytinga jest w rzeczywistości algebrą Boole'a. ${\displaystyle z}$${\displaystyle y}$${\displaystyle x\klin y=0.}$

Stan łańcucha Jordan-Dedekind

Łańcucha od celu jest zestaw , w którym długość tej sieci jest N lub mniej niż jeden liczbę elementów. Łańcuch jest maksymalny, jeśli obejmuje wszystkich${\displaystyle x_{0}}$${\displaystyle x_{n}}$${\ Displaystyle \ lewo \ {x_ {0}, x_ {1}, \ ldots, x_ {n} \ po prawej \},}$${\displaystyle x_{0}<x_{1}<x_{2}<\ldots <x_{n}.}$${\displaystyle x_{i}}$${\displaystyle x_{i-1}}$${\displaystyle 1\leq i\leq n.}$

Jeśli dla każdej pary, a gdzie wszystkie sieci maksymalne od aby mieć taką samą długość, a następnie kratownica mówi się zaspokoić Jordan-DEDEKIND stan łańcucha . ${\displaystyle x}$${\displaystyle y}$${\displaystyle x<y}$${\displaystyle x}$${\displaystyle y}$

Darmowe kraty

Każdy zestaw może być używany do generowania wolnego semilattice Wolną semilattice zdefiniowany składać się ze wszystkich podzbiorów skończonych z semilattice działania danego zwykłą zestaw jedności . Swobodna półsieć ma właściwość uniwersalną . Za darmo kraty na zbiorze Whitman dała konstrukcję opartą na wielomianów nad " członków s. ${\ Displaystyle X}$ ${\displaystyle FX.}$${\displaystyle X,}$${\displaystyle X,}$ ${\ Displaystyle X}$

Ważne pojęcia w teorii sieci

Zdefiniujemy teraz kilka pojęć teorii rzędów, które mają znaczenie dla teorii sieci. W dalszej części niech będzie elementem jakiejś sieci Jeśli ma dolny element jest czasami wymagany. nazywa się: ${\displaystyle x}$${\ Displaystyle L.}$${\ Displaystyle L}$${\displaystyle 0,}$ ${\displaystyle x\neq 0}$${\displaystyle x}$

• Łączenie nieredukowalne, jeśli implikuje dla wszystkich Kiedy pierwszy warunek jest uogólniony na arbitralne łączenie nazywa się łączeniem całkowicie nieredukowalnym (lub -irreducible). Podwójnym pojęciem jest spełnienie nieredukowalności ( -irreducible). Na przykład na rys. 2, elementy 2, 3, 4 i 5 łączą się nieredukowalnie, podczas gdy 12, 15, 20 i 30 łączą się nieredukowalnie. W siatce liczb rzeczywistych o zwykłym porządku każdy element jest sprzężony nierozkładalny, ale żaden nie jest całkowicie złączony nierozkładalny.${\displaystyle x=a\vee b}$${\displaystyle x=a{\tekst{lub}}x=b.}$${\displaystyle a,b\wl.}$${\ Displaystyle \ Bigvee _ {i \ w I} a_ {i}}$ ${\displaystyle x}$${\displaystyle \vee}$${\ Displaystyle \ klin}$
• Połącz pierwsze, jeśli implikuje To również można uogólnić, aby uzyskać pojęcie całkowicie złączyć pierwsze . Podwójnym pojęciem jest spotkanie pierwsze . Każdy element sprzężenia pierwszego jest również nieredukowalny, a każdy element styku pierwszego jest również nieredukowalny. Odwrotność obowiązuje, jeśli jest dystrybutywna.${\displaystyle x\leq a\vee b}$${\displaystyle x\leq a{\tekst{lub}}x\leq b.}$${\ Displaystyle L}$

Pozwolić mieć dolny element 0. Element of stanowi atom jeśli i nie istnieje żaden element, taki, że A jest o nazwie: ${\ Displaystyle L}$${\displaystyle x}$${\ Displaystyle L}$${\displaystyle 0<x}$${\ Displaystyle y \ w L}$${\displaystyle 0<y<x.}$${\ Displaystyle L}$

• Atomowych , jeśli dla każdego elementu niezerowym w istnieje atom w taki sposób, że${\displaystyle x}$${\ Displaystyle L}$${\displaystyle a}$${\ Displaystyle L}$${\displaystyle a\leq x;}$
• Atomistyczny jeśli każdy element jest Supremum atomów.${\ Displaystyle L}$

Pojęcia ideałów i podwójne pojęcie filtrów odnoszą się do poszczególnych rodzajów podzbiorów zbioru częściowo uporządkowanego i dlatego są ważne dla teorii sieci. Szczegóły można znaleźć w odpowiednich wpisach.

Zobacz też

• Dołącz i spotkaj się
• Mapa krat
• Krata ortouzupełniona
• Zamówienie całkowite  – Zamówienie, którego wszystkie elementy są porównywalne
• Idealny i filtrujący (podwójne pojęcia)
• Skew lattice (uogólnienie do nieprzemiennego łączenia i spotykania)
• Sieć Eulera
• Krata posta
• Krata Tamari
• Sieć Younga-Fibonacciego
• 0,1-prosta krata

Aplikacje wykorzystujące teorię sieciową

Zauważ, że w wielu zastosowaniach zbiory są tylko częściowymi sieciami: nie każda para elementów ma spotkanie lub złącze.

• Topologia bezcelowa
• Krata podgrup
• Przestrzeń spektralna
• Niezmiennicza podprzestrzeń
• Operator zamknięcia
• Abstrakcyjna interpretacja
• Sieć subsumpcji
• Teoria zbiorów rozmytych

Uwagi

Bibliografia

Monografie dostępne bezpłatnie online:

• Burris, Stanley N. i Sankappanavar, HP, 1981. Kurs algebry uniwersalnej. Springer-Verlag. ISBN  3-540-90578-2 .
• Jipsen, Peter i Henry Rose, Varieties of Lattices , Wykład z matematyki 1533, Springer Verlag, 1992. ISBN  0-387-56314-8 .
• Nation, JB, Uwagi dotyczące teorii krat . Rozdziały 1-6. rozdziały 7-12; Załączniki 1–3.

Teksty podstawowe zalecane dla osób z ograniczoną dojrzałością matematyczną :

• Donnellan, Thomas, 1968. Teoria kraty . Pergamon.
• Grätzer, George , 1971. Teoria krat: Pierwsze koncepcje i kraty rozdzielcze . WH Freemana.

Standardowy współczesny tekst wprowadzający, nieco trudniejszy niż powyższy:

• Davey, licencjat; Priestley, HA (2002), Wprowadzenie do krat i porządku , Cambridge University Press , ISBN 978-0-521-78451-1

Zaawansowane monografie:

• Garrett Birkhoff , 1967. Teoria kraty , wyd. Tom. 25 publikacji AMS Colloquium. Amerykańskie Towarzystwo Matematyczne .
• Robert P. Dilworth i Crawley, Peter, 1973. Algebraiczna teoria krat . Prentice-Hall. ISBN  978-0-13-022269-5 .
• Grätzer, George (1996) [1978]. Ogólna teoria sieci (wyd. drugie). Bazylea: Birkhäuser. Numer ISBN 978-3-7643-6996-5.

Na darmowych kratach:

• R. Freese, J. Jezek i JB Nation, 1985. „Free Lattices”. Ankiety matematyczne i monografie tom. 42. Matematyczne Stowarzyszenie Ameryki .
• Johnstone, PT , 1982. Przestrzenie kamienia . Cambridge Studies in Advanced Mathematics 3. Cambridge University Press.

O historii teorii krat:

• Štĕpánka Bilová (2001). Eduarda Fuchsa (red.). Teoria sieci — jej narodziny i życie (PDF) . Prometeusz. s. 250-257.

O zastosowaniach teorii sieci:

• Garrett Birkhoff (1967). James C. Opat (red.). Co mogą dla Ciebie zrobić Lattices? . Van Nostranda. Spis treści

Zewnętrzne linki

• "Grupa uporządkowana w sieci" , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Weisstein, Eric W. „Krata” . MatematykaŚwiat .
• JB Nation, Notes on Lattice Theory , niepublikowane notatki do kursu dostępne w postaci dwóch plików PDF.
• Ralph Freese, „Strona domowa teorii krat” .
• Sekwencja OEIS A006966 (Liczba nieoznakowanych sieci z n elementami)