Petr Hliněný, FI MU Brno 1 FI: IB000: 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ávají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í.
2
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 FI: IB000: 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 2
* symetrická, právě když pro každé a, b  M platí, že jestliže (a, b)  R, pak
také (b, a)  R; s s
* antisymetrická, právě když pro každé a, b  M platí, že jestliže
(a, b), (b, a)  R, pak a = b;
s sX
2
* 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 FI: IB000: 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í. 2Tyto tři vlastnosti je tedy třeba ověřit k důkazu
toho, že daná relace R je uspořádání.2
* 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. 2
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é.)2
* Zajisté jste se již neformálně setkali s ,,neostrým uspořádáním čísel  a
,,ostrým uspořádáním < . 2Vš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 FI: IB000: 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 reflexivity
a tranzitivity, viz Oddíl 5.3):
Všimněte si, že je zvykem ,,větší prvky kreslit nad ty ,,menší .
Petr Hliněný, FI MU Brno 5 FI: IB000: 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.2
Definice: Uspořádání R na M je lineární (nebo také úplné), pokud každé dva
prvky M jsou v R srovnatelné.2
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;2
* (x, y)  R právě když y má alespoň takovou výšku jako x;2
* (x, y)  R právě když x a y mají stejné rodné číslo. 2
Další ukázky uspořádaných množin následují zde:
* (, ) je lineárně uspořádaná množina, kde  má ,,obvyklý význam.2
* (, | ), kde | je relace dělitelnosti, je uspořádaná množina. Toto uspořádání
není lineární.2
* Buď M množina. Pak (2M , ) je uspořádaná množina (říkáme inkluzí).
Petr Hliněný, FI MU Brno 6 FI: IB000: 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 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 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 třeba lexikograficky se řadí slova ve slovníku. . .
Petr Hliněný, FI MU Brno 7 FI: IB000: 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
2
* 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.)2
* x  M je nejmenší právě když pro každé y  M platí, že x  y.
s s s
s
x
2
* x  M je největší právě když pro každé y  M platí, že y  x.
Petr Hliněný, FI MU Brno 8 FI: IB000: 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
2
* 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
* x  M je horní závora (mez) množiny A  M právě když y  x pro
každé y  A.
Petr Hliněný, FI MU Brno 9 FI: IB000: Uspořádané množiny, Uzávěry
* x  M je infimum množiny A  M právě když x je největší dolní závora
množiny A.
s
A
* x  M je supremum množiny A  M, právě když x je nejmenší horní
závora množiny A.2
* A  M je řetězec v uspořádání  právě když (A, ) je lineárně uspořádaná
množina.
s
s
s
s
2
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 FI: IB000: 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í.2
Rozdíl mezi uspořádáním a předuspořádáním je (neformálně řečeno!) v tom, že u předuspořá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 . 2
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í .2
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 ukázku si vezměme relaci dělitelnosti na . Pak třeba -2  2.
Jádrem zde jsou dvojice čísel stejné absolutní hodnoty.
Petr Hliněný, FI MU Brno 11 FI: IB000: Uspořádané množiny, Uzávěry
Důkaz (náznak): Tranzitivita a reflexivita relace  vyplývá z tranzitivity a reflexivity
relace . Symetrie  pak je přímým důsledkem její definice. Tudíž 
skutečně je relací ekvivalence a M/  je platný rozklad.
Tranzitivita a reflexivita relace se opět dědí z relace . Její antisymetrie
vyplývá následující úvahou: Pokud [x] [y] a [y] [x], pak podle naší definice
x  y a y  x, neboli x  y a [x] = [y] podle definice tříd rozkladu. Pozor,
nejdůležitější částí této větve důkazu je však ještě zdůvodnit, že naše podaná
definice vztahu [x] [y] je korektní, což znamená, že její platnost nezávisí na
konkrétní volbě reprezentantů x z [x] a y z [y]. 2
Petr Hliněný, FI MU Brno 12 FI: IB000: Uspořádané množiny, Uzávěry
5.3 Hasseovské diagramy5.3 Hasseovské diagramy
Motivace: tzv. Hasseovské diagramy uspořádaných množin jsou přehlednější než
grafy relací. Například si srovnejte:
2
Definice: Hasseovský diagram konečné uspořádané množiny (M, ) je (jednoznač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.)2
­ 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 13 FI: IB000: Uspořádané množiny, Uzávěry
Příklad 5.6. Relaci dělitelnosti na množině {1, 2, . . ., 12} zakreslíme:
2
2
Jak vidíme, v Hasseově diagramu ,,vynecháváme ty hrany relace , které vyplý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 14 FI: IB000: 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 .2
Fakt: Libovolná kombinace vlastností reflexivita, symetrie, tranzitivita je uzavíratelná
vlastnost.
Antisymetrie není uzavíratelná vlastnost. 2
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 15 FI: IB000: 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}.2
* Symetrický uzávěr R je přesně relace

R= {(x, y) | (x, y)  R nebo (y, x)  R}.2
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 . 2
* Tranzitivní uzávěr R je přesně relace R+ = 
i=1 T i(R).2
* 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.2
* Reflexivní, symetrický a tranzitivní uzávěr R (tj. nejmenší ekvivalence obsahující
R) je přesně relace (

Q)+, kde Q je reflexivní uzávěr R.
Petr Hliněný, FI MU Brno 16 FI: IB000: 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. Nakreslete si to
na papír pro nějakou jednoduchou relaci, abyste význam tranzitivního uzávěru
lépe pochopili.
A jak bylo dříve řečeno, antisymetrický uzávěr relace prostě nemá smysl.
Buď R  ×  definovaná takto: R = {(i, i + 1) | i  }. Pak R je běžné
lineární uspořádání  přirozených čísel.