Binární relace v množině, vlastnosti binárních relací, ekvivalence, uspořádání.


Binární relace v množině M je libovolná podmnožina kartézského součinu M x M.


Znázornění binárních relací

Kartézský graf relace R  – sestrojíme dvě na sebe kolmé přímky x, y (vodorovnou a svislou). Na
vodorovnou přímku (osu) znázorníme pomocí bodů všechny prvky množiny, z níž vybíráme první složky
dvojic,  na svislou přímku (osu) znázorníme pomocí bodů všechny prvky množiny, z níž vybíráme druhé
složky dvojic. (Obvykle jsou sousední body na obou osách od sebe stejně vzdáleny.)  Uspořádanou
dvojici [a,b] R znázorníme bodem, který je průsečíkem dvou přímek procházejících body a, b a
rovnoběžných po řadě se svislou a vodorovnou osou.

Uzlový graf relace R v množině M -  v rovině znázorníme pomocí bodů (tzv. uzlů) všechny prvky
množiny M (pokud bychom znázorňovali relaci z množiny A do množiny B, pak znázorníme všechny prvky
sjednocení množina A a B). Uspořádanou dvojici [a,b] R znázorníme pomocí šipky (tzv. orientované
hrany), která vychází z uzlu a a směřuje do uzlu b. V případě, že a = b, nazýváme šipku smyčkou.
Pokud jsou v relaci R dvojice [a,b] a [b,a], znázorníme je “dvojšipkou” (tzv. neorientovanou
hranou).



Vlastnosti relací v množině M


Binární relace R v množině M je reflexivní  právě tehdy, když  ( x M) ([x,x] R),

tzn. obsahuje všechny uspořádané dvojice [x,x], kde x M.


Binární relace R v množině M je antireflexivní právě tehdy,  když  ( x M) ([x,x] R),

tzn. neobsahuje žádnou uspořádanou dvojici typu [x,x], kde x M.


Binární relace R v množině M je symetrická právě tehdy, když

( x,y M) ([x,y] R  [y,x] R),

tzn. s každou uspořádanou dvojicí [x,y] obsahuje i dvojici ([y,x].


Binární relace R v množině M je antisymetrická právě tehdy,  když

 ( x,y M) ( (x y  [x,y] R) [y,x] R ),

tzn. s žádnou dvojicí [x,y] různých prvků neobsahuje dvojici [y,x].


Binární relace R v množině M je tranzitivní právě tehdy, když

( x,y,z M) ( ([x,y] R  [y,z] R)  [x,z] R ),

tzn. jestliže se v relaci vyskytují „na sebe navazující dvojice“ (tj. druhá složka jedné dvojice je
stejná jako první složka jiné dvojice), pak musí relace obsahovat i dvojici, jejíž první složkou je
1. složka z první dvojice a druhou složkou je 2. složka z druhé dvojice.


Binární relace R v množině M je souvislá právě tehdy, když

( x,y M) ( x y  ([x,y] R  [y,x] R) ),

tzn. každé dva různé prvky z množiny M musí být „spolu v relaci“.





Binární relaci U v množině M nazýváme ostré lineární uspořádání v M, právě když je antisymetrická,
tranzitivní, souvislá a antireflexivní.


Binární relaci R v množině M nazýváme relací ekvivalence na M, právě když je reflexivní, symetrická
a tranzitivní.

Každá relace ekvivalence na množině M vytváří rozklad této množiny, což je systém neprázdných
podmnožin (tzv. tříd rozkladu) množiny M takových, že průnik každých dvou tříd je prázdná množina a
sjednocení všech tříd rozkladu tvoří množinu M.

Jinak lze také říci, že říci, že rozklad množiny M je systém neprázdných podmnožin (tzv. tříd
rozkladu) množiny M takových, že každý prvek množiny M patří právě do jedné z těchto tříd.



Cvičení

1. Rozhodněte, jaké vlastnosti mají následující binární relace v množině M = {a, b, c, d}

R[1] = {[c,b], [b,c], [a,a], [b,b], [c,c], [d,d]}

R[2] = {[a,b], [c,d], [a,a], [b,b]}

R[3] = {[a,b], [d,c],[b,d],[a,c], [a,d], [b,c]}

R[4] = {[c,b], [b,c],[b,a]}

R[5] = {[a,a], [b,b], [c,c], [c,b], [b,c], [b,a], [a,b], [a,c], [c,a], [d,d]}

R[6] = {[c,a], [d,b]}

R[7] = {[a,a]}


2. Zapište aspoň jednu neprázdnou binární relaci v množině A = {1, 2, 3}, která je

a) reflexivní                  b) symetrická               c) tranzitivní                 d)
antireflexivní

e) antisymetrická          f) souvislá                    g) symetrická a není tranzitivní

V každém případě určete, jaké další vlastnosti má zvolená relace.


3. Rozhodněte o vlastnostech následujících relací:

a) rovnost v množině přirozených čísel

b) relace „být menší“ v množině přirozených čísel

c) relace „být podmnožinou“ v libovolném systému množin

d) kolmost přímek v rovině

e) rovnoběžnost přímek v rovině

f) shodnost trojúhelníků v rovině

g) relace „být sourozencem“

h) relace „být otcem“ ve vaší rodině

i) relace „narodit se ve stejném měsíci“ v množině lidí v této místnosti

j) relace „dávat stejný zbytek při dělení číslem 3“ v množině přirozených čísel.


Pokud je některá z výše uvedených relací relace ekvivalence, určete příslušný rozklad množiny.


Uvažujte další relace a určujte jejich vlastnosti.