' $'
&
$
%Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5 Uspořádané množiny, Uzávěry5 Uspořádané množiny, Uzávěry
V této lekci dále pokračujeme probíráním binárních relací na množinách jako nástroji
vyjadřujícími vztahy mezi objekty. Zaměřujeme se nyní především na relace ,,srovnáva-
jící objekty podle jejich vlastností. Takto vágně opsané relace mívají jasné společné
znaky, které se objevují ve formální definici relace uspořádání.
' $'
&
$
%Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5 Uspořádané množiny, Uzávěry5 Uspořádané množiny, Uzávěry
V této lekci dále pokračujeme probíráním binárních relací na množinách jako nástroji
vyjadřujícími vztahy mezi objekty. Zaměřujeme se nyní především na relace ,,srovnáva-
jící objekty podle jejich vlastností. Takto vágně opsané relace mívají jasné společné
znaky, které se objevují ve formální definici relace uspořádání.
Stručný přehled lekce
* Uspořádané množiny a relevantní pojmy k uspořádání.
* Hasseovské diagramy uspořádaných množin.
* Uzávěry relací ­ jak danou relaci ,,obohatit o zvolenou vlastnost.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Vlastnosti binárních relací, zopakování
Nechť R  M × M. Binární relace R je
ˇ reflexivní, právě když pro každé a  M platí (a, a)  R;
s s
ˇ ireflexivní, právě když pro každé a  M platí (a, a)  R;
s sX X
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Vlastnosti binárních relací, zopakování
Nechť R  M × M. Binární relace R je
ˇ reflexivní, právě když pro každé a  M platí (a, a)  R;
s s
ˇ ireflexivní, právě když pro každé a  M platí (a, a)  R;
s sX X
ˇ symetrická, právě když pro každé a, b  M platí, že jestliže (a, b)  R, pak
také (b, a)  R; s s
hh33
hh33
ˇ antisymetrická, právě když pro každé a, b  M platí, že jestliže
(a, b), (b, a)  R, pak a = b;
s s
hh33
hh33
X
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Vlastnosti binárních relací, zopakování
Nechť R  M × M. Binární relace R je
ˇ reflexivní, právě když pro každé a  M platí (a, a)  R;
s s
ˇ ireflexivní, právě když pro každé a  M platí (a, a)  R;
s sX X
ˇ symetrická, právě když pro každé a, b  M platí, že jestliže (a, b)  R, pak
také (b, a)  R; s s
hh33
hh33
ˇ antisymetrická, právě když pro každé a, b  M platí, že jestliže
(a, b), (b, a)  R, pak a = b;
s s
hh33
hh33
X
ˇ tranzitivní, právě když pro každé a, b, c  M platí, že jestliže (a, b), (b, c) 
R, pak také (a, c)  R.
s s s$$ $$
&&
@@
a b c
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.1 Uspořádané množiny5.1 Uspořádané množiny
ˇ Relace R  M × M je (částečné) uspořádání právě když R je reflexivní,
antisymetrická a tranzitivní.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.1 Uspořádané množiny5.1 Uspořádané množiny
ˇ Relace R  M × M je (částečné) uspořádání právě když R je reflexivní,
antisymetrická a tranzitivní.Tyto tři vlastnosti je tedy třeba ověřit k důkazu
toho, že daná relace R je uspořádání.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.1 Uspořádané množiny5.1 Uspořádané množiny
ˇ Relace R  M × M je (částečné) uspořádání právě když R je reflexivní,
antisymetrická a tranzitivní.Tyto tři vlastnosti je tedy třeba ověřit k důkazu
toho, že daná relace R je uspořádání.
ˇ Neformálně řečeno: uspořádání je taková relace R  M×M, kde (x, y)  R
právě když x je v nějakém smyslu ,,menší nebo rovno než y.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.1 Uspořádané množiny5.1 Uspořádané množiny
ˇ Relace R  M × M je (částečné) uspořádání právě když R je reflexivní,
antisymetrická a tranzitivní.Tyto tři vlastnosti je tedy třeba ověřit k důkazu
toho, že daná relace R je uspořádání.
ˇ Neformálně řečeno: uspořádání je taková relace R  M×M, kde (x, y)  R
právě když x je v nějakém smyslu ,,menší nebo rovno než y.
Mohou ovšem existovat taková x, y  M, kde neplatí (x, y)  R ani
(y, x)  R. (Pak říkáme, že x a y jsou nesrovnatelné.)
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.1 Uspořádané množiny5.1 Uspořádané množiny
ˇ Relace R  M × M je (částečné) uspořádání právě když R je reflexivní,
antisymetrická a tranzitivní.Tyto tři vlastnosti je tedy třeba ověřit k důkazu
toho, že daná relace R je uspořádání.
ˇ Neformálně řečeno: uspořádání je taková relace R  M×M, kde (x, y)  R
právě když x je v nějakém smyslu ,,menší nebo rovno než y.
Mohou ovšem existovat taková x, y  M, kde neplatí (x, y)  R ani
(y, x)  R. (Pak říkáme, že x a y jsou nesrovnatelné.)
ˇ Zajisté jste se již neformálně setkali s ,,neostrým uspořádáním čísel  a
,,ostrým uspořádáním <.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.1 Uspořádané množiny5.1 Uspořádané množiny
ˇ Relace R  M × M je (částečné) uspořádání právě když R je reflexivní,
antisymetrická a tranzitivní.Tyto tři vlastnosti je tedy třeba ověřit k důkazu
toho, že daná relace R je uspořádání.
ˇ Neformálně řečeno: uspořádání je taková relace R  M×M, kde (x, y)  R
právě když x je v nějakém smyslu ,,menší nebo rovno než y.
Mohou ovšem existovat taková x, y  M, kde neplatí (x, y)  R ani
(y, x)  R. (Pak říkáme, že x a y jsou nesrovnatelné.)
ˇ Zajisté jste se již neformálně setkali s ,,neostrým uspořádáním čísel  a
,,ostrým uspořádáním <.Všimněte si dobře, že námi definované uspořádání
je vždy ,,neostré .
Avšak pokud byste chtěli definovat ,,ostré uspořádání, mělo by vlastnosti
ireflexivní, antisymetrické a tranzitivní. (Příliš se však toto nepoužívá.)
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
ˇ Jak názorně zobrazit (částečné) uspořádání?
Příklad zjednodušeného zakreslení (jsou vynechány šipky vyplývající z refle-
xivity a tranzitivity, viz Oddíl 5.3):
1
3
64
2
12
8
75
10 119
dělitelnost:
Všimněte si, že je zvykem ,,větší prvky kreslit nad ty ,,menší .
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Definice 5.1. Uspořádaná množina je dvojice (M, ),
kde M je množina a je (částečné) uspořádání na M.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Definice 5.1. Uspořádaná množina je dvojice (M, ),
kde M je množina a je (částečné) uspořádání na M.
Definice: Uspořádání R na M je lineární (nebo také úplné), pokud každé dva
prvky M jsou v R srovnatelné.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Definice 5.1. Uspořádaná množina je dvojice (M, ),
kde M je množina a je (částečné) uspořádání na M.
Definice: Uspořádání R na M je lineární (nebo také úplné), pokud každé dva
prvky M jsou v R srovnatelné.
Buď M množina všech studentů 1. ročníku FI. Uvažme postupně relace uspo-
řádání R  M × M definované takto:
ˇ (x, y)  R právě když x má alespoň takovou výšku jako y;
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Definice 5.1. Uspořádaná množina je dvojice (M, ),
kde M je množina a je (částečné) uspořádání na M.
Definice: Uspořádání R na M je lineární (nebo také úplné), pokud každé dva
prvky M jsou v R srovnatelné.
Buď M množina všech studentů 1. ročníku FI. Uvažme postupně relace uspo-
řádání R  M × M definované takto:
ˇ (x, y)  R právě když x má alespoň takovou výšku jako y;
ˇ (x, y)  R právě když y má alespoň takovou výšku jako x;
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Definice 5.1. Uspořádaná množina je dvojice (M, ),
kde M je množina a je (částečné) uspořádání na M.
Definice: Uspořádání R na M je lineární (nebo také úplné), pokud každé dva
prvky M jsou v R srovnatelné.
Buď M množina všech studentů 1. ročníku FI. Uvažme postupně relace uspo-
řádání R  M × M definované takto:
ˇ (x, y)  R právě když x má alespoň takovou výšku jako y;
ˇ (x, y)  R právě když y má alespoň takovou výšku jako x;
ˇ (x, y)  R právě když x a y mají stejné rodné číslo.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Definice 5.1. Uspořádaná množina je dvojice (M, ),
kde M je množina a je (částečné) uspořádání na M.
Definice: Uspořádání R na M je lineární (nebo také úplné), pokud každé dva
prvky M jsou v R srovnatelné.
Buď M množina všech studentů 1. ročníku FI. Uvažme postupně relace uspo-
řádání R  M × M definované takto:
ˇ (x, y)  R právě když x má alespoň takovou výšku jako y;
ˇ (x, y)  R právě když y má alespoň takovou výšku jako x;
ˇ (x, y)  R právě když x a y mají stejné rodné číslo.
Další ukázky uspořádaných množin následují zde:
ˇ (N, ) je lineárně uspořádaná množina, kde  má ,,obvyklý význam.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Definice 5.1. Uspořádaná množina je dvojice (M, ),
kde M je množina a je (částečné) uspořádání na M.
Definice: Uspořádání R na M je lineární (nebo také úplné), pokud každé dva
prvky M jsou v R srovnatelné.
Buď M množina všech studentů 1. ročníku FI. Uvažme postupně relace uspo-
řádání R  M × M definované takto:
ˇ (x, y)  R právě když x má alespoň takovou výšku jako y;
ˇ (x, y)  R právě když y má alespoň takovou výšku jako x;
ˇ (x, y)  R právě když x a y mají stejné rodné číslo.
Další ukázky uspořádaných množin následují zde:
ˇ (N, ) je lineárně uspořádaná množina, kde  má ,,obvyklý význam.
ˇ (N, | ), kde | je relace dělitelnosti, je uspořádaná množina. Toto uspořádání
není lineární.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Definice 5.1. Uspořádaná množina je dvojice (M, ),
kde M je množina a je (částečné) uspořádání na M.
Definice: Uspořádání R na M je lineární (nebo také úplné), pokud každé dva
prvky M jsou v R srovnatelné.
Buď M množina všech studentů 1. ročníku FI. Uvažme postupně relace uspo-
řádání R  M × M definované takto:
ˇ (x, y)  R právě když x má alespoň takovou výšku jako y;
ˇ (x, y)  R právě když y má alespoň takovou výšku jako x;
ˇ (x, y)  R právě když x a y mají stejné rodné číslo.
Další ukázky uspořádaných množin následují zde:
ˇ (N, ) je lineárně uspořádaná množina, kde  má ,,obvyklý význam.
ˇ (N, | ), kde | je relace dělitelnosti, je uspořádaná množina. Toto uspořádání
není lineární.
ˇ Buď M množina. Pak (2M , ) je uspořádaná množina (říkáme inkluzí).
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Příklad 5.2. Uspořádání ,,po složkách .
Nechť (A, A) a (B, B) jsou uspořádané množiny. Definujme binární relaci na
A × B předpisem
(a, b) (a , b ) právě když a A a a b B b .
Pak (A × B, ) je uspořádaná množina. Toto usp. se nazývá ,,po složkách .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Příklad 5.2. Uspořádání ,,po složkách .
Nechť (A, A) a (B, B) jsou uspořádané množiny. Definujme binární relaci na
A × B předpisem
(a, b) (a , b ) právě když a A a a b B b .
Pak (A × B, ) je uspořádaná množina. Toto usp. se nazývá ,,po složkách . 2
Příklad 5.3. Lexikografické uspořádání.
Nechť (A, A) a (B, B) jsou uspořádané množiny. Definujme binární relaci na
A × B předpisem
(a, b) (a , b ) právě když buď a A a a a = a , nebo a = a a b B b .
Pak (A × B, ) je uspořádaná množina. Navíc pokud A i B jsou lineární, je i
lineární. Toto uspořádání se nazývá lexikografické.
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Příklad 5.2. Uspořádání ,,po složkách .
Nechť (A, A) a (B, B) jsou uspořádané množiny. Definujme binární relaci na
A × B předpisem
(a, b) (a , b ) právě když a A a a b B b .
Pak (A × B, ) je uspořádaná množina. Toto usp. se nazývá ,,po složkách . 2
Příklad 5.3. Lexikografické uspořádání.
Nechť (A, A) a (B, B) jsou uspořádané množiny. Definujme binární relaci na
A × B předpisem
(a, b) (a , b ) právě když buď a A a a a = a , nebo a = a a b B b .
Pak (A × B, ) je uspořádaná množina. Navíc pokud A i B jsou lineární, je i
lineární. Toto uspořádání se nazývá lexikografické. 2
Fakt: Jsou-li (A1, 1),    , (An, n) uspořádané množiny, kde n  2, pak mno-
žinu A1 ×    × An lze uspořádat po složkách nebo lexikograficky.
Všimněte si, že lexikograficky se řadí slova ve slovníku. . .
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.2 Další pojmy uspořádaných množin5.2 Další pojmy uspořádaných množin
Definice 5.4. Buď (M, ) uspořádaná množina.
ˇ x  M je minimální právě když pro každé y  M platí, že jestliže y x,
pak x y.
(Tj. x je minimální právě když neexistuje žádný prvek ostře menší než x.)
s
sX
x
d
d
d
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.2 Další pojmy uspořádaných množin5.2 Další pojmy uspořádaných množin
Definice 5.4. Buď (M, ) uspořádaná množina.
ˇ x  M je minimální právě když pro každé y  M platí, že jestliže y x,
pak x y.
(Tj. x je minimální právě když neexistuje žádný prvek ostře menší než x.)
s
sX
x
d
d
d
ˇ x  M je maximální právě když pro každé y  M platí, že jestliže x y,
pak y x.
(Tj. x je maximální právě když neexistuje žádný prvek ostře větší než x.)
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.2 Další pojmy uspořádaných množin5.2 Další pojmy uspořádaných množin
Definice 5.4. Buď (M, ) uspořádaná množina.
ˇ x  M je minimální právě když pro každé y  M platí, že jestliže y x,
pak x y.
(Tj. x je minimální právě když neexistuje žádný prvek ostře menší než x.)
s
sX
x
d
d
d
ˇ x  M je maximální právě když pro každé y  M platí, že jestliže x y,
pak y x.
(Tj. x je maximální právě když neexistuje žádný prvek ostře větší než x.)
ˇ x  M je nejmenší právě když pro každé y  M platí, že x y.
s s s
s
x
d
d
d
 
 
 
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.2 Další pojmy uspořádaných množin5.2 Další pojmy uspořádaných množin
Definice 5.4. Buď (M, ) uspořádaná množina.
ˇ x  M je minimální právě když pro každé y  M platí, že jestliže y x,
pak x y.
(Tj. x je minimální právě když neexistuje žádný prvek ostře menší než x.)
s
sX
x
d
d
d
ˇ x  M je maximální právě když pro každé y  M platí, že jestliže x y,
pak y x.
(Tj. x je maximální právě když neexistuje žádný prvek ostře větší než x.)
ˇ x  M je nejmenší právě když pro každé y  M platí, že x y.
s s s
s
x
d
d
d
 
 
 
ˇ x  M je největší právě když pro každé y  M platí, že y x.
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
ˇ x  M pokrývá y  M právě když x = y, y x a neexistuje žádné
z  M takové, že x = z = y a y z x.
s
s
s
x
y
X
 
 
 
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
ˇ x  M pokrývá y  M právě když x = y, y x a neexistuje žádné
z  M takové, že x = z = y a y z x.
s
s
s
x
y
X
 
 
 
ˇ x  M je horní závora (mez) množiny A  M právě když y x pro
každé y  A.
ˇ x  M je dolní závora (mez) množiny A  M právě když x y pro každé
y  A.
s
x
y  A




d
d
d
 
 
 
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
ˇ x  M je supremum množiny A  M, právě když x je nejmenší horní
závora množiny A.
ˇ x  M je infimum množiny A  M právě když x je největší dolní závora
množiny A.
s
A




d
d
d
 
 
 
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
ˇ x  M je supremum množiny A  M, právě když x je nejmenší horní
závora množiny A.
ˇ x  M je infimum množiny A  M právě když x je největší dolní závora
množiny A.
s
A




d
d
d
 
 
 
ˇ A  M je řetězec v uspořádání právě když (A, ) je lineárně uspořádaná
množina.
s
s
s
s
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
ˇ x  M je supremum množiny A  M, právě když x je nejmenší horní
závora množiny A.
ˇ x  M je infimum množiny A  M právě když x je největší dolní závora
množiny A.
s
A




