5   Uspořádané množiny, Uzávěry
V teto lekci dale pokračujeme probírán ím binarn ích relací na množinách jako nástrojů vyjadřuj ících vžtahy meži objekty. Zameřujeme se nyn í především na relace „srovnavaj íc í " objekty podle jejich vlastnost í. Takto vagne opsane relace m ívaj í jasne spolecne žnaky, ktere se objevuj í ve formaln í definici relace uspořadan í.
Stručný přéhléd lékcé
* Uspořádané množiny a relevantní pojmy k uspořádání.
* Hasseovské diagramy uspořádaných množin.
* Užavéry relací-jak danou relaci „obohatit" o zvolenou vlastnost.
Petr Hliněný,  FI MU Brno_FI: IB000: Uspořádané množiny, Uzávěry
_
Vlastnosti binárních relací, zopakování
Nechť R C M x M. Binární relace R je
• reflexivní, práve kdyz pro kazde a € M plaťí (a, a) € R;
•O *č>
• ireflexivní, práve kdyz pro kazde a € M plaťí (a, a) € R;
« X  <X c
• symetrická, práve kdyz pro kazde a, b € M plaťí, Ze jesťlize (a, b) € R, pak ťake (b, a) € R;
antisymetrická,  práve kdyz pro kazde a, b   €   M plaťí, ze jesťlize
(a, b), (b, a) € R, pak a = b;
X
• tranzitivní, práve kdyz pro kazde a, b, c € M plaťí, ze jesťlize (a, b), (b, c) € R, pak ťake (a, c) € R. a       b c
e- e-í=-pt
Petr Hliněný,  FI MU Brne_2       FI: IB000: Uspořádané množiny, Uzávěry
5.1   Uspořádané množiny
• Relace R C M x M je (částečné) uspořádání právě když R je reflexivní, an-tisymetrická a tranzitivní. nTyto tri vlastnosti je tedy třeba overit k důkažu toho, že dana relace R je uspořadaní.c
• Neformalne řeCeno: uspořadaní je takova relace R C M x M, kde (x, y) € R prave když x je v nejakem smyslu „mensí nebo rovno" než y. c
Mohou ovsem existovat takova x, y € M, kde neplatí (x, y) € R ani (y, x) € R. (Pak ríkame, že x a y jsou nesrovnatelné.)c
• Zajiste jste se již neformálne setkali s „neostrym" uspořádáním císel < a „ostrím" uspořídíním <. nVsimnete si dobře, že ními definovane usporídíníje vždy „neostre".
Avsak pokud byste chteli definovat „ostre" uspořadaní, melo by vlastnosti ireflexivn , antisymetricke a tranžitivní. (Přílis se vsak toto nepoužíva.)
Petr Hliněný,  FI MU Brnc_3       FI: IB000: Uspořádané množiny, Uzávěry
• Jak názorně zobrazit (částečné) uspořádání?
Příklad zjednoduSeného zakreslení (jsou vynechány Šipky vyplývající z reflexivity a tranzitivity, viz Oddíl 5.3):
8 12
dělitelnost:
Vsimnete si, že je žvykem „vetsí" prvky kreslit nad ty „mensí".
Petr Hliněný,  FI MU Brno__rI: IB000: Uspořádaně množiny, Uzávěry
Definice 5.1. Uspořádaná množina je dvojice (M, C), kde M je množina a C je (CasteCne) uspořádání na M .c
Definice: Uspořadaní R na M je lineární (nebo take úplné), pokud každe dva prvky M jsou v R srovnatelne.c
Bud' M množina vsech studentU 1. roCníku FI. Uvažme postupne relace uspořadaní R C M x M definovane nasledovne (jsou to vždy uspořadaní?):
• (x, y) € R prave když x ma alespon takovou výsku jako y;c
• (x, y) € R prave když y ma alespoř takovou výsku jako x;c
• (x, y) € R prave když x a y mají stejne rodne Císlo. c
Dalsí ukažky usporadanych množin nasledují žde:
• (N, <) je linearne uspořadana množina, kde < ma „obvykly" vyžnam.c
• (N, |), kde | je relace delitelnosti, je uspořadana množina. Toto usporadaní není linearní.c
• Bud' M množina. Pak (2M, C) je uspořadana množina (říkame inkluzi).
Petr Hliněný,  FI MU Brno _:I: 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 C na
Příklad 5.3. Lexikografické uspořádání.
Necht (A, <a) a (B, <b) jsou uspořádané množiny. Definujme binární relaci < na A x B předpisem
(a, b) ^ (a', 6')    prave když    bud' a <a a' a a = a', nebo a = a' a b <b b'.
Pak (A x B, <) je uspořádaná množina. Navíc pokud <a i <B jsou lineární, je i ^ linearní. Toto uspořadání se nažyva lexikograficke.n □
Fakt: Jsou-li (Ai, <i), ••• , (An, <n) usporadane množiny, kde n > 2, pak množinu A1 x • • • x An lže usporadat po složkach nebo lexikograficky.
Vsimnete si, že treba lexikograficky se řadí slova ve slovníku...
A x B přredpisem
(a, b) C (a', b')    prave když    a <a a' a b <b b'.
Pak (A x B, C) je usporadana množina. Toto usp. se nažyva „po složkach".c
□
'etr Hliněný.  FI MU Brno
6
FI: IB000: Uspořádaně množiny. Uzávěry
r.
5.2   Další pojmy uspořádaných množin Definice 5.4.   Bud' (M, C) uspořádaná množina.
• x € M je minimální práve když pro každe y € M platí, že jestliže y C x,
pak x C y.
(Tj. x je minimálni práve když neexistuje žádny prvek ostře menSí než x.)
• x € M je maximálni práve když pro každe y € M platí, že jestliže x C y,
pak y C x.
(Tj. x je maximálni práve když neexistuje žádný prvek ostre vetsá než x.)c
• x € M je nejmensi práve když pro každe y € M platá, že x C y.
x «
x
• x € M je nejvetší práve když pro každe y € M platá, že y C x.
'etr Hliněný,  FI MU Brno
FI: IB000: Uspořádané množiny, Uzávěry
* x € M pokrývá y € M právě když x = y, y C x a neexistuje žádné z € M takové, že x = z = y a y C z C x.
X
y
• x € M je dolní závora (mež) množiny A C M právě když x C y pro každé
ž/ e A.
► x € M je horní závora (mež) množiny A C M práve když y C x pro každe y € A.
Petr Hliněný,  FI MU Brno
_FI: IB000: Uspořádaně množiny, Uzávěry
x
x
► x € M je infimum množiny A C M právě když x je největší dolní závora množiny A.
• x € M je supremum množiny A C M, právě když x je nejmenší horní závora množiny A.c
• A C M je řetězec v uspořádání C práve když (A, C) je lineárne uspořádaná množiná.
Požor! Nektere uvedene definice máj í došti „netriviáln í chován í" ná nekonečných množinách. Proto je budeme obvykle uvážovát jen nád konecnymi množinámi.. .
etr Hliněný,  FI MU Brno
FI: IB000:_množiny, Uzývě
9
Rélacé přéduspořádání
Définicé: Relace R C M x M je předuspořádáni (take kvaziuspořádáni, nebo polouspořádáni) prave když R je reflexivn í a tranzitivní._
Rožd íl meži usporadan ím a předuspořadan ím je (neformalne receno!) v tom, že u predusporadan í srovnavame prvky podle kriteria, ktere nen í pro dany prvek jedinecne. V předuspořadan í takto mohou vznikat „cykly". _
Tvrzéní 5.6. Je-li C preduspořadan í na M, mužeme definovat relaci ~ na M předpisem
x ~ y    prave když    x C y a y C x. Pak ~ je ekvivalence na M, ktera se nažyva jádro předuspořádán i C._ Na rožkladu M/ ~ pak lže žavest relaci ^ definovanou takto
[x] r< [y]    prave když x C y.
Pak (M/ ~, ^) je usporadana množina. _
Pro ukažku si vežmeme relaci delitelnosti na 7L. Pak třeba —2 ~ 2. Jadrem žde jsou dvojice císel stejne absolutní hodnoty.
Petr Hliněný,  FI MU Brno _ FI: IB000: Uspořádaně množiny, Uzávěry
Tvrzení 5.6. Je-li C preduspořadaní na M, mužeme definovat relaci ~ na M přredpisem
x ~ y    prave když    x C y a y C x. Pak ~ je ekvivalence na M, ktera se nažyva jádro předuspořádáni C.c Na rožkladu M/ ~ pak lže žavest relaci ^ definovanou takto
[x] r< [y]    prave když x C y.
Pak (M/ ~, ^) je usporadana množina. c
Důkaz (nažnak): Tranžitivita a reflexivita relace ~ vyplyva ž tranžitivity a reflexivity relace C. Symetrie ~ pak je přímym dusledkem její definice. Tudíž ~ skutecne je relací ekvivalence a M/ ~ je platny rožklad.
Tranžitivita a reflexivita relace ^ se opet dedí ž relace C. Její antisymetrie vyplyva nasledující uvahou: Pokud [x] ^ [y] a [y] ^ [x], pak podle nasí definice x C y a y C x, neboli x ~ y a [x] = [y] podle definice tříd rožkladu. Požor, nejduležitejsí castí teto vetve dukažu je vsak jeste žduvodnit, že nase podana definice vžtahu [x] ^ [y] je korektní, což žnamená, že její platnost nežávisí na konkrátní volbe reprežentantu x ž [x] a y ž [y]. □
Petr Hliněný.  FI MU Brno _:I: IB000: Uspořádaně množiny. Uzávěry
5.3   Hasseovské diagramy
Motivace: tzv. Hasseovské diagramy uspořádaných množin jsou přehlednější nez grafy relací. Například si srovnejte:
Definice: Hasseovský diagram konečne uspořadane množiny (M, C) je (jed-noznaCne) grafičke znazornen í vznikle takto:
- Do prvn í „horizontaln í vrstvy" zakresl íme body odpovídaj ící mininaln ím prvkUm (M, C). (Tj. ktere nepokryvaj i nic.)_
- Mame-li jiz zakreslenu „vrstvu" i, pak do „vrstvy" i + 1 (ktera je „nad" vrstvou i) zakresl íme vsechny nezakreslene prvky, ktere pokryvaj i pouze prvky „vrstev" < i. Pokud prvek x „vrstvy" i + 1 pokryva prvek y „vrstvy" < i, spoj íme x a y neorientovanou hranou (tj. „carou").
'etr Hliněný,  FI MU Brno
12
FI: IB000:_mnoziný, Uzávěi
erý
_
Příklad 5.7. Relaci dělitelnosti na množine (1, 2,..., 12} zakreslíme:
□
Jak vidíme, v Hasseove diagramu „vynechavame" ty hrany relace C, které vyplyvají ž reflexivity ci tranžitivity. To cely obražek vyražne žprehlední, a pritom nedochaží ke žtrate informace.
Lže vynechat i sipky na hranach, neboť dle definice vsechny mírí „vžhuru".
Take pojem „vrstvy" v definici je jen velmi neformalní, duležite je, že vetsí (pokryvající) prvky jsou nad mensími (pokryvanymi).
>ětr Hliněný,  FI MU Brn
FI: IB000: Uspořádaně množiny, Uzávěry
5.4   Uzávěry relací
Bud' V (nejaka) vlastnost binarní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 C M x M existuje alespon jedna relace S C M x M, ktera ma vlastnost V a pro kterou platí R C S.
- Necht I je množina a necht R C M x M je relace mající vlastnost V pro každe i € I. Pak relace P|ieI Rj ma vlastnost V .c
Fakt: Libovolna kombinace vlastností reflexivita, symetrie, tranžitivita je užav íratelna vlastnost.
Antisymetrie není užavíratelna vlastnost. c
Věta 5.8. Necht V je uzavíratelná vlastnost binárních relací. Bud M množina a R libovolná binární relace na M. Pak pro množinu všech relaci S 5 R na M majících vlastnost V existuje infimum Rv (vzhledem k množinové inkluzi), ktere samo ma vlastnost V.
Tuto „nejmensí" relaci Ry s vlastností V nažyvame V-uzáver relace .
Pětr Hliněny,  FI MU Brno _ FI: IB000: Uspořádaně množiny, Uzávěry
Tvrzení 5.9. Bud' R binárn í reláce ná M.
• Reflexivní uzáver R je prešne reláce R U {(x, x) | x € M}.l
• Symetricky uzáver R je přešne reláce
R= {(x, y) | (x, y) € R nebo (y, x) € R}.l
Bud' T funkce, která pro káždou binárn í reláci S vrát í reláci
T (S) = S U {(x, z) | exištuje y tákove, že (x, y), (y, z) € S} a T1 = To — of budiž í-krát iterovaná aplikace funkce T. c
i
• Tranzitivní uzáver R je prešne reláce R+ = \J°=1 Ti(R).
• Reflexivn í á tránžitivn í užáver R je přešne reláce R* = [j°=1 Ti(Q), kde Q je reflexivn í užáver R.l
• Reflexivn í, šymetricky á tránžitivn í užáver R (tj. nejmenší ekviválence ob-šáhuj íc i R) je prešne reláce (Q)+, kde Q je reflexivn í užáver R.
Petr Hliněný,  FI MU Brno _ FI: IB000: Uspořádaně množiny, Uzávěry
Vyžnam reflexivních a symetrických užaverU je ž předchožího docela žrejmy.
Vyžnam tranžitivního užaveru R+ je nasledovny: Do R+ pridame vSechny ty dvojice (x, z) takove, že v R se lže „dostat po Sipkach" ž x do z. Nakreslete si to na papír pro nejakou jednoduchou relaci, abyste vyžnam tranžitivního užaveru lepe pochopili.
A jak bylo dříve řeceno, antisymetricky užaver relace proste nema smysl.
Bud' R C N x N definovana takto: R = {(i, i + 1) | i € N}. Pak R* je bežne linearní uspořadaní < přiroženych císel.
Petr Hliněný,  FI MU Brno
16      FI: IB000: Uspořádaně množiny, Uzávěry