Relace zobrazení z množiny do množiny Def. Relace R z množiny M do množiny N se nazývá relace zobrazení z M do N, právě když ("a Î M)("b,b´ Î N) ( ([a,b] ÎR U [a,b´]ÎR) TH b =b´ ), nebo: (("aÎM)("b,b´ÎN) ( ([a,b]ÎR U b ^1 b´) TH [a, b´] I R). Jestliže ve výše uvedené definici je M = N, pak mluvíme o zobrazení v množině M. Z definice zobrazení z množiny M do množiny N plyne, že ke každému aÎM existuje nejvýše jeden prvek bÎN takový, že platí [a,b]ÎR. Prvek aÎM se nazývá vzor, prvek bÎN jeho obraz. Typy zobrazení (rozlišujeme 4 typy) Zobrazení z množiny M do množiny N, které 1. není zobrazením celé množiny M, ani zobrazením na celou množinu N, 2. je zobrazením nikoliv celé množiny M na celou množinu N, 3. je zobrazením celé množiny M do nikoliv celé množiny N, 4. je zobrazením celé množiny M na celou množinu N Def. Zobrazení R z množiny M do množiny N se nazývá prosté, právě tehdy, když relace R^-1 je zobrazení z množiny N do množiny M. (Jinak: Zobrazení R je prosté právě tehdy, mají-li každé dva různé prvky definičního oboru různé obrazy.) 1. Rozhodněte, zda následující relace jsou zobrazení z množiny M do množiny N, M = {a,b,c,d,e}, N = {1,3,5,7,9} a) R[1] = { [a,5], [b,3], [c,9], [d,7], [e,3] } b) R[2] = { [d,7],[e,9],[b,1],[a,5]} c) R[3] = {[b,9],[a,7],[c,5],[b,1],[e,3]} d) R[4] = {[e,1],[d,7],[c,3],[b,9],[a,5],} Určete typy zobrazení a rozhodněte, která jsou prostá. 2. Určete, které z následujících relací v množině M = {0,1,2, ...,6} jsou zobrazení. V případě zobrazení zapište definiční obor a obor hodnot. Zobrazení znázorněte graficky. a) R[1] = {[2,3], [3,4], [1,3], [4,5], [0,3]} b) R[2] = {[3,2], [2,3], [1,5], [3,4], [1,2]}. 3. Je dána množina A = {xÎZ: x 1/236 } kde Z = {1, 2, 3, ...,20}. Doplňte uspořádané dvojice [2, ], [ ,9], [4, ], [ ,2], [12, ] tak, aby vzniklo a) zobrazení v množině A, které je prosté, b) zobrazení v množině A, které není prosté. 4. Relace R v množině M = {0,1,2, ...,8} obsahuje všechny uspořádané dvojice [a,b], kde b je zbytek při dělení čísla a třemi. Určete relaci R výčtem prvků, graficky ji znázorněte a určete zda R je zobrazení v množině M. Pokud ano, určete přesně jeho typ a rozhodněte zda je prosté. 5. Jsou dány množiny M = {1,2,3,4} a N = {a,b,c,d}. a) Definujte výčtem prvků relaci R z množiny M do množiny N, která není zobrazením. Dále definujte relaci Z, která je zobrazením z množiny N do množiny M. Zapište výčtem prvků relaci R [o] Z a rozhodněte zda je tato relace zobrazením. Pokud ano určete jeho typ. b) Definujte výčtem prvků vždy alespoň dvě zobrazení R[1], R[2] (pokud existují), pro která platí: - Jde o zobrazení z množiny M do množiny N, které není zobrazením celé množiny M, ani na celou množinu N. - Jde o zobrazení (celé) množiny M do množiny N, které není zobrazením na celou množinu N. - Jde o zobrazení z množiny M na (celou) množinu N, které není zobrazením celé množiny M. - Jde o zobrazení množiny M na množinu N. Sestrojte uzlový graf každého z těchto zobrazení a rozhodněte zda je či není prosté. 6. Jsou dány množiny A = {1,2,3,a,b}, B = {a,b,c,d}. Definujte (pokud to lze) všechny typy zobrazeni z množiny A do množiny B. V každém případě rozhodněte, zda se jedná o zobrazení prosté. 7. Jsou dány množiny A = {a,b,c}, B = {1, -1}. Určete výčtem prvků všechna zobrazení, která jsou zobrazením celé množiny A do nikoliv celé množiny B. 8. Je dána množina M = {1,2,3}. V množině M jsou dány binární relace R, S takto: R = {[x,y] ÎM´M: x ^1 3 U y = 1 }, S = { [1,2], [2,3],[3,1]}. Jsou relace R, S zobrazení v množině M ? Pokud ano, určete přesně jejich typ a rozhodněte zda jsou prostá. Dále určete RoS, SoR a rozhodněte, zda jsou tyto složené relace zobrazení v množině M. 9. Je dána množina A = { -3, -2, -1, 0, 1, 2, 3 }. V množině A jsou definovány dvě binární relace R, S takto: R = { [x,y] Î A^2 : y = |x| }, S = { [x,y] Î A^2: y = - x}. Relace R a S určete výčtem prvků a rozhodněte, zda se jedná o zobrazení v množině A. Pokud ano, rozhodněte zda jsou prostá a určete přesně jejich typ. Jsou zobrazením v množině A relace R[o]S, R^-1, S^-1 ? 10. Je dána množina M = {1,2,3}. V této množině jsou definovány binární relace R = {[x,y] Î M^2 : x ^1y TH x = y }, S = { [1,3], [2,1], [3,2]}. Rozhodněte a zdůvodněte, zda jsou tyto relace permutace množiny M. Je některá z relací R, S uspořádáním v množině M ? Na množině M definujte další permutaci T a ověřte, že platí vztah: Ro (So T ) = (R oS) o T . 11. Jsou dány relace R = { [x,y] Î R^2 : y = x } S = { [x,y] Î R^2 : y = |x| } T = { [x,y] Î R^2 : x^2 + y^2 = 4 }. Rozhodněte, která z těchto relací je zobrazení v množině R všech reálných čísel. Sestrojte kartézský graf každé zadané relace. 12. Definujte alespoň jedno zobrazení z množiny A do množiny B, je-li: A - množina všech osob přítomných v určité místnosti B - množina všech jihomoravských měst A - množina všech mužů B - množina všech žen A - množina všech občanů ČR B - množina všech rodných čísel (v ČR). Ekvivalence množin Def.: Ří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. 1. Jsou dány množiny A= {0, 1, 2, ...,6}, B = {k, l, m, n, o}, C = {m, n, l, k, o} a D = {2, 3, 4, ...,8}. Rozhodněte, zda platí: A~B, B~C, B~D, D~A, B = C. 2. Určete, zda jsou množiny A, B ekvivalentní. Své rozhodnutí zdůvodněte. A = { x Î N: x > 0 }, B = {x Î C: 2 1/2x U x > 0 }. 3. Zdůvodněte, že pro libovolné množiny A, B platí: A~ A, A~B TH B~A, (A~B U B~C) TH A~C. 4. Ukažte, že množina N všech přirozených čísel je ekvivalentní a) s množinou A trojnásobků všech přirozených čísel b) s množinou B všech přirozených čísel větších než 10 c) s množinou S všech přirozených čísel sudých d) s množinou L všech přirozených čísel lichých. Def.: Množina A je konečná právě tehdy, když není ekvivalentní s žádnou svou vlastní podmnožinou. Množina, která není konečná se nazývá nekonečná. Tzn., že množina B je nekonečná právě tehdy, když existuje alespoň jedna vlastní podmnožina množiny B, která je s množinou B ekvivalentní. 5. Zdůvodněte (užitím definice), že množina M = {a, b, c, d} je konečná a množiny A, B, S, L z příkladu 4 jsou množiny nekonečné. Podobnost lineárně uspořádaných množin Def. Množiny (M, R[1]), (N, R[2]) jsou dvě lineárně uspořádané množiny. Zobrazení Z (celé) množiny M na (celou) množinu N, které má vlastnost ("x,y ÎM) [ x p [ ]y TH Z(x) p Z(y) ], R[1] R[2 ]se nazývá podobné zobrazení lineárně uspořádané množiny (M, R[1]) na lineárně uspořádanou množinu (N, R[2]). Existuje-li podobné zobrazení lu množiny (M,R[1]) na lu množinu (N, R[2]) pak říkáme, že lu množiny (M, R[1]) , (N, R[2]) jsou podobné a zapisujeme (M, R[1]) » (N, R[2]). 6. Jsou lineárně uspořádané množinyëAu, ëBu podobné ? Odpověď zdůvodněte. a) ëAu = ë{5,6,7,8,9 }u , ëBu = ë{t,s,r,q, p}u b] ëAu = ë{a,b,c,d}u , ëB u = ë{a, b, g}u c] (A, < ), (B, > ), kde A = {7,3,1,4}, B = {15, 2, 5, 8}. [ ]7. Je dána množina K = {xÎC: x 1/25 } a relace R[1] definovaná v této množině vztahem y < x, tj. R[1] = {[x,y]Î K´K: y < x}. 1. Určete množinu K výčtem prvků a dokažte, že R[1] je lineární uspořádání množiny K. Dále je dána množina L = {aÎN: a 1/28} a v ní relace R[2] = {[a,b]ÎN: a < b}. 2. Dokažte, že R[2] je lineární uspořádání mn. L. 3. Definujte podobné zobrazení lu množiny (K, R[1]) na lu množinu (L, R[2]) a dokažte, že (K,R[1]) » (L,R[2]) . 8. Rozhodněte o pravdivosti následujících výroků: a) Jsou-li dvě množiny podobné, pak jsou obě lineárně uspořádané. b) Mají-li dvě lu množiny první prvek, pak jsou podobné. c) Dvě podobné konečné množiny mají stejný počet prvků. d) Platí-li (A, R[1]) » (B, R[2]), pak A ~ B.