Svaz (matematika)

Svazjealgebraická strukturase dvěmabinárními operacemizvanýmiprůsek(∧{\displaystyle \land }) aspojení(∨{\displaystyle \lor }), která splňuje několik axiomů.
Jde oabstraktní strukturu, tj. svazem je jakákoli množina (zvaná „nosná množina“) vybavená těmito operacemi; např. množina čísel, množina množin čísel, množina funkcí atd.
Ekvivalentně se dá svaz definovat jakočástečně uspořádaná množina, ve které má každá dvojice prvkůsupremum(tj.nejmenšíhorní závoru mezihorními závoramitěch prvků) ainfimum(největší dolní závoru). Existují-li suprema a infima pro každou množinu, nejen dvouprvkovou, hovoříme oúplném svazu.
Příkladem svazu jsou přirozená čísla, kde průsek vrátí menší z čísel a spojení vrátí větší z nich. Jiným svazem jsou přirozená čísla s operaceminejmenší společný násobekanejvětší společný dělitel. Mnoho aplikací mají svazy všech nebo některých podmnožin jisté množiny, kde průsek odpovídá množinovémuprůnikua spojení často odpovídásjednocení.
Jednodušší struktura se nazývápolosvaz, jistý typ svazu pakBooleova algebra, která zobecňuje logické pojmykonjunkce(logické „a zároveň“),disjunkce(logické „nebo“) anegace(logické „ne“). Dvouprvková Booleova algebra{0;1}{\displaystyle \{0;1\}}reprezentuje logickou nepravdu a pravdu.
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)M{\displaystyle M}se nazýváspojový polosvaz, pokud nad každými dvěma prvkya,b∈M{\displaystyle a,b\in M}existujesupremumnebolinejmenší horní závora. Pojemhorní závorah{\displaystyle h}znamená, žea⪯h{\displaystyle a\preceq h}ab⪯h{\displaystyle b\preceq h}. Pojemnejmenšípak to, že musí předcházet každé jiné horní závoře.
Ekvivalentně lze spojový polosvaz definovat jakoalgebraickou strukturus binární operací∨{\displaystyle \lor }zvanouspojení, která splňuje axiomy:
Ekvivalence těchto zdánlivě různorodých definice plyne z toho, že
Obdobněprůsekový polosvazjeposet, v němž každá dvojice prvků máinfimumnebolinejvětší dolní závoru. Ekvivalentně je to množina s binární operací∧{\displaystyle \land }zvanouprůsek, která odpovídáinfimuv posetech. Axiomy jsou stejné. Relace předcházení v posetech (a⪯b{\displaystyle a\preceq b}) je definována vztahema∧b=a{\displaystyle a\land b=a}
Uspořádaná množina se nazývásvaz, pokud každá dvojicea,b∈M{\displaystyle a,b\in M}másupremum(nejmenší horní závoru) iinfimum(největší dolní závoru). Supremum a infimum se ve svazu značí∨{\displaystyle \lor }a∧{\displaystyle \land }a nazývajíspojeníaprůsek.
Např. diagram 1 zachycuje poset některých přirozených čísel, kde předcházenía⪯b{\displaystyle a\preceq b}je definováno vztahem „a jedělitelb“. Číslo 12 je největší prvek tohoto svazu. 2 i 3 jsouminimá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:
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 slovya⪯b{\displaystyle a\preceq b}se nahradíb⪯a{\displaystyle b\preceq a}.
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 slogickým „nebo“alogický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ý jedirektním součinemněkolika dvouprvkových Booleových algeber. Tj. pro libovolné konečnén{\displaystyle n}lze za nosnou množinu vzítn{\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. Pron=7{\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čí se0{\displaystyle 0}a1{\displaystyle 1}) a unární operacikomplement, 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:
Mnohé svazy mají jako nosnou množinu všechny (nebo některé - napříkladměřitelé) podmnožiny dané množinyM{\displaystyle M}. V takových je téměř vždy nulouprázdná množinaa jedničkou celáM{\displaystyle M}a komplementem množinyA⊆M{\displaystyle A\subseteq M}je jejímnožinový doplněkdo celé množinyM{\displaystyle M}, tj.M−A{\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é prvkya,b,c∈M{\displaystyle a,b,c\in M}platí:
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á2n{\displaystyle 2^{n}}prvků pro nějakén>0{\displaystyle n>0}a je izomorfní sdirektním součinemn{\displaystyle n}dvouprvkových Booleových algeber.
Jako v každém svazu se používá symbola⪯b{\displaystyle a\preceq b}proa∧b=a{\displaystyle a\land b=a}(nebo ekvivalentněa∨b=b{\displaystyle a\lor b=b}) a symbola≺b{\displaystyle a\prec b}proostré uspořádání, tj. relaci „a⪯b{\displaystyle a\preceq b}a zároveňa≠b{\displaystyle a\neq b}“.
Nekonečné Booleovy algebry mohou býtatomární, kdy pod každým nenulovým prvkemx{\displaystyle x}je atoma{\displaystyle a};atomje prvek, pod kterým již nic neleží, tj. neexistujey{\displaystyle y}takové, že0≺y≺a{\displaystyle 0\prec y\prec a}. Existují naopakbezatomárníalgebry, které nemají žádné atomy. Příkladem bezatomárních algeber jsouhustéBooleovy algebry, v nichž pro každéa≺b{\displaystyle a\prec b}existujex{\displaystyle x}takové, žea≺x≺b{\displaystyle a\prec x\prec b}.
Úplný svazje 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á čireálná číslajsou svazem, ale nikoli úplným svazem. Typičtějším příklad neúplného svazu jemnožina všech konečných množin celých číseluspořádaná obvyklou množinovouinkluzí.
Strukturu svazu lze zavést na množinách objektů různého druhu: na množinách čísel, množin, funkcí atd.
Zajímavými příklady svazu jsouřetězecaprotiřetězec. PokudX{\displaystyle X\,\!}obsahuje právě jeden prvek, pak jej nazývámetriviální svaz.
Potenční algebra(tj. množina všech podmnožin nějaké množiny s uspořádáním relací "býtpodmnožinou") jesvaz, protože sjednocení je v tomto případě supremem a průnik infimem
Uvažujme o množině všechpřirozených čísela ouspořádáníR{\displaystyle R\,\!}, pro které platí, žea≤Rb⇔a|b{\displaystyle a\leq _{R}b\Leftrightarrow a|b\,\!}(tj. a je menší než b, pokud adělíb)Opět se jedná osvaz, protoženejmenší společný násobekjesupremumanejvětší společný děliteljeinfimumdvouprvkové množiny přirozených čísel podle tohoto uspořádání.