Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Drsná matematika I – 4. přednáška Relace a zobrazení Jan Slovák Masarykova univerzita 10. 10. 2011 Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Obsah přednášky 1 Literatura 2 Relace a zobrazení 3 Relace na množině 4 Rozklad podle ekvivalence 5 Rozklad podle ekvivalence Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Kde je dobré číst? vlastní poznámky, texty současného nebo předcházejícího přednášejícího, GOOGLE, atd. Pavel Horák, Úvod do lineární algebry, MU Brno, skripta. Luboš Motl, Miloš Zahradník, Pěstujeme lineární algebru, 3. vydání, Univerzita Karlova v Praze, Karolinum, 348 stran (elektronické vydání také na http://www.kolej.mff.cuni.cz/˜lmotm275/skripta/). Riley, K.F., Hobson, M.P., Bence, S.J. Mathematical Methods for Physics and Engineering, second edition, Cambridge University Press, Cambridge 2004, ISBN 0 521 89067 5, xxiii + 1232 pp. František Šik, Lineární algebra zaměřená na numerickou analýzu, MU, 1998, 176 s. ISBN 80-210-1996-2. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence V závěrečné části úvodní motivační kapitoly se vrátíme k formálnímu popisu matematických struktur, budeme se je ale průběžně snažit ilustrovat na již známých příkladech. Zároveň můžeme tuto část brát jako cvičení ve formálním přístupu k objektům a konceptům matematiky. Definition Binární relací mezi množinami A a B rozumíme podmnožinu R kartézského součinu A × B. Často píšeme a R b pro vyjádření skutečnosti, že (a, b) ∈ R, tj. že body a ∈ A a b ∈ B jsou v relaci R. Definičním oborem relace je podmnožina D ⊂ A, D = {a ∈ A; ∃b ∈ B, (a, b) ∈ R}. Podobně oborem hodnot relace je podmnožina I ⊂ B, I = {b ∈ B; ∃a ∈ A, (a, b) ∈ R}. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Speciálním případem relace mezi množinami je zobrazení z množiny A do množiny B. Je to případ, kdy pro každý prvek definičního oboru relace existuje právě jeden prvek z oboru hodnot, který je s ním v relaci. Nám známým případem zobrazení jsou všechny skalární funkce, kde oborem hodnot zobrazení je množina skalárů, třeba celých nebo reálných čísel. Pro zobrazení zpravidla používáme značení, které jsme také u skalárních funcí zavedli. Píšeme f : D ⊂ A → I ⊂ B, f (a) = b pro vyjádření skutečnosti, že (a, b) patří do relace, a říkáme, že b je hodnotou zobrazení f v bodě a. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Dále říkáme, že f je zobrazení množiny A do množiny B, jestliže je D = A, zobrazení množiny A na množinu B, jestliže je D = A a I = B, často také surjektivní zobrazení injektivní zobrazení, jestliže je D = A a pro každé b ∈ I existuje právě jeden vzor a ∈ A, f (a) = b. Vyjádření zobrazení f : A → B jakožto relace f ⊂ A × B, f = {(a, f (a)); a ∈ A} známe také pod názvem graf zobrazení f . Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence U zobrazení je jasná koncepce, jak se skládají. Máme-li zobrazení f : A → B a g : B → C, pak jejich složení g ◦ f je definováno (g ◦ f )(a) = g(f (a)). Ve značení používaném pro relace totéž můžeme zapsat jako f ⊂ A × B, f = {(a, f (a)); a ∈ A} g ⊂ B × C, g = {(b, g(b)); b ∈ B} g ◦ f ⊂ A × C, g ◦ f = {(a, g(f (a))); a ∈ A}. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Zcela obdobně definujeme skládání relací, v předchozích vztazích jen doplníme existenční kvantifikátory, tj. musíme uvažovat všechny „vzory“ a všechny „obrazy“.Uvažme relace R ⊂ A × B, S ⊂ B × C. Potom S ◦ R ⊂ A × C, S ◦ R = {(a, c); ∃b ∈ B, (a, b) ∈ R, (b, c) ∈ S}. Zvláštním případem relace je identické zobrazení idA = {(a, a) ∈ A × A; a ∈ A} na množině A. Je neutrální vzhledem ke skládání s každou relací s definičním oborem nebo oborem hodnot A. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Pro každou relaci R ⊂ A × B definujeme inverzní relaci R−1 = {(b, a); (a, b) ∈ R} ⊂ B × A. Pozor, u zobrazení, je stejný pojem užíván ve specifičtější situaci. Samozřejmě, že existuje pro každé zobrazení jeho invezní relace, ta však nemusí být zobrazením. Zcela logicky proto hovoříme o existenci inverzního zobrazení, pokud každý prvek b ∈ B je obrazem pro právě jeden vzor v A. V takovém případě je samozřejmě inverzní zobrazení právě inverzní relací. Všimněme si, že složením zobrazení a jeho inverzního zobrazení (pokud obě existují) vždy vznikne identické obrazení, u obecných relací tomu tak být nemusí. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Definition V případě A = B hovoříme o relaci na množině A. Říkáme, že R je: reflexivní, pokud idA ⊂ R (tj. (a, a) ∈ R pro všechny a ∈ A), symetrická, pokud R−1 = R (tj. pokud (a, b) ∈ R, pak i (b, a) ∈ R), antisymetrická, pokud R−1 ∩ R ⊂ idA (tj. pokud (a, b) ∈ R a zároveň (b, a) ∈ R, pak a = b), tranzitivní, pokud R ◦ R ⊂ R, tj. pokud z (a, b) ∈ R a (b, c) ∈ R vyplývá i (a, c) ∈ 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á. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Dobrým příkladem uspořádání je inkluze. Uvažme množinu 2A všech podmnožin konečné množiny A (značení je speciálním případem obvyklé notace BA pro množinu všech zobrazení A → B) a na ní relaci X ⊂ Z danou vlastností „být podmnožinou“. Evidentně jsou splněny všechny tři vlastnosti pro uspořádání: skutečně, je–li X ⊂ Y a zároveň Y ⊂ X musí být nutně množiny X a Y stejné. Je–li X ⊂ Y ⊂ Z je také X ⊂ Z a také reflexivita je zřejmá. Říkáme, že uspořádání je úplné, když pro každé dva prvky platí že jsou srovnatelné, tj. buď a ≤ b nebo b ≤ a. Všimněme si, že ne všechny dvojice (X, Y ) podmnožin v A jsou srovnatelné v tomto smyslu. Přesněji, pokud je v A více než jeden prvek, existují podmnožiny X a Y , kdy není ani X ⊂ Y ani Y ⊂ X. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Připomeňme rekurentní definici přirozených čísel N = {0, 1, 2, 3, . . . }, kde 0 = ∅, n + 1 = {0, 1, 2, . . . , n}. Definujeme relaci m < n právě, když m ∈ n. Evidentně jde o úplné úspořádání. Např. 2 ≤ 4, protože 2 = {∅, {∅}} ⊂ {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}} = 4. Jinak řečeno, samotná rekurentní definice zadává vztah n ≤ n + 1 a tranzitivně pak n ≤ k pro všechna k, která jsou tímto postupem definována později. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Každá ekvivalence R na množině A zadává zároveň rozklad množiny A na podmnožiny vzájemně ekvivalentních prvků, tzv. třídy ekvivalance. Klademe pro libovolné a ∈ A Ra = {b ∈ A; (a, b) ∈ A}. Často budeme psát pro Ra prostě [a], je-li z kontextu zřejmé, o kterou ekvivalenci jde. Zjevně Ra = Rb právě, když (a, b) ∈ R a každá taková podmnožina je tedy reprezentována kterýmkoliv svým prvkem, tzv. reprezentantem. Zároveň Ra ∩ Rb = ∅ právě, když Ra = Rb, tj. třídy ekvivalence jsou po dvou disjunktní. Konečně, A = ∪a∈ARa, tj. celá množina A se suktečně rozloží na jednotlivé třídy. Můžeme také třídám rozkladu rozumět tak, že třídu [a] vnímáme jako prvek a „až na ekvivalenci“. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Příklad – konstrukce celých čísel Na přirozených číslech umíme sice sčítat a víme, že přičtením nuly se číslo nezmění. Umíme i definovat odečítání, při něm ale jen někdy existuje výsledek. Základní ideou konstrukce celých čísel z přirozených je tedy přidat k nim chybějící rozdíly. To můžeme udělat tak, že místo výsledku odečítání budeme pracovat s uspořádanými dvojicemi čísel, které nám samozřejmě vždy výsledek dobře reprezentují. Zbývá jen dobře definovat, kdy jsou (z hlediska výsledku odečítání) takové dvojice ekvivalentní. Potřebný vztah tedy je: (a, b) ∼ (a , b ) ⇐⇒ a−b = a −b ⇐⇒ a+b = a +b. Všimněme si, že zatímco výrazy v prostřední rovnosti v přirozených číslech neumíme, výrazy v pravo už ano. Snadno ověříme, že skutečně jde o ekvivalenci a její třídy označíme jako celá čísla Z. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Na třídách ekvivalence definujeme operaci sčítání (a s ní i odečítání) pomocí reprezentantů. Např. [(a, b)] + [(c, d)] = [(a + c, b + d)], což zjevně nezávisí na výběru reprezentantů. Lze si přitom vždy volit reprezentanty (a, 0) pro kladná čísla a reprezentanty (0, a) pro čísla záporná, se kterými se nám bude patrně počítat nejlépe. Tento jednoduchý přklad ukazuje, jak důležité je umět nahlížet na třídy ekvivalence jako na celistvý objekt a soustředit se na vlastnosti těchto objektů, nikoliv formální popisy jejich konstrukcí. Ty jsou však důležité k ověření, že takové objekty vůbec existují. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence U celých čísel nám už platí všechny vlastnosti skalárů (KG1)–(KG4) a (O1)-(O4), z popisu vlastností skalárů. Pro násobení je neutrálním prvkem jednička, ale pro všechna čísla a různá od nuly a jedničky neumíme najít číslo a−1 s vlastností a · a−1 = 1, tzn. chybí nám inverzní prvky. Zároveň si povšimněte, že platí vlastnost oboru integrity (OI), tzn. je-li součin dvou čísel nulový, musí být alespoň jedno z nich nula. Díky poslední jmenované vlastnosti můžeme zkonstruovat racionální čísla Q přidáním všech chybějících inverzí zcela obdobným způsobem, jak jsme konstruovali Z z N. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Příklad – konstrukce racionálních čísel Na množině uspořádáných dvojic (p, q), q = 0, celých čísel definujeme relaci ∼ tak, jak očekáváme, že se mají chovat podíly p/q: (p, q) ∼ (p , q ) ⇐⇒ p/q = p /q ⇐⇒ p · q = p · q. Opět neumíme očekávané chování v prostřední rovnosti v množině Z formulovat, nicméně rovnost na pravé straně ano. Zjevně jde o dobře definovanou relaci ekvivalence (ověřte podrobnosti!) a racionální čísla jsou pak její třídy ekvivalence. Když budeme formálně psát p/q místo dvojic (p, q), budeme definovat operace násobení a sčítání právě pomocí formulí, které nám jsou jistě dobře známy. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Příklad – zbytkové třídy Jiným dobrým a jednoduchým příkladem jsou tzv. zbytkové třídy celých čísel. Pro pevně zvolené přirozené číslo k definujeme equivalenci ∼k tak, že dvě čísla a, b ∈ Z jsou ekvivalentní, jestliže jejich zbytek po dělení číslem k je stejný. Výslednou množinu tříd ekvivalence označujeme Zk. Nejjednodušší je tato procedura pro k = 2. To dostáváme Z2 = {0, 1}, kde nula reprezentuje sudá čísla, zatímco jednička čísla lichá. Opět lze snadno zjistit, že pomocí reprezentantů můžeme definovat násobení a sčítání. Zkuste si ověřit, že výsledná množina „skalárů“ je komutativním tělesem (tj. splňuje i vlastnost (P) pole) právě když je k prvočíslo. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Každá ekvivalence R na množině A zadává zároveň rozklad množiny A na podmnožiny vzájemně ekvivalentních prvků, tzv. třídy ekvivalance. Klademe pro libovolné a ∈ A Ra = {b ∈ A; (a, b) ∈ A}. Často budeme psát pro Ra prostě [a], je-li z kontextu zřejmé, o kterou ekvivalenci jde. Zjevně Ra = Rb právě, když (a, b) ∈ R a každá taková podmnožina je tedy reprezentována kterýmkoliv svým prvkem, tzv. reprezentantem. Zároveň Ra ∩ Rb = ∅ právě, když Ra = Rb, tj. třídy ekvivalence jsou po dvou disjunktní. Konečně, A = ∪a∈ARa, tj. celá množina A se suktečně rozloží na jednotlivé třídy. Můžeme také třídám rozkladu rozumět tak, že třídu [a] vnímáme jako prvek a „až na ekvivalenci“. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Příklad – konstrukce celých čísel Na přirozených číslech umíme sice sčítat a víme, že přičtením nuly se číslo nezmění. Umíme i definovat odečítání, při něm ale jen někdy existuje výsledek. Základní ideou konstrukce celých čísel z přirozených je tedy přidat k nim chybějící rozdíly. To můžeme udělat tak, že místo výsledku odečítání budeme pracovat s uspořádanými dvojicemi čísel, které nám samozřejmě vždy výsledek dobře reprezentují. Zbývá jen dobře definovat, kdy jsou (z hlediska výsledku odečítání) takové dvojice ekvivalentní. Potřebný vztah tedy je: (a, b) ∼ (a , b ) ⇐⇒ a−b = a −b ⇐⇒ a+b = a +b. Všimněme si, že zatímco výrazy v prostřední rovnosti v přirozených číslech neumíme, výrazy v pravo už ano. Snadno ověříme, že skutečně jde o ekvivalenci a její třídy označíme jako celá čísla Z. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Na třídách ekvivalence definujeme operaci sčítání (a s ní i odečítání) pomocí reprezentantů. Např. [(a, b)] + [(c, d)] = [(a + c, b + d)], což zjevně nezávisí na výběru reprezentantů. Lze si přitom vždy volit reprezentanty (a, 0) pro kladná čísla a reprezentanty (0, a) pro čísla záporná, se kterými se nám bude patrně počítat nejlépe. Tento jednoduchý přklad ukazuje, jak důležité je umět nahlížet na třídy ekvivalence jako na celistvý objekt a soustředit se na vlastnosti těchto objektů, nikoliv formální popisy jejich konstrukcí. Ty jsou však důležité k ověření, že takové objekty vůbec existují. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence U celých čísel nám už platí všechny vlastnosti skalárů (KG1)–(KG4) a (O1)-(O4), z popisu vlastností skalárů. Pro násobení je neutrálním prvkem jednička, ale pro všechna čísla a různá od nuly a jedničky neumíme najít číslo a−1 s vlastností a · a−1 = 1, tzn. chybí nám inverzní prvky. Zároveň si povšimněte, že platí vlastnost oboru integrity (OI), tzn. je-li součin dvou čísel nulový, musí být alespoň jedno z nich nula. Díky poslední jmenované vlastnosti můžeme zkonstruovat racionální čísla Q přidáním všech chybějících inverzí zcela obdobným způsobem, jak jsme konstruovali Z z N. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Příklad – konstrukce racionálních čísel Na množině uspořádáných dvojic (p, q), q = 0, celých čísel definujeme relaci ∼ tak, jak očekáváme, že se mají chovat podíly p/q: (p, q) ∼ (p , q ) ⇐⇒ p/q = p /q ⇐⇒ p · q = p · q. Opět neumíme očekávané chování v prostřední rovnosti v množině Z formulovat, nicméně rovnost na pravé straně ano. Zjevně jde o dobře definovanou relaci ekvivalence (ověřte podrobnosti!) a racionální čísla jsou pak její třídy ekvivalence. Když budeme formálně psát p/q místo dvojic (p, q), budeme definovat operace násobení a sčítání právě pomocí formulí, které nám jsou jistě dobře známy. Literatura Relace a zobrazení Relace na množině Rozklad podle ekvivalence Rozklad podle ekvivalence Příklad – zbytkové třídy Jiným dobrým a jednoduchým příkladem jsou tzv. zbytkové třídy celých čísel. Pro pevně zvolené přirozené číslo k definujeme equivalenci ∼k tak, že dvě čísla a, b ∈ Z jsou ekvivalentní, jestliže jejich zbytek po dělení číslem k je stejný. Výslednou množinu tříd ekvivalence označujeme Zk. Nejjednodušší je tato procedura pro k = 2. To dostáváme Z2 = {0, 1}, kde nula reprezentuje sudá čísla, zatímco jednička čísla lichá. Opět lze snadno zjistit, že pomocí reprezentantů můžeme definovat násobení a sčítání. Zkuste si ověřit, že výsledná množina „skalárů“ je komutativním tělesem (tj. splňuje i vlastnost (P) pole) právě když je k prvočíslo.