Svaz (matematika)

Následující struktury se běžně definují jako algebraické struktury, ale lze je definovat i pomocí částečných uspořádání:

Poset (tj. částečně uspořádaná množina) ${\displaystyle M}$  se nazývá spojový polosvaz, pokud nad každými dvěma prvky ${\displaystyle a,b\in M}$  existuje supremum neboli nejmenší horní závora. Pojem horní závora ${\displaystyle h}$  znamená, že ${\displaystyle a\preceq h}$  a ${\displaystyle b\preceq h}$ . Pojem nejmenší pak to, že musí předcházet každé jiné horní závoře.

Ekvivalentně lze spojový polosvaz definovat jako algebraickou strukturu s binární operací ${\displaystyle \lor }$  zvanou spojení, která splňuje axiomy:

Asociativita: ${\displaystyle (a\lor b)\lor c=a\lor (b\lor c)}$  
Komutativita: ${\displaystyle a\lor b=b\lor a}$ 
Idempotence:${\displaystyle a\lor a=a}$ 

Ekvivalence těchto zdánlivě různorodých definice plyne z toho, že

• Je-li na množině definována struktura polosvazu algebraicky, ekvivalentem je poset, v němž ${\displaystyle a\preceq b}$  je definováno jako ${\displaystyle a\lor b=b}$ .
• Naopak od posetu k algebraické definici lze přejít tak, že spojení dvou prvků je definováno jako jejich supremum, které ve spojovém polosvazu vždy existuje.

Obdobně průsekový polosvaz je poset, v němž každá dvojice prvků má infimum neboli největší horní závoru. Ekvivalentně je to množina s binární operací ${\displaystyle \land }$  zvanou průsek, která odpovídá infimu v posetech. Axiomy jsou stejné. Relace předcházení v posetech (${\displaystyle a\preceq b}$ ) je definována vztahem ${\displaystyle a\land b=a}$ 

Uspořádaná množina se nazývá svaz, pokud každá dvojice ${\displaystyle a,b\in M}$  má supremum (nejmenší horní závoru) i infimum (největší dolní závoru). Supremum a infimum se ve svazu značí ${\displaystyle \lor }$  a ${\displaystyle \land }$  a nazývají spojení a průsek.

Např. diagram 1 zachycuje poset některých přirozených čísel, kde předcházení ${\displaystyle a\preceq b}$  je definováno vztahem „a je dělitel b“. Číslo 12 je největší prvek tohoto svazu. 2 i 3 jsou minimální prvky (tj. nic jim nepředchází), ale poset nemá nejmenší prvek, který by předcházel všem ostatním. Protože čísla 2 a 3 nemají dolní závoru, tento poset není svazem.

V druhém diagramu je číslo 2 největší dolní závora, tj. infimum, prvků 4 a 6. Nejmenší horní závora prvků 4 a 6 (supremum) neexistuje, i když existují dvě minimální horní závory, 24 a 36. Proto daný poset rovněž není svazem. Navíc prvky 2 a 5 nemají vůbec žádnou horní závoru. Jejich jediná (a tedy největší) dolní závora je 1.

Tato definice je ekvivalentní s tím, že svaz je algebraická struktura, která je spojovým i průsekovým polosvazem (tj. má binární operace ${\displaystyle \land }$  i ${\displaystyle \lor }$ , obě splňující axiomy polosvazu, tj. idempotenci, komutativitu a asociativitu) a tyto dvě operace si navzájem „odpovídají“, tj. splňují ještě tyto axiomy:

 Asociativita
 ${\displaystyle (a\lor b)\lor c=a\lor (b\lor c)}$ 
 ${\displaystyle (a\land b)\land c=a\land (b\land c)}$ 

 Absorpce
 ${\displaystyle a\lor (a\land b)=a}$ 
 ${\displaystyle a\land (a\lor b)=a}$ 

Tyto axiomy se vyskytují ve dvojicích, které jsou k sobě duální, tj. každý axiom vznikne z druhého nahrazením průseků spojením a spojení průseky. V posetech vznikne k tvrzení či definici duální tvrzení či definice tím, že ${\displaystyle \preceq }$  se nahradí ${\displaystyle \succeq }$ , jinými slovy ${\displaystyle a\preceq b}$  se nahradí ${\displaystyle b\preceq a}$ .

Názvosloví

