Relace a zobrazení Rozklad podle ekvivalence Matematika I – 4b Relace a zobrazení Jan Slovák Masarykova univerzita, Fakulta informatiky 10. 10. 2012 Relace a zobrazení Rozklad podle ekvivalence Obsah přednášky 1 Relace a zobrazení 2 Rozklad podle ekvivalence Relace a zobrazení Rozklad podle ekvivalence 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}. Relace a zobrazení 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á. Relace a zobrazení 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. Relace a zobrazení 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“. Relace a zobrazení 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. Relace a zobrazení 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í. Relace a zobrazení 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. Relace a zobrazení 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. Relace a zobrazení Rozklad podle ekvivalence Přímky v rovině Vybereme-li v prostoru R2 směr v = (a, b), pak máme dobře definovánu relaci P ∼ Q, právě když P = Q + kv. Jde o ekvivalenci a třídy rozkladu jsou právě rovnoběžné prímky se směrovým vektorem v.