Svaz (matematika)

Svaz je algebraická struktura se dvěma binárními operacemi zvanými průsek ( $\land$ ) a spojení ( $\lor$ ), která splňuje několik axiomů.

Jde o 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ší horní závoru mezi 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é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ůniku a spojení často odpovídá sjednocení.

Jednodušší struktura se nazývá polosvaz, jistý typ svazu pak Booleova algebra, která zobecňuje logické pojmy konjunkce (logické „a zároveň“), disjunkce (logické „nebo“) a negace (logické „ne“). Dvouprvková Booleova algebra $\{0;1\}$ 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í:

Spojový polosvaz

Poset (tj. částečně uspořádaná množina) $M$ se nazývá spojový polosvaz, pokud nad každými dvěma prvky $a,b\in M$ existuje supremum neboli nejmenší horní závora. Pojem horní závora $h$ znamená, že $a\preceq h$ a $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í $\lor$ zvanou spojení, která splňuje axiomy:

Asociativita:  $(a\lor b)\lor c=a\lor (b\lor c)$  
Komutativita:  $a\lor b=b\lor a$ 
Idempotence: $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ž $a\preceq b$ je definováno jako $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.

Průsekový polosvaz

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í $\land$ zvanou průsek, která odpovídá infimu v posetech. Axiomy jsou stejné. Relace předcházení v posetech ( $a\preceq b$ ) je definována vztahem $a\land b=a$

Typy svazů

Svaz

**Diagram 1**
		12
		↑
		6
	↗		↖
2				3

**Diagram 2**
		72
	↗		↖
24				36
↑	↗		↖	↑
4				6	15
	↖		↗		↑
		2			5
		↑		↗
		1

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

Např. diagram 1 zachycuje poset některých přirozených čísel, kde předcházení $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 $\land$ i $\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
  $(a\lor b)\lor c=a\lor (b\lor c)$ 
  $(a\land b)\land c=a\land (b\land c)$ 

 Absorpce
  $a\lor (a\land b)=a$ 
  $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 $\preceq$ se nahradí $\succeq$ , jinými slovy $a\preceq b$ se nahradí $b\preceq a$ .

Názvosloví

Symboly pro spojení a průsek byly záměrně zvoleny podobné symbolům $\cup$ a $\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čí $\lor$ a $\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é $n$ lze za nosnou množinu vzít $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 $\preceq$ 10101. Nikoli však 00110 $\preceq$ 10101, protože čtvrtá složka je u prvně jmenované posloupnosti větší.

Tento svaz je Booleovou algebrou. Pro $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 $\land$ 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ší i největší prvek (značí se $0$ a $1$ ) a unární operaci komplement, která se označuje $\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
 $a\lor \lnot a=1$ 
 $a\land \lnot a=0$ 

Involutivita
 $\lnot (\lnot a)=a$ 

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

Identita
 $1\land a=a$ 
 $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 $M$ . V takových je téměř vždy nulou prázdná množina a jedničkou celá $M$ a komplementem množiny $A\subseteq M$ je její množinový doplněk do celé množiny $M$ , tj. $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.

Booleovy algebry

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

  $a\land (b\lor c)=(a\land b)\lor (a\land c)$ 
  $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á $2^{n}$ prvků pro nějaké $n>0$ a je izomorfní s direktním součinem $n$ dvouprvkových Booleových algeber.

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

Nekonečné Booleovy algebry mohou být atomární, kdy pod každým nenulovým prvkem $x$ je atom $a$ ; atom je prvek, pod kterým již nic neleží, tj. neexistuje $y$ takové, že $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é $a\prec b$ existuje $x$ takové, že $a\prec x\prec b$ .

Ú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á čí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í.

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

Řetězce

Zajímavými příklady svazu jsou řetězec a protiřetězec. Pokud $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

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

Uvažujme o množině všech přirozených čísel a o uspořádání $R\,\!$ , pro které platí, že
$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í.

Odkazy

Reference

Související články

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

Literatura

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

Externí odkazy

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
Lattice [online]. EMS Press. (Encyclopedia of Mathematics). Dostupné online. (anglicky)