Kartézský součin množin, binární relace z množiny do množiny


Kartézským součinem dvou množin A, B rozumíme množinu A x B = {[x,y]; x A  y B}, tj. množinu všech
uspořádaných dvojic [x,y], kde x A a y B.


Znázornění kartézského součinu A x B se provede tzv. kartézským grafem – sestrojíme dvě na sebe
kolmé přímky x, y (vodorovnou a svislou). Na vodorovnou přímku x (osu) znázorníme pomocí bodů
všechny prvky množiny A, z níž vybíráme první složky dvojic,  na svislou přímku y (osu) znázorníme
pomocí bodů všechny prvky množiny B, z níž vybíráme druhé složky dvojic. Uspořádanou dvojici [x,y]
A x B  znázorníme bodem, který je průsečíkem dvou přímek procházejících body x, y a rovnoběžných po
řadě se svislou a vodorovnou osou.


Binární relací R v neprázdné množině M rozumíme libovolnou podmnožinu kartézského součinu M x M.


Znázornění binárních relací se provede:

•         Kartézským grafem relace R  – analogicky jako u kartézského součinu výše.

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


↑ Opakování z minulého semestru ↑

---------------------------------------------------------------------------------------------------
------------------------

↓ Nová látka ↓


Definice 1: Binární relací R  z množiny M do množiny N rozumíme libovolnou podmnožinu kartézského
součinu M x N.


Příklad 1. Jsou dány množiny M = {x, y, z}, N = {a, b}.

·         Kartézský součin množin M, N:  M x N = {[x,a], [x,b], [y,a], [y,b], [z,a], [z,b]}

·         Binární relace R z množiny M do množiny N je libovolná podmnožina množiny M x N, tedy
např.:

R[1] = {[x,a]},

R[2] = {[x,a], [y,a], [y,b]},

R[3] = {[z,a], [y,a], [z,b], [x,b]},

R[4 ]= {[x,a], [x,b], [y,a], [y,b], [z,a], [z,b]} = M x N (tj. úplná relace z M do N)

R[5 ]= f (tj. nulová relace z M do N)


Znázornění binární relace  R z množiny M do množiny N se provede:

·         Kartézským grafem – analogicky jako u kartézského součinu množin výše.

·         Uzlovým grafem – vysvětleno níže na Příkladu 2.


Příklad 2. Jsou dány množiny M = {1, 2, 3, 4, 5}, N = {a, b, c, d} a relace R[ ]= {[2,a], [3,a],
[4,b], [5,d]} z množiny M do množiny N. Sestrojte kartézský a uzlový graf relace R.


Definice 2: Nechť R je relace z množiny A do množiny B a nechť S je relace z množiny B do množiny
C. Pak relace daná vztahem



R ○ S = {[x,y]  A x C; existuje b  B tak, že [x,b]  R    [b,y]  S}


se nazývá složená relace R ○ S z relací R a S.


Poznámka. Relaci R ○ S čteme: „S po R“.


Příklad 3. Jsou dány množiny A = {a, b, c, d}, B = {x, y, z}, C = {k, l, m, n}. Dále je dána relace
R = {[a,x], [c,y], [c,z]} z množiny A do množiny B a relace S = {[x,k], [x,l], [x,m], [x,n], [y,k],
[y,n]} z množiny B do množiny C. Určete relaci R ○ S.


Definice 3: Nechť R je relace z množiny A do množiny B. Relace R^-1 z množiny B do množiny A daná
vztahem



R^-1 = {[y,x]  B x A:  [x,y]  R}


se nazývá relace inverzní k relaci R.


Poznámka. Vzhledem k Definici 3 platí:

·         R  A x B

·         R^-1   B x A.


Příklad 4.  Jsou dány množiny A = {a, b, c, d}, B = {x, y, z} a relace R = {[a,x], [a,y], [b,z],
[c,y], [d,x]} z množiny A do množiny B. Určete relaci R^-1^  (tj. relaci inverzní k relaci R).


Poznámka. Pro libovolnou relaci R z množiny A do množiny B platí: (R^-1)^-1 = R.



Zobrazení z množiny do množiny, typy zobrazení


Definice 4: Nechť R je relace z množiny A do množiny B splňující vlastnosti: Ke každému prvku a  A
existuje nejvýše jeden prvek b  B takový, že [a,b]  R. Tato relace se nazývá zobrazení z množiny A
do množiny B. Značíme R: A → B.


Definice 5: Nechť R je zobrazení z množiny A do množiny B.

·       Jestliže [a,b]  R, pak prvek a  A nazýváme vzorem prvku  b  B v zobrazení R; prvek b  B
nazýváme obrazem prvku a  A v zobrazení R.

·         Množina O[1](R) = {a  A: existuje b  B takové, že [a,b]  R} se nazývá definiční obor
zobrazení R. Platí O[1](R)  A.

·         Množina O[2](R) = {b  B: existuje a  A takové, že [a,b]  R} se nazývá obor hodnot
zobrazení R. O[2](R)  B.


Příklad 5. Jsou dány množiny A = {x, y, z}, B = {a, b}. Rozhodněte, zda dané relace z množiny A do
množiny B jsou zobrazení z A do B, případně určete definiční obor a obor hodnot zobrazení.

            a) R[1] = {[x,a], [y,b], [z,a], [z,b]},

            b) R[2] = {[x,a], [z,b]},

            c) R[3] = {[x,a], [y,a], [z,a]}.



Rozlišujeme následující typy zobrazení R:


I) Je – li O[1](R) = A  O[2](R)  B  O[2](R) ≠ B, nazývá se R zobrazení množiny A do množiny B.


II) Je – li O[1](R)  A  O[1](R) ≠ A  O[2](R) = B, nazývá se R zobrazení z množiny A na množinu B.


III) Je – li O[1](R) = A  O[2](R) = B, nazývá se R zobrazení množiny A na množinu B.


IV) Je – li O[1](R)  A  O[1](R) ≠ A  O[2](R)  B  O[2](R) ≠ B, nazývá se R zobrazení z množiny A do
množiny B.


Příklad 6. Jsou dány množiny A = {x, y, a, c}, B = {c, x, b, z}.

a) Rozhodněte, o jaký typ zadaných zobrazení se jedná?

            1) R = {[x,z], [c,c], [y,c]}.

            2) S = {[x,z], [y,z], [a,z], [c,x]}.

b) Zapište výčtem prvků jednu binární relaci z množiny A do množiny B, která není zobrazením.

c) Zapište výčtem prvků

1) jedno zobrazení R[1] typu z množiny A do množiny B,

            2) jedno zobrazení R[2 ]množiny A do množiny B,

            3) jedno zobrazení množiny A na množinu B,

            4) jedno zobrazení z množiny A na množinu B.


Definice 5: Zobrazení R z množiny A do množiny B se nazývá prosté právě tehdy, když relace R^-1 je
zobrazení z množiny B do množiny A.


Důsledek: Zobrazení R z množiny A do množiny B je prosté právě tehdy, když

            a) ke každému y  B existuje nejvýše jedno x  A takové, že [x,y]  R,

            b) ke každým dvěma různým vzorům x[1, ]x[2][  ]  A přiřadíme dva různé obrazy y[1,
]y[2][ ]  B

                v zobrazení R.

Hovoříme pak o:

·         Prostém zobrazení množiny A do množiny B,

·         Prostém zobrazení z množiny A na množinu B,

·         Prostém zobrazení množiny A na množiny B,

·         Prostém zobrazení z množiny A do množiny B.


Definice 6: Prosté zobrazení množiny A na množinu B nazýváme bijektivní zobrazení nebo také
vzájemně jednoznačné zobrazení.


Příklad 7. Jsou dány množiny A = {1, 2, 3, 4}, B = {a, b, c, d}. Rozhodněte, o jaký typ zobrazení
se jedná a zda je toto zobrazení prosté:

            a) R[1][ = ]{[1,a], [2,c], [3,d]},

            b) R[2][ = ]{[1,a], [2,c], [3,d], [4,a]},

            c) R[3][ = ]{[2,a], [1,c], [3,b], [4,d]}.

Definice 7: Permutací konečné množiny A nazýváme každé prosté zobrazení množiny A na množinu A
(vzájemně jednoznačné zobrazení).


Příklad 8. Zapište všechny permutace tříprvkové množiny A = {x, y, z}.


Definice 8: Nechť R je zobrazení z množiny M do množiny N a S je zobrazení z množiny N do množiny
K. Pak relace R ○ S je zobrazení a nazývá se složené zobrazení ze zobrazení R a S.


Příklad 9. Složte permutace P[2] ○ P[3],  P[3] ○ P[2], P[4] ○ P[6] z  Příkladu 8.



Ekvivalence množin, konečné a nekonečné množiny


Definice 9: Říkáme, že dvě množiny A, B jsou ekvivalentní právě tehdy, když existuje prosté
zobrazení množiny A na množinu B.  Zapisujeme A ~ B.


Příklad 10. Jsou dány množiny A = {a, b, c}, B = {x, y, z}, C = {x, y}. Rozhodněte, které dvojice
zadaných množin jsou ekvivalentní.


Poznámka. Relace  ~  dvou množin definovaná v libovolném systému množin M má vlastnosti:
reflexivní, symetrická, tranzitivní. Relace ~ je tedy relací ekvivalence. Relace ekvivalence dvou
množin v libovolném systému množin M vytváří rozklad systému M  na třídy ekvivalentních množin.


Příklad 11. Je dán systém množin M  = {A, B, C, D, E, F, G, H}, kde A = {a, b, c}, B = {1, 2}, C =
{x, y}, D = {○, ○, ○, ○}, E = {∆, ∆, ∆}, F = { [*],  [*]}, G = { □ }, H = {☺, ☺, ☺, ☺}. Rozhodněte,
které množiny ze systému M  jsou ekvivalentní.


Definice 10: Řekneme, že množina A je konečná právě tehdy, když žádná vlastní podmnožina množiny A
není ekvivalentní s množinou A.


Definice 11: Řekneme, že množina B je nekonečná právě tehdy, když existuje alespoň jedna vlastní
podmnožina množiny B, která je ekvivalentní s množinou B.


Poznámka. Množina M je vlastní podmnožinou množiny N právě tehdy, když

M  N  M ≠ N.





[ ]