Zobrazení zdroje stránky Svaz (matematika)

'''Svaz''' je [[algebraická struktura]] se dvěma [[Binární operace|binárními operacemi]] zvanými '''průsek''' (<math>\land</math>) a '''spojení''' (<math>\lor</math>), která splňuje několik axiomů.

Jde o [[Matematická struktura|abstraktní 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ší a největší prvek|nejmenší]] horní závoru mezi [[Majoranta|horními závorami]] těch prvků) a [[infimum]] (největší dolní závoru). Existují-li suprema a infima pro každou množinu, nejen dvouprvkovou, hovoříme o '''[[Úplný svaz|ú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 operacemi [[nejmenší společný násobek]] a [[nejvě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ému [[průnik]]u a spojení často odpovídá [[sjednocení]].

Jednodušší struktura se nazývá '''[[polosvaz]]''', jistý typ svazu pak '''[[Booleova algebra]]''', která zobecňuje logické pojmy [[Konjunkce (logika)|konjunkce]] (logické „a zároveň“), [[disjunkce]] (logické „nebo“) a [[negace]] (logické „ne“). Dvouprvková Booleova algebra <math>\{0; 1\}</math> reprezentuje logickou nepravdu a pravdu.

== Typy polosvazů ==

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

{{Kotva|Polosvaz}}
=== Spojový polosvaz  ===
Poset (tj. [[částečně uspořádaná množina]]) <math>M</math> se nazývá '''spojový polosvaz''', pokud nad každými dvěma prvky <math>a, b \in M</math> existuje '''[[supremum]]''' neboli '''nejmenší horní závora'''. Pojem '''[[Majoranta|horní závora]]''' <math>h</math> znamená, že <math>a \preceq h</math> a <math>b \preceq h</math>. Pojem '''[[Nejmenší a největší prvek|nejmenší]]''' pak to, že musí předcházet každé jiné horní závoře.

Ekvivalentně lze spojový polosvaz definovat jako [[Algebraická struktura|algebraickou strukturu]] s binární operací <math>\lor</math> zvanou '''spojení''', která splňuje axiomy:

* [[Asociativita]]: <math>(a \lor b) \lor c = a \lor (b \lor c)</math> 
* [[Komutativita]]: <math>a \lor b = b \lor a</math>
* [[Idempotence]]: <math>a \lor a = a</math>

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ž <math>a\preceq b</math> je definováno jako <math>a \lor b = b</math>. 
* 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.

=== Průsekový polosvaz ===
Obdobně '''průsekový polosvaz''' je [[poset]], v němž každá dvojice prvků má '''infimum''' neboli '''největší dolní závoru'''. Ekvivalentně je to množina s binární operací <math>\land</math> zvanou '''průsek''', která odpovídá [[Infimum|infimu]] v posetech. Axiomy jsou stejné. Relace předcházení v posetech (<math>a \preceq b</math>) je definována vztahem <math>a \land b = a</math>

== Typy svazů ==
=== Svaz ===

<div style="float:left;margin-bottom:15px;margin-right:60px">
{|
|+ '''Diagram 1'''
|      ||   || 12
|-
|      ||   || ↑
|-
|      ||   || 6
|-
|      || ↗ ||   || ↖ ||
|-
|    2 ||   ||   ||  || 3 || 
|}
</div>

<div style="float:left;margin-bottom:15px;margin-right:60px">
{|
|+ '''Diagram 2'''
|-
|      ||   || 72
|-
|      || ↗ || ||↖ || 
|-
|   24 ||   || ||  || 36
|-
|    ↑ || ↗ || ||↖ || ↑
|-
|    4  ||  ||  ||   ||6 ||  ||  || 15
|-
|       ||↖ ||  || ↗||   || ||   || ↑
|-    
|       ||  || 2 ||  ||  || ||  || 5 || 
|-    
|       ||  || ↑||     || ↗  
|-    
|       ||  || 1|| 
|}
</div>

Uspořádaná množina se nazývá '''[[Svaz (matematika)|svaz]]''', pokud každá dvojice <math>a,b \in M</math> má '''[[supremum]]''' (nejmenší horní závoru) i '''[[infimum]]''' (největší dolní závoru). Supremum a infimum se ve svazu značí <math>\lor</math> a  <math>\land</math> a nazývají '''spojení''' a '''průsek'''. 

Např. diagram 1 zachycuje poset některých přirozených čísel, kde předcházení <math>a \preceq b</math> je definováno vztahem „a je [[Dělitelnost|dělitel]] b“. Číslo 12 je největší prvek tohoto svazu. 2 i 3 jsou [[Minimální a maximální prvek|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 <math>\land</math> i <math>\lor</math>, 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'''
:<math> (a \lor b) \lor c = a \lor (b \lor c)  </math>
:<math>(a \land b) \land c = a \land (b \land c)</math>

* '''Absorpce'''
:<math> a \lor (a \land b) = a </math>
:<math> a \land (a \lor b) = a </math>

Tyto axiomy se vyskytují ve dvojicích, které jsou k sobě '''[[Dualita pojmů|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 <math>\preceq</math> se nahradí <math>\succeq</math>, jinými slovy <math>a \preceq b</math> se nahradí <math>b \preceq a</math>.

; Názvosloví

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

Jejich souvislost s [[Disjunkce|logickým „nebo“]] a [[Konjunkce (logika)|logickým „a zároveň“]], které se rovněž značí <math>\lor</math> a <math>\land</math>, 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í součin|direktním součinem]] několika dvouprvkových Booleových algeber. Tj. pro libovolné konečné <math>n</math> lze za nosnou množinu vzít <math>n</math>-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 <math>\preceq</math> 10101. Nikoli však 00110<math>\preceq</math> 10101, protože čtvrtá složka je u prvně jmenované posloupnosti větší.

Tento svaz je Booleovou algebrou. Pro <math>n=7</math> 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 <math>\land</math> 0111111 = 00100000 pak vyjadřuje, které dny je možno zajít na úřad a po něm hned do kina.

=== Komplementární svaz ===

Svaz se nazývá '''komplementární''', pokud má [[Nejmenší a největší prvek|nejmenší i největší prvek]] (značí se <math>0</math> a <math>1</math>) a unární operaci '''komplement''', která se označuje <math>\lnot</math>. Toto značení opět vystihuje souvislost s logickou nulou a jedničkou; komplement pak odpovídá logické [[Negace|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'''
:<math> a \lor \lnot a = 1 </math>
:<math> a \land \lnot a = 0 </math>
 
*  '''Involutivita'''
:<math> \lnot (\lnot a) = a </math>
 
*  '''0 a 1 jsou infimem a supremem celého svazu'''
:<math> 1 \lor a = 1 </math>
: <math> 0 \land a = 0 </math>
 
*  '''Identita'''
:<math> 1 \land a = a </math>
:<math> 0 \lor a = a </math>

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

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.

=== Booleovy algebry === 
{{Podrobně|Booleova algebra}}

Komplementární svaz se nazývá '''Booleova algebra''', pokud je distributivní, tj. pro libovolné prvky <math>a, b, c \in M</math> platí:
:<math>a \land (b \lor c) = (a \land b) \lor (a \land c)</math>
:<math>a \lor (b \land c) = (a \lor b) \land (a \lor c)</math>

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á <math>2^n</math> prvků pro nějaké <math>n>0</math> a je izomorfní s [[Direktní součin|direktním součinem]] <math>n</math> dvouprvkových Booleových algeber.

Jako v každém svazu se používá symbol <math>a \preceq b</math> pro <math>a \land b = a</math> (nebo ekvivalentně <math>a \lor b = b</math>) a symbol <math>a \prec b</math> pro [[Částečně_uspořádaná_množina#Ostré_uspořádání|ostré uspořádání]], tj. relaci „<math>a \preceq b</math> a zároveň <math>a\neq b</math>“.

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

=== Úplné svazy === 
'''[[Ú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é číslo|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  [[Podmnožina (matematika)|inkluzí]].

== Příklady ==

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 <math>S</math> je množina <math>\mathcal{P}(S)</math> všech jejích podmnožin svazem, a to s sjednocení <math>\cup</math> a průniku <math>\cap</math>. Rovněž je svazem množina konečných podmnožin <math>S</math>. Mnoho svazů je definováno jako množina podmnožin <math>S</math>, které splňují nějakou dodatečnou podmínku.
* '''Dělitelé přirozeného čísla''': Pro přirozené číslo <math>n</math>, množina všech dělitelů <math>n</math> s operacemi největšího společného dělitele (NSD) jako <math>\land</math> a nejmenšího společného násobku (NSN) jako <math>\lor</math> tvoří svaz.
* '''Logické hodnoty''': Množina <math>\{ \text{true}, \text{false} \}</math> se standardními logickými operacemi AND (<math>\land</math>) a OR (<math>\lor</math>) 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 <math>\land</math> jako infimum a <math>\lor</math> jako supremum. 
:*Například každá [[Lineární uspořádání|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ů <math>[a, b]</math> 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 <math>f, g: \mathbb{R} \to \mathbb{R}</math> s operacemi <math>(f \land g)(x) = \min(f(x), g(x))</math> a <math>(f \lor g)(x) = \max(f(x), g(x))</math>, tvoří svaz.

=== Řetězce ===
Zajímavými příklady svazu jsou [[řetězec]] a [[protiřetězec]]. Pokud <math> X \,\! </math> 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žina|podmnožinou]]") je '''svaz''', protože sjednocení je v tomto případě supremem a průnik infimem <br />
* <math> \inf_{\subseteq} \{ a,b \} = a \cap b \,\! </math>
* <math> \sup_{\subseteq} \{ a,b \} = a \cup b \,\! </math>

Uvažujme o množině všech [[Přirozené číslo|přirozených čísel]] a o [[uspořádání]] <math> R \,\! </math>, pro které platí, že <br />
<math> a \leq_R b \Leftrightarrow a | b \,\! </math> (tj. a je menší než b, pokud a [[dělitelnost|dělí]] b) <br />
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í.

== Odkazy ==

=== Reference ===
<references />

=== Související články ===
* [[Podsvaz]]
* [[Modulární svaz]]
* [[Distributivní svaz]]
* [[Úplný svaz]]
* [[Booleova algebra]] – distributivní a komplementární svaz

=== Literatura ===
* {{Citace monografie
 | ref = harv
 | titul = Uspořádání a Booleovy algebry
 | jméno = Robert
 | příjmení = Faure
 | jméno2 = Edith
 | příjmení2 = Heurgonová
 | vydavatel = Academia
 | místo = Praha
 | rok = 1984
}}

=== Externí odkazy ===
* {{Commonscat}}
* {{Wikislovník|heslo=svaz}}
* [https://web.archive.org/web/20110910031713/http://trace.dump.cz/papers/qm3.pdf Semimodulární, modulární a distributivní svazy - Jiří Hýsek]
* {{SpringerEOM|Lattice|téma=Lattice}}
* {{Nlab|lattice|Lattice}}
{{Autoritní data}}

{{Portály|Matematika}}

[[Kategorie:Algebraické struktury]]
[[Kategorie:Teorie svazů| ]]