PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Svazy

Zobrazit kapitoly článku
  1. Relace
  2. Operace s relacemi
  3. Binární relace
  4. Binární relace na množině
  5. Relace ekvivalence
  6. Relace uspořádání
  7. Svazy

Svaz je uspořádaná množina, která je doplněna o vlastnost, že pro každé dva prvky z daného svazu musí existovat supremum a infimum, které také náleží danému svazu.

Horní a dolní kužel #

Na začátku máme množinu M, na které máme definované nějaké uspořádání . Toto uspořádání může být libovolné, ale musí splňovat podmínky relace uspořádání.

Dále vezmeme nějaký prvek a z množiny M. Horní kužel prvku a v množině M definujeme jako všechna \(x \in M\), která jsou větší nebo rovna než a, tedy platí pro ně a ≤ x.

Pokud si jako množinu vezmeme přirozená čísla a jako prvek a = 7, pak horním kuželem je množina čísel {7, 8, 9, …}. Na reálných číslech bychom získali interval \(\left<7, \infty\right)\).

Pokud bychom si vzali množinu \(M = 2^{\mathbb{N}}\) – jedná se o potenční množinu, tedy o množinu všech podmnožin přirozených číslech. Jedná se tak o všechny množiny, které můžeme zkonstruovat pomocí přirozených čísel. Uspořádání bude generováno pomocí relace podmnožiny. Platí tak, že {3, 5} ≤ {3, 4, 5} apod.

Horním kuželem množiny {1, 2, 3, 4} budou všechny množiny, které obsahují prvky 1, 2, 3, 4. Například množina {1, 2, 3, 4, 5, 6, 9} nebo {1, 2, 3, 4, 2323, 454645}. V horním kuželu bude i samotná množina {1, 2, 3, 4}.

Dolní kužel definujeme obdobně – obsahuje prvky, které jsou menší nebo rovny než prvek a. Pro a = 7 a M přirozená dostaneme množinu {1, 2, 3, 4, 5, 6, 7}. Jsou to ta přirozená čísla, která jsou menší nebo rovna sedmi.

Pro množinu {1, 2, 3, 4} dostaneme všechny podmnožiny této množiny.

Horní a dolní kužel více prvků #

V předchozí části jsme definovali kužele pro jeden prvek. My ale můžeme definovat kužel i pro více prvků. Pokud máme množinu M a prvky a, b, pak jejich společný horní kužel bude obsahovat prvky, které jsou větší nebo rovny než oba prvky a i b současně. Jinými slovy vypočítáme horní kužele obou prvků a spočítáme jejich průnik. Tím dostaneme prvky, které jsou určitě větší než a a zároveň větší než b.

Pokud zůstaneme u přirozených číslech: a = 3, b = 5. Všechny prvky větší nebo rovny než a jsou rovny množině {3, 4, 5, 6, …} a než b: {5, 6, 7, 8, …}. Nyní uděláme průnik, čímž dostaneme opět množinu {5, 6, 7, 8, …}. Pokud máme úplně uspořádanou množinu, tak stačí zjistit větší z těch dvou prvků a spočítat jeho horní kužel.

V případě množin už to tak jednoduché nebude. Můžeme si zkusit spočítat dolní kužel množin: a = {1, 2, 3} a b = {2, 3, 4}. Jsou to všechny množiny, které jsou zároveň podmnožinami a i b. Je například množina {1, 2, 3} podmnožinou a? Ano. Je i podmnožinou b? Ne. Tato množina nebude v dolním kuželi.

Můžeme se zkusit podívat na to, jaká bude největší množina, která bude podmnožinou a i b. Bude to zřejmě množina {2, 3}, což je množina, která vznikne průnikem množin \(a \cap b\). V dolním kuželi bude. A všechny podmnožiny této množiny také. Protože pokud například \(\emptyset \subseteq {2, 3}\) a zároveň \({2, 3} \subseteq a \wedge {2, 3} \subseteq b\), tak jistě i \(\emptyset \subseteq a \wedge \emptyset \subseteq b\). Vyplývá to z transitivity.

Nakonec si nadefinujeme horní a dolní kužel pro celou množinu, ne jen pro dvojici prvků. Mějme množinu M a nějakou množinu \(A \subseteq M\), pro kterou chceme spočítat horní a dolní kužel. Pak platí:

\[\begin{eqnarray}H(A)&=&\left\{x\,|\,\forall a\in A: x \ge a\right\}\\D(A)&=&\left\{x\,|\,\forall a\in A: x \le a\right\}\end{eqnarray}\]

Supremum a infimum #

Pomocí kuželů můžeme lehce zadefinovat infimum a supremum. Máme-li množinu M a prvek \(a \in M\), pak supremem i infimem prvku a je opět tentýž prvek a.

Chceme-li ale zjistit supremum dvou prvků z M, prvků a, b, pak už na to musíme jinak. Supremum z prvků a, b, značíme \(a \vee b\) nebo sup(a, b), se rovná nejmenšímu prvku z horního kužele prvků a, b. Tedy spočítáme si všechny prvky, které jsou větší nebo rovny než prvky a, b a z těch prvků vezmeme prvek nejmenší. Ne minimální, nejmenší. Nejmenší prvek obecně existovat nemusí, takže ani supremum obecně existovat nemusí.

Pokud počítáme infimum, tak nejdříve nalezneme dolní kužel obou prvků a poté nalezneme největší prvek.

Příklad: už víme, že horní kužel čísel 3 a 5 je množina {5, 6, 7, …}. Nejmenší prvek je rovný pěti. Platí tak, že sup(3, 5) = 5.

Dále víme, že dolní kužel množin a = {1, 2, 3} a b = {2, 3, 4} je rovný množině všech podmnožin množiny {2, 3}. To odpovídá množinám: {1, 2}, {1}, {2}, \(\emptyset\). Přičemž největší množina je právě množina {2, 3}. Takto množina je tak infimem množin a, b. Značíme \(a \wedge b = {2, 3}\) nebo inf(a, b) = {2, 3}.

Definice svazu #

Svaz S je uspořádaná množina, ve které ke každým dvěma prvkům \(a, b \in S\) existuje supremum a infimum, přičemž toto infimum a supremum patří do množiny S. Můžeme tak napsat, že uspořádaná množina S je svaz, pokud

\[\forall a,b \in S:\quad \sup(a, b) \in S\quad\mbox{a}\quad \inf(a, b) \in S\]

Jednoduchým příkladem svazu jsou reálná čísla s klasickým uspořádáním. Platí, že sup(a, b) = max(a, b) a inf(a, b) = min(a, b), což jsou vždy reálná čísla.

Systém množin s uspořádáním podle relace býti podmnožinou, jaký jsme si zavedli v minulé kapitole, je také svaz. Platí, že \(\sup(a, b) = a \cup b\) a \(\inf(a, b) = a \cap b\). To jsou opět množiny ze systému množin.

Pokud za systém množin S vezeme všechny dvouprvkové podmnožiny přirozených čísel (např. {1, 2}, {7, 19}, …), pak tato množina není svazem, protože například sup({1, 2}, {3, 4}) = {1, 2, 3, 4} a množina {1, 2, 3, 4} není prvkem množiny všech dvouprvkových podmnožin přirozených čísel.

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace