Připojte se a setkejte se - Join and meet

Tento Hasseův diagram zobrazuje částečně uspořádanou sadu se čtyřmi prvky - A, b, maximální prvek rovná se spojení A a b (A ∨ b) a minimální prvek rovná se setkání A a b (A ∧ b). Spojení / splnění prvku maximální / minimální a dalšího prvku je prvek maximální / minimální a naopak splnění / spojení prvku maximální / minimální s jiným prvkem je dalším prvkem. Každý pár v tomto posetu tedy má jak schůzku, tak spojení a poset lze klasifikovat jako a mřížka (teorie objednávek).

v matematika konkrétně teorie objednávek, připojit se a podmnožina S a částečně objednaná sada P je supremum (nejméně horní mez) S, označeno ⋁Sa podobně setkat z S je infimum (největší dolní mez), označeno ⋀S. Obecně platí, že spojení a setkávání podmnožiny částečně uspořádané sady nemusí existovat. Připojte se a setkejte se dvojí navzájem s ohledem na inverzi objednávky.

Částečně uspořádaná množina, ve které mají všechny páry spojení, je a spojit-semilattice. Duálně je částečně uspořádaná sada, ve které se setkávají všechny páry, a setkat-semilattice. Částečně uspořádaná množina, která je spojovací a semilatickou, je a mříž. Mřížka, ve které se každá podskupina, nejen každá dvojice, setkává a spojení je úplná mříž. Je také možné definovat a částečná mříž, ve kterém se ne všechny páry setkávají nebo se připojují, ale operace (pokud jsou definovány) splňují určité axiomy.^[1]

Spojení / setkání podmnožiny a úplně objednaná sada je jednoduše jeho maximální / minimální prvek, pokud takový prvek existuje.

Pokud podmnožina S částečně objednané sady P je také (nahoru) řízená sada, pak se jeho spojení (pokud existuje) nazývá a řízené spojení nebo řízený supremum. Duálně, pokud S je sestava směřující dolů, pak její splnění (pokud existuje) je řízené setkání nebo řízený infimum.

Přístup částečné objednávky

Nechat A být set s částečná objednávka ≤ a nechte X a y být dva prvky v A. Prvek z z A je setkání (nebo největší dolní hranice nebo infimum) z X a y, pokud jsou splněny následující dvě podmínky:

1. z ≤ X a z ≤ y (tj., z je dolní mez X a y).
2. Pro všechny w v A, takový, že w ≤ X a w ≤ y, my máme w ≤ z (tj., z je větší nebo rovno jakékoli jiné spodní hranici X a y).

Pokud dojde k setkání X a y, pak je jedinečný, protože pokud obojí z a z′ Jsou největší dolní hranice X a y, pak z ≤ z′ a z′ ≤ z, a tudíž z = z′. Pokud schůzka existuje, je označena X ∧ yNěkteré páry prvků v A může postrádat setkání, buď proto, že vůbec nemají dolní mez, nebo protože žádná z jejich dolních mezí není větší než všechny ostatní. Pokud jsou všechny páry prvků z A mít schůzku, pak je schůzka a binární operace na A, a je snadno vidět, že tato operace splňuje následující tři podmínky: Pro všechny prvky X, y, a z v A,

A. X ∧ y = y ∧ X (komutativita ),

b. X ∧ (y ∧ z) = (X ∧ y) ∧ z (asociativita ), a

C. X ∧ X = X (idempotence ).

Spojení jsou definována duálně a spojení X a y v A (pokud existuje) je označeno X ∨ y. Pokud ne všechny páry prvků z A mít schůzku (respektive se připojit), pak lze schůzku (respektive připojit) stále považovat za částečný binární operace zapnuta A.

Přístup univerzální algebry

Podle definice a binární operace ∧ na setu A je setkat pokud splňuje tři podmínky A, b, a C. Dvojice (A, ∧) je pak a setkat-semilattice. Dále pak můžeme definovat a binární relace ≤ zapnuto Atím, že to uvedete X ≤ y kdyby a jen kdyby X ∧ y = X. Ve skutečnosti je tento vztah částečná objednávka na A. Ve skutečnosti pro všechny prvky X, y, a z v A,

• X ≤ X, od té doby X ∧ X = X podle C;
• -li X ≤ y a y ≤ X, pak X = X ∧ y = y ∧ X = y podle A; a
• -li X ≤ y a y ≤ z, pak X ≤ z, od té doby X ∧ z = (X ∧ y) ∧ z = X ∧ (y ∧ z) = X ∧ y = X podle b.

Všimněte si, že jak splnění, tak spojení se shodují s touto definicí: pár přidružených operací setkání a spojení přináší dílčí objednávky, které jsou naopak. Když vyberete jednu z těchto objednávek jako hlavní, opraví se také, která operace se považuje za splnění (ta, která dává stejnou objednávku) a která se považuje za spojení (druhá).

Rovnocennost přístupů

Pokud (A, ≤) je a částečně objednaná sada, takže každá dvojice prvků v A má tedy schůzku X ∧ y = X kdyby a jen kdyby X ≤ y, protože ve druhém případě skutečně X je dolní mez X a y, a protože jasně X je největší dolní mez právě tehdy, pokud se jedná o dolní mez. Částečný řád definovaný metodou meet v univerzální algebře se tedy shoduje s původním dílčím řádem.

Naopak, pokud (A, ∧) je a setkat-semilattice a dílčí řád ≤ je definován jako v přístupu univerzální algebry a z = X ∧ y pro některé prvky X a y v A, pak z je největší dolní mez X a y vzhledem k ≤, protože

z ∧ X = X ∧ z = X ∧ (X ∧ y) = (X ∧ X) ∧ y = X ∧ y = z

a proto z ≤ X. Podobně, z ≤ y, a pokud w je další dolní mez X a y, pak w ∧ X = w ∧ y = w, odkud

w ∧ z = w ∧ (X ∧ y) = (w ∧ X) ∧ y = w ∧ y = w.

Existuje tedy schůzka definovaná částečným řádem definovaným původní schůzkou a dvě schůzky se shodují.

Jinými slovy, dva přístupy přinášejí v zásadě ekvivalentní koncepty, množinu vybavenou jak binárním vztahem, tak binární operací, takže každá z těchto struktur určuje druhou a splňuje podmínky pro dílčí objednávky nebo splňuje.

Splňuje obecné podmnožiny

Pokud (A, ∧) je meet-semilattice, pak může být meet rozšířen na dobře definovaný meet any neprázdný konečná množina technikou popsanou v iterované binární operace. Alternativně, pokud setkání definuje nebo je definováno částečným řádem, některé podmnožiny A opravdu mít infima s ohledem na to, a je rozumné považovat takové infimum jako setkání podmnožiny. U neprázdných konečných podmnožin tyto dva přístupy přinášejí stejný výsledek, a proto lze oba brát jako definici meet. V případě, že každý podmnožina A ve skutečnosti má schůzku (A, ≤) je a úplná mříž; podrobnosti viz úplnost (teorie objednávek).

Poznámky

Reference