Určete, zda následující relace je reflexivní, symetrická, tranzitivní a souvislá: a) rovnoběžnost přímek v rovině b) kolmost přímek v rovině c) mimoběžnost přímek v prostoru Zobrazení z množiny do množiny, typy zobrazení 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. 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. Platí O[2](R) Ì B. 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. Zobrazení Z z množiny A do množiny B se nazývá prosté zobrazení právě tehdy, když relace Z^−1 je zobrazení z množiny B do množiny A. Uzlový graf prostého zobrazení Z z množiny A do množiny B je charakteristický tím, že do každého bodu, který znázorňuje prvek y Î B, směřuje nejvýše jedna šipka. Můžeme tedy říci, že platí následující věta: Zobrazení Z z množiny A do množiny B je prosté právě tehdy, když pro každé y Î B platí, že je obrazem nejvýše jednoho prvku x Î A v zobrazení Z. V praxi používáme pro rozlišení prostého zobrazení následující tvrzení: Zobrazení Z z množiny A do množiny B je prosté právě tehdy, když každé dva různé vzory mají různé obrazy. Př. 1: Jsou dány množiny A = {a, b, c} a B = {u, v}. Nechť R[1], R[2], R[3], R[4] jsou binární relace z množiny A do množiny B definované takto: a) R[1] = {[a, v], [b, v], [c, u]}, b) R[2] = {[a, u], [b, v]}, c) R[3] = {[a, v], [b, v], [c, v]}, d) R[4] = {[a, u], [b, u]}. Rozhodněte, zda tyto relace jsou zobrazení z množiny A do množiny B. Pokud ano, určete typ zobrazení. a) R[1] je zobrazení množiny A na množinu B, není prosté. b) R[2] je prosté zobrazení z množiny A na množinu B. c) R[3] je zobrazení množiny A do množiny B, není prosté. d) R[4] je zobrazení z množiny A do množiny B, není prosté. Př. 2: 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. 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]}. R[1][ ]není zobrazení. R[2][ ]je prosté zobrazení z množiny A na množinu B. R[3][ ]je zobrazení celé množiny A na množinu B, není prosté (nemůže být). Př. 3: 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á. R = {[x, z], [c, c], [y, c]}, 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] z množiny A do množiny B, 2) jedno zobrazení R[2 ]množiny A do množiny B, 3) jedno zobrazení R[3 ]množiny A na množinu B, 4) jedno zobrazení R[4 ]z množiny A na množinu B. Řešení: a) R je zobrazení z množiny A do množiny B, není prosté. S je zobrazení množiny A do množiny B, není prosté. b) T = {[x, z], [x, b], [a, z], [c, x]}. c) R[1] = {[x, z]}, je prosté. R[2] = {[x, z], [y, z], [a, z], [c, z]}, není prosté. R[3] = {[x, c], [y, b], [a, z], [c, x]}, je prosté. R[4] neexistuje. Prosté zobrazení množiny A na množinu B nazýváme bijektivní zobrazení nebo také vzájemně jednoznačné zobrazení. Př. 4: 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]}. Vzájemně jednoznačné zobrazení. a) Prosté zobrazení z množiny A do množiny B. b) Zobrazení množiny A do množiny B, není prosté. c) Prosté zobrazení množiny A na množinu B. 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ř. 5: Zapište všechny permutace tříprvkové množiny A = {1, 2, 3}. a = , b = , c = , d = , e = , f = . Definice: 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ř. 6: Jsou dána zobrazení R, S v množině A = {1, 2, 3, 4} takto: R = {[1, 3], [4, 2], [2, 3], [3, 1]}, S = {[1, 1], [4, 2], [2, 1], [3, 4]}. Určete složené relace R ○ S, S ○ R. Řešení: R ○ S = {[1, 4], [4, 1], [2, 4], [3, 1]}, S ○ R = {[1, 3], [4, 3], [2, 3], [3, 2]}. Vidíme, že R ○ S ¹ S ○ R. Složení dvou zobrazení je vždy zobrazení, složení dvou permutací je permutace. Př. 7: Složte permutace b ○ c, f ○ d, e ○ b z předchozího příkladu. b ○ c = = d , f ○ d = = b, e ○ b = = c. Povšimněte si, že platí e ○ d = d ○ e = , což je identická permutace. Obě permutace d, e jsou navzájem inverzní. Řekneme, že množiny A, B jsou ekvivalentní právě tehdy, když existuje prosté zobrazení množiny A na množinu B. Značíme A ~ B. Př. 8: Jsou dány množiny A = {a, b, c}, B = {x, y}, C = {1, 2, 3}. Rozhodněte, které množiny jsou ekvivalentní. Ř: Množiny A, B nejsou ekvivalentní (neexistuje prosté zobrazení množiny A na množinu B). Množiny A, C jsou ekvivalentní (existuje prosté zobrazení množiny A na množinu C, například R = {[a,3],[b,1],[c,2]}), tj. A ~ C. Množina M je vlastní podmnožinou množiny N právě tehdy, když M je podmnožinou N a současně M ≠ N. Ř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. Ř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. Př. 9: Uvažujme množinu ℕ všech přirozených čísel a množinu S všech kladných sudých čísel. Zjistěte, zda jsou ekvivalentní. Řešení: Připomeneme, že ℕ = {1, 2, 3, 4, 5,…}, S = {2, 4, 6, 8 , 10,…}. Uvažujme relaci R = {[x,y] ϵ ℕ ´ S; y = 2x}. Relace R je prosté zobrazení množiny ℕ na množinu S, neboť ke každému x ϵ ℕ existuje právě jedno y ϵ S takové, že [x,y] ϵ R, ke každému y ϵ S existuje právě jedno x ϵ ℕ takové, že [x,y] ϵ R. Tedy ℕ ~ S. Množina ℕ všech přirozených čísel je nekonečná, neboť je ekvivalentní s množinou S všech kladných sudých čísel, přičemž S je vlastní podmnožinou množiny ℕ. Nechť A, B jsou konečné množiny. Pak platí: A ~ B Û |A | = |B | , tedy dvě konečné množiny jsou ekvivalentní, právě když mají stejný počet prvků. Př. 10: Jsou dány množiny M = a N = . a) Definujte výčtem prvků relaci R z množiny M do N, která není zobrazením. b) Definujte relaci Z, která je zobrazením z množiny N do M a určete jeho typ. c) Zapište výčtem prvků relaci R•Z a rozhodněte, zda je tato relace zobrazením. Pokud ano, určete, zda je prosté. d) Zapište dvě různé bijekce množiny N na množinu M. e) Na množině N definujte dvě různé permutace P[1], P[2] a určete permutace P[1]•P[2] a P[2]•P[1]. Řešení: a) R = {[2, b], [2, c], [3, a]}. b) Z[1] = {[c, 4]}. Prosté zobrazení z N do M. Z[2] = {[a, 4], [b, 4], [c, 1], [d, 1]}. Zobrazení celé N do M, není prosté. c) R•Z[1 ]= {[2, 4]}. Prosté zobrazení z M do M. R•Z[2] = {[2, 4], [2, 1], [3, 4]}. Není zobrazení. d) B[1 ]={[a, 4], [b, 3], [c, 2], [d, 1]}, B[2 ]={[a, 2], [b, 4], [c, 3], [d, 1]}. Platí A ~ B. e) P[1 ]= {[a, b], [b, c], [c, d], [d, a]}, P[2 ]= {[a, c], [b, d], [c, b], [d, a]}. Jinak zapsáno P[1 ]= , P[2 ]= . P[1 ]• P[2] = , P[2 ]• P[1 ]= . Př. 11: Je dána množina M = . V množině M jsou dány relace R, T, U, V takto: R = , T = , U = , V = . a) Rozhodněte a zdůvodněte, zda jsou některé z relací R, T, U, V zobrazení v množině M. Pokud ano, určete přesně jejich typ. Je některá z těchto relací permutací na množině M? b) Zapište relace R^-1, V^-1, V•V, U•V, R•U, R•(V•U). Je některá z těchto relací zobrazením v množině M? Pokud ano, určete přesně typ. Řešení: a) R = {[2, 3], [3, 2], [1, 1], [2, 2], [3, 3]}. Není zobrazení. T = {[1, 1], [1, 2], [1, 3], [3, 1], [3, 2], [3, 3], [2, 3]}. Není zobrazení. U = {[1, 2], [2, 3]}. Prosté zobrazení z M do M. V = {[1, 3], [2, 1], [3, 2]}. Permutace množiny M. b) R^-1 = {[3, 2], [2, 3], [1, 1], [2, 2], [3, 3]}. Není zobrazení. V^-1 = {[3, 1], [1, 2], [2, 3]}. Permutace množiny M. V•V = {[1, 2], [2, 3], [3, 1]}. Permutace množiny M. U•V = {[1, 1], [2, 2]}. Prosté zobrazení z M do M. R•U = {[3, 3], [1, 2], [2, 3]}. Zobrazení celé M do M, není prosté. V•U = {[2, 2], [3, 3]}. Prosté zobrazení z M do M. R•(V•U) = {[2, 3], [3, 2], [2, 2], [3, 3]}. Není zobrazení. Binární operace v množině Nechť M je libovolná neprázdná množina. Binární operací ○ v množině M rozumíme zobrazení z množiny kartézského součinu M x M do množiny M. · Jestliže v binární operaci je vzoru [x,y] M x M přiřazen obraz z M, píšeme: 1. x ○ y = z; prvek z M se nazývá výsledek operace ○. 2. ○: M x M → M. Zápisu [[x,y], z] ○, odpovídá zápis x ○ y = z (tj. z je výsledek operace ○). Zápisu [[1,2], 3] + odpovídá 1 + 2 = 3 (tj. 3 je výsledek operace sčítání čísel 1 a 2). Zápisu [[2,3], 6] ·, odpovídá 2 · 3 = 6 (tj. 6 je výsledek operace násobení čísel 2 a 3). Označení binárních operací: +, ·, ○, ⁎, □,.. Příklady binárních operací ve školské matematice: 1) Sčítání (+), odčítání (-), násobení (·), dělení (:), umocňování,… (pracujeme s nimi v číselných množinách). 2) Sjednocení (), průnik (), rozdíl ( - ), symetrický rozdíl ( ) množin,… (pracujeme s nimi v systémech množin). Určení binární operace: Tabulkou nebo předpisem. Vlastnosti binárních operací: Definice : Binární operace ○ v množině M, která má vlastnost, že je definována pro každou uspořádanou dvojici [x,y] M x M, se nazývá operace neomezeně definovaná v množině M (zkráceně operace definovaná na množině M). Značíme ND. Symbolicky: x, y M)( z M)[ x ○ y = z]. Definice: Binární operace ○ definovaná na množině M (je ND), se nazývá komutativní právě tehdy, když platí: x, y M)[ x ○ y = y ○ x]. Značíme K. Definice: Binární operace ○ definovaná na množině M, se nazývá asociativní právě tehdy, když platí: x, y, z M)[ (x ○ y) ○ z = x ○ (y ○ z)]. Značíme A. Definice: Nechť v množině M je definována binární operace ○. Existuje-li prvek e M, pro který platí: x M)[ x ○ e = e ○ x = x]. Pak se prvek e M nazývá neutrálním prvkem množiny M vzhledem k operaci ○. Značíme EN. Poznámka. Je-li operace ○ komutativní, pak v zápisu vlastnosti EN lze vynechat jedna ze dvou stran rovnosti x ○ e nebo e ○ x. Definice : Nechť v množině M je definována binární operace ○ a nechť e je neutrální prvek množiny M vzhledem k operaci ○. Prvek ā M nazýváme inverzním prvkem k prvku a M v operaci ○ v množině M právě tehdy, když platí: ā ○ a = a ○ ā = e. Jestliže (a M)( ā M)[ ā ○ a = a ○ ā = e], řekneme, že ke každému prvku množiny M existuje prvek inverzní vzhledem k operaci ○. Značíme EI. Poznámka . Je-li operace ○ komutativní, pak v zápisu vlastnosti EI lze vynechat jedna ze dvou stran rovnosti ā ○ a = a ○ ā. Definice : Říkáme, že binární operace ○ definovaná na množině M má vlastnost řešitelnost základních rovnic právě tehdy, když platí: a, b M) )( x, y M)[ a ○ x = b y ○ a = b]. Značíme ZR. Poznámka. Je-li operace ○ komutativní, pak v zápisu vlastnosti ZR lze vynechat jedna z výrokových forem a ○ x = b nebo y ○ a = b. Definice: Nechť v množině M je definována binární operace ○. Existuje-li prvek g M, pro který platí: x M)[ x ○ g = g ○ x = g]. Pak se prvek g nazývá agresivním prvkem množiny M vzhledem k operaci ○. Určování vlastností operací I. Určených předpisem – přímým výpočtem II. Určených tabulkou: ND – tabulka zcela vyplněna prvky množiny M K – tabulka souměrná podle hlavní diagonály A – kromě výjimek nelze z tabulky přímo poznat – viz dále EN – existuje řádek a sloupec shodný se záhlavím tabulky EI – v každém řádku a každém sloupci tabulky je neutrální prvek ZR – v každém řádku i sloupci tabulky jsou všechny prvky množiny M Agresivní prvek g M poznáme tak, že v celém jemu příslušejícím řádku i sloupci se vyskytuje pouze prvek g. Užitečné vztahy: K Þ ND, A Þ ND, EI Þ EN (užívají se v obměněném tvaru) A Þ (EI Û ZR) Určování asociativnosti z tabulek: 1. Pohledem (velmi zřídka) 2. Ověřením všech možných trojic prvků (s využitím cvičení 9 – 13, s. 123 – 124) (těžkopádné a zdlouhavé) 3. Využitím obměny implikace A Þ ND a implikace A Þ (EI Û ZR) 4. Podle tvrzení: „ Operace, která splňuje EN Ù EI Ù ZR a současně není asociativní, existuje na množině o nejméně pěti prvcích“. Užití na příkladech: o a b c a b c a a a a a a a a a ad 1. Např. ad 3. Nejčastější případ – rozbor implikace A Þ (EI Û ZR). Je-li u EI a ZR rozdílná pravdivostní hodnota, pak operace není asociativní. Jsou-li u EI a ZR pravdivostní hodnoty 1, pak postupujeme podle bodu 4 (v písemných pracích jsou zadávány tabulky o maximálně čtyřech prvcích). Jsou-li u EI a ZR pravdivostní hodnoty 0, pak je nutno postupovat podle bodu 1 nebo 2. Zpravidla jde o bod 1, kdy určíme asociativnost přímo z tabulky. Př. 12: Rozhodněte a zdůvodněte, které z vlastností ND, A, K, EN, EI, ZR má v množině M = operace určená tabulkou: ⁕ a b c ○ a b c □ a b c a b c a a b a b a c a c a a a a b c b a b c b c b a b c b b b a c c b c b c a c b c a b c c c b a ⁕: [DEL: ND :DEL] [DEL: K :DEL] [DEL: A :DEL] EN EI Ù [DEL: ZR :DEL] ○: ND [DEL: K :DEL] [DEL: A :DEL] [DEL: EN :DEL] [DEL: EI :DEL] Ù ZR □: [DEL: ND :DEL] [DEL: K :DEL] [DEL: A :DEL] EN EI [DEL: ZR :DEL] ■: ND [DEL: K :DEL] [DEL: A :DEL] EN EI [DEL: ZR :DEL] Př. 13: V množině M = definujte tabulkou aspoň jednu binární operaci, která má vlastnosti: a) K [DEL: EN :DEL] b) ND [DEL: K :DEL] EN c) ND EN [DEL: EI :DEL] d) A [DEL: ZR :DEL] e) [DEL: K :DEL] EN [DEL: EI :DEL] f) EI ZR g) ND [DEL: A :DEL] EI [DEL: ZR :DEL] a) a b c b) a b c c) a b c d) a b c a c c b a b a a a b a a a a a a b a b c b c b b b a c b b a a a c b c b c a b c c a b c c a a a e) a b c f) a b c g) a b c a a b a a b c a c a a b a b c b b c a b a c b c c c a c c a b c a b c