Binární relace II

(binární relace v množině – uspořádání, ekvivalence)


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


Příklad:

1.      Je dána množina M = {1,2,3,4,5}. Zapište následující relace výčtem prvků.

R[1] = {[x,y]  M x M; x + 2 = y}

(zápis čteme: „Relace R[1] je množina všech uspořádaných dvojic [x,y]  z kartézského součinu M x M,
pro které platí, že  x + 2 = y - tedy druhá složka je o 2 větší než první složka.“)

R[2] = {[x,y]  M x M;  x > y }

R[3] = {[x,y]  M x M;  x < y  x + y = 4}

R[4 ]= {[x,y]  M x M;  x  je násobkem  y}

R[5] = {[x,y]  M x M;  x = y}

R[6] = {[x,y]  M x M;  x dává při dělení dvěma stejný zbytek jako y při dělení dvěma}.

Je některá z uvedených relací zobrazení v množině M? Pokud ano, určete přesně typ zobrazení.


2.      Uvažujte množinu O všech osob v dané místnosti (posluchárně, v sále kina) a na této

množině binární relace S[1] - S[5] . Uvažujte o tom, z jakých uspořádaných dvojic osob se tyto
relace skládají.:

S[1]  =  {[x,y]  O x O;  x  je v abecedě před y}

S[2]  =  {[x,y]  O x O;  x  je narozen ve stejném měsíci jako y}

S[3]  =  {[x,y]  O x O;  x  je starší než y}

S[4]  =  {[x,y]  O x O;  x je na mateřské dovolené a y neviděl film Vratné lahve}

S[5]  =  {[x,y]  O x O;  x má stejný počet dětí jako y}



Binární relace S[1],  S[3],  R[2] jsou tzv. relace uspořádání.  Určují pořadí prvků v množině, na
níž jsou definovány. Uveďte výčtem prvků takto uspořádané množiny - nyní již záleží na pořadí.
Např.

= , je množina M uspořádaná relací R[2].

 je množina osob O uspořádaných podle abecedy (tedy uspořádáním S[1]),

 je množina osob O uspořádaných podle stáří od nejstaršího (tedy uspořádáním S[3]).



Binární relace S[2], S[5] jsou tzv. relace ekvivalence na množině O.

Relace R[5, ]R[6] jsou ekvivalence na množině M.

Jsou to takové relace, které vytvářejí  rozklad množiny, na níž jsou definované. Tato množina se
rozpadá na podmnožiny (říkáme třídy rozkladu). Přitom do  téže třídy rozkladu patří ty prvky
z původní množiny, které „ jsou spolu v uspořádané dvojici“, tedy jsou vázané vztahem popsaným
v příslušné relaci)


Rozklad množiny A je systém neprázdných podmnožin množiny A, tzv. tříd rozkladu, takových, že každý
prvek z množiny A patří právě do jedné třídy rozkladu.

(Jinak můžeme také říci, že žádné dvě třídy rozkladu nemají společné prvky a současně sjednocení
všech tříd rozkladu je původní množina.)



Příklad:

·        Rozklad množiny M vytvořený relací R[6]:  {{1, 3, 5}, {2, 4}} .


·        Rozklad množiny M vytvořený relací R[5]:  {{1}, {2},{3},{4},{5}}


·        V každé třídě rozkladu množiny O vytvořeného relací  S[2] budou osoby, které se narodily
ve stejném měsíci. Tzn., že rozklad bude obsahovat nejvýše 12 tříd rozkladu.


·        Rozklad množiny O vytvořený relací  S[5] bude obsahovat třídu osob, které nemají žádné
dítě, další třídu osob, které mají 1 dítě, další třídu osob, které mají 2 děti atd. (jako třídy
rozkladu neuvažujeme prázdné množiny).


[ ]



[ ]