Spojení a průsek

V matematice, konkrétně v teorii uspořádání, spojení podmnožiny $S$ uspořádané množiny $P$ je supremum (nejmenší horní závora) množiny $S,$ které značíme ${\textstyle \bigvee S.}$ A obdobně průsek podmnožiny $S$ je infimum (největší dolní závora), které značíme ${\textstyle \bigwedge S.}$ Spojení a/nebo průsek podmnožiny částečně uspořádané množiny nemusí vždy existovat. Spojení a průsek jsou navzájem duální podle uspořádání inverzní.

Částečně uspořádaná množina, v níž má každá dvojice prvků supremum neboli spojení, nazýváme spojový polosvaz.^[1] Duálně, částečně uspořádaná množina, v níž má každá dvojice prvků infimum neboli průsek, nazýváme průsekový polosvaz.^[1] Částečně uspořádanou množinu, která je jak spojovým polosvazem tak průsekovým polosvazem nazýváme svaz. Svaz, ve kterém nejen každá dvojice, ale i každá podmnožina má průsek a spojení je úplný svaz. Je také možné definovat částečný svaz, ve kterém všechny dvojice prvků nemusí mít průsek nebo spojení, ale tyto operace (pokud jsou definovány) vyhovují určitým axiomům.^[2]

V případě lineárně uspořádané množiny je spojení resp. průsek podmnožiny prostě největší resp. nejmenší prvek její podmnožiny, pokud takový prvek existuje.

Pokud podmnožina $S$ částečně uspořádané množiny $P$ je také (nahoru) usměrněná, pak se její spojení (pokud existuje) nazývá orientované spojení nebo orientované supremum. Duálně, pokud $S$ je dolů usměrněná množina, pak se její průsek (pokud existuje) nazývá orientovaný průsek nebo orientované infimum.

Definice

Pro částečně uspořádané množiny

Nechť $A$ je množina s částečným uspořádáním $\,\leq ,\,$ a nechť $x,y\in A.$ Prvek $m$ množiny $A$ se nazývá spojení (nebo největší dolní závora nebo infimum) množiny $\{x,y\}$ a značí se $x\wedge y,$ pokud jsou splněny následující dvě podmínky:

$m\leq x{\text{ a }}m\leq y$ (tj. $m$ je dolní závora množiny $\{x,y\}$ ).
Pro libovolný $w\in A,$ pokud $w\leq x{\text{ a }}w\leq y,$ pak $w\leq m$ (tj. $m$ je větší nebo rovno jiné dolní závoře množiny $\{x,y\}$ ).

Průsek nemusí existovat, buď protože dvojice nemá vůbec žádnou dolní závoru, anebo protože žádná z dolních závor není větší než všechny ostatní. Pokud však existuje průsek množiny $\{x,y\},$ pak je jediný, protože, pokud oba $m{\text{ a }}m^{\prime }$ jsou největší dolní závory množiny $\{x,y\},$ pak $m\leq m^{\prime }{\text{ a }}m^{\prime }\leq m,$ a tedy $m=m^{\prime }.$ ^[3] Pokud všechny dvojice prvků z $A$ nemají průsek, pak průsek můžeme stále chápat jako částečnou binární operaci na $A.$ ^[2]

Pokud průsek existuje, značí se $x\wedge y.$ Pokud všechny dvojice prvků z $A$ mají průsek, pak je průsek binární operací na $A,$ a lze snadno vidět, že toto operace splňuje následující tři podmínky: Pro libovolné prvky $x,y,z\in A,$

$x\wedge y=y\wedge x$ (komutativita),
$x\wedge (y\wedge z)=(x\wedge y)\wedge z$ (asociativita), a
$x\wedge x=x$ (idempotence).

Spojení jsou definovaný duálně s spojení množiny $\{x,y\},$ pokud existuje, značí se $x\vee y.$ Prvek $j$ množiny $A$ je spojení (nebo nejmenší horní závora nebo supremum) množiny $\{x,y\}$ v $A$ pokud jsou splněny následující dvě podmínky:

$x\leq j{\text{ a }}y\leq j$ (tj. $j$ je horní závora $\{x,y\}$ ).
Pro libovolné $w\in A,$ pokud $x\leq w{\text{ a }}y\leq w,$ pak $j\leq w$ (tj. $j$ je menší nebo rovno jiné horní závoře $\{x,y\}$ ).

Algebraická definice

Podle definice Binární operace $\,\wedge \,$ na množina $A$ je spojení, pokud splňuje tři podmínky a, b a c. Dvojice $(A,\wedge )$ pak je průsekový polosvaz. Navíc pak můžeme definovat binární relaci $\,\leq \,$ na A, by uvádí, že $x\leq y$ právě tehdy, když $x\wedge y=x.$ Tato relace je vlastně částečným uspořádáním na $A.$ Skutečně, pro libovolné prvky $x,y,z\in A,$

$x\leq x,$ protože $x\wedge x=x$ podle c;
pokud $x\leq y{\text{ a }}y\leq x$ pak $x=x\wedge y=y\wedge x=y$ podle a; a
pokud $x\leq y{\text{ a }}y\leq z$ pak $x\leq z$ od té doby $x\wedge z=(x\wedge y)\wedge z=x\wedge (y\wedge z)=x\wedge y=x$ podle b.

