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“, 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 uspořádání v M, právě když U je antisymetrická a tranzitivní.

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

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

Binární relaci U v množině M nazýváme ostré lineární uspořádání v M, právě když U 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í



Příklad 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]}


Příklad 2: Je dána množina A, jejímiž prvky jsou vybraní žáci z 3. třídy. Jejich jména a další
údaje o nich jsou uvedeny níže v tabulce. Tvořte relace v množině A pomocí slovního zadání, zapište
je pak výčtem prvků a určete jejich vlastnosti.

Jméno

     Datum narození

                   Váha

                        Výška

                              Domácí mazlíček

Kája

     6. 7. 2010

                   35 kg

                        136 cm

                              Pes

Adéla

     15. 4. 2010

                   27 kg

                        132 cm

                              Kočka

Tomáš

     3. 3. 2010

                   41 kg

                        146 cm

                              had

Petra

     7. 3. 2010

                   31 kg

                        134 cm

                              Pes

Marek

     6. 3. 2010

                   30 kg

                        141 cm

                              Kočka