mřížka - online puzzle
Online puzzle mřížka
Svaz je matematický pojem z algebry, konkrétněji z oboru teorie uspořádání, který vymezuje mezi uspořádanými množinami ty, které jsou uspořádány „rozumně“ (to znamená, že zachovávají suprema a infima).
Definice
Množinu
X
{\displaystyle X}
uspořádanou relací
R
{\displaystyle R}
nazveme svazem, pokud pro každou dvouprvkovou podmnožinu obsahuje i její supremum a infimum.
(
∀
a
,
b
∈
X
)
(
∃
i
,
s
∈
X
)
(
(
i
=
inf
R
{
a
,
b
}
)
∧
(
s
=
sup
R
{
a
,
b
}
)
)
{\displaystyle (\forall a,b\in X)(\exists i,s\in X)((i=\inf _{R}\{a,b\})\land (s=\sup _{R}\{a,b\}))}
Jako horní polosvaz se označuje uspořádaná množina zachovávající suprema:
(
∀
a
,
b
∈
X
)
(
∃
s
∈
X
)
(
s
=
sup
R
{
a
,
b
}
)
{\displaystyle (\forall a,b\in X)(\exists s\in X)(s=\sup _{R}\{a,b\})}
A jako dolní polosvaz se označuje uspořádaná množina zachovávající infima:
(
∀
a
,
b
∈
X
)
(
∃
i
∈
X
)
(
i
=
inf
R
{
a
,
b
}
)
{\displaystyle (\forall a,b\in X)(\exists i\in X)(i=\inf _{R}\{a,b\})}
Takže jde také definovat, že uspořádaná množina je svazem právě tehdy, je-li zároveň horním i dolním polosvazem.
Příklady
Zajímavými příklady svazu jsou řetězec a protiřetězec. Pokud
X
{\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
i
n
f
⊆
{
a
,
b
}
=
a
∩
b
{\displaystyle inf_{\subseteq }\{a,b\}=a\cap b\,\!}
s
u
p
⊆
{
a
,
b
}
=
a
∪
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í
R
{\displaystyle R\,\!}
, pro které platí, že
a
≤
R
b
⇔
a
|
b
{\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í.
Svazová algebra
Na svazu lze poměrně snadno definovat dvě binární operace, které označují supremum a infimum dvouprvkové množiny (můžeme si je nazvat třeba součet a součin).
Svaz je pak zapisován jako
(
X
,
∧
,
∨
)
{\displaystyle (X,\land,\vee )\,\!}
, kde
a
,
b
∈
X
{\displaystyle a,b\in X}
a platí
a
∧
b
=
i
n
f
R
{
a
,
b
}
{\displaystyle a\land b=inf_{R}\{a,b\}}
a zároveň
a
∨
b
=
s
u
p
R
{
a
,
b
}
{\displaystyle a\vee b=sup_{R}\{a,b\}\,\!}
Příklad svazové algebry
Pokud budeme uvažovat o množině přirozených čísel a jejím běžném uspořádání podle velikosti, pak výše definovanými operacemi nejsou běžný součet a součin, ale operace
a
∧
b
=
m
i
n
(
a
,
b
)
{\displaystyle a\land b=min(a,b)\,\!}
a
∨
b
=
m
a
x
(
a
,
b
)
{\displaystyle a\vee b=max(a,b)\,\!}
Neutrální prvky svazu
Pokud má svaz nejmenší prvek vzhledem k relaci
R
{\displaystyle R\,\!}
, pak je tento prvek neutrální vzhledem k operaci suprema, můžeme ho tedy označit symbolem 0 a platí pro něj:
a
∧
0
=
0
{\displaystyle a\land 0=0\,\!}
a
∨
0
=
a
{\displaystyle a\vee 0=a\,\!}
Pokud má svaz největší prvek vzhledem k relaci
R
{\displaystyle R\,\!}
, pak je tento prvek neutrální vzhledem k operaci infima, můžeme ho tedy označit symbolem 1 a platí pro něj:
a
∧
1
=
a
{\displaystyle a\land 1=a\,\!}
a
∨
1
=
1
{\displaystyle a\vee 1=1\,\!}
Pokud se vrátím k předchozímu případu, je číslo 0 neutrálním prvkem pro supremum, ale neexistuje žádný největší prvek, takže neexistuje ani neutrální prvek pro infimum – s trochou nadsázky by se dalo říct, že v našem případě „přirozené číslo 1 není symbol 1“
Pokud se vrátím k příkladu potenční algebry, pak jako 0 mohu označit prázdnou množinu a jako 1 celou původní množinu (ze které jsou vybírány podmnožiny).