d
d
d
 
 
 
ˇ A  M je řetězec v uspořádání právě když (A, ) je lineárně uspořádaná
množina.
s
s
s
s
Pozor! Některé uvedené definice mají dosti ,,netriviální chování na nekonečných mno-
žinách. Proto je budeme obvykle uvažovat jen nad konečnými množinami. . .
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Relace předuspořádání
Definice: Relace R  M × M je předuspořádání (také kvaziuspořádání, nebo
polouspořádání) právě když R je reflexivní a tranzitivní.
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Relace předuspořádání
Definice: Relace R  M × M je předuspořádání (také kvaziuspořádání, nebo
polouspořádání) právě když R je reflexivní a tranzitivní.
Rozdíl mezi uspořádáním a předuspořádáním je (neformálně řečeno!) v tom, že u pře-
duspořádání srovnáváme prvky podle kritéria, které není pro daný prvek jedinečné.
V předuspořádání takto mohou vznikat ,,cykly .
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Relace předuspořádání
Definice: Relace R  M × M je předuspořádání (také kvaziuspořádání, nebo
polouspořádání) právě když R je reflexivní a tranzitivní.
Rozdíl mezi uspořádáním a předuspořádáním je (neformálně řečeno!) v tom, že u pře-
duspořádání srovnáváme prvky podle kritéria, které není pro daný prvek jedinečné.
V předuspořádání takto mohou vznikat ,,cykly .
Tvrzení 5.5. Je-li předuspořádání na M, můžeme definovat relaci  na M
předpisem
x  y právě když x y a y x.
Pak  je ekvivalence na M, která se nazývá jádro předuspořádání .
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Relace předuspořádání
Definice: Relace R  M × M je předuspořádání (také kvaziuspořádání, nebo
polouspořádání) právě když R je reflexivní a tranzitivní.
Rozdíl mezi uspořádáním a předuspořádáním je (neformálně řečeno!) v tom, že u pře-
duspořádání srovnáváme prvky podle kritéria, které není pro daný prvek jedinečné.
V předuspořádání takto mohou vznikat ,,cykly .
Tvrzení 5.5. Je-li předuspořádání na M, můžeme definovat relaci  na M
předpisem
x  y právě když x y a y x.
Pak  je ekvivalence na M, která se nazývá jádro předuspořádání .
Na rozkladu M/  pak lze zavést relaci definovanou takto
[x] [y] právě když x y.
Pak (M/ , ) je uspořádaná množina.
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Relace předuspořádání
Definice: Relace R  M × M je předuspořádání (také kvaziuspořádání, nebo
polouspořádání) právě když R je reflexivní a tranzitivní.
Rozdíl mezi uspořádáním a předuspořádáním je (neformálně řečeno!) v tom, že u pře-
duspořádání srovnáváme prvky podle kritéria, které není pro daný prvek jedinečné.
V předuspořádání takto mohou vznikat ,,cykly .
Tvrzení 5.5. Je-li předuspořádání na M, můžeme definovat relaci  na M
předpisem
x  y právě když x y a y x.
Pak  je ekvivalence na M, která se nazývá jádro předuspořádání .
Na rozkladu M/  pak lze zavést relaci definovanou takto
[x] [y] právě když x y.
Pak (M/ , ) je uspořádaná množina. 2
Pro příklad si vezměme relaci dělitelnosti na Z. Pak třeba -2  2.
Jádrem zde jsou dvojice čísel stejné absolutní hodnoty.
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.3 Hasseovské diagramy5.3 Hasseovské diagramy
Hasseovské diagramy uspořádaných množin jsou přehlednější než grafy relací.
Například:
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.3 Hasseovské diagramy5.3 Hasseovské diagramy
Hasseovské diagramy uspořádaných množin jsou přehlednější než grafy relací.
Například:
Definice: Hasseovský diagram konečné uspořádané množiny (M, ) je (jedno-
značné) grafické znázornění vzniklé takto:
­ Do první ,,horizontální vrstvy zakreslíme body odpovídající mininálním
prvkům (M, ) (tj. které nepokrývají nic).
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.3 Hasseovské diagramy5.3 Hasseovské diagramy
Hasseovské diagramy uspořádaných množin jsou přehlednější než grafy relací.
Například:
Definice: Hasseovský diagram konečné uspořádané množiny (M, ) je (jedno-
značné) grafické znázornění vzniklé takto:
­ Do první ,,horizontální vrstvy zakreslíme body odpovídající mininálním
prvkům (M, ) (tj. které nepokrývají nic).
­ Máme-li již zakreslenu ,,vrstvu i, pak do ,,vrstvy i + 1 (která je ,,nad
vrstvou i) zakreslíme všechny nezakreslené prvky, které pokrývají pouze
prvky ,,vrstev  i. Pokud prvek x ,,vrstvy i + 1 pokrývá prvek y ,,vrstvy
 i, spojíme x a y neorientovanou hranou (tj. ,,čárou ).
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Příklad 5.6. Relaci dělitelnosti na množině {1, 2, . . . , 12} zakreslíme:
1
3
64
2
12
8
75
10 119
dělitelnost:
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Příklad 5.6. Relaci dělitelnosti na množině {1, 2, . . . , 12} zakreslíme:
1
3
64
2
12
8
75
10 119
dělitelnost:
2
Jak vidíme, v Hasseově diagramu ,,vynecháváme ty hrany relace , které vy-
plývají z reflexivity či tranzitivity. To celý obrázek výrazně zpřehlední, a přitom
nedochází ke ztrátě informace.
Lze vynechat i šipky na hranách, neboť dle definice všechny míří ,,vzhůru .
Také pojem ,,vrstvy v definici je jen velmi neformální, důležité je, že větší
(pokrývající) prvky jsou nad menšími (pokrývanými).
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.4 Uzávěry relací5.4 Uzávěry relací
Buď V (nějaká) vlastnost binárních relací. Řekneme, že V je uzavíratelná, pokud
splňuje následující podmínky:
­ Pro každou množinu M a každou relaci R  M ×M existuje alespoň jedna
relace S  M × M, která má vlastnost V a pro kterou platí R  S.
­ Nechť I je množina a nechť Ri  M × M je relace mající vlastnost V pro
každé i  I. Pak relace iI Ri má vlastnost V .
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.4 Uzávěry relací5.4 Uzávěry relací
Buď V (nějaká) vlastnost binárních relací. Řekneme, že V je uzavíratelná, pokud
splňuje následující podmínky:
­ Pro každou množinu M a každou relaci R  M ×M existuje alespoň jedna
relace S  M × M, která má vlastnost V a pro kterou platí R  S.
­ Nechť I je množina a nechť Ri  M × M je relace mající vlastnost V pro
každé i  I. Pak relace iI Ri má vlastnost V .
Fakt: Libovolná kombinace vlastností reflexivita, symetrie, tranzitivita je uza-
víratelná vlastnost.
Antisymetrie není uzavíratelná vlastnost.
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
5.4 Uzávěry relací5.4 Uzávěry relací
Buď V (nějaká) vlastnost binárních relací. Řekneme, že V je uzavíratelná, pokud
splňuje následující podmínky:
­ Pro každou množinu M a každou relaci R  M ×M existuje alespoň jedna
relace S  M × M, která má vlastnost V a pro kterou platí R  S.
­ Nechť I je množina a nechť Ri  M × M je relace mající vlastnost V pro
každé i  I. Pak relace iI Ri má vlastnost V .
Fakt: Libovolná kombinace vlastností reflexivita, symetrie, tranzitivita je uza-
víratelná vlastnost.
Antisymetrie není uzavíratelná vlastnost.
Věta 5.7. Nechť V je uzavíratelná vlastnost binárních relací. Buď M množina
a R libovolná binární relace na M. Pak pro množinu všech relací S  R na
M majících vlastnost V existuje infimum RV (vzhledem k množinové inkluzi),
které samo má vlastnost V .
Tuto ,,nejmenší relaci RV s vlastností V nazýváme V -uzávěr relace R.
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Tvrzení 5.8. Buď R binární relace na M.
ˇ Reflexivní uzávěr R je přesně relace R  {(x, x) | x  M}.
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Tvrzení 5.8. Buď R binární relace na M.
ˇ Reflexivní uzávěr R je přesně relace R  {(x, x) | x  M}.
ˇ Symetrický uzávěr R je přesně relace

