Dołącz i spotkaj się - Join and meet
Przechodnie relacje binarne | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Wszystkie definicje milcząco wymagają, aby jednorodna relacja była przechodnia : „ ” wskazuje, że właściwość kolumny jest wymagana przez definicję terminu wiersza (po lewej stronie). Na przykład definicja relacji równoważności wymaga, aby była ona symetryczna. Wymieniono tutaj dodatkowe właściwości, które może spełniać relacja jednorodna.
|
W matematyce , zwłaszcza teoria celu The połączyć z podzbioru o częściowy porządek jest Supremum (przynajmniej górna granica) o oznaczonej i podobnie, spotyka się z jest infimum (kres dolny), oznaczone w ogólności, łączenia i spotykają podzbioru częściowo uporządkowanego zbioru nie musi istnieć. Połącz i spotykaj się są podwójne w odniesieniu do odwrócenia kolejności.
Częściowo uporządkowany zestaw, w którym wszystkie pary mają sprzężenie, to sprzężenie-semilattyka . Podwójnie, częściowo uporządkowany zestaw, w którym wszystkie pary spotykają się, to spotkanie-semilattyka . Częściowo uporządkowany zestaw, który jest zarówno pół-semilatacją sprzężenia, jak i pół-semilatacją, jest kratą . Krata, w której każdy podzbiór, a nie tylko każda para, zawiera spotkanie i sprzężenie, jest pełną kratą . Możliwe jest również zdefiniowanie częściowej kraty , w której nie wszystkie pary mają spotkanie lub łączenie, ale operacje (jeśli są zdefiniowane) spełniają określone aksjomaty.
Złączenie/spotkanie podzbioru całkowicie uporządkowanego zbioru jest po prostu jego maksymalnym/minimalnym elementem, jeśli taki element istnieje.
Jeśli podzbiór częściowo uporządkowanego zbioru jest również (w górę) zbiorem skierowanym , to jego łączenie (jeśli istnieje) nazywane jest łączeniem skierowanym lub supremum skierowanym . Podwójnie, jeśli jest zbiorem skierowanym w dół, to jego spotkanie (jeśli istnieje) jest spotkaniem skierowanym lub skierowanym do dołu .
Podejście częściowego porządku
Niech będzie zbiorem z częściowego porządku i niech Element of jest spotkać (lubnajwiększa dolna granica lubinfimum )jeżeli spełnione są dwa następujące warunki:
- (to znaczy jest niższy związany z ).
- Dla dowolnego if then (czyli jest większa lub równa dowolnej innej dolnej granicy ).
Jeśli istnieje spotkanie, to jest unikalne, ponieważ jeśli oba są największymi dolnymi granicami wtedy, a zatem Jeśli spotkanie istnieje, jest to oznaczane Niektóre pary elementów mogą nie mieć spotkania, ponieważ w ogóle nie mają dolnego ograniczenia , lub ponieważ żadna z ich dolnych granic nie jest większa niż wszystkie inne. Jeśli wszystkie pary elementów z mają spotkać, to spotkać jest binarny operacja na i to łatwo zauważyć, że operacja ta spełnia następujące trzy warunki: W przypadku jakichkolwiek elementów
- ( przemienność ),
- ( stowarzyszenie ) i
- ( idempotencja ).
Przyłącza są zdefiniowane podwójnie przy sprzężeniu , jeśli istnieje, oznaczoną tu element o jest dołącz (lubnajmniejsza górna granica lubsupremum )in,jeżeli spełnione są dwa następujące warunki:
- (to znaczy, jest to górna granica w ).
- Dla any if then (czyli jest mniejsze lub równe dowolnej innej górnej granicy ).
Jeśli nie wszystkie pary elementów z mają się spotkać (odpowiednio join), to spotkanie (odpowiednio join) nadal może być postrzegane jako częściowa operacja binarna na
Uniwersalne podejście do algebry
Z definicji operacja binarna na zbiorze jest spełnieniem trzech warunków a , b i c . Para jest wtedy spotkaniem-semilatką . Co więcej, możemy następnie zdefiniować relację binarną na A , stwierdzając, że wtedy i tylko wtedy, gdy W rzeczywistości ta relacja jest częściowym porządkiem na Rzeczywiście, dla dowolnych elementów
- ponieważ przez c ;
- Jeśli następnie przez ; oraz
- jeśli to od tego czasu przez b .
Zarówno spotkania, jak i łączenia w równym stopniu spełniają tę definicję: kilka skojarzonych operacji spełniania i łączenia daje zamówienia częściowe, które są odwrotnością siebie. Wybierając jedno z tych zleceń jako główne, ustala się również, która operacja jest uważana za spotkanie (ta dająca to samo zamówienie), a która jest uważana za złączenie (druga).
Równoważność podejść
Jeśli jest zbiorem częściowo uporządkowanym , takim, że każda para elementów w ma spotkanie, to rzeczywiście wtedy i tylko wtedy, gdy w tym drugim przypadku rzeczywiście jest ograniczeniem dolnym i ponieważ jest największym ograniczeniem dolnym wtedy i tylko wtedy, gdy jest ograniczeniem dolnym uwiązany. Tak więc porządek częściowy zdefiniowany przez spotkanie w podejściu algebry uniwersalnej pokrywa się z pierwotnym porządkiem częściowym.
Z drugiej strony, jeśli jest Meet-semilattice i częściowe celu definiuje się jak w powszechnym podejścia Algebra, a dla niektórych elementów , a następnie jest największa dolna granica w odniesieniu do od
Innymi słowy, te dwa podejścia dają zasadniczo równoważne koncepcje, zbiór wyposażony zarówno w relację binarną, jak i operację binarną, w taki sposób, że każda z tych struktur determinuje drugą i spełnia odpowiednio warunki dla porządków cząstkowych lub spełnia.
Spotkania podzbiorów ogólnych
Jeśli jest to spotkanie-semilattic, to spotkanie może zostać rozszerzone na dobrze zdefiniowane spotkanie dowolnego niepustego skończonego zbioru, za pomocą techniki opisanej w iterowanych operacjach binarnych . Alternatywnie, jeśli spotkanie definiuje lub jest zdefiniowane przez porządek częściowy, niektóre podzbiory mają rzeczywiście niedoskonałości w odniesieniu do tego i rozsądne jest uznanie takiego niedoskonałości za spotkanie podzbioru. W przypadku niepustych podzbiorów skończonych te dwa podejścia dają ten sam wynik, a zatem każde z nich może być traktowane jako definicja spotkania. W przypadku, gdy każdy podzbiór ma spotkanie, w rzeczywistości jest to pełna krata ; aby uzyskać szczegółowe informacje, zobacz kompletność (teoria porządku) .
Uwagi
Bibliografia
- Davey, licencjat; Priestley, HA (2002). Wprowadzenie do Krat i Porządku (2nd ed.). Cambridge: Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 0-521-78451-4. Zbl 1002.06001 .
- Vickers, Steven (1989). Topologia przez logikę . Cambridge Tracts w informatyce teoretycznej. 5 . Numer ISBN 0-521-36062-5. Zbl 0668.54001 .