Relace a zobrazení Petr Pupík 11.3.2009 □ S - = -š -O^o SŠIlí^H M Sni ĚTgjšEg *]ř Obsah O Relace O Zobi □ S - = -š -O^o Kartézský součin množin Definice Nechť A, ßjsou množiny. Potom kartézským součinem množin /\, B rozumíme množinu všech uspořádaných dvojic (a, b), kde a e A, b e B. Tedy A x B = {(a, b)\aeA,beB}. Označení Nechť A\e konečná množina, symbolem \A\ budeme označovat počet prvků množiny A. Nechť A, ßjsou konečné množiny. Potom \A x B\ = \A\ • |ß|. □ s - = ^ -o^O Kartézský součin množin Příklad ^ Nechť A = {1,2, 3},ß = = {a,£>},C = 0. Potom • Ax B = {(1 ,a),(1, ö),(2, a), (2,0), (3 a), (3,0)} • Bx A = {(a ,1),(í>, 1),(a, 2), (ö,2), (a 3), (ö,3)} • AxC = 0 □ S1 -Oc\o Definice relace Definice Nechť A, B jsou množiny. Potom relací p mezi množinami A, B rozumíme libovolnou podmnožinu možiny A x B. Je-li A = B, mluvíme o relaci na množině A. Je-li (a, b) g p, říkáme, že prvek a je v relaci p s prvkem b. Můžeme také psát a p b. 22 Příklad relace Příklad Nechf/\ = {1,2,3},ß = {a, g /4 : (a, b) g p => (í), a) g p, • antisymetrická relace, jestliže Va, í) g /\: (a, b) g p, (£>, a) g p => a = £>, • tranzitivní relace, jestliže Va, £>, c g /\: (a, £>) g p, (b, c) g p => (a, c) g p, « úplná relace, jestliže Va, £> g A ■. (a, Ď) g p v (£>, a) g p. Příklady Příklad ^ Nechť A je množina všech studentů, kteří mají zapsaný předmět Matematika 1. Řekneme, že student a je v relaci se studentem b, jestliže • a chodí do stejné seminární skupiny jako b. • a viděl studenta b na přednášce • a má stejnou strukturu DNA jako b • a je zamilovaný do b Příklad Nechť je dána relace p na množině přirozených čísel takto xpy právě tehdy, když je x ■ y liché číslo. Určete vlastnosti této relace. J Příklad ^ Nechť A = {a, b,c,d},B = {x,y,z},C = {k, l,m,n}. Nechť p je relace mezi množinami A,B,p = {(a, y),(c ,y),(c, z)}- Nechť a je relace mezi množinami B, C, a = {(x, k), (x, /), (x, m), (x, n), (y, k), (y, n)}. Potom aop = {(a, k), (a, n), (c, k), (c, n)}. □ S - = -š -O^o Skládání relací E ft Nechť A B, C, D množinami A, B, mezi množinami jsou množiny. Nechť p je relace mezi a je relace mezi množinami B, C, r je C, D. Potom platí r o (u o p) = (r o a) o p. relace □ S1 -ŕ)c\o Inverzní relace Definice Nechť A, ßjsou množiny. Nechť p je relace mezi množinami A B. Potom inverzní relaci p-1 k relaci p definujeme vztahem p"1 = {(x,y)eßx/\|(y,x)ep}. F75E1 Nechť Aß, C jsou množiny. Nechť p je relace mezi množinami A ß, a je relace mezi množinami B, C. Potom platí, že • (p-1)-1=p, • (o-°P)"1 = P~ 10<7"1. _____( Ekvivalence a uspořádání Definice Nechť A\e množina. Nechť p je relace na množině A, která je reflexivní, symetrická a tranzitivní. Potom říkáme, že p je relace ekvivalence. Definice Nechť A\e množina. Nechť p je relace na množině A, která je reflexivní, antisymetrická a tranzitivní. Potom říkáme, že p je relace uspořádání. □ r5" ■f)<\(y Ekvivalence a uspořádání Příklady • Relace rovnosti na množině celých čísel. • Relace dělitelnosti na množině přirozených čísel. • Relace množinové inkluze na systému všech podmnožin libovolné množiny. • Relace kongruence na množině celých čísel. • Relace menší nebo rovno na množině reálných čísel. • Relace zamilovanost na množině všech zapsaných studentů do MB101. □ r5" ■f)<\(y Ekvivalence Definice Nechť X libovolná množina. Potom systém po dvou disjunktních neprázdných podmnožin množiny X, jejichž sjednocením je celá množina X nazýváme rozklad množiny X. Jednotlivé podmnožiny nazýváme třídy rozkladu. Příklad • Sudá a lichá celá čísla tvoří tozklad množiny Z. • Kladná reálná čísla, záporná reálná čísla a {0} tvoří rozklad množiny R. Rozklad příslušný ekvivalenci, ekvivalence příslušná rozkladu Nechť p je ekvivalence na množině X. Uvažme systém podmnožin A-, takový, že x,y e A, o xpy. Potom systém podmnožin A, tvoří rozklad namnožině X. Nechť {A} je rozklad na množině X. Položme xpy právě tehdy, když 3/: x, y e A,. Potom p je relace ekvivalence na množině X. Příklad Zbytkové třídy modulo m. Uspořádání Definice Nechť A je množina, < relace uspořádání na A. Potom dvojci (A, <) nazýváme uspořádaná množina. Definice Nechť (A, <) je uspořádaná množina, B její podmnožina. Řekneme, že prvek a e A je horní závora množiny B, jestliže pro všechny prvky b množiny B platí, že b < a. Nechť (A, <) je uspořádaná množina, B její podmnožina. Řekneme, že prvek a e A je dolní závora množiny B, jestliže pro všechny prvky b množiny B platí, že a < b. Uspořádání Definice Nechť (A, <) je uspořádaná množina, ß její podmnožina. Řekneme, že množina ß je shora ohraničená, jestliže existuje alespoň jedna její horní závora. Podobně řekneme, že ß je zdola ohraničená, jestliže existuje alespoň jedna její dolní závora. Uspořádání Definice Nechť (A, <) je uspořádaná množina, ß její podmnožina. Řekneme, že prvek a e A je supremum množiny B, jestliže a je horní závora množiny ß a je-li h horní závora množiny B, potom a< h. Nechť (A <) je uspořádaná množina, ß její podmnožina. Řekneme, že prvek ae A\e infimum množiny B, jestliže a je dolní závora množiny ß a je-li d horní závora množiny B, potom d < a. Obsah Q Zobrazení □ S - = -š -O^o Definice Speciálním případem relace mezi množinami A,B\e zobrazení z množiny A. Jedná se o takovou relaci, kdy ke každému prvku množiny A existuje právě jeden prvek množiny B, který je s ním v relaci. Místo xpy pak píšeme p(x) = y Definice Definiční obor, Obor hodnot Vlastnosti zobrazení Definice Řekneme, že zobrazení f -. A —> B je injektivní, jestliže ke každému prvku B existuje nejvýše jeden vzor. Řekneme, že zobrazení f ■. A —► B je surjektivní, jestliže ke každému prvku B existuje alespoň jeden vzor. Řekneme, že zobrazení f ■. A —► B je bijektivní, jestliže ke každému prvku B existuje právě jeden vzor. Skládání zobrazení Definice Nechť A, B, C jsou množiny, f: A^ B, g : B -► C. • Jsou-li f,g injektivní, potom je injektivní \gof. 9 Jsou-li f,g surjektivní, potom je surjektivní \gof. • Je-li go f injektivní, potom je i f injektivní. • je-li go f surjektivní, potom je i g surjektivní. □ S1 ■f)<\(y Inverzní zobrazení Definice Je-li f bijektivní zobrazení. Potom definujeme inverzní zobrazení f-1 jako relaci inverzní k relaci f. Poznámka Bijektivita zobrazení f nám zaručuje korektnost definice. □ s - = -e -o<\ N, f{x) = { 2x - 1, W • f : Z- -Q, r(*) = f. • f : Z- -► Z, f{x) = x. • f : Z- ■> Zm, f{x) = [x]m. x<0; x>0; x=0. □ g - = ^ -o^O