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 ∈ 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 <7, ∞).

Pokud bychom si vzali množinu M = 2^ℕ — 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 ∩ b. V dolním kuželi bude. A všechny podmnožiny této množiny také. Protože pokud například ∅ ⊆ {2, 3} a zároveň {2, 3} ⊆ a ∧ {2, 3} ⊆ b, tak jistě i ∅ ⊆ a ∧ ∅ ⊆ 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 ⊆ 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 ∈ 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 ∨ 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}, ∅. 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 ∧ 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 ∈ 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 ∪ b a inf(a, b) = a ∩ 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.