Průseky i spojení také vyhovují této definici: dvojice souvisejících operací průseku a spojení dávají částečná uspořádání, která jsou svým vzájemným opakem. Při výběru jednoho z těchto uspořádání jako hlavního také fixujeme, kterou operaci považujeme za průsek (tu, která dává stejné uspořádání), a kterou považujeme za spojení (tu druhou).

Ekvivalence přístupů

Pokud $(A,\leq )$ je uspořádaná množina taková, že každá dvojice prvků v $A$ má průsek, pak skutečně $x\wedge y=x$ právě tehdy, když $x\leq y,$ protože ve druhém případě skutečně $x$ je dolní závorou $\{x,y\},$ a protože $x$ je největší dolní závora právě tehdy, když je dolní závora. Částečné uspořádání definované průsekem v přístupu vycházejícím z univerzální algebry se tedy shoduje s původní částečným uspořádáním.

Opačně, pokud $(A,\wedge )$ je průsekový polosvaz, a částečné uspořádání $\,\leq \,$ je definované jako v přístupu vycházejícím z univerzální algebry, a $z=x\wedge y$ pro nějaké prvky $x,y\in A,$ pak $z$ je největší dolní závorou množiny $\{x,y\}$ s uspořádáním $\,\leq ,\,$ protože

z\wedge x=x\wedge z=x\wedge (x\wedge y)=(x\wedge x)\wedge y=x\wedge y=z

a proto $z\leq x.$ Obdobně $z\leq y,$ a pokud $w$ je jiná dolní závora množiny $\{x,y\},$ pak $w\wedge x=w\wedge y=w,$ protože

w\wedge z=w\wedge (x\wedge y)=(w\wedge x)\wedge y=w\wedge y=w.

Existuje tedy průsek definovaný částečným uspořádáním definovaným původním průsekem, a oba průseky se shodují.

Jinými slovy, oba přístupy dávají v zásadě stejný výsledek, množinu opatřenou binární relací a binární operací, přičemž každá ztěchto struktur určuje tu druhou, a splňuje podmínku pro částečné uspořádání, respektive pro průseky.

Průseky obecných podmnožin

Pokud $(A,\wedge )$ je průsekový polosvaz, pak průsek může být rozšířena dobře definovaný průsek libovolné neprázdné konečné množiny, postupem popsaným v opakovaný binární operace. Alternativně, pokud průsek definuje nebo je definovaný vztahem částečné uspořádání, některé podmnožiny $A$ skutečně mít infima podle toto, a je významné považovat takový infimum jako průsek podmnožiny. Pro neprázdné konečné podmnožiny, dva přístupy dává stejný výsledek, a tak jak může být převzaté jako definice průsek. V případě, kdy každá podmnožina $A$ má průsek, vlastně $(A,\leq )$ je Úplný svaz; pro detaily, viz úplnost (uspořádání teorie).

Příklady

Pokud je nějaká potenční množina $\wp (X)$ částečně uspořádaná obvyklým způsobem (inkluzí, tj. relací $\,\subseteq$ ) pak spojení jsou sjednocení a průseky jsou průniky; při znázornění pomocí symbolů $\,\vee \,=\,\cup \,{\text{ a }}\,\wedge \,=\,\cap \,$ (kde podobnost těchto symbolů může posloužit pro zapamatování, že $\,\vee \,$ označuje spojení neboli supremum a $\,\wedge \,$ průsek neboli infimum^{[pozn. 1]}).

Obecněji, za předpokladu, že ${\mathcal {F}}\neq \varnothing$ je systém podmnožin nějaké množiny $X,$ který je částečně uspořádaný inkluzí $\,\subseteq .\,$ Pokud ${\mathcal {F}}$ je uzavřený pro libovolná sjednocení a libovolné průniky, a pokud $A,B,\left(F_{i}\right)_{i\in I}$ patří do ${\mathcal {F}}$ pak

A\vee B=A\cup B,\quad A\wedge B=A\cap B,\quad \bigvee _{i\in I}F_{i}=\bigcup _{i\in I}F_{i},\quad {\text{ a }}\quad \bigwedge _{i\in I}F_{i}=\bigcap _{i\in I}F_{i}.

pokud však systém ${\mathcal {F}}$ není uzavřený pro sjednocení, pak $A\vee B$ existuje v $({\mathcal {F}},\subseteq )$ právě tehdy, když existuje jediný $\,\subseteq$ -nejmenší $J\in {\mathcal {F}}$ takový, že $A\cup B\subseteq J.$ Pokud například ${\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\mathbb {R} \}$ pak $\{1\}\vee \{2\}=\{1,2,3\},$ zatímco pokud ${\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\{0,1,2\},\mathbb {R} \}$ pak $\{1\}\vee \{2\}$ neexistuje, protože množiny $\{0,1,2\}{\text{ a }}\{1,2,3\}$ jsou jediné horní závory množiny $\{1\}{\text{ a }}\{2\}$ v $({\mathcal {F}},\subseteq )$ což by mohlo případně být nejmenší horní závora $\{1\}\vee \{2\}$ ale $\{0,1,2\}\not \subseteq \{1,2,3\}$ a $\{1,2,3\}\not \subseteq \{0,1,2\}.$ Pokud ${\mathcal {F}}=\{\{1\},\{2\},\{0,2,3\},\{0,1,3\}\}$ pak $\{1\}\vee \{2\}$ neexistuje, protože neexistuje žádná horní závora množin $\{1\}{\text{ a }}\{2\}$ v $({\mathcal {F}},\subseteq ).$

