Matematika I - 4. přednáška Geometrie v rovině, relace a zobrazení >razení oooooo< Michal Bulant Masarykova univerzita Fakulta informatiky 12. 3. 2012 Rovina geometrie oooooo Relace a zobrazení oooooooooooooo< O Rovina geometrie • Obsah trojúhelníka • Viditelnost v rovině Q Relace a zobrazení • Relace na množině • Rozklad podle ekvivalence Rovina geometrie oooooo Relace a zobrazení oooooooooooooo< • Martin Panák, Jan Slovák - Drsná matematika, e-text. • Roman Hilscher - MB101, e-text. • Slidy z přednášek a democvičení • Pavel Horák, Úvod do lineárni algebry, MU Brno, skripta (http://www.math.muni.cz/~horak) • 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/). Závěrem úvodního výletu do geometrie se zaměřme na pojem obsah. Trojúhelník je vymezen dvojicí vektorů v a w, které přiloženy do počátku O zadají zbylé dva vrcholy. Chtěli bychom tedy najít formuli (skalární funkci vol), která dvěma vektorům přiřadí číslo rovné obsahu vol A(v, w) takto definovaného trojúhelníku A(v, w). Ze zadání je vidět, že by mělo platit vol A(v + v', w) = vol A(v, w) + vol A(v', w) vol A(av, w) = a vol A(v, w) a přidejme požadavek vol A(v, w) = — vol A(w/, v), který odpovídá představě, že opatříme plochu znaménkem podle toho, v jakém pořadí bereme vektory. Rovina geometrie o»oooo Relace a zobrazení oooooooooooooo< Pokud vektory v a w napíšeme do sloupců matice A, pak A = (v, w) 1-» detA splňuje všechny tři naše požadavky. Kolik takových zobrazení ale může být? Každý vektor umíme vyjádřit pomocí dvou souřadných vektorů v = (1, 0) a w = (0,1) a evidentně tedy každá možnost pro vol A je jednoznačně určena už vyčíslením na této jediné dvojici argumentů (v, w). Jsou si tedy všechny možnosti rovny až na skalární násobek. Ten umíme určit požadavkem volA((l,0),(0,l)) = Í tj. volíme orientaci a měřítko. Vidíme tedy, že determinant zadává plochu rovnoběžníka určeného sloupci matice A (a plocha trojúhelníku je tedy poloviční). Rovina geometrie oo»ooo Relace a zobrazení OOOOOOOOOOOOOOÍ Obsah mnohoúhelníka Mnohoúhelník rozdělíme na trojúhelníky, jejichž obsahy sečteme (tzv. triangulace - promyslete si, že je to vždy, i u nekonvexních mnohoúhelníků, možné). Příklad Úloha o hlídačích v galerii (art gallery problém -http://en.wikipedia.org/wiki/Art_gallery_problem) - je třeba v rozích galerie mnohoúhelníkového tvaru umístit co nejmenší počet hlídačů (kamer) tak, aby byl střeženo každé místo v galerii. Problém někdy nese jméno svého řešitele, Vaška Chvátala. Řešení S pomocí triangulace a obarvení jejích vrcholů (je možné obarvit vrcholy každé triangulace n-úhelníka 3 barvami tak, že žádné 2 sousední nemají tutéž barvu) lze snadno dokázat, že hlídačů vždy stačí [§J. Rovina geometrie 000*00 Relace a zobrazení OOOOOOOOOOOOOOÍ Viditelnost Předchozí popis hodnot pro orientovaný objem nám dává do rukou elegantní nástroj pro určování viditelnosti orientovaných úseček. Orientovanou úsečkou rozumíme dva body v rovině M2 s určeným pořadím. Můžeme si ji představovat jako šipku od prvého k druhému bodu. Taková orientovaná úsečka nám rozděluje rovinu na dvě poloroviny, říkejme jim levou a pravou. Jestliže uvažujeme obvyklou orientaci proti směru hodinových ručiček pro hranici mnohoúhelníka, pak pozorovatel stojící vně takového mnohoúhelníka některé jeho hrany vidí a některé nevidí. Pokud je daný mnohoúhelník konvexní, tj. jeho hrany zatáčejí pouze doleva, potom pozorovatel vidí právě ty hrany (orientované úsečky), od nichž je napravo. Rovina geometrie oooo»o Relace a zobrazení oooooooooooooo< Je-1i AB vektor takové orientované úsečky, potom pro bod C ležící napravo od ní platí, že vektory CA = A — C a CB = B — C, které směřují z bodu C do bodů A a B, jsou vzájemně orientovány v záporném směru, a proto je jejich jejich vol A(ČA, ČB) < 0, úsečku AB z bodu C vidíme. Naopak, pro bod C ležící nalevo od AB platí, že vol A(G4, C6) > 0, úsečku AB z bodu C nevidíme. Protože je funkce vol A pouze kladným násobkem funkce det/4, kde sloupce matice A jsou vektory CA, CB v tomto pořadí, stačí pouze sledovat znaménka příslušných determinantů. Pro konvexní mnohoúhelník nastanou zřejmě právě 2 znaménkové změny v posloupnosti těchto determinantů. Uvedený jednoduchý postup je často využíván pro testování polohy při standardních úlohách ve 2D (a podobně pro příslušnou funkci vol ve 3D) grafice. Rovina geometrie 00000» Relace a zobrazení oooooooooooooo< Príklad Určete, které hrany jsou vidět z bodu C = [2,0] pro čtyřúhelník daný vrcholy ^ = [0,0], 6 = [2,1], D = [3,3], E = [1,4]. Body jsou již seřazeny v kladném směru a tvoří konvexní čtyřúhelník. Vypočítáme příslušné determinanty \A-C,B-C\ = \D- C,E - C\ = Pororovatel v bodě -2 O 0 1 1 -1 3 4 = -2, \B — C, D — C = 7,|E- C,A- C\ ~- C tedy vidí pouze první dvě hrany: AB a BD. Rovina geometrie oooooo Relace a zobrazení •ooooooooooooo< V závěrečné části úvodní motivační kapitoly se vrátime k formálnímu popisu matematických struktur, budeme seje 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. Definice Kartézským součinem A x B dvou množin A a B rozumíme množinu všech uspořádaných dvojic (a, b), kde a G A, b G B. Binární relací mezi množinami A a B rozumíme libovolnou podmnožinu R kartézského součinu A x B. Často píšeme a ~r b (nebo aRb) pro vyjádření skutečnosti, že (a, b) G R, tj. že body a G A a b G B jsou v relaci R. Pro A = B hovoříme o (binární) relaci na množině A. Později se setkáte s příklady obecnějších n-árních relací. Rovina geometrie oooooo Relace a zobrazení o»oooooooooooo< Definice Definičním oborem relace je podmnožina DCA, D = {a G A; 3b G B,(a,b) G /?}. Podobně oborem hodnot relace je podmnožina / C B, I = {b G B;3a G A,(a,b) G /?}. Rovina geometrie oooooo Relace a zobrazení oo»ooooooooooo< 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:DCA->IC 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. Rovina geometrie oooooo Relace a zobrazení ooo»oooooooooo< 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 G / existuje právě jeden vzor a G A, f (a) = b (injektivita se nejčastěji dokazuje ve tvaru f{a\) = f{a2) =4> a\ = 32). Vyjádření zobrazení f : A —^ B jakožto relace f C A x B, f = {(a, f (a)); a G Ä} známe také pod názvem graf zobrazení f. Rovina geometrie oooooo Relace a zobrazení oooo»ooooooooo< U zobrazení je jasná koncepce, jak se skládají. Máme-li zobrazení f: A^-Bag: B^-C, pak jejich složení g o f je definováno (gof)(a) = g(f(a)). Ve značení používaném pro relace totéž můžeme zapsat jako faxe, f = {(a, f(a)); a e A} gCBxC, g = {(b,g(b));be B} gofCAxC, gof = {{a,g{f{a)));aeA}. Rovina geometrie oooooo Relace a zobrazení ooooo»oooooooo< 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 C A x B, S C B x C. Potom S o R C A x C, So R = {(a, c); 3b G B, (a, b) G R, (b, c) G S}. Zvláštním případem relace je identické zobrazení icU = {(a, a) £ Ax 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. Rovina geometrie oooooo Relace a zobrazení oooooo»ooooooo< Pro každou relaci R C A x B definujeme inverzní relaci R-1 = {(/,, a); (a, b) G R} C B x 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 G 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é obražení, u obecných relací tomu tak být nemusí. Rovina geometrie oooooo Relace a zobrazení ooooooo»oooooo< Definice V případě A = B hovoříme o relaci na množině A. Říkáme, že R je: • reflexivní, pokud id^ C R (tj. (a, a) 6 R pro všechny a G /4), • symetrická, pokud R^1 = R (tj. pokud (a,b) £ /?, pak i (Z), a) G /?), » antisymetrická, pokud Z?-1 n R C id^ (tj. pokud (a, fa) G /? a zároveň (fa, a) £ /?, pak a = fa), « tranzitivní, pokud R o R C /?, tj. pokud z (a, fa) £ /? a (fa, c) 6 /? 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á. Rovina geometrie oooooo Relace a zobrazení oooooooo»ooooo< 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 danou vlastností být podmnožinou. Evidentně jsou splněny všechny tři vlastnosti pro uspořádání: skutečně, je-li X C y a zároveň Y C X musí být nutně množiny X a Y stejné. Je-li X C V C Zje také X C 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 C Y ani Y C X. Rovina geometrie oooooo Relace a zobrazení ooooooooo«oooo< Připomeňme rekurentní definici přirozených čísel N = {0,1,2,3,...}, kde 0 = 0, n + 1 = {0,1,2,...,/)}. Definujeme relaci m < n právě, když m £ n. Evidentně jde o úplné uspořádání. Např. 2 < 4, protože 2 = {0,{0}} C {0, {0}, {0, {0}},{0,{0},{0,{0}}}} = 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. Rovina geometrie oooooo Relace a zobrazení oooooooooo»ooo< Buď (A, <) uspořádaná množina, B C A. 9 Horní závora množiny B je prvek a G A tak, že \/b G B : b < a, analogicky dolní závora. • Supremum množiny B je prvek a G A, který je horní závorou B a každá jiná horní závora z splňuje a < z. Analogicky infimum. Príklad sup(0,1) = 1, inf{^; n G N} v M je 0. Rovina geometrie oooooo Relace a zobrazení ooooooooooo«oo< 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 G A Ra = [a]R = {beA;{a,b)eA}. Často budeme psát pro Ra prostě [a], je-li z kontextu zřejmé, o kterou ekvivalenci jde. Zjevně Ra = Rt, právě, když (a, b) G R a každá taková podmnožina je tedy reprezentována kterýmkoliv svým prvkem, tzv. reprezentantem. Zároveň Ra n /?£, 7^ 0 právě, když Ra = Rt,, tj. třídy ekvivalence jsou po dvou disjunktní. Konečně, A = Uae^/?a, tj. celá množina A se skuteč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. Rovina geometrie oooooo Relace a zobrazení oooooooooooo»o< Príklad • Z = S U L je rozklad celých čísel na sudá a lichá, odpovídající relací ekvivalence je a ~ b právě tehdy, když má a stejnou paritu jako b. 9 R = M~ U {0} U M+ je rozklad reálných čísel na záporná, nulu a kladná. Odpovídající relace je dána znaménkem. Rovina geometrie oooooo Relace a zobrazení ooooooooooooo»< Na přirozených číslech umíme 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, fa) ~ (a', Z/) 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 vpravo už ano. Snadno ověříme, že skutečně jde o ekvivalenci a její třídy označíme jako celá čísla Z. Rovina geometrie oooooo Relace a zobrazení OOOOOOOOOOOOOOÍ 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í. Rovina geometrie oooooo Relace a zobrazení ooooooooooooocx U celých čísel nám už platí všechny vlastnosti skalárů (KG1)-(KG4) a (01)-(04), z popisu vlastností skalám. 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 (Ol), 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. Na množině uspořádaných dvojic (p,q), q 7^ 0, celých čísel definujeme relaci ~ tak, jak očekáváme, že se mají chovat podíly 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. P/fT- pl q = p1 I q' p-q = p ■ q- Rovina geometrie oooooo Relace a zobrazení ooooooooooooocx 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 ~^ tak, že dvě čísla a, b G Z jsou ekvivalentní, jestliže jejich zbytek po dělení číslem k je stejný. Výslednou množinu tříd ekvivalence označujeme Z^. 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 pole (P) ) právě když je k prvočíslo.