Kartézský součin množin, binární relace, zobrazení - opakování


Kartézský součin množin A, B je množina, ozn. A x B, která se skládá ze všech uspořádaných dvojic,
jejichž první složkou je prvek množiny A a druhou složkou prvek množiny B.


Binární relace z množiny A do množiny B je kterákoliv množina R, která je podmnožinou kartézského
součinu A x B.


(Pokud A = B, pak mluvíme o binární relaci v množině A – a jde o libovolnou podmnožinu kartézského
součinu A x A.

Doplňková relace R´ k relaci R v množině A je množina všech uspořádaných dvojic z AxA, které
nepatří do relace R, tj. R´= (AxA) – R.

Inverzní relace R^-1 k relaci R v množině A   je relace R^-1 = {[x,y] AxA; [y,x]  R} )


První obor relace O[1](R) je množina všech prvních složek uspořádaných dvojic z relace R.

Druhý obor relace O[2](R) je množina všech prvních složek uspořádaných dvojic z relace R.


Relace R z množiny A do množiny B se nazývá zobrazením z A do B, právě když ke každému prvek a  A
existuje nejvýše jeden prvek b  B takový, že platí [a,b] R.

(Tedy každý prvek z množiny A se může vyskytnout jako první složka  uspořádané dvojice v relaci R
nejvýše jednou.)

Jestliže [a,b] R, pak prvek a nazýváme vzorem prvku b a prvek b obrazem prvku a  v zobrazení R
(nebo že zobrazení R přiřazuje prvku a prvek b).


Příklad:

Jsou dány množiny A, B:  A = {a, b, c, d},  B = {1, 2, 3}. Rozhodněte, které z binárních relací R[1
]- R[5 ] jsou zobrazení z A do B.

R[1] = {[a,1], [b,2], [d,3]}            - je zobrazení

R[2] = {[a,2], [c,1], [a,3], [b,3]}  - není zobrazení - prvek a je 1. složkou ve dvou dvojicích

R[3] = {[a,1], [b,2],[c, 3] [d,1]}   - je zobrazení

R[4] = {[b,3]}                               - je zobrazení

R[5] = {[a,2], [c,1], [d,2], [b,3]}  - je zobrazení



Typy zobrazení:

Podle toho, jaký je vztah mezi prvním oborem relace R a množinou A a druhým oborem relace R a
množinou B, rozlišujeme:

  zobrazení celé množiny A na necelou množinu B, je-li   O[1](R) = A a   O[2](R) B,

   (tzn. každý prvek z A je vzorem a v B existuje aspoň jeden prvek, který není obrazem žádného
prvku z A),

  zobrazení  necelé množiny A na celou množinu B, je-li   O[1](R)  A a   O[2](R) = B,

    (tzn.v A existuje prvek, který není vzorem žádného prvku z B a  každý prvek z B je aspoň jednou
obrazem

     nějakého prvku z A)

 zobrazení  necelé množiny A na necelou množinu B, je-li   O[1](R)  A a   O[2](R) B,

    (tzn. v A existuje prvek, který není vzorem žádného prvku z B a v B existuje aspoň jeden prvek,
který není

     obrazem žádného prvku z A )

  zobrazení celé množiny A na celou množinu B, je-li  O[1](R) = A a O[2](R) = B.

     (tzn. každý prvek z A je vzorem a každý prvek z B je aspoň jednou obrazem  nějakého prvku z A)


Každé z uvedených typů zobrazení může být navíc prosté zobrazení:


Zobrazení R z  A do  B se nazývá prosté, právě když každé dva různé vzory mají různé obrazy. (Jinak
řečeno: Zobrazení je prosté, právě když relace inverzní R^-1 je zobrazením z B do A.)


Prosté zobrazení celé množiny na celou množinu se nazývá vzájemně jednoznačné zobrazení.


Říkáme, že dvě množiny A, B jsou ekvivalentní (A ~ B), právě když existuje aspoň jedno prosté
zobrazení (=vzájemně jednoznačné zobrazení) jedné z těchto množin na druhou.




Cvičení:

1. Rozhodněte přesně o typu jednotlivých zobrazení ve výše uvedeném příkladu včetně toho, zda jsou
prostá .


2. Zapište několik zobrazení z množiny M do množiny N tak, abyste na nich mohli ilustrovat
jednotlivé typy zobrazení.  M = {1, 2, 3, 4, 5},  N = {x, y, z, u, v}.


3. Uvažujte množinu všech cestujících v jisté tramvaji, množinu všech sedadel v této tramvaji a
binární relaci určenou vztahem „Osoba X sedí na sedadle Y“. Přemýšlejte o různých situacích v této
tramvaji (např. Každý cestující sedí na jednom sedadle a ještě jsou dvě místa volná.) a rozhodněte,
zda se jedná o zobrazení z množiny cestujících do množiny sedadel. Pokud ano, určete přesně typ
tohoto zobrazení.


4. Rozhodněte a zdůvodněte, zda jsou některé z množin ve výše uvedeném textu ekvivalentní?


5. Zdůvodněte, že množina N všech přirozených čísel N = {1, 2, 3, 4, .... } je ekvivalentní
s množinou S všech sudých čísel S = {2, 4, 6, ... } a množinou všech desetinásobků přirozených
čísel  D = {10, 20, 30, ... }.

(návod: Je potřeba najít prosté zobrazení množiny N na množinu S a  na množinu D.



Připoměňte si: Množina je nekonečná, právě když je ekvivalentní se svou vlastní podmnožinou.


Ve cvičení 5 jste tedy zdůvodnili nekonečnost množiny všech přirozených čísel.  Množina N je
ekvivalentní se svou vlastní podmnožinou (N ~ S,  S Ì N,  S ≠ N).