Relace a zobrazení Relace na množině Rozklad podle ekvivalence Matematika I – 4. přednáška Relace a zobrazení Jan Slovák Masarykova univerzita, Fakulta informatiky 8. 10. 2012 Relace a zobrazení Relace na množině Rozklad podle ekvivalence Obsah přednášky 1 Relace a zobrazení 2 Relace na množině 3 Rozklad podle ekvivalence Relace a zobrazení Relace na množině 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}. Relace a zobrazení Relace na množině 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. Relace a zobrazení Relace na množině 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 . Relace a zobrazení Relace na množině 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}. Relace a zobrazení Relace na množině 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. Relace a zobrazení Relace na množině 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í. Relace a zobrazení Relace na množině 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í Relace na množině 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. Relace a zobrazení Relace na množině 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í Relace na množině Rozklad podle ekvivalence Příklad – zbytkové třídy 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í. 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. 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í.