Odkazy

Poznámky

↑ Okamžitě lze určit, že suprema a infima v tomto jednoduchém kanonickém příkladu jsou $(\wp (X),\subseteq )$ are $\,\cup \,{\text{ resp. }}\,\cap \,,$ . Podobnost symbolů $\,\vee \,$ s $\,\cup \,$ a $\,\wedge \,$ s $\,\cap \,$ může tedy posloužit pro zapamatování, že v nejobecnějším případě $\,\vee \,$ označuje supremum (protože supremum je omezené shora, stejně jako $A\cup B$ je „nad“ $A$ a $B$ ) zatímco $\,\wedge \,$ označuje infimum (protože infimum je omezené zdola, stejně jako $A\cap B$ je „pod“ $A$ a $B$ ). To lze také použít pro zapamatování, zda se průseky/spojení značí $\,\vee \,$ nebo $\,\wedge .\,$ Intuice naznačuje, že „spojení“ dvou množin musí produkovat jejich sjednocení $A\cup B,$ které vypadá podobně jako „spojení“ $A\vee B,$ a proto se spojení musí značit $A\vee B,$ . Obdobně dvě množiny musí mít „průsek“ v jejich průniku $A\cap B,$ který se značí podobně jako „průsek“ $A\wedge B,$ a proto se značí symbolem $\,\wedge .\,$

Reference

V tomto článku byl použit překlad textu z článku Join and meet na anglické Wikipedii.

↑ ^a ^b Faure a Heurgonová 1984, s. 57.
↑ ^a ^b GRÄTZER, George. General Lattice Theory: Second edition. [s.l.]: Springer Science & Business Media, 2002-11-21. Dostupné online. ISBN 978-3-7643-6996-5. S. 52. (anglicky)
↑ HACHTEL, Gary D.; SOMENZI, Fabio, 1996. Logic synthesis and verification algorithms. [s.l.]: Kluwer Academic Publishers. Dostupné online. ISBN 0792397460. S. 88.

Literatura

DAVEY, B.A.; PRIESTLEY, H.A., 2002. Introduction to Lattices and Order. 2. vyd. Cambridge: Cambridge University Press. ISBN 0-521-78451-4.
VICKERS, Steven, 1989. Topology via Logic. [s.l.]: [s.n.]. (Cambridge Tracts in Theoretic Computer Science). ISBN 0-521-36062-5.
ROBERT, Faure; HEURGONOVÁ, Edith, 1984. Uspořádání a Booleovy algebry. Praha: Academia.

Související články

Loálně konvexní svaz vektorů

[4] Okamžitě lze určit, že suprema a infima v tomto jednoduchém kanonickém příkladu jsou $(\wp (X),\subseteq )$ are $\,\cup \,{\text{ resp. }}\,\cap \,,$ . Podobnost symbolů $\,\vee \,$ s $\,\cup \,$ a $\,\wedge \,$ s $\,\cap \,$ může tedy posloužit pro zapamatování, že v nejobecnějším případě $\,\vee \,$ označuje supremum (protože supremum je omezené shora, stejně jako $A\cup B$ je „nad“ $A$ a $B$ ) zatímco $\,\wedge \,$ označuje infimum (protože infimum je omezené zdola, stejně jako $A\cap B$ je „pod“ $A$ a $B$ ). To lze také použít pro zapamatování, zda se průseky/spojení značí $\,\vee \,$ nebo $\,\wedge .\,$ Intuice naznačuje, že „spojení“ dvou množin musí produkovat jejich sjednocení $A\cup B,$ které vypadá podobně jako „spojení“ $A\vee B,$ a proto se spojení musí značit $A\vee B,$ . Obdobně dvě množiny musí mít „průsek“ v jejich průniku $A\cap B,$ který se značí podobně jako „průsek“ $A\wedge B,$ a proto se značí symbolem $\,\wedge .\,$

[FOOTNOTEFaureHeurgonová198457-1] Faure a Heurgonová 1984, s. 57.

[Grätzer-2] GRÄTZER, George. General Lattice Theory: Second edition. [s.l.]: Springer Science & Business Media, 2002-11-21. Dostupné online. ISBN 978-3-7643-6996-5. S. 52. (anglicky)

[3] HACHTEL, Gary D.; SOMENZI, Fabio, 1996. Logic synthesis and verification algorithms. [s.l.]: Kluwer Academic Publishers. Dostupné online. ISBN 0792397460. S. 88.

[1]

[2]

[3]

[pozn. 1]