Symboly pro spojení a průsek byly záměrně zvoleny podobné symbolům ${\displaystyle \cup }$  a ${\displaystyle \cap }$ , protože ve svazech množin se často supremum rovná sjednocení a infimum průniku.

Jejich souvislost s logickým „nebo“ a logickým „a zároveň“, které se rovněž značí ${\displaystyle \lor }$  a ${\displaystyle \land }$ , vynikne na dvouprvkové Boolově algebře, kterou lze chápat jako logickou nulu a jedničku (tj. nepravdu a pravdu). Nebo na svazu, který je direktním součinem několika dvouprvkových Booleových algeber. Tj. pro libovolné konečné ${\displaystyle n}$  lze za nosnou množinu vzít ${\displaystyle n}$ -prvkové posloupnosti logických nul a jedniček; posloupnost předchází druhou, pokud je menší nebo rovna ve všech složkách. Např. platí 10100 ${\displaystyle \preceq }$  10101. Nikoli však 00110${\displaystyle \preceq }$  10101, protože čtvrtá složka je u prvně jmenované posloupnosti větší.

Tento svaz je Booleovou algebrou. Pro ${\displaystyle n=7}$  jej lze interpretovat např. jako informaci, které dny v týdnu má nějaký podnik otevřeno. Úřad otevřený v pondělí a středu je popsán posloupností 1010000, kino otevřené všechny dny kromě pondělí posloupností 0111111. Průsek 1010000 ${\displaystyle \land }$  0111111 = 00100000 pak vyjadřuje, které dny je možno zajít na úřad a po něm hned do kina.

Svaz se nazývá komplementární, pokud má nejmenší i největší prvek (značí se ${\displaystyle 0}$  a ${\displaystyle 1}$ ) a unární operaci komplement, která se označuje ${\displaystyle \lnot }$ . Toto značení opět vystihuje souvislost s logickou nulou a jedničkou; komplement pak odpovídá logické negaci.

Komplementární svaz má již většinu vlastností očekávaných od Booleových algeber. Kromě definice svazu musí splňovat i další axiomy:

Komplementárnost
${\displaystyle a\lor \lnot a=1}$ 
${\displaystyle a\land \lnot a=0}$ 

Involutivita
${\displaystyle \lnot (\lnot a)=a}$ 

0 a 1 jsou infimem a supremem celého svazu
${\displaystyle 1\lor a=1}$ 
${\displaystyle 0\land a=0}$ 

Identita
${\displaystyle 1\land a=a}$ 
${\displaystyle 0\lor a=a}$ 

Mnohé svazy mají jako nosnou množinu všechny (nebo některé - například měřitelé) podmnožiny dané množiny ${\displaystyle M}$ . V takových je téměř vždy nulou prázdná množina a jedničkou celá ${\displaystyle M}$  a komplementem množiny ${\displaystyle A\subseteq M}$  je její množinový doplněk do celé množiny ${\displaystyle M}$ , tj. ${\displaystyle M-A}$ .

Svaz bez největšího prvku nemůže být komplementární. Proto přirozená čísla nejsou komplementární svazy ani při uspořádání podle velikosti, ani při uspořádání podle dělitelnosti.

Komplementární svaz se nazývá Booleova algebra, pokud je distributivní, tj. pro libovolné prvky ${\displaystyle a,b,c\in M}$  platí:

 ${\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}$ 
 ${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)}$ 

Booleovy algebry musí splňovat více axiomů, než svazy, a proto je jejich struktura jednotnější. Například každá konečná Booleova algebra má ${\displaystyle 2^{n}}$  prvků pro nějaké ${\displaystyle n>0}$  a je izomorfní s direktním součinem ${\displaystyle n}$  dvouprvkových Booleových algeber.

Jako v každém svazu se používá symbol ${\displaystyle a\preceq b}$  pro ${\displaystyle a\land b=a}$  (nebo ekvivalentně ${\displaystyle a\lor b=b}$ ) a symbol ${\displaystyle a\prec b}$  pro ostré uspořádání, tj. relaci „${\displaystyle a\preceq b}$  a zároveň ${\displaystyle a\neq b}$ “.

Nekonečné Booleovy algebry mohou být atomární, kdy pod každým nenulovým prvkem ${\displaystyle x}$  je atom ${\displaystyle a}$ ; atom je prvek, pod kterým již nic neleží, tj. neexistuje ${\displaystyle y}$  takové, že ${\displaystyle 0\prec y\prec a}$ . Existují naopak bezatomární algebry, které nemají žádné atomy. Příkladem bezatomárních algeber jsou husté Booleovy algebry, v nichž pro každé ${\displaystyle a\prec b}$  existuje ${\displaystyle x}$  takové, že ${\displaystyle a\prec x\prec b}$ .

Úplný svaz je svaz, ve kterém všechna suprema a infima existují nejen pro dvojice prvků, ale pro libovolné množiny. Analogicky se definuje úplná Booleova algebra.

Např. celá či reálná čísla jsou svazem, ale nikoli úplným svazem. Typičtějším příklad neúplného svazu je množina všech konečných množin celých čísel uspořádaná obvyklou množinovou inkluzí.

Strukturu svazu lze zavést na množinách objektů různého druhu: na množinách čísel, množin, funkcí atd.

• Množiny s inkluzí: Pro libovolnou množinu ${\displaystyle S}$  je množina ${\displaystyle {\mathcal {P}}(S)}$  všech jejích podmnožin svazem, a to s sjednocení ${\displaystyle \cup }$  a průniku ${\displaystyle \cap }$ . Rovněž je svazem množina konečných podmnožin ${\displaystyle S}$ . Mnoho svazů je definováno jako množina podmnožin ${\displaystyle S}$ , které splňují nějakou dodatečnou podmínku.
• Dělitelé přirozeného čísla: Pro přirozené číslo ${\displaystyle n}$ , množina všech dělitelů ${\displaystyle n}$  s operacemi největšího společného dělitele (NSD) jako ${\displaystyle \land }$  a nejmenšího společného násobku (NSN) jako ${\displaystyle \lor }$  tvoří svaz.
• Logické hodnoty: Množina ${\displaystyle \{{\text{true}},{\text{false}}\}}$  se standardními logickými operacemi AND (${\displaystyle \land }$ ) a OR (${\displaystyle \lor }$ ) je svaz.
• Částečně uspořádaná množina: Každá částečně uspořádaná množina, ve které existuje infimum a supremum pro každou dvojici prvků, tvoří svaz s ${\displaystyle \land }$  jako infimum a ${\displaystyle \lor }$  jako supremum.

• Například každá lineárně uspořádání množina, jako množina přirozených čísel, je svazem.

• Intervaly reálných čísel: Množina všech uzavřených intervalů ${\displaystyle [a,b]}$  na reálné ose se operacemi průniku a sjednocení tvoří svaz.
• Funkce na svazu: Funkce s hodnotami v libovolném svazu, například reálné funkce ${\displaystyle f,g:\mathbb {R} \to \mathbb {R} }$  s operacemi ${\displaystyle (f\land g)(x)=\min(f(x),g(x))}$  a ${\displaystyle (f\lor g)(x)=\max(f(x),g(x))}$ , tvoří svaz.

Zajímavými příklady svazu jsou řetězec a protiřetězec. Pokud ${\displaystyle X\,\!}$  obsahuje právě jeden prvek, pak jej nazýváme triviální svaz.

Potenční algebra (tj. množina všech podmnožin nějaké množiny s uspořádáním relací "být podmnožinou") je svaz, protože sjednocení je v tomto případě supremem a průnik infimem

• ${\displaystyle \inf _{\subseteq }\{a,b\}=a\cap b\,\!}$ 
• ${\displaystyle \sup _{\subseteq }\{a,b\}=a\cup b\,\!}$ 

Uvažujme o množině všech přirozených čísel a o uspořádání ${\displaystyle R\,\!}$ , pro které platí, že
${\displaystyle a\leq _{R}b\Leftrightarrow a|b\,\!}$  (tj. a je menší než b, pokud a dělí b)
Opět se jedná o svaz, protože nejmenší společný násobek je supremum a největší společný dělitel je infimum dvouprvkové množiny přirozených čísel podle tohoto uspořádání.

• Podsvaz
• Modulární svaz
• Distributivní svaz
• Úplný svaz
• Kongruence na svazech
• Booleova algebra – distributivní a komplementární svaz

• FAURE, Robert; HEURGONOVÁ, Edith, 1984. Uspořádání a Booleovy algebry. Praha: Academia. 

•   Obrázky, zvuky či videa k tématu svaz na Wikimedia Commons
•   Slovníkové heslo svaz ve Wikislovníku
• Semimodulární, modulární a distributivní svazy - Jiří Hýsek