Lineární modely - 3. přednáška Základní pojmy z teorie množin Ondřej Klíma 7. 3. 2013 3. přednáška Pojmy z teorie množin Osnova přednášky a Množiny: kartézský součin množin, podmnožiny • Zobrazení: injektivní, surjektivní, bijektivní • Relace: uspořádání, relace ekvivalence • Matice 3. přednáška Pojmy z teorie množin Množiny • Intuitivní definice: množina je soubor prvků. Pouze nahrazujeme jedno slovo druhým. Formálně se teorie množin buduje jinak. • My si potřebujeme rozumnět, když řekneme, že: a je prvek množiny X ... a e X. • Kdy jsou dvě množiny stejné? Když mají stejné prvky. 3. přednáška Pojmy z teorie množin Kartézský součin množin • Kartézský součin množin A x B: prvky uspořádané dvojice. Dvě uspořádané dvojice se rovnají, když mají stejné obě složky. • Formální zápis: AxB = {(x,y) |xeAye8} • Příklady: lxl,{1,...,6}x{1,...,6}. o Obecněji A-\ x A2 x • • • x An, prvky a = (a-i, a2,..., an). Příklad: Rn (n = 3). |Ai x A2x ■■■ x An\ = |A|| • |/A2|.....|A?|. 3. přednáška Pojmy z teorie množin Podmnožiny Systém všech podmnožin: pro X klademe V(X) = {A | A c X}. Pro počet prvků platí: je-li |X| = n pak \V(X)\ = 2n. Víme, že k prvkových podmnožin /i-prvkové množiny je (nk). Tedy dle Binomické věty. Jde i přímo. Když „vyrábíme" podmnožinu, procházíme množinu X a pro každý prvek zvlášť se rozhodujeme, zda jej do budované podmnožiny dáme nebo ne. Pro každý prvek z množiny X tedy máme dvě možnosti. Proto celkem 2n. Pozn.: Předvedli jsme kombinatorický důkaz rovnosti J2k=o O — 2"- Zobrazení • Zobrazení f z množiny A do množiny B, f : A fí, je předpis, který pro každý prvek A jednoznačně určuje jeden prvek b = f(a) z množiny B. • Definujeme lm(f) = {f(ä) \ a e A}c B, tzv. obor hodnot. • Někdy se zobrazení chápe obecněji: pro každé ae A určuje f nejvýše jeden prvek b = f (a) z množiny B. (Potom se také definuje Dom(f) = {a g A \ 3 f {ä)}.) • Příklady: • transformace roviny - shodnosti (rotace, translace), podobnosti, promítání (projekce) o konjugování (sdruženost): a : C ->• C, a(z) = z • operace na množině: + :ZxZ^Z • vol : A -)■ R, zde A c -p(M2) • pravděpodobnost P : ^4 ->• M, lm(P) =< 0,1 >. • Formálně: f je podmnožina A x B - graf zobrazení. 3. přednáška Pojmy z teorie množin Skládání zobrazení • Máme-li zobrazení f: A ->• B a g : fí ->• C, pak jejich složení g o f je definováno takto: pro a g/A klademe (goř)(a) = g(/(a)). Tedy gof\e zobrazení zAdoC. Skutečně je, pro libovolné ae A jednoznačně určeno (flfoř)(a)GC. Pozn.: Anglická literatura často používá zápis skládání zleva doprava. a Příklad: f, g : M ->• M, f(x) = x2 + 2, g(x) = x3 + 3. Pak (f o gf)(x) = f(g(x)) = f(x3 + 3) = = (x3 + 3)2 + 2 = x6 + 6x3 + 11. (9 ° OM = = 9(*2 + 2) = (x2 + 2)3 + 3 = x6 + 6x4 + 12x2 + 11. Tedy f og ^ gof. 3. přednáška Pojmy z teorie množin Injektivní, surjektvní a bijektivní zobrazení Říkáme, že zobrazení f z množiny A do množiny B je • surjektivní, jestliže lm(f) = B, 9 injektivní, jestliže pro každé b g lm(f) existuje právě jeden vzor a g A tak že f(a) = b, (Alternativně: pro libovolná a, á g A z f(a) = ŕ(a') plyne a = a7.) • bijektivní, jestliže je surjektivní a injektivní zároveň. Příklad Buď n > 0 přirozené číslo a X = {1,..., n}. Uvažme a : V{X) {0,1 }n, dané takto: f(B) = {a^..., a„), kde pro každé 1 < i < n platí a, = 1 , kde a g d, £> g B. Toto zobrazením se nazývá inverzní zobrazení a značí se f 1. Existence inverzního zobrazení je ekvivalentní s bijektivitou f: pokud k zobrazení f -. A fí existuje zobrazení g : fí /A, takové, že g o f = \d,A a f o g = ide, pak f i g jsou bijekce. Příklad Pro zobrzení a : C C, a(a + /?./) = a - /?./, máme a o a = ide- Příklad Shodná zobrazení v rovině. 3. přednáška Pojmy z teorie množin Relace • Intuitivně lze relaci chápat jako „vícehodnotové zobrazení". Formálně: naopak - zobrazení je speciální případ relace. • Binární relací mezi množinami AaB rozumíme podmnožinu R kartézského součinu A x B. Často píšeme a ~r b pro vyjádření skutečnosti, že (a, b) g R, tj. že prvky a e A a b e B jsou v relaci R. • Definičním oborem relace je množina Dom(R) c A, Dom(R)= {a e 4 | 3/? e B, (a, fc) e fl} . Podobně oborem hodnot relace je množina lm{R) c e, = {/? g e | 3a g A, (a, fc) e fl} . • Obecně: /i-ární relace, tj. podmnožiny x • • • x A 3. přednáška Pojmy z teorie množin Relace - příklady • Databáze: kódy předmětů, A2 vyučující, A3 semestr,... Nás zajímají nejvíce binární relace, a to jednak zobrazení, a dále relace na množině, tj. situace, kdy A = B. • \dA = {(a, a) g A x A \ a g A}, « R< = {(a, b) g N x N | a < b}, relace „menší" • R\ = {{a,b) g N x N | (3c e N) {b = a- c)}, relace „dělí". 9 c na množině • R = {(A, B) | \A\ = \B\} na V(X), „stejná mohutnost" • grafy ... 3. přednáška Pojmy z teorie množin Skládání relací, inverzní relace • Skládání relací se definuje podobně jako u zobrazení, jen je třeba uvažovat „víc hodnot". • Pro relace RcAxBaScBxC. Definujeme SoRcAx C takto: S o R= {(a, c) | {3b g B) ((a, b) g R, {b, c) g S )}. • Pro každou relaci R Q Ax B definujeme inverzní relaci Rr1 = {{b, a) | {a, b) e R} c B x A. • Pozor, pro každé zobrazení máme takto definovánu jeho inverzní relaci, ta však nemusí být zobrazením! • Pro zobrazení f: A B platí: f \e bijekce právě tehdy, když inverzní relace je zobrazení. V tom případě je inverzní relace inverzním zobrazením. • Obecně R o R11 není identita. Např: oM< = N x N. 3. přednáška Pojmy z teorie množin Základní vlastnosti relací Definice O relaci R na množině A řekneme, že je: a reflexivní, pokud id^ c R, tj. pokud pro všechny A platí (a, a) g R, a symetrická, pokud R 1 = R, tj. pokud pro všechny a,beA platí (a, jb) g R => {b, a) g R, a antisymetrická, pokud 1 n R c id^, tj. pokud pro všechny a, /? g /A platí ((a, £>) g (£>, a) g /?) =>- a = b, a tranzitivní, pokud R o R c R,\\. pokud pro všechny a, b,c & A platí ((a, £>) g fl, (b, c) e R) =>- (a, c) g R. Relace se nazývá ekvivalence, pokud je současně reflexivní, symetrická i tranzitivní. Relace se nazývá uspořádání jestliže je reflexivní, tranzitivní a antisymetrická. 3. přednáška Pojmy z teorie množin Relace ekvivalence a uspořádání - příklady • icU relace ekvivalence i uspořádání. • R< není uspořádání (není reflexivní). • R< = {(a, b) g N x N | a < b} je uspořádání. • R\ je uspořádání. • c na množině V(X) je uspořádání. 9 R = {(A, B) | \A\ = \B\} na V(X) je relace ekvivalence. Příklad Buď n > 1 přirozené číslo. Definujeme relaci ~n na množině Z takto: pro libovolná a,beZ máme a ~n b . Potom ~n je relace ekvivalence. 3. přednáška Pojmy z teorie množin Rozklad podle relace ekvivalence Každá relace ekvivalence R na množině A zadává tzv. rozklad množiny A na disjunktní podmnožiny vzájemně ekvivalentních prvků (tzv. třídy ekvivalance). Klademe pro a g A libovolné [a]fí = {btA\(a,b)£A}. Potom A/R = {[a]r | a g A}. Příklad Pro n = 4 a relaci R =~n=~4 máme [0]4 = {0,4,8,...,-4,-8,...} = {4/f |/fGZ} [1]4 = {1,5,9,...,-3,-7,...} = {4/c + 1 |/cgZ} [2]4 = {2,6,10,.. .,-2,-6,... } = {4k + 2 | IteZ} [3]4 = {3,7,11,...,-1,-5,...} = {4/c + 3 | /cg Z} Z/ ~4={[0]4,[1]4,[2]4,[3]4} 3. přednáška Pojmy z teorie množin Matice - definice • Co je matice? Neformálně: Obdélníkové schéma s prvky z R (pole skalárů). • Matice typu m x n má m řádků a n sloupců: A 321 ^22 \ 3/771 3/772 am \ ^2/7 • Formálně: A : {1,..., m} x {1,..., n} R • My budeme pracovat s maticemi nad R g {Z, q, M, C}. Obecně se někdy hodí i jiné množiny R: např. R = {0,1} v teorii grafů. 3. přednáška Pojmy z teorie množin Sčítání a násobení matic • Matmn{R) množina všech matic typu m x n nad R. • Pro A, B g Matmn{R) definujeme matici A + Bg Matmn{R), vztahem /A + fí = (c,y), kde c,y= a,y + jfc>,y, 1 < / < m, 1 <}