R= {(x, y) | (x, y)  R nebo (y, x)  R}.
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Tvrzení 5.8. Buď R binární relace na M.
ˇ Reflexivní uzávěr R je přesně relace R  {(x, x) | x  M}.
ˇ Symetrický uzávěr R je přesně relace

R= {(x, y) | (x, y)  R nebo (y, x)  R}.
Buď T funkce, která pro každou binární relaci S vrátí relaci
T (S) = S  {(x, z) | existuje y takové, že (x, y), (y, z)  S}
a T i = T      T
i
budiž i-krát iterovaná aplikace funkce T .
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Tvrzení 5.8. Buď R binární relace na M.
ˇ Reflexivní uzávěr R je přesně relace R  {(x, x) | x  M}.
ˇ Symetrický uzávěr R je přesně relace

R= {(x, y) | (x, y)  R nebo (y, x)  R}.
Buď T funkce, která pro každou binární relaci S vrátí relaci
T (S) = S  {(x, z) | existuje y takové, že (x, y), (y, z)  S}
a T i = T      T
i
budiž i-krát iterovaná aplikace funkce T .
ˇ Tranzitivní uzávěr R je přesně relace R+ = 
i=1 T i(R).
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Tvrzení 5.8. Buď R binární relace na M.
ˇ Reflexivní uzávěr R je přesně relace R  {(x, x) | x  M}.
ˇ Symetrický uzávěr R je přesně relace

R= {(x, y) | (x, y)  R nebo (y, x)  R}.
Buď T funkce, která pro každou binární relaci S vrátí relaci
T (S) = S  {(x, z) | existuje y takové, že (x, y), (y, z)  S}
a T i = T      T
i
budiž i-krát iterovaná aplikace funkce T .
ˇ Tranzitivní uzávěr R je přesně relace R+ = 
i=1 T i(R).
ˇ Reflexivní a tranzitivní uzávěr R je přesně relace R = 
i=1 T i(Q), kde
Q je reflexivní uzávěr R.
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Tvrzení 5.8. Buď R binární relace na M.
ˇ Reflexivní uzávěr R je přesně relace R  {(x, x) | x  M}.
ˇ Symetrický uzávěr R je přesně relace

R= {(x, y) | (x, y)  R nebo (y, x)  R}.
Buď T funkce, která pro každou binární relaci S vrátí relaci
T (S) = S  {(x, z) | existuje y takové, že (x, y), (y, z)  S}
a T i = T      T
i
budiž i-krát iterovaná aplikace funkce T .
ˇ Tranzitivní uzávěr R je přesně relace R+ = 
i=1 T i(R).
ˇ Reflexivní a tranzitivní uzávěr R je přesně relace R = 
i=1 T i(Q), kde
Q je reflexivní uzávěr R.
ˇ Reflexivní, symetrický a tranzitivní uzávěr R (tj. nejmenší ekvivalence ob-
sahující R) je přesně relace (

Q)+, kde Q je reflexivní uzávěr R.
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Uspořádané množiny, Uzávěry
Význam reflexivních a symetrických uzávěrů je z předchozího docela zřejmý.
Význam tranzitivního uzávěru R+ je následovný: Do R+ přidáme všechny ty
dvojice (x, z) takové, že v R se lze ,,dostat po šipkách z x do z.
A jak bylo dříve řečeno, antisymetrický uzávěr relace prostě nemá smysl.
Buď R  N×N definovaná takto: R = {(i, i+1) | i  N}. Pak R je běžné .