Opakování (předmět IMAk02) Kartézský součin, binární relace · Kartézským součinem dvou množin A, B rozumíme množinu A x B = {[x,y]; x A y B}, tj. množinu všech uspořádaných dvojic [x,y], kde x A a y B. · Binární relací R z množiny A do množiny B rozumíme libovolnou podmnožinu kartézského součinu A x B. · Binární relací R v neprázdné množině A rozumíme libovolnou podmnožinu kartézského součinu A x A. Příklad 1. Na množině A = {0,1,2,3,4} jsou definovány binární relace R, S, T, U, V. Zapište je výčtem prvků: R = {[x,y] A x A; x > y} S = {[x,y] A x A; x + y = 5} U = {[x,y] A x A; x = y} V = {[x,y] A x A; x = y x = 2.y} · Nechť v A je definována relace R: Relaci R´ v množině M definovanou předpisem R´ = (A x A) - R nazýváme doplňkovou relací k relaci R v množině A. · Nechť v A je definována relace R: Relaci R^-1 = {[x,y] A x A; {[y,x] R} nazýváme relací inverzní k relaci R v množině A. Vlastnosti binárních relací v množině A Binární relace R v množině A je · reflexivní právě tehdy, když ( x A) ([x,x] R), (obsahuje všechny uspořádané dvojice [x,x], kde x A, tj. v uzlovém grafu je každý uzel opatřen smyčkou) · antireflexivní právě tehdy, když ( x A) ([x,x] R), (neobsahuje žádnou uspořádanou dvojici typu [x,x], kde x A, tj. v uzlovém grafu není žádný uzel opatřen smyčkou) · symetrická právě tehdy, když ( x,y A) ([x,y] R [y,x] R], (s každou uspořádanou dvojicí [x,y] obsahuje i dvojici [y,x], tj. v uzlovém grafu jsou mezi dvěmi uzly buď dvě šipky nebo žádná) · antisymetrická, právě tehdy, když ( x,y A) [(x y [x,y] R) [y,x] R], (s žádnou dvojicí [x,y] různých prvků neobsahuje dvojici [y,x], tj. v uzlovém grafu je mezi dvěmi různými uzly buď jedna šipka nebo žádná) · tranzitivní právě tehdy, když ( x,y,z A) [([x,y] R [y,z] R) [x,z] R], (jestliže se v relaci vyskytují „na sebe navazující dvojice“, pak musí relace obsahovat i dvojici, jejíž první složkou je 1. složka z první dvojice a druhou složkou je 2. složka z druhé dvojice). · souvislá právě tehdy, když ( x,y A) [x y ([x,y] R [y,x] R)], (každé dva různé prvky z množiny A musí být „spolu v relaci“, tj. v uzlovém grafu jsou dva různé uzly spojeny alespoň jednou šipkou) Binární relaci U v množině A nazýváme uspořádání v A, právě když U je antisymetrická a tranzitivní. Binární relaci U v množině A nazýváme uspořádání · ostré právě tehdy, když U je antisymetrická, tranzitivní a antireflexivní, · neostré právě tehdy, když U je antisymetrická, tranzitivní a reflexivní. · lineární právě tehdy, když U je antisymetrická, tranzitivní a souvislá. Binární relaci R v množině M nazýváme relací ekvivalence na M, právě když je reflexivní, symetrická a tranzitivní. Každá relace ekvivalence na množině M vytváří rozklad této množiny, což je systém neprázdných podmnožin (tzv. tříd rozkladu) množiny M takových, že průnik každých dvou tříd je prázdná množina a sjednocení všech tříd rozkladu tvoří množinu M. Jinak lze také říci, že říci, že rozklad množiny M je systém neprázdných podmnožin (tzv. tříd rozkladu) množiny M takových, že každý prvek množiny M patří právě do jedné z těchto tříd. Příklad 2. V množině M = {1,2,3} je definována binární relace a) R[1] = {[x,y]∈ M ×M;x < 3⇒ x+y = 3}, b) R[2] = {[x,y]∈ M ×M;x = y ⇒ x = y}, c) R[3] = {[x,y]∈ M ×M;x = y ⇒ x+y = 3}, d) R[4] = {[x,y]∈ M ×M;x < y ⇔ x = y}, e) R[5] = {[x,y]∈ M ×M;x = 2 ∨ y > x+2}, f) R[6 ]= {[x,y]∈ M ×M;x < y ∧ x|y}. Zapište tyto relace výčtem prvků, určete jejich kartézské a uzlové grafy, určete jejich vlastnosti. Zobrazení z množiny do množiny, typy zobrazení · Nechť R je relace z množiny A do množiny B splňující vlastnosti: Ke každému prvku a A existuje nejvýše jeden prvek b B takový, že [a,b] R. Tato relace se nazývá zobrazení z množiny A do množiny B. Značíme R: A → B. Nechť R je zobrazení z množiny A do množiny B. · Jestliže [a,b] R, pak prvek a A nazýváme vzorem prvku b B v zobrazení R; prvek b B nazýváme obrazem prvku a A v zobrazení R. · Množina O[1](R) = {a A: existuje b B takové, že [a,b] R} se nazývá definiční obor zobrazení R. Platí O[1](R) A. · Množina O[2](R) = {b B: existuje a A takové, že [a,b] R} se nazývá obor hodnot zobrazení R. O[2](R) B. Příklad 3. Jsou dány množiny A = {x, y, z}, B = {a, b}. Rozhodněte, zda dané relace z množiny A do množiny B jsou zobrazení z A do B, případně určete definiční obor a obor hodnot zobrazení. a) R[1] = {[x,a], [y,b], [z,a], [z,b]}, b) R[2] = {[x,a], [z,b]}, c) R[3] = {[x,a], [y,a], [z,a]}. Rozlišujeme následující typy zobrazení R: I) Je – li O[1](R) = A O[2](R) B O[2](R) ≠ B, nazývá se R zobrazení množiny A do množiny B. II) Je – li O[1](R) A O[1](R) ≠ A O[2](R) = B, nazývá se R zobrazení z množiny A na množinu B. III) Je – li O[1](R) = A O[2](R) = B, nazývá se R zobrazení množiny A na množinu B. IV) Je – li O[1](R) A O[1](R) ≠ A O[2](R) B O[2](R) ≠ B, nazývá se R zobrazení z množiny A do množiny B. · Zobrazení R z množiny A do množiny B se nazývá prosté právě tehdy, když relace R^-1 je zobrazení z množiny B do množiny A. · Prosté zobrazení množiny A na množinu B nazýváme bijektivní zobrazení nebo také vzájemně jednoznačné zobrazení. Příklad 4. Jsou dány množiny A = {1, 2, 3, 4}, B = {a, b, c, d}. Rozhodněte, o jaký typ zobrazení se jedná a zda je toto zobrazení prosté: a) R[1][ = ]{[1,a], [2,c], [3,d]}, b) R[2][ = ]{[1,a], [2,c], [3,d], [4,a]}, c) R[3][ = ]{[2,a], [1,c], [3,b], [4,d]}. Ekvivalence množin, konečné a nekonečné množiny · Říkáme, že dvě množiny A, B jsou ekvivalentní právě tehdy, když existuje prosté zobrazení množiny A na množinu B. Zapisujeme A ~ B. Příklad 5. Jsou dány množiny A = {a, b, c}, B = {x, y, z}, C = {x, y}. Rozhodněte, které dvojice zadaných množin jsou ekvivalentní. Poznámka. Relace ~ dvou množin definovaná v libovolném systému množin M má vlastnosti: reflexivní, symetrická, tranzitivní. Relace ~ je tedy relací ekvivalence. Relace ekvivalence dvou množin v libovolném systému množin M vytváří rozklad systému M na třídy ekvivalentních množin. Příklad 6. Je dán systém množin M = {A, B, C, D, E, F, G, H}, kde A = {a, b, c}, B = {1, 2}, C = {x, y}, D = {○, ○, ○, ○}, E = {∆, ∆, ∆}, F = { [*], [*]}, G = { □ }, H = {☺, ☺, ☺, ☺}. Rozhodněte, které množiny ze systému M jsou ekvivalentní. · Množina A je konečná právě tehdy, když žádná vlastní podmnožina množiny A není ekvivalentní s množinou A. · Množina B je nekonečná právě tehdy, když existuje alespoň jedna vlastní podmnožina množiny B, která je ekvivalentní s množinou B. Poznámka. Množina M je vlastní podmnožinou množiny N právě tehdy, když M N M ≠ N. Binární operace v množině (nová látka) · Nechť M je libovolná neprázdná množina. Binární operací ○ v množině M rozumíme zobrazení z množiny kartézského součinu M x M do množiny M. · Jestliže v binární operaci je vzoru [x,y] M x M přiřazen obraz z M, píšeme: x ○ y = z; prvek z M se nazývá výsledek operace ○. Poznámka. Označení binárních operací: +, ·, ○, ⁎, □,.. Příklady binárních operací ve školské matematice: 1) Sčítání (+), odčítání (-), násobení (·), dělení (:), umocňování,… (pracujeme s nimi v číselných množinách). 2) Sjednocení ( ), průnik ( ), rozdíl ( - ), symetrický rozdíl ( ) množin,… (pracujeme s nimi v systémech množin). Vlastnosti binárních operací: Označení: · ℕ - {1, 2, 3, 4, …} - množina všech přirozených čísel · ℕ[0] - {0, 1, 2, 3, 4, …} - množina všech přirozených čísel s nulou (množina všech nezáporných celých čísel) · ℂ - {…, -2, -1, 0, 1, 2, 3, 4, …} - množina všech celých čísel · ℚ - množina všech racionálních čísel (zlomky) · ℝ - množina všech reálných čísel --------------------------------------------------------------------------------------------------- -------------- · Binární operace ○ v množině M, která má vlastnost, že je definována pro každou uspořádanou dvojici [x,y] M x M, se nazývá operace neomezeně definovaná v množině M (zkráceně operace definovaná na množině M). Značíme ND. Symbolicky: x, y M)( z M)[ x ○ y = z]. --------------------------------------------------------------------------------------------------- -------------- · Binární operace ○ definovaná na množině M (je ND), se nazývá komutativní právě tehdy, když platí: x, y M)[ x ○ y = y ○ x]. Značíme K. --------------------------------------------------------------------------------------------------- -------------- · Binární operace ○ definovaná na množině M, se nazývá asociativní právě tehdy, když platí: x, y, z M)[ (x ○ y) ○ z = x ○ (y ○ z)]. Značíme A. --------------------------------------------------------------------------------------------------- -------------- · Nechť v množině M je definována binární operace ○. Existuje-li prvek e M, pro který platí: x M)[ x ○ e = e ○ x = x]. Pak se prvek e M nazývá neutrálním prvkem množiny M vzhledem k operaci ○. Značíme EN. --------------------------------------------------------------------------------------------------- -------------- · Nechť v množině M je definována binární operace ○ a nechť e je neutrální prvek množiny M vzhledem k operaci ○. Prvek ā M nazýváme inverzním prvkem k prvku a M v operaci ○ v množině M právě tehdy, když platí: ā ○ a = a ○ ā = e. Jestliže a M)( ā M)[ ā ○ a = a ○ ā = e], řekneme, že ke každému prvku množiny M existuje prvek inverzní vzhledem k operaci ○. Značíme EI. --------------------------------------------------------------------------------------------------- -------------- · Říkáme, že binární operace ○ definovaná na množině M má vlastnost řešitelnost základních rovnic právě tehdy, když platí: a, b M) )( x, y M)[ a ○ x = b y ○ a = b]. Značíme ZR. Algebraické struktury s jednou operací · Uspořádaná dvojice (M, ○), kde M je neprázdná množina, ve které je definována binární operace ○, se nazývá algebraická struktura s jednou operací. I. Algebraická struktura (M, ○) se nazývá grupoid právě tehdy, když operace ○ je neomezeně definovaná v množině M (ND). II. Grupoid (M, ○), jehož operace ○ je asociativní, se nazývá podgrupa (ND, A). III. Pologrupa (M, ○) taková, že v M existuje neutrální prvek vzhledem k operaci (M, ○) a ke každému prvku a M existuje prvek inverzní ā M, se nazývá grupa (ND, A, EN, EI). Poznámka 6. Jestliže v případech I., II., III. je operace ○ komutativní, pak hovoříme o I. Komutativním grupoidu II. Komutativní pologrupě III. Komutativní grupě Schéma k Algebraickým strukturám s jednou operací: Vlastnost operace ○ Algebraická struktura ND Grupoid ND K Komutativní grupoid (M, ○) ND A Pologrupa ND A K Komutativní pologrupa ND A EN EI Grupa ND A EN EI K Komutativní grupa Určení vlastností binárních operací podle tvaru operační tabulky Uvažujme binární operaci ○ v množině M zapsané pomocí operační tabulky, viz příklad: Příklad 1: Je dána množina M = {a, b, c} a operace ○ v množině M daná tabulkou. Určete vlastnosti operace ○. Pokud existuje neutrální nebo agresivní prvek, určete je. K jednotlivým prvkům stanovte prvky inverzní, pokud existují. ○ a b c a b c a b c c b c a b c Vysvětlivky k tabulce: a ○ a = b b ○ c = b c ○ a = a Řešení: ND K [DEL: A :DEL] EN EI [DEL: ZR :DEL] [DEL: :DEL] Pravidla pro určování vlastností operace v množině dané tabulkou: ND: Tabulka je celá vyplněná prvky množiny M K: Prvky tabulky, která je celá vyplněná prvky množiny M, jsou souměrně rozloženy podle hlavní diagonály A: Z tabulky obvykle nepoznáme - určujeme z definice nebo ze vztahu A (ZR EI) EN: Alespoň jeden řádek a jeden sloupec jsou stejné jako záhlaví tabulky EI: Každý řádek i sloupec tabulky obsahuje neutrální prvky tak, že ve všech řádcích a sloupcích existují takové, že jsou souměrně rozloženy podle hlavní diagonály. ZR: Každý řádek i sloupec obsahuje všechny prvky množiny M Agresivní prvek g M poznáme tak, že v celém jemu příslušejícím řádku i sloupci se vyskytuje pouze prvek g. Problém asociativity operace ○ Vyjdeme ze vztahu A (ZR EI): 1. Pokud nastane situace, že EI [DEL: ZR :DEL] nebo [DEL: EI :DEL] ZR, pak platí, že operace ○ není asociativní, tj. [DEL: A :DEL] 2. Pokud nastane situace, že [DEL: EI :DEL] [DEL: ZR :DEL] nebo EI ZR, pak asociativitu operace ○ nelze určit přímo, ale je potřeba využít Definici 4 ověřením všech možných trojic prvků z dané množiny (zdlouhavé) Příklad 2: Je dána množina M = {a, b, c} a operace ○ v množině M daná tabulkou. Určete vlastnosti operace ○. Pokud existuje neutrální nebo agresivní prvek, určete je. K jednotlivým prvkům stanovte prvky inverzní, pokud existují. Určete typ algebraické struktury (M, ○). 1. ○ a b c a b a c b c b a c a c b 2. ○ a b c a c a a b a c b c a b c 3. ○ a b c a c a a b c b c a b c Algebraické struktury se dvěma operacemi · Na množině M jsou definovány dvě binární operace ⨁ a ⨀. Operace ⨀ je distributivní vzhledem k operaci ⨁ právě tehdy, když platí x, y, z M)[ (x ⨁ y) ⨀ z = (x ⨀ z) ⨁ (y ⨀ z)] … pravý distributivní zákon (PDZ) [z ⨀ (x ⨁ y) = (z ⨀ x) ⨁ (z ⨀ y)] … levý distributivní zákon (LDZ). Značíme ⨀ D ⨁. Nechť M je neprázdná množina, ve které jsou definovány dvě operace ⨁ a ⨀. · Algebraická struktura (M, ⨁ , ⨀ ) se nazývá polookruh právě tehdy, když: I. Operace ⨁ je ND A K II. Operace ⨀ je ND A III. Platí ⨀ D ⨁ · Je-li operace ⨁ navíc K, pak polookruh (M, ⨁, ⨀) nazýváme komutativní polookruh. · Pologrupu (M, ⨁ ) nazýváme aditivní pologrupa. · Pologrupu (M, ⨀) nazýváme multiplikativní pologrupa. · Polookruh (M, ⨁ , ⨀ ), jehož aditivní pologrupa (M, ⨁) je komutativní grupou, se nazývá okruh. · Je-li operace ⨀ navíc K, pak okruh (M, ⨁ , ⨀ ), nazýváme komutativní okruh. · Nechť (M, ⨁ , ⨀) je okruh. Prvky a ≠ 0, b ≠ 0, a, b M, pro které platí a ⨀ b = 0, se nazývají dělitelé nuly okruhu (M, ⨁ , ⨀ ). · Komutativní okruh (M, ⨁ , ⨀ ), ve kterém neexistují dělitelé nuly, se nazývá obor integrity. · Okruh (M, ⨁ , ⨀ ), pro který platí, že (M – {0}, ⨀ ) je grupa, se nazývá těleso. · Je-li operace · navíc K, pak těleso (M, ⨁ , ⨀ ).nazýváme komutativní těleso. Poznámka: Uvažujeme polookruh (M, ⨁ , ⨀ ): · Operace ⨁ se nazývá sčítání. V zápise a ⨁ b = c nazýváme prvky a, b sčítanci, prvek c nazýváme součet prvků a, b. Neutrální prvek nazýváme nulový prvek, značíme 0. Pokud k prvku a existuje prvek inverzní, nazýváme jej opačný prvek k prvku a, značíme – a. Existuje-li prvek x, pro který platí b ⨁ x = a, nazýváme jej rozdíl prvků a, b a zapisujeme x = a ⊝ b. V tomto zápise prvek a nazýváme menšenec, prvek b nazýváme menšitel. Pokud existuje prvek ⊝b, pak platí x = a ⊝ b = a ⨁ (⊝ b). Operace ⊝ se nazývá odčítání. · Operace ⨀ se nazývá násobení. V zápise a ⨀ b = c nazýváme prvek a, resp. b 1. činitel, resp. 2. činitel, prvek c nazýváme součin prvků a, b. Neutrální prvek nazýváme jednotkový prvek, značíme 1. Pokud k prvku a existuje prvek inverzní, nazýváme jej převrácený prvek k prvku a, značíme nebo též a ^-1. Existuje-li pro prvky a, b ≠ 0 prvek x, pro který platí b ⨀ x = a, nazýváme jej podíl prvků a, b a zapisujeme x = a ⨸ b nebo taky x = . V tomto zápise prvek a nazýváme dělenec (čitatel), prvek b nazýváme menšitel (jmenovatel). Pokud existuje prvek , resp. b ^-1, pak platí x = a ⨸ b = = a ⨀ = a ⨀ b ^-1 . Operace ⨸ se nazývá dělení. Podíl prvků pro b = 0 nedefinujeme, neboť: 1. v případě, že a = 0, je řešením rovnice 0 ⨀ x = 0 každý prvek množiny M. 2. v případě, že a ≠ 0, rovnice 0 ⨀ x = a nemá řešení v množině M. Případ 1. vede k tomu, že by dělení nebylo operací! Schéma k Algebraickým strukturám se dvěma operacemi: operace a vlastnosti algebraická struktura ⨁ ND K A Polookruh (komutativní) ⨀ ND (K) A ⨀ D ⨁ ⨁ ND K A EN EI Okruh (komutativní) ⨀ ND (K) A ⨀ D ⨁ ⨁ ND K A EN EI Komutativní okruh bez dělitelů nuly = Obor integrity (M, ⨁ , ⨀ ) ⨀ ND K A ⨀ D ⨁ Neexistují a ≠ 0, b ≠ 0, a, b M, pro které platí a ⨀ b = 0. ⨁ ND K A EN EI Těleso (komutativní) ⨀ ND (K) A ⨀ D ⨁ (M – {0}, ⨀ ) je grupa, tj. na množině M – {0} je operace ⨀ ND A EN EI Příklady algebraických struktur číselných množin se dvěmi operacemi Příklad: Uvažujme binární operace obyčejné sčítání + a obyčejné násobení · v číselných množinách: 1. (ℕ, +, · ) komutativní polookruh s jednotkovým prvkem + … ND K A [DEL: EN :DEL] [DEL: EI :DEL] · … ND K A EN [DEL: EI :DEL] e = 1 · D + --------------------------------------------------------------------------------------------------- ------------- 2. (ℕ[0], +, · ) komutativní polookruh s nulovým (e = 0) a jednotkovým prvkem (e = 1) + … ND K A EN [DEL: EI :DEL] e = 0 · … ND K A EN [DEL: EI :DEL] e = 1 · D + --------------------------------------------------------------------------------------------------- ------------- 3. (ℂ, +, · ) komutativní okruh bez dělitelů nuly = obor integrity + … ND K A EN EI e = 0 · … ND K A EN [DEL: EI :DEL] e = 1 · D + V množině ℂ neexistují dělitelé nuly. --------------------------------------------------------------------------------------------------- ------------- 4. (ℚ, +, · ), (ℝ, +, · ) komutativní těleso + … ND K A EN EI e = 0 · … ND K A EN EI[DEL: :DEL] e = 1 · D + (ℚ – {0}, · ), (ℝ – {0}, · ) komutativní grupa, tzn. na množině ℚ – {0} a na množině ℝ – {0} má operace · vlastnosti: ND K A EN EI [ ]