1 Princip indukce 1. Označme sumu na levé straně L(n) a výraz vpravo P(n). 1. Pro n = 1 tvrzení zřejmě platí (L(í) = l3 = | = P(l)). 2. Předpokládejme, že tvrzení platí pro n (tj. L(n) = P(n)) a dokazujme, že poté platí i pro n+í. Tzn. chceme ukázat, že L(n + 1) = P(n + 1). Počítejme: L(n + 1) = L(n) + (n + l)3 = P(n) + (n + l)3 dle indukčního předpokladu. Tedy L(n + 1) = P(n) + (n+l)3="2("+1)2+(n+l)3 = (n+l)2"2+4f+1) = (n + 1)2^±^ = P(n + 1). 2. Podobně jako v předchozím: 1. Pro n = 1 máme L(í) = if = I, P(l) = ^ = \. 2. L(n + 1) = L(n) + |"t^"t^ = P(n) + í"+^"+^ = ^±^ + 1"+^"+^ = *±± • (n + 2±|) = v ' / vy1 (n+3)(n+4) ^ ' (n+3)(n+4) n+3 (n+3)(n+4) n+3 ^ n+4' n+1 n2+4n+n+6 _ n+1 (n+2)(n+3) _ (n+l)(n+2) _ p/ -, n n+3 ' n+4 n+3 ' n+4 n+4 V Ť^ 3. 1. Pro n = 2 máme L(2) = ±, P(2) = ^ - ± = i S i neboť předposlední nerovnost plyne z ^2 ^ n+2 — (n+1)2 - 4. 1. Pro n = 6 máme L(6) = 26 = 64, P(6) = 72 = 49. 2. L(n + 1) = 2n+1 = 2 • 2™ = 2 • L(n) > 2 • P(n) = 2(n + l)2 = 2n2 + 4n + 2. Z druhé strany P(n + 1) = (n + 2)2 = n2 + 4n + 4. Protože n2 > 2, máme 2n2 + 4n + 2 > n2 + 4n + 4 a tedy celkem L(n +1) > 2n2 + 4n + 2 > n2 + 4n + 4 = P(n + 1). 5. Označme An = rn + -^. Máme ukázat, že pokud A\ G Z, pak i An G Z, pro libovolné n G N. To dokážeme indukcí vzhledem k n. 1. Pro n = í máme A\ G Z. 2. Předpokládáme, že Ak G Z pro všechna k < n a. chceme ukázat, že An+i G Z. Proto se pokusíme vyjádřit An+1 pomocí A/, pro k < n + 1. Snadno se přesvědčíme, že platí An+i = A\An — An-\. Dle indukčního předpokladu Ai G Z, An_i G Z a A„ G Z, proto i An+i = AxAn - An-i e Z. 6. Indukcí vzhledem k počtu vrcholů. 1. Pro n = 3 platí. 2. Nechť tvrzení platí pro n a ukažme, že pak platí i pro n+í. Uvažujme tedy konvexní (n + l)-úhelník A1A2 .. .An+i. Rozdělme jej nyní úhlopříčkou A\An na n-úhelník A1A2 .. .An a trojúhelník A1AnAn+1. Součet vnitřních úhlů v n-úhelníku AiA2 ■ ■ ■ An je dle indukčního předpokladu 7T • (n — 2) a součet vnitřních úhlů v trojúhelníku A1AnAn+1 je -k. Celkem je tedy součet vnitřních úhlů v (n + l)-úhelníku A\A2 ■ ■ ■ An+i roven n ■ (n — 1), což jsme měli dokázat. 7. Dokážeme silnější tvrzení o nesousedních vrcholech. 1. Pro n = 4 evidentně platí. 2. Nechť máme (n + l)-úhelník A\A2 ... An+i a předpokládáme, že tvrzení platí pro libovolný fc-úhelník, kde k < n. Uvažme některou úhlopříčku v (n + l)-úhelníku AiA2 ■ ■ ■ An+1 (pokud tam, žádná není, tvrzení platí). Tato úhlopříčka, např AiAj rozdělí (n + l)-úhelník na dva mnohoúhelníky s menším počtem vrcholů kde AiAj je stranou. Ukážeme, že v obou existuje vrchol, různý od Ai i Aj z něhož nevychází žádná úhlopříčka. Pokud je tímto „menším" mnohoúhelníkem trojúhelník, pak je hledaným vrcholem třetí vrchol (různý od Ai a Aj). Pokud je „menším" mnohoúhelníkem A;-úhelník, kde 4 < k < n, pak můžeme využít indukčního předpokladu. Existují zde tedy dva nesousední vrcholy, z nichž nevychází žádná úhlopříčka. Protože jsou nesousední, je alespoň jeden z nich různý od Ai i Aj. V obou „menších" mnohoúhelnících jsme našli jeden vrchol, z něhož nevychází žádná úhlopříčka. A tyto dva vrcholy jsou nesousední, neboť jsou „odděleny" úhlopříčkou AiAj. 8. Označme An = ln ■ cos «.7. Dle návodu máme cos «.7 + cos(n — 2)7 = 2cos(n — 1)70037, z čehož po pronásobení ln dostaneme An + l2 ■ An-2 = 2An-\A\. 1. Pro n = 1 platí Ax G Z. 2. Pokud Ai, An_2, An_i G Z pak dle předchozího vztahu i An G Z. 1 9. Indukcí vzhledem k m • n. 1. Pro lxl platí. 2. Pokud máme tabulku m x n pak po prvním rozlomení dostaneme dvě menší tabulky, a to buď m-i x n, i7i2 x n, kde mi + m-2 = m, nebo m x n-i, m x n-2, kde n-i + n-2 = n. Použitím indukčního předpokladu dostaneme celkový počet lámání jako 1 + (mi • n — 1) + (m-2 • n — 1) = (mi + m.2) • n — 1 v prvním případě a podobně m • (n-i + n2) — 1 ve druhém. 2 Logika a přirozená čísla 1. Tabulkou... 2. Pokud hledáme formuli, jejíž sloupec v tabulce pravdivostních hodnot má v prvním řádku 1 a ve zbylých 0, pak snadno nahlédneme, že takovou formulí je A A B AC. Podobně, pokud hledáme formuli, jejíž sloupec v tabulce pravdivostních hodnot obsahuje právě jednu 1 (např. v šestém řádku), pak lze uvažovat konjunkci příslušných atomických výroků (tj. např. -iAaBA-iC). V našem případě je ve sloupci 1 vícekrát, takže jej budeme uvažovat jako disjunkci příslušných sloupců s jednou 1. Tzn. hledaným výrokem je např. (A A B A C) V (-iA A B A -iC). Z popsaného je zřejmé, že takto lze postupovat pro libovolný sloupec. 3. (a) Pro C nedává smysl, neb nemáme <. V R platí; takovým z je například ^L- V Z ani N neplatí; např. pro x = 1, y = 2 takové z neexistuje. (b) V N neplatí; např. pro x = 4, y = 1 takové z G N neexistuje. V R, C i Z platí; takovým z je vždy y — x. (c) Formule říká, že existuje nejmenší prvek z. Pro C nedává smysl. V N je takovým prvkem 1. V R a Z neplatí. (d) Formule říká, že existuje nevětší společný dělitel z dvou čísel x, y. To platí v N i Z. Formule je pravdivá taktéž i v R i C, protože zde se navzájem dělí všechna nenulová čísla a cokoli dělí nulu. Proto zde lze za nevětšího společného dělitele brát 1 nebo 0. (e) Formule vyjadřuje existenci „nulového prvku". Číslo 0 je takové x, a formule je tedy splněna v C, R a Z a není splněna v N. 4. (a) (3x)(3y)(x < y A (Vz)(-i(x < z) V -1(2 < yj). Odpověď (3x)(3y)(x < y A (Vz)(z < x V y < z)) není zcela správná, protože o relaci < nevíme, že se jedná o „uspořádání podle velikosti" i když v tomto příkladě jsme ji tak interpretovali. (b) (3x)(3y)(\/z)(x + zyty) (c) (\/z)(3x)(-i(z < x)). Komentář viz a). (d) (3x)(3y)(\fz)(z\x A z\y A (3u)(u\x A u\y A ~'{u\z))) (e) (\/x)(3y)(y + x^yVx + y^y) 5. (a) Nejdříve vytvoříme formuli, která o p říká, že je prvočíslo. Dle definice je p prvočíslo právě tehdy, když není 1 a má pouze triviální dělitele (1 a sebe sama). Formulí: Prv(p) = (p /t) A (\/x)(x\p =^> (x = 1 V x = p)). Hledaná formule tedy je, že každé číslo je dělitelné prvočíslem: (\/y)(3p)(Prv(p) Ap\y) tzn. jde o formuli (\/y)(3p)((p /L) A (\/x)(x\p =^> (x = 1 V x = p)) Ap\y). V N to neplatí. Číslo 1 není dělitelné prvočíslem. (b) Podobně jako u největšího společného dělitele. 6. (\/x)(3y)f(x,y) =^> (3y)(\/x)f(x, z) neplatí; stačí vzít příklad, který byl již dříve: (\/x)(3y)(x < y) platí např. v N, ale (3y)(\/x)(x < y) v N neplatí, neboť zde není největší prvek. (3y)(\/x)f(x,z) => (\/x)(3y)f(x, y) platí. 2 7. Uvažujme množinu {a — bx > 0|x G Z} a vezměme její nejmenší prvek a — by. Takový prvek jistě existuje, protože se jedná o neprázdnou podmnožinu přirozených čísel. Pokud hy b < a — by, odečtením b od obou stran nerovnosti dostaneme 0 < a — b(y + 1), ale protože a — b(y + 1) < a — by jsme ve sporu s tím, že a — by je nejmenší. Dostáváme tedy, že 0 < a — by (x e AAx <£A)v (x eAAx e B)o x g Ac\B (b) Pro libovolné x platí: x e (A - B) U (B - A) u (An B) 4$ x G (A - B) V x G (B - A) V x G (A n B) <^- (x e AAx <£ B)v (x e B Ax <£A)v (x eAAx e B) o (x G A A (x <£ B A x G B)) V (x G B A x <£ A) <^- x e A\/ (x e B A x <£ A) <=> (x e Avx e B) A (x e Avx <£ A) o x e (A n B) (c) Pro libovolné x platí: xeA-(BnC)^ xeAAx<£(BnC)o x G A A -i(x eßAieC)^ xeAA(x<£BVx<£C)o (x e AAx <£ B)v (x eAAx <£C) o x G (A - B) V x G (A - C) o x e (A-B) U (A-C) (d) Po nakreslení diagramů zjistíme, že prvek x by měl být v daných množinách pravě tehdy, když je ve všech třech množinách A, B, C nebo právě v jedné z nich. Tento fakt bychom měli ověřit formálně. Pro libovolné x platí: i€[(A-(Sť C)) U {{B + C)- A)] <* x e (A- (B + C))v x e ((B + C) - A) o (x G A A x £ (B -f- C)) V (x G (B -f- C) A x £ A) Snadno se ověří x <£ B -=- C <ŕ==> (leßAieC)V(i^ßAi^C). Podobně igBťC «=> (iGßAi^C)V(i^ßAieC). 3 Tedy (xe AAx£(B + C))\/ (x£AAxe{B + C))^ (x e AAx g B Ax e C) V (x G AAx <£ BAx <£ C) V (x ^ AAx G BAx <£ C) V (x ^ AAi ^ BAx G C). Což je fakt, který jsme chtěli ověřit. Výpočet pro x G (A -=- B) -=- C je podobný. (e) „=>" Nechť 0 A n B C C. Dokazujeme A D (B - C) = 0. Sporem. xGAn(ß-C,)=>xGAAxGß-C,=>xGAAxGßAx^C,=>xGAnßAx^Cr. Spor. „<=" Buď A n (B - C) = 0. Dokazujeme A D B C C. Sporem. Nechť 0 x G A D B a zároveň x <£ C. Potom x G A A x G B, vzhledem k x ^ C také x G B — C a proto x G a n (B — C); spor. (f) Buď A C C. Dokážeme ekvivalenci. „=>" Nechť ACS. Ukážeme, zeC-ßCC-A Buď x G C — B, pak x G C A x ^ B. Protože iCß dostáváme i j ^ i. Tedy x G C A x ^ A, tj. x G C - A. „<=" Nechť C - B CC -A. Ukážeme, že A C B. Sporem. Buď x G A takový, že x ^ B. Protože A C C, máme x G C a tedy i x G C — B. Odtud (vzhledem k předpokladu C — B C C — A) dostaneme x G C — A, což je spor s předpokladem x G A. 4. (a) Ano. Pro libovolné x platí: x G A n (B - C) «=^ xgAAxgB-C <ŕ==> xgAAxgBAx^C <ŕ==> x eAnB Ax <£C ^=> x e (AnB) -C. (b) Ne. Stačí vzít A = B = C neprázdnou množinu. (c) Ne. Stačí vzít A = 0, B = C. 5. 0 v (a) - (d); A v (e). 6. (a) Pro libovolné x platí: xeAn\JieIBi <*=> x G A A x G Uie/ -B» ^ x G A A (3i G i") (x G Bj) <ž=> (3i G I)(x G A A x G Bj) <ž=> (3i g J) (x einßj)» (b) Pro libovolné x platí: x G A V x G flie/ ßi ^ x G A V (Vi G i") (x G B») <^- (Vi G i")(x G A V x G B») <^- (\/ieI)(xeAuBi)^ xGflie/^UBi) (c) Pro libovolné x platí: ^A-nie/Bi ^ x G A A x ^ flie/ ßi ^ xG A A-.(x G f]ieIBi) <& x G A A -.((Vi G J) (x G Bi)) <^- x G A A (3i G i") (x ^ Bi) O (3i G i") (x eAAx^B-)^- (3i G J) (x G A - Bi) <& * e \JieI(A - Bi) 4 (d) „C" Pro libovolné x platí: x & Ui.eiiBi+Cj) ==> (3íg1)(3jg TjixzBi+Cj) => (3i G i)(3j G J)((x G ß;A i Có) V (x ^ ß;A G Có) ==> (* € Uie/ Bi U UjeJ Cj) A (x £ nie/ Bi n njeJ Cj) => x g U (B» u c,-) a x i p (Bi n C,-) =*► ie/ ie/ x g 'u (Bi u c,-) - p & n c,-) iei iei jeJ jeJ „D" Nechť x G U (Bi U C j) - f| (ßi n Cj), tedy x G U (Bi U Cj) A x <£ f] (Bi D Cj). iei iei iei iei JEJ j£J j£J j£J Zvolme «o & I, jo £ J pevně. Pokud x G ßj0 -ŕ- Cj0 pak x G IJie/ (Bi -=- Cj). Předpokládejme tedy, že x ^ ßj0 -=- Cj0. Tudíž buď x ^ ßj0 U Cj0 nebo x G ßj0 n Cj0. Rozlišme obě možnosti. V prvním případě víme, že x G |J (Bi U Cj) a tedy buď existuje í e I takové, že x G ßj, potom iei je J ovšem igBíť Cj0, nebo existuje j & J takové, že x G Cj, potom ovšem x G ßj0 -ŕ- Cj. Vždy tedy z € Uie-r(Bi^-Cr/). je J V druhém případě, tj. x G ßj0 n Cj0, vime, že x ^ p (Bi f] C j). Tedy buď existuje i G J takové, že ie/ je J x ^ Bi, potom ovšem x G Bí^-Cj0, nebo existuje j & J takové, že x ^ Cj, potom ovšem x G ßj0 -j-Cj. Ve všech případech jsme tedy dostali x G [Jiti (Bi -=- Cj) a inkluze je dokázána. jeJ 7. Pokud je I jednoprvková obě tvrzení zřejmě platí. Nechť dále I obsahuje aspoň dva prvky. (a) Platí. Nechť x G f)iei(A -=- Bi). Pak pro každé i G I platí x G A -=- ßj, tzn. buď x G A A x ^ ßj nebo x ^ A A x G ßj. Rozlišíme dva případy leiai^iaY obou ukážeme, že x G A -f- Hie/ Bj. Nechť nejdříve x G A. Pak podle předchozího x ^ Bi (pro libovolné i G I) a tedy x G A Ax ^ Hie/ Bj. Odtud x G A + f)ieIBi. Předpokládejme nyní, že x $. A. Pak podle předchozího x G ßj pro libovolné ie Ja tedy x ^ A Ax G f|ie/ Bi. Odtud opět iěíť f|i£/ Bi- (b) Neplatí. Stačí vzít j & I pevné a uvážit: A = B3■ ^ 0, ßj = 0 pro i ^ j. Potom f]ieI Sj = 0 a tedy A^-f]ieI Bi = A, přičemž A+-Bj = 0 a tedy f]ieI(A^-Bi) = 0. Uvědomme si, že předpoklad I ^ {j} jsme skutčně v tomto příkladu využili. 8. (a) AC{{0},{{0}}} (b) A = {{0}} nebo A = {0, {0}} (c) 10 řešení (d) A prázdný a systémy sestávající z jedné množiny. (e) A = {ß,ßU{0}} 9. Uvědomme si, že množina Ap je množina čísel, která mají v rozkladu na prvočinitele prvočíslo p. (a) „C" Zřejmě Ap C N — {1} a tedy platí i [JpeI Ap C N — {1}. „D" Libovolné přirozené číslo n, které je různé od 1, je dělitelné nějakým prvočíslem p a proto n G Ap. Odtud N — {1} C |J e/ Ap. (b) Sporem. Nechť x G p| e/ Ap. Pak existuje prvočíslo p > x, což je spor s předpokladem x G Ap. (c) Buď J neprázdná, konečná podmnožina /. Tj. J = {pit,Pi2, ■ ■ ■ ,Pik}- Potom n = pit ■ pÍ2 ■ ■ -pik G HpEjAp- 5 10. (a) „C" Nechť x e Ax (B U C), pak x = (y, z), kde y e A, z e B U C. Proto z G B V z G C. Tudíž (y, z) e A x B V (y, z) e A x C. Odtud x = (y, z) e (A x B) U (A x C). „D" Nechť x(AxB)U(AxC). Potom x e AxB\/x e AxC, tedy x = (a,b), kde a G A, b G B, nebo x = (k, /), kde k G A, l G C. Protože beBUC&leBUCv obou případech máme x G A x (B U C). (b) „C" Nechť x e (A- B) x C, pak x = (y, z), kde y e A - B,z e C. Proto y £ A Ay <£ B. Odtud (y, z) e AxC ale (y, z) <£ B xC. Celkem tedy x = (y, z) G (A x C) - (B x C). „D" Nechť x G (AxC)-(BxC). Potom x G (AxC)Ax <£ (B x C). Tedy x = (y, z), kde y e A, z e C. Pokud by y G B, pak x = (y, z) G (B x C), což je spor, a tedy y £ B. Proto y e A — B & tedy i x = (y, z) e (A- B) x C. (c) „C" Nechť x G A x [JieI Ai, pak x = (y, z), kde y G A, z G Uie/ ^i- Existuje tedy j G / takové, že z G Aj a proto x = (y, z) G A x Aj. Odtud x G Uie/(^ x ^«)- „D" Nechť x G [Jiei(A x Ai). Potom existuje j G / takové, že x G A x Aj. Tudíž x = (y, z), kde y E A, z e Aj. Odtud z G {JieI Ai a celkem x = (y, z) G A x [jieI Ai. (d) Sporem. Nechť x G (A x B) D (B x A). Potom x G (A x B) A x G (B x A). Proto x = (a, 6), kde a G A, b G B a zároveň x = (y, z), kde j/£ß,zGA Protože x = (a, 6) = (y, z) dostáváme a = y (a 6 = z). Ovšem a G A, y G B a tedy oGÄflíí, což je spor s předpokladem A n B = 0. 11. (a) Inkluze není splněna nikdy. Zřejmě 0 G P (A - B), ale protože 0 G P (A) a 0 G P (B) tak 0 £ P(A) - P(B). (b) 1. Pokud AC B potom P(A) C V (B), tedy P(A) - V (B) = 0 C P(A - B) D. 2. Pokud A n B = 0 potom A - B = A a tedy P(A) - V (B) C P(A) = P(A - B). 3. V ostatních případech neplatí. Podmínka A % B znamená existenci prvku a G A, a £ B. Podmínka An B ^ 0 znamená existenci prvku b G A, b G B. Nyní {a, 6} g A - B neboť b <£ A - B. Na druhou stranu {a, 6} C A, {a, 6} g B a tedy {a, 6} G V (A), {a, b} <£ V (B), celkem {a, 6} G V (A) - V (B). (c) Pokud 7 = 0, potom f|ie/^i = 0, ^(flie/^i) = M* flie/^O4») = 0 a rovnost neplatí. Pokud i" ť^ 0, pak rovnost platí. Důkaz: Pro libovolné X palatí: (V* g J)(X g V{Ai) ^ (Vi g J)(X C Ai) ^ XeV(f]ieIAi). (d) Pokud 7 = 0, potom \JieIAi = 0, P(Uie/^i) = {0}, Ue/^O4») = 0 a rovnost neplatí. Předpokládejme, že rovnost platí a označme A = {JieIAi. Protože A G V (A) dostáváme A G \JieIV(Ai). Existuje tedy jel tak, že A G P(A,). Tzn. Pro libovolné i G i platí Ai C Uie/^i = A C Aj. Naopak, pokud existuje j £ I tak, že pro libovolné i G I platí Aj C Aj, pak zřejmě V(Ai) C V(Aj) a tedy Uie/^^í) = ^(Aí)> na druhou stranu Uie/^i = A? a tedy rovnost platí. Ukázali jsme, že rovnost platí pro systémy, které splňují podmínku (3j G i")(Vi G -004-i í= Ar)-Poznamenejme, že tato podmínka zahrnuje i případ jednoprvkové množiny /. 4 Zobrazení 1. /(I) = /(2) = /(3) = a /(l) = /(2) = /(3) = * /(l) = /(2) = a, /(3) = /(l) = /(3) = a, /(2) = /(2) = /(3) = a, /(l) = /(l) = /(2) = i, /(3) = /(l) = /(3) = i, f (2) = f (2) = /(3) = i, /(l) = surjekce surjekce surjekce surjekce surjekce surjekce 9 (a) g(a) g(a) 9(a) = 1 g(a) = 1 g(a) = 2 g(a) = 2. gr(a) = 3 g (a) = 3. 3« = 3« = 3« = g( g( g( --1 = 2 = 3 ) = 2 ) = 3 ) = 3 ) = 1 ) = 1 S« = 2 injekce injekce injekce injekce injekce injekce 6 2. Počet všech zobrazení je ba. Injektivní zobrazení existuje právě tehdy, když a b. Bijektivní zobrazení existuje právě tehdy, když a = b. 3. Pro n-prvkovou množinu A má množina {0,1}A právě 2™ prvků a množina A x A má n2 prvků. Pro n > 6 platí 2™ > (n + l)2 > n2 dle příkladu z kapitoly o indukci. My však chceme aby 2™ < n2 a tedy v (a) i (b) je odpověď n G {2, 3, 4}. 4. (a) např. (36 G B)(3a G A)(f (a) = b). (b) např. A = {1, 2}, B = {a}. 5. (a) není zobrazení; f (2) = |2| ^]0,1[. (b) není zobrazení; /(O) není určeno jednoznačně (c) je zobrazení, surjekce, není injekce; /(3) = /(O). (d) je zobrazení, injekce, není surjekce; 1 ^ Im(f). (e) je zobrazení, není injekce ani surjekce; /(O) = f(2), 3 ^ Im(f). (f) není zobrazení; f (2) není určeno jednoznačně. (g) je zobrazení, není injekce ani surjekce; /((l, 3)) = /((3,1)), 0 ^ Im(f). (h) není zobrazení; /(Z) není určeno. (i) není zobrazení; /(0) není určeno. 6. Například je-li a = 4 A b = 0, jde o injektivní zobrazení, je-li a = 1 A b = 0, jde o surjektivní zobrazení. 7. /o<7 = 2x+l, f-1(x)=x + 2, ff-i(x) = |_|, gof = 2x-l, f o g-1 = § - f, 9o/-1=2x + 7 Při nahrazení množiny R množinou Z se výsledné předpisy nezmění, pouze zobrzení g^1 nebude existovat. 8. (a) Injektivita: Dokážeme, že /((xi,j/i)) = /((x2,ž/2)) => (^i,ž/i) = (^2,1/2); tj. 2*1-1(2Ž/1 - 1) = 2^-\2y2 - 1) => (x1)ž/1) = (x2,ž/2). Z jednoznačného rozkladu na prvočinitele máme (vzhledem k tomu, že 2X~X je mocnina 2 a 2y — 1 je liché číslo) 2Xi-x(2yi - 1) = 2X2-\2y2 - 1) => 2*1-1 = 2X2-\ 2y2 - 1 = 2j/i - 1. Odtud xi = x2, í/i = j/2) což jsme měli ukázat. Surjektivita: Dokážeme, že pro každé n G N existuje dvojice (x, y) G N x N tak, že n = 2x~1(2y — 1). 1 = 2° • (2 • 1 - 1), tedy f ((í, 1)) = 1 Libovolné přirozené číslo n (dle jednoznačnosti rozkladu na prvočinitele) zapsat ve tvaru n = 2k ■ l, kde k G N0, / G N liché. Potom f ((k + 1, ^)) = n, přičemž (/ + 1, '4±) G N x N. Inverze: Dle druhé části důkazu f^1 : N —> N x N je dáno předpisem /_1(n) = (k + 1, r^t+i ), kde A; G N je největší číslo s vlastností 2k\n. (b) Injektivita: Dokážeme, že f(x{) = f(x2) => x\ = x2; tj. x\ — a x2 — a --------- =--------- => xi = x2. b — x\ b — x2 Pokud jsou zlomky nalevo rovny, pak pronásobením a úpravou dostaneme (a — b)x\ = (a — b)x2, což vzhledem k a < b dává požadované. Surjektivita: Dokážeme, že pro každé y G M+ existuje x e]a, b[ tak, že y = f5f • Vyjádřením x: yb + a x = —------- 7 (Vzhledem k y G M+ lze provést dělení kladným číslem y + 1.) Zbývá ověřit, že x é\a, b[: yb + b yb + a y a + a b = -------- > -------- > --------- = a. í+y í+y í+y Inverze: Dle druhé části důkazu f^1 : R+ —>]a, b[ je dáno předpisem /_1(ž/) = \ta ■ 9. Spočítáme kompozice: 1. (g o f)(x) = g(f(x)) = g((—í)x[^\). Pro přehlednost rozlišme dva případy: x sudé nebo liché. Tedy pro x sudé, tj. x = 2a, kde a G N, máme [f J = «• Proto (g o f) (x) = g((—í)2aa) = g (a) = 2\a-\\ + \ = 2(a-\) + \ = 2a = x. Pro x liché, tj. x = 2a + 1, kde a G N0, máme [f J = o- Proto (g o f) (x) = g(( — í)2a+1a) = g (—a) = 2\ — a — ^ | + | = 2(a + |) + | = 2a + 1 = x. V obou případech tedy (g o f)(x) = x a proto g o f = idN. 2. (f o g) (y) = f (g (y)) = f(2\y — \\ + ^). Pro přehlednost rozlišme dva případy: y > 1 nebo y < 0. Tedy pro y > 1, máme 2|y - \\ + | = 2y a tedy (/ o g)(y) = f (2y) = (-l)2^ [f J = ž/- Pro y < 0, máme 2|y - ±| + \ = -2y + 1 a tedy (/ o <,)(y) = f (-2y + 1) = (_l)-2y+i|_^±ij = (-1) [~y +\\= (-1) • (-Ž/) = ž/- V obou případech tedy (/ o g) (y) = y a proto / o g = idz. 10. Injektivita. Dokážeme, že f (X) = f (Y) ^ X = Y. Platí f(X) = (xnA,xnB), f(Y) = (YnA,YnB), tj. pro X, Y C AuB platí XnA = YnA A XnB = YnB. Odtud X = Y; skutečně, pokud x e X C AuB, pak buď x G A nebo x G B, proto v prvním případě x e X P\A = Y P\A =>• x G Y a podobně v druhém případě x e X D B = Y D B =>• x e Y, tzn. X C y a pro opačnou inkluzi stačí zaměnit X &Y. Surjektivita: Dokážeme, že pro každé dvě množiny A\ C A, B\ C B existuje množina X C AU B taková,že f (X) = (A1,B1). Stačí položit X = Ax U Bx. Zobrazení inverzní k /: r1 : P (Ä) x P(B) -^ P (A U B), r1(A1,B1) =A1UB1 11. Injektivita: Dokážeme, že f (B) = f (C) =4> B = C, kde B, C C A. Rovnost f (B) = f (C) znamená, že množinám ß aCje přiřazena stejná charakteristická funkce

{0,1}, vztahem x G B <ŕ=> <£>(#) = 1 ^> x G C, tedy B = C. Surjektivita: Dokážeme, že pro každé zobrazení

{0,1} existuje B C A tak, že /(B) = je hledanou množinou B = {x G A\ V (A), p2 : P(A) x V (B) -> V (B) projekce. Pak hledáme F : {0, í}AuB -* {0, Í}A x {0, Í}B odpovídající zobrazení /. Tj. F(f) = (^AoPlofo ^JB (f),^Bop2ofo ^JB (■ {0,1} je ÝAiB(y>) = {x G iUß | (p (x) = 1}, dále pľ o /of^^) = {x G AuB \ ip(x) = 1} n A = {x G A | ^(x) = 1}. Odtud *A oPl o / o Y^fa) = C'4 x CB, F( x\ = x2- pro libovolné dva prvky x\, x2 G A. Pokud na prvek j(x\) = f(x2) aplikujeme zobrazení /n_1 dostaneme fn(xi) = fn(x2), tedy idA(xi) = idA(x2). Protože idA(xi) = xx a idA(x2) = x2, injektivita je dokázána. Surjektivita: Dokážeme, že pro libovolné a G A existuje b G A tak, že f (b) = a. Hledaným prvkem je b = fn^1(a). 8 14. (a) 1. pokud / a g jsou injektivní, pak g o f je injektivní. Důkaz: Nechť x,y taková, že (gof)(x) = (gof)(y). Odtud g(f(x)) = g(f(y)) a protože g je injektivní, máme /(#) = f(y)- Odtud z injektivity / plyne x = y a zobrazení g o f je injektivní. 2. pokud g o f je injektivní, pak / je injektivní. Důkaz: Nechť x,y taková, že /(#) = f(y)- Pak aplikací g dostaneme g(f(x)) = g(f(y)), tedy (gro f)(x) = (g° f)(y)- z injektivity g o f tdy plyne x = y. (b) 1. pokud / a g jsou surjektivní, pak g o f je surjektivní. Důkaz: Nechť c G C libovolný. Pak existuje b G B takové, že g (b) = c, protože g je surjektivní. Pro toto b G B pak existuje a e A takové, že f (a) = b. Celkem (gof)(a) = g(f(a)) = g (b) = c a zobrazení g ° f Je surjektivní. 2. pokud g o f je surjektivní, pak g je surjektivní. Důkaz: Nechť c G C libovolný. Pak existuje a G A takové, že (go f) (a) = c, neboť go f je surjektivní. Tedy g(f(a)) = c zobrazení g je surjektivní, protože prvek f (a) G B je vzor prvku c. 15. (a) =>•: Množina A je neprázdná, označme tedy nějaký její prvek a G A. Zobrazení / je injektivní, tj. pro každé b G Im(f) existuje právě jedno x G A s vlastností f (x) = b. Proto následující předpis korektně definuje zobrazení: a, b i Im(f) g:B^A, g(b) - ^ ^ b(_ /m(/)^ /(x) = b Snadno se vidí, že skutečně g o f = id^. <í=: id^i je injektivní a tedy / je injektivní dle předchozího příkladu. (b) =>•: Zobrazení / je surjektivní, tj. pro každé b G B existuje x G A s vlastností f (x) = b. Pro každé b G B označme některý prvek s touto vlastností x&. Můžeme definovat zobrazení h : B —> A, h(b) = xi,. Pak f o h = idß. <í=: Opět použitím předchozího příkladu. 16. (a) Například g = f. Zde nejsou třeba předpoklady. (b) Protože / není identita, existuje prvek a G A s vlastností f (a) ^ a. Definujme nyní zobrazení h : A —> A předpisem h(x) = a. Potom (h o f)(x) = h(f(x)) = a avšak (/ o h)(x) = f(h(x)) = f (a) ^ a, tudíž f o h y^ ho f. 17. Stačí dokázat, že pokud / je bijekce, potom F je bijekce. Nechť tedy / je bijekce, tj. existuje f^1 : B —> A. Definujme zobrazení G : Bc —> Ac vztahem G() = f^1 o 4>. Snadno se ověří, že F a G jsou vzájemně inverzní zobrazení. 5 Relace na množině, ekvivalence a rozklady množin 1. Relace na {0,1}: (a) 0 (prázdná relace) - sym., tranz., antisym.; (b) {(0,0)} sym., tranz., antisym.; (c) {(1,1)} sym., tranz., antisym.; (d) {(0,1)} tranz., antisym.; (e) {(1,0)} tranz., antisym.; (f) {(0,0), (1,1)} reflex., sym., tranz., antisym.; (g) {(0,0), (0,1)} tranz., antisym.; (h) {(0,0), (1, 0)} tranz., antisym.; (i) {(1,1), (0,1)} tranz., antisym.; (j) {(1,1), (1, 0)} tranz., antisym.; (k) {(0,1), (1,0)} sym.; 9 (1) {(0,0), (1,1), (0,1)} reflex., tranz., antisym.; (m) {(0,0), (1,1), (1,0)} reflex., tranz., antisym.; (n) {(0,0),(0,l),(l,0)}sym.; (o) {(l,l),(0,l),(l,0)}sym.; (p) {(0,0), (1,1), (0,1), (1,0)} reflex, sym, tranz. Relace na {0}: prázdná relace - sym., tranz., antisym.; {(0,0)} reflex., sym., tranz., antisym. Relace na 0: prázdná relace - sym., tranz., antisym. 2. Relace ekvivalence na množině A = {1, 2, 3}: idA = {(1,1), (2, 2), (3, 3)} {(1,1), (1,2), (2, 2), (2,1), (3, 3)} {(1,1), (1,3), (2, 2), (3,1), (3, 3)} {(1,1), (2, 2), (2, 3), (3, 2), (3, 3)} AxA např: / = {(1,1), (2,1), (3, 3)}, g = {(1, 2), (2, 2), (3, 3)}; zde / o g ± f, g o f = g; např:/ = {(1,2), (2,1), (3, 3)}; napni? ={(1,1), (2, 2), (3, 3), (1,2)}; např:/= {(1,2), (2,1), (3, 3)}; např: R = {(1,1), (2, 2), (3, 3)}, S = R U {(1, 2)}. např: R = 0. např: R = i?< nebo R = N x N nebo R< = {(a,b) e N x N \ a < b}. Pozn: nestačí vzít s U s2 = s U {(n, n + 2) | n G N}, neboť to není tranzitivní relace. Nejmenší relace (vzhledem k inkluzi) s požadovanou vlastností je relace i?<. např: R = i?< nebo R = {(a, b) G N x N | a ^ b}. Pozn: nikoli R< = {(a, b) G N x N | a < b}, neboť R (36 G B)((a, b) e R A (b, z) e T o S) ^=> (36 G B)(3y G C)((a, 6) G R A (b, y) G S* A (y, z) G T) a rovnost tudíž platí. (c) Pro y e A, x e C: (x, y) G (S o R)-1 «=^ (y,x)eSoR «=^ (3z G B) ((y, z) G R A (z, x) G S) «=^ (3z G B)((x, z) G S*"1 A (z, y) G i?"1) «=^ (x, y) e Ä"1 o S"1. (d) Pro x G A, y G C: (x, y) G S* o (i?! U i?2) ^=> (3z G B)((x, z) G i?i U i?2 A (z, y) e S) <*=> [(3z G B)((x, z) G i?i A (z, y) G S) V (3z G B)((x, z) G i?2 A (z, y) G S)] <*=> [(x, y) G S o Rx V (x, y) G S o R2] ^=> (x,y)e(SoR1)U(SoR2). (e) Pro x e A, y e C: (x, y) G S o (Ä! n i?2) <*=*> (3* € B)((x, z) G i?i n i?2 A (z, y) G S*) ==> [(3z G B)((x, z) G i?i A (z, y) e S) A (3z G B)((x, z) £ R2 A (z, y) G 5)] «=^ [(x, y) G 5 o Rx A (x, y) G S o R2] -^> (x,y)G(S'oi?1)n(S'oi?2). Opačná inkluze neplatí; stačí například zvolit A = B = C = {a, b}, i?i = {(a, a)}, i?2 = {(a, 6)}, S* = {(a, 6), (6, 6)}, kde R1C\R2 = 0, tj. So(R1n R2) = 0, ale S o Rx = S o R2 = {(a, b)}. (f) podobně jako (a),(c). (g) podobně jako (a),(c). (h) Pro x G A, y G C: (x,y)eSoR1-SoR2 ==> ((x, y) G S* o i?! A ((x, y) ^ S o R2). Existuje tedy z G B, takové, že (x, z) G R\ A (z, y) G S. Pokud by (x, z) G i?2, pak by (x, y) G S*o i?2, což neplatí a tedy (x, z) ^ R2. Odtud (x, z) G R\ — R2 a proto platí (x, y) G S* o (i?x — i?2). Opačná inkluze neplatí; stačí například zvolit A = B = C = {a, b}, i?x = {(a, a), (6, a), (6, 6)}, i?2 = {(6, 6)}, S = {(a, b), (b, b)}, kde SoR1 = {(a, b), (b, b)}, SoR2 = {(b, b)}, So(R1-R2) = {(a, b), (b, b)}. 17. (a) např. xpy ■& (x = 1) A (y = 1); nejmenší p = 0; (b) např. xpy ■& x = y; nejmenší p = 0; (c) např. xpy <(=> (y = 1) V (y = 2); nejmenší vzhledem k inkluzi neexistuje, minimální vzhledem k inkluzi jsou relace p = {(a, 6), (6, a), (c, tí)}, kde a 7^ b, c ^ d, (c, tí) ^ {(a, 6), (6, a)}. (d) např. xpy ■& x, y dávají stejný zbytek po dělení 2; nejmenší vzhledem k inkluzi neexistuje, minimální vzhledem k inkluzi jsou relace p = {(a, 6), (6, a)}, kde a^b. (e) např. xpy ■& x < y; nejmenší vzhledem k inkluzi neexistuje, minimální vzhledem k inkluzi jsou relace p = {(a, 6)}, kde a^b. (f) xpy <(=> (x < y) V (x = 2); nejmenší vzhledem k inkluzi neexistuje, minimální vzhledem k inkluzi jsou např. relace p = {(a, 6), (6, a), (c, tí)} U {(x, x) | x G N}, kde a, 6, c, tí jsou navzájem různé prvky. (g) neexistuje. 18. (a) f je injektivní zobrazení; (b) f je surjektivní zobrazení. 19. Sjednocení libovolného počtu reflexivních, resp. symetrických relací je rexlexivní, resp. symetrická relace. Sjednocení tranzitivních relací nemusí být tranzitivní relace. Např. pro dvouprvkovou množinu A = {a, 6} jsou relace {(a, 6)} i {(6, a)} tranzitivní ale jejich sjednocení tranzitivní relace není. Průnik libovolného počtu reflexivních, resp. symetrických, resp. tranzitivních relací je reflexivní, resp. symetrická, resp. tranzitivní relace. Zde jsme měli na mysli vždy neprázdné sjednocení a průniky. V případě prázdných systémů je sjednocení i průnik prázdná relace, která je symetrická a tranzitivní relace, ale není reflexivní. 12 20. Odpověď je kladná v příkladech (a) — (g) pro nejmenší relace ß „nad" danou relací; vždy se jedná o průnik všech relací s touto vlastností. (Relace A x A je relace ekvivalence a jedná se tedy vždy o neprázdný systém, který obsahuje tuto relaci A x A — viz předchozí příklad.) V případě (h) je odpověď ne; stačí vzít libovolnou relaci a, která není antisymetrická a potom neexistuje antisymetrická relace ß s vlastností aC/J. Odpovědi v případě největší relace obsažené v dané relaci a jsou většinou negativní. V následujících protipříkladech máme na mysli relaci a na množině A = {a, 5, c}, pro niž neexistuje největší relace /3Ca dané vlastnosti. (a) 0; (b) existuje; ß je sjednocení všech symetrických relací obsažených v a; (c) {(a, 6), (6, a)}; (d) 0; (e) 0; (f) {(a, a), (5, 5), (c, c), (a, 5), (5, a), (5, c), (c, 6)}; (g) {(a, a), (5, 5), (c, c), (a, 6), (6, a), (5, c), (c, 6)}; (h) {(a, 6), (6, a)}. 21. Dichotomická relace je vždy reflexivní. Pro libovolné a ^ b G A obsahuje dichotomická relace R buď (a, 6) nebo (6, a). Tj. pro tuto dvojici a y^ b e A máme tři možnosti jak vypadá neprázdná množina R P\ {(a, 6), (6, a)}. Existuje celkem 3© dichotomických relací. Existuje pouze jedna relace, která je symetrická a dichotomická zároveň. Tvrzení o složení reflexivních relací platí, podstatná vlastnost tohoto složení totiž je, že obsahuje sjednocení všech těchto relací. Opak tvrzení neplatí. 22. (a) neplatí, (b) platí. Obecně lze dokázat, že n-tranzitivita implikuje m-tranzitivitu, pokud n — 1 dělí m — 1. 6 Uspořádané množiny i. 2. 3. (a; (b; (c (d (e; (f (g (a (b; (c (d (a (b; (c uspořádání, které není lineární, různé prvky jsou nesrovnatelné, tj. protiřetězec; lineární uspořádání; není uspořádání, neboť není reflexivní relací; uspořádání, které není lineární, od (a) se liší pouze tím, že 4 je největším prvkem který pokrývá ostatní nesrovnatelné prvky; není uspořádání, neboť není antisymetrickou relací; není uspořádání, neboť nesplňuje žádnou z definičních podmínek; lineární uspořádání; diagram: nejdříve lichá čísla dle velikosti a „nad" nimi všechna sudá čísla opět dle velikosti. jednoprvková uspořádaná množina; dvouprvková uspořádaná množina, 0 nejmenší prvek a A největší prvek; čtyřprvková uspořádaná množina, diagram: „kosočtverec postavený na špičku"; osmiprvková uspořádaná množina, diagram: „krychle postavený na špičku". Maximální prvky: a, 6, c; minimální prvky: a, 6, c; největší ani nejmenší prvek neexistuje. Maximální a největší prvekk: c; minimální a nejmenší prvek: c. Maximální prvky: 6, c, d; minimální prvky: a, d; největší ani nejmenší prvek neexistuje. 13 (d) Maximální a největší prvekk: {a, b}; minimální a nejmenší prvek: 0. 4. (a) dva maximální a dva minimální, žádný nejmenší a žádný největší; (b) jeden největší a tedy i maximální, dva minimální, žádný nejmenší; (c) jeden nejmenší a tedy i minimální, dva maximální, žádný největší; (d) jeden prvek který je zároveň minimální i maximální, kromě něj jeden minimální a jeden maximální, žádný nejmenší a žádný největší. 5. (a) 3 relace uspořádání, pouze 2 pokud nás zajímá celkový počet uspořádání až na přejmenování prvků; (b) 19 uspořádání, resp. 5 až na přejmenování prvků. 6. ({1, 2, 3,4, 5, 6, 7}, R): maximální prvky 4, 5, 6, 7, nejmenší prvek 1, největší prvek neexistuje. (N, R): maximální prvek neexistuje, nejmenší prvek 1. 7. Supremum a infimum libovolné konečné neprázdné podmnožiny M C N existuje; infimum je největší společný dělitel, supremum je nejmenší společný násobek. Infimum existuje dokonce i pro nekonečné podmožiny, supremum existuje pro prázdnou podmnožinu. 8. Relace R je reflexivní, stačí za c zvolit 1. Tranzitivita: (x, y) G R A (y, z) G R => (3c G R)(c > 1 A ex = y) A (3d G l)(á > í Ady = z). Odtud z = dcx kde de > 1 a tedy (x, z) G R. Antisymetrie: (x, y) e R A (y, x) e R ==> (3c G R) (c > 1 A ex = y) A (3d G R) (tí > í Ady = x). Odtud x = dcx a tedy de = 1, což vzhledem k c > l,d> 1, dává c = d = 1 a tedy x = y. Diagram: má tři vzájemně nesrovnatelné části. Jednak reálná kladná čísla uspořádaná podle velikosti, druhák reálná záporná čísla uspořádaná opačně podle velikosti, a konečně nulu, která není srovnatelná s žádným prvkem. Množina má tedy jeden prvek, který je minimlní a maximální zároveň. 9. (a) např. první příklad z 4; (b) čtyřprvkový protiřetězec; (c) nelze, konečná uspořádaná množina musí mít aspoň jeden maximální prvek. 10. (a) např. první příklad z 4, nebo čtyřprvkový protiřetězec; (b) např. množina všech přirozených čísel uspořádaná dle velikosti s přidaným jedním nesrovnatelným prvkem; (c) nelze, má-li množina nejmenší prvek, pak se jedná o jediný minimální prvek; (d) např. celá čísla uspořádaná dle velikosti s přidaným jedním prvkem, který je menší než kladná, větší než záporná a nesrovnatelný s 0; (e) protiřetězec. 11. (a) je uspořádání; (b) není uspořádání, např. pro lineární uspořádání R není i? U R^1 uspořádání; (c) je uspořádání; (d) není uspořádání, např. pro A = {a, b} a uspořádání i?x = {(a, a), (a, 6), (6, 6)}, R2 = {(a, a), (6, a), (6, 6)} je i?x o R2 = A x A. 12. Součin řetězců obecně není řetězec. 13. Do relace < nepřibude nic nového; tedy budou spolu v relaci zase jen ty prvky, které spolu byly i v relacích relace ■< je lineární. 15. (a) je izotonní, není izomorfismus; (b) je izotonní, je izomorfismus; 14 (c) je izotonní, není izomorŕlsmus; (d) není izotonní, napr. —3 < 1 ale (—3)2 < l2 neplatí; (e) není izotonní, napr. —4 < 2 ale | — 4| < |2| neplatí; (f) je izotonní, není izomorŕlsmus; to platí pro libovolné konstantní zobrazení; (g) je izotonní, není izomorŕlsmus; to platí pro libovolnou „inkluzi"; (h) je izotonní, není izomorŕlsmus. 16. Celkem 15 izotonních zobrazení. 17. Existuje celkem 8 automoríismů uspořádané množiny {a, 6, c, d, e, /}: 1) id; 2) b i-» 6, o i-» a, C 1—> c,/ i—> /, eí i—> e, e i—> d 3) b i—> 6, a i—> c, C 1—> a,/ 1—> /', tí 1—> tí, e i—> e 4) b i—> 6, a i—> c, C 1—> a,/ i—> /, cí i—> e, e i—> d 5) b »f, f »b, a i—> tí, c i—> e, tí i—> a e i—> c 6) b »f, f »b, a i—> tí, c i—>■ e, ■ c, e i—> a 7)5 »f, f »b, a i—> e, c i—>■ cř, cř i—>■ c 8) b »f, f »b, a i—> e, c i—>■ cř, cř i—>■ c, e i—> a 18. (a) Takový příklad nelze zkonstruovat na konečné množině. Vezměme množinu celých čísel Z a označme S, resp. L, podmnožinu všech sudých, resp. lichých, čísel. Na Z definujeme uspořádání < následujícím předpisem: x ľi V '^=^* x < y A (x x < q a dále jedno izotonní zobrazení e dané předpisem: e(x) = 0 <ŕ=> x < q. Konečně pro libovolné iracionální číslo r existuje izotonní zobrazení u> dané předpisem: u>(x) = 0 x < r. 20. Pro u> existuje pouze jeden automorfismus a to identita, pro u> x u> existuje kromě identity ještě jeden automorfismus a to výměna souřadnic. Pro Z existuje nekonečně mnoho izotonních zobrazení: pro A; G Z předpis i^i+fc zadává automorfismus; žádný další není. Pro Z x Z se nakombinuji tyto automoriismy s identitou a výměnou souřadnic. Tj. pro k, l G Z máme automorfismus daný předpisem (x, y) i-^ (x + k,y + l) a také automorfismus daný předpisem (x,y) i-> (y + k,x + l). 7 Úplné svazy 21. (a) není svaz, dvouprvková podmnožina prvků z „druhého patra" nemá supremum; (b) je svaz; (c) je svaz; (d) je svaz. 15 22. Je jich pět (až na izomorfismus, tj. přejmenování prvků). K libovolné tříprvkové uspořádané množině se přidá nejmenší a největší prvek. 23. (a) je úplný svaz; (b) je svaz, infimum konečné množiny je průnik, supremum konečné množiny je interval jehož krajní bod dostaneme jako nejmenší, resp. největší, krajní bod jednotlivých intervalů. Úplný svaz to není. Vezměme například systém intervalů {(0, x) | x > 1} — tato množina nemá infimum. (c) je svaz — infimum je průnik, supremum sjednocení, není úplný svaz — nemá největší prvek, neexistují nekonečná suprema; (d) je úplný (jednoprvkový) svaz; (e) je svaz — infima n.s.d, suprema n.s.n, není úplný svaz — neexistuje největší prvek; (f) je úplný svaz — největší prvek 0, nejmenší 1, infima jsou n.s.d. (zjednodušeně řečeno: konečná suprema jsou n.s.n, nekonečná jsou rovna 0). (g) je svaz, není úplný svaz — neexistuje největší prvek; (h) je svaz, není úplný svaz — neexistuje nejmenší prvek; (i) je úplný svaz — největší prvek A x A, nejmenší prvek „diagonála", infima jsou průniky, suprema — tzv. tranzitivní obal sjednocení — zde je dobře vidět aplikace příslušné věty, že stačí existence všech infim. 24. Vše se počítá „po složkách". 25. (a) Označme A = aAb,B = bAc,C = cAa& dále X = a\/ b, Y = bV c, Z = cV a. Nyní vidíme, že A < a < X a podobně A < b < Y, A < a < Z. Je tedy A dolní závora množiny {X, Y, Z} a tedy menší než její infimum. Tzn. A < X A Y A Z. Stejným způsobem dostaneme B < X AY A Z, C < X AY AZ. Prvek X A Y A Z je tedy horní závora množiny {A, B, C} a proto je větší než její supremum A V B V C, tzn. A\/ B V C < X AY A Z což jsme měli dokázat. (b) Podobně. 8 Základní algebraické struktury 2. a b c 3. a b c 4. Pologrupa, neutrální prvek je 0, nulový prvek neexistuje, je to komutativní grupa. Pologrupa, neutrální prvek 1, nulový prvek je 0, není grupa, je komutativní. Pologrupa to není: 1 — (2 — 3) ^ (1 — 2) — 3, neutrálni a nulový prvek nemá (pozor 0 je pouze pravý neutrální prvek), grupa není, není komutativní: 1 — 2^2 — 1. Pologrupa, neutrální prvek nemá, nulový prvek je 1, grupa není, je komutativní. Je komutativní pologrupa, neutrální prvek je X. Je komutativní pologrupa, neutrální prvek je 0. Není pologrupa, není komutativní, neutrální prvek nemá. Je komutativní pologrupa, neutrální prvek je 0 (dokonce je to i grupa). Komutativní je, asociativní není: a o (b o c) ^ (a o b) o c, neutrální prvek nemá. Komutativní je, asociativní není: c o (a o a) ^ (c o a) o a, neutrální prvek b. Komutativní není: a o b ^ b o a, asociativní je, neutrální prvek nemá. (pon) ocr = {(x,y)\3z G X : (x, z) G er, (z, y) G p o n} = {(x,y)\3z, u G X : (x, z) G a, (z, u) G n, (u, y) G p} 16 podobně p o (jr o a) = {(x, y)|3a G X : (x, a) G 7t o a, (a, y) G /?} = {(x, y) \3a, 6 G X : (x, 6) G a, (6, a) G n, (a, y) G p} a rovnost je evidentní. (Jiný zápis viz. př. 16(b) v kapitole o relacích.) Neutrálním prvkem je „diagonála" {(x, x)|x G X}, nulový prvek je prázdná relace. Pro prázdnou a jednoprvkovou množinu je každá relace symetrická a tudíž jde o grupoid. Pokud obsahuje alespoň dva různé prvky a, 6, pak pro p = {(b, b)}, n = {(a, 6), (6, a)} není relace pon = {(a, 6)} symetrická. Obecně tedy nejde o grupoid. Pokud |X| < 1, je každá relace tranzitivní a jde tudíž o grupoid. Pokud množina X obsahuje aspoň tři různé prvky a, 6, c, pak pro p = {(a, a), (6, c)}, n = {(a, 6), (c, c)} není relace n o p = {(a, 6), (6, c)} tranzitivní. V případě |X| = 2 lze ukázat, že složení dvou tranzitivních relací je tranzitivní relace. Intuitivně je důvodem fakt, že existuje velmi málo netranzitivních relací. Obecně tedy nejde o grupoid. 5. Skládání zobrazení i relací je asociativní operace, jak jsme již dokázali v předchozím. Složení injektiv-ních (resp. surjektivních, resp. bijektivních) transformací je injektivní (resp. surjektivní, resp. bijektivní). Všechny množiny obsahují identitu a proto se jedná o monoidy. Pro konečnou množinu X jsou všechny tři množiny stejné a tvoří grupu. Pro nekonečnou množinu X tvoří grupu pouze bijekce. V případě parciálních transformací: X konečná množina — surjektivní a bijektivní transformace jsou permutace a jedná se o grupu, injektivní tvoří pouze monoid; X nekonečná množina — pouze monoid ve všech případech (odečtení 1 na množině N je příkladem parciální transformace, která je injektivní i surjektivní, ale neexistuje k ní inverze, neboť příslušná kompozice nemůže být identita, neboť 1 nepatří do definičního oboru). 6. Operace je obecně asociativní, proto je asociativní i na dané množině O. Prvek 0 je nulový prvek, neutrální prvek neexistuje. Grupa to není. 7. a) Ne. Neexistuje neutrální prvek b) Ano. c) Ano. d) Ano. e) Ano. 8. a) Předpokládáme, že platí ab = inverzní k a, označme ho a 1, a vynásobme jím rovnici zleva. Pak a~ (ab) = a~ (ac) (a~ a)b = (a~ a)c eb = ec b = c Přitom e je neutrální prvek. Podobně pravý zákon o krácení, pouze prvkem a-1 násobíme zprava, b) (N,.),(N,+); c) o a b c a b c a b a b c c c a b L- L- U/ U Asociativní není, neboť (a o b) o c ^ a o (b o c). 17 o a b c a a b c b b c a c c a b o a b c a c a b b a b c c b c a o a b c a b c a b c a b c a b c d) Tyto tři grupy jsou izomorfní (a jsou izomorfní (Z3, +)). Pokud zvolíme neutrální prvek lze tabulku doplnit jediným způsobem. e) Je jich celkem 16 — po vybrání neutrálního prvku máme vždy 4 možnosti jak tabulku doplnit. Všechny grupy jsou komutativní. Až na izomorfismus jsou právě dvě — buď každý prvek x má vlastnost, že x ■ x je neutrální prvek, nebo tuto vlastnost nemá. Podle toho poznáme, zda je grupa izomorfní (1^,+) x (Z2,+) nebo (Z4,+). 9. a) Sčítání je operace, množina všech matic nad celými čísly s operací sčítání je komutativní grupa, neutrální prvek je matice 0 0 0 0 a prvky navzájem inverzní jsou matice b a c d a, 6, c, tí G Násobení je operace, je asociativní, není komutativní. Neutrální prvek je E = 1 0 0 1 grupa vzhledem k násobení to není. Množina všech matic nad Z spolu s operacemi sčítání a násobení tvoří nekomutativní okruh, kvůli nekomutativitě není ani obor integrity, ani těleso. b) Stejné. c) Sčítání není operací. Např. fí 0\ f-í 0 \_ /O (^ V° V + V° -V V° °y kde první dvě matice jsou regulární a jejich součet není regulární matice. Násobení je operace. Matice spolu s násobením tvoří nekomutativní grupu, inverzní prvky vzhledem k násobení jsou matice a b c d 1 ad — be a, 6, c, tí G Množina všech regulárních matic nad Q spolu s operacemi sčítání a násobení netvoří okruh, d) Sčítání není operace, protože 1 a 0 1 1 b 0 1 a + b 2 neleží v dané množině matic. Násobení je operace, je komutativní a asociativní, neutrální prvek je E, navzájem inverzní prvky jsou matice '\ a\ í\ —0s v0 l) & \0 1 tedy množina takových matic spolu s násobením tvoří komutativní grupu. (Tato grupa je izomorfní grupě (R,+).) e) Sčítání není operace. Násobení je operace, je asociativní, není komutativní, neutrální prvek je E, není grupa. 18 10. (A, +, •) je obor integrity, inverze existuje ke všem prvkům množiny to, p G Z — {0}, 3 { to, p p (B, +, •) je obor integrity, inverze existuje ke všem prvkům množiny ±3m, n, to G N 11. (Z2, +, •) x (Z3, +, •) není oborem integrity, neboť obsahuje dělitele nuly: ([0]2,[1]3).([1]2,[0]3) = ([0]2,[0]3). Je izomorfní s okruhem (Z6,+, •), protože existuje izomorfismus /: Z6 —► Z2 x Z3 daný předpisem /(KU) = (H2, W3)) c°ř není obtížné ukázat. 12. a) a(a + 6) = 3a+6 = 3a • 36 = a(a) • a(6), kera = {0}, Ima = R+. b) /3(a + 6) = ia+b = ia -ib = ß(a) •/3(6), ker/3 = {z G Z;4|z} = [0]4, /to/3 = {1, -1, i, -i}. c) 7((a + 6i) • (c + eři)) = 7(ac — 6tí + (ad + 6c)i) = = \/(ac -bd)2 + (ad + 6c)2 = v^c2 + 62d2 + a2d2 + 62c2 = = \Ja2 + b2 ■ \Jc2 + d2 = 7(a + bi) ■ 7(0 + di), ker7 = {a + 6i GC*|a2 + 62 = 1}, Jto7 = R+. 13. a) a homomorfismus, b) ß není zobrazení, c) 7 izomorfismus, d) ô izomorfismus, e) e není zobrazení, f) ( homomorfismus, g) rj není zobrazení, h) 9 je zobrazení, není homomorfismus, i) 1 homomorfismus. 14. kera = {([0]4, [0]3), ([2]4, [0]3)}, Ima = {[0]12, [2]12, [4]12, [6]12, [8]12, [10]12} ker 7 = {1}, Irrvy = Q* ker S = {[0]i5}, ImS = Z5 x Z3 kerC = {[0]4,}, ImC = {l,-l,i,-i} ker 1 = {2k\k e Z} = [0]2, Imi = Z2. 15. '\ a b\ (l d e\\ //l a + d e + 6 + a/N /||0 1c-0 1/=/0 1 f + c \\=a + d-f-c, vo 0 1/ \0 0 1// \\o o 1 rl a 6\\ I l\ d, e> /I |0 1 c +/ 0 1 /|| =a-c + d-/. V° ° V/ VV° ° h 16. Není homomorfismus okruhů. Snadno se ověří, že platí f((a + bi) + (c+di)) = f(a + bi) + f (c+di), ovšem pro součin požadovaná rovnost nevyjde: f ((a, + bi) ■ (c + di)) = f(ac — bd + (6c + ad) i) = ac — bd + bc + ad f (a + bi) ■ f(c + di) = (a + b)(c+ d) = ac + ad + bc + bd. Tedy konkrétně, např. f (i • i) = f(-í) = -1^1 = 1-1 = f (i) • f (i). 19 17. Množina Q (a/3) je nekonečná (a tedy alespoň dvouprvková). Zřejmě 0,1 G Q(a/3). Snadno též nahlédneme, že množina je uzavřena na sčítání i násobení. Dále pro a, 6 G Q platí (a + 5a/3) + ((—a) + (—5)a/3) = 0 a existuje tedy prvek opačný. Pokud c + dy/3 ± 0 (všimněme si, že c + d a/3 = 0, c, d G Q implikuje c = d = 0), pak též c — di/Š ^fla platí: 1 1 c — dy/Š c — dy/3 c —d r- „ / /--. :VŠeQ(VŠ). c + dVŽ c + dVŽ c-dVŽ c2-3d2 c2-3d2 c2-3d2 Tedy (Q(a/3),+,-) je těleso. Buď a : Q (a/3) —> C okruhový homomoriismus. Potom a(l) = 1, tedy i a(2) = a(í + 1) = a(l) + a(l) = 1 + 1 = 2. Podobně lze nahlédnout, že a(n) = n pro libovolné n G N. Dále 0 = a(0) = a(í + (—1)) = a(l) + a(—1) = 1 + a(—1) a odtud a(—1) = —1. Použitím vlastnosti homomorfismu dostaneme pro libovolné n G N: a(—n) = a((—1) • n) = a( — 1) • a(n) = (—1) • n = —n. Tudíž a(n) = n pro libovolné n G Z. Ukážeme totéž pro libovolné n G Q a to nejdříve pro čísla tvaru -. Platí a(-) ■ n = a(-) ■ a(n) = a(— ■ n) = a(l) = 1, tedy a(-) = nT1 = -. Pro libovolná p,q G Z — {0} tedy máme a(-) = a(p) ■ a(-) = p ■ - = -. Čímž jsme dokončili důkaz, že a(r) = r platí pro libovolné r G Q. Označme dále w = a(i/3) G C. Potom podle vlastností homomorfismu máme pro libovolný prvek a+6i/3 G Q(a/3) následujícíc rovnost: a(a + 6a/3) = a(a) + a(b) ■ a(i/3) = a + b ■ iv. Tzn. homomoriismus je zcela popsán hodnotou weC. Pokusme se tedy určit všechny možné hodnoty u>. Opět ze základních vlastností máme: to2 = a(\/3) • a(\/3) = a(\/3 • a/Š) = a(3) = 3. Tedy to je takové komplexní číslo, pro něž platí J2 = 3. Vidíme tedy, že buď w = a/3 nebo w = —a/3. První možnost vede k tomu, že a. je identita, která je homomorfismem. Druhá vede k předpisu a(a + 6a/3) = a — 6a/3 o kterém se již snadno dokáže, že zadává homomoriismus. Existují tedy dva homomoriismy, které nejsou izomoriismy. Lze však nahlédnout, že se jedná o automorfismy okruhu Q(a/3). 9 Kombinatorika 1. Spočítáme postupně počet čtverců s délkou strany n+í—i. Celkový počet tedy je 5^ľ=i *2 = ^^—(j —■ 2. Soubor 28 kostek domina sestává z 7 kostek, které mají stejné poloviny, říkejme jim kostky typu A, a 21 = (2) kostek, které mají odlišné poloviny, typ B. Dvě kostky, které lze k sobě přiložit, lze vybrat tak, že buď vybereme dvě kostky typu B, nebo po jedné kostce od obou typů. Dvě kostky typu B: Vybereme společnou hodnotu: 7 možností; posléze dvě čísla ze zbylých 6, kde nám nezáleží na pořadí: (2), tj. dohromady 7 • (2) = 7 • 15 = 105 možností. Kostky obou typů: Vybereme kostku typu A: 7 možností; posléze doplníme jedno číslo ze zbylých 6, tj. dohromady 7 • 6 = 42. Celkem 147. 3. (a) 5! = 120; (b) 4! = 24; z A a B uděláme „dvojpísmeno" AB; (c) 60; vybereme nejdříve dvě místa, kdy budou mluvit A a B (v tomto pořadí), tj. (2) = 10 a zbylá 3 4. místa obsadíme libovolně řečníky C, D, E, tj. 3! = = 6 možností. (a) 4! = 24; (b) 6 • 5 • 4 • 3 = 360; (c) 5 • 5 • 4 • 3 = 300. Sudá čísla: (a) 2 • 3 • 2 • 1 = 12, začneme obsazovat odzadu; (b) 2 • 5 • 4 • 3 = 180; (c) obsadíme nejdříve první a poslední místo: první sudé: 2 • 2 možnosti, první liché 3 • 3 možnosti, celkem 13 dvojic první+poslední. Zbylá dvě místa: 4 • 3. Celkem 13 • 12 = 156. 20 Čísla dělitelná čtyřmi: Záleží na posledním dvojčíslí - musí být dělitelné 4, tj. především sudé. (a) Možná dvojčíslí: 12, 32, 24. Tzn. celkem 6 čísel. (b) 8 možných dvojčíslí, celkem 96 čísel. (c) 4 dvojčíslí bez použití 0, lze doplnit 3-3 možnostmi, 3 dvojčíslí s použitím 0, lze doplnit 4-3 možnostmi. Celkem 4 • 9 + 3 • 12 = 72 čísel. 5. («) = 15. 6. Pokud vybereme dvě dívky máme (2) • (4) = 210 možností, pokud tři dívky (3) • (3) = 140 možností, pokud čtyři dívky (4) • (2) = 21 možností. Celkem 371. 7. 2 + 22 + 23 + 24 = 30. 8. Nejdřív vybereme osazenstvo dvoulůžkového pokoje: (2) = 28 možností. Poté vybereme osazenstvo prvního trojlůžkového pokoje: (3) = 20. Celkem 28-20 = 560 možností. K výsledku dojdeme i když začnem obsazovat nejdříve trojlůžkové pokoje: (3)(3). 9. Použijeme distributivní zákon na součin (a + b)(a + b)(a + b) ■ ■ ■ (a + b). Potřebujeme pouze určit, kolikrát se objeví sčítanec a%bn~% v součtu po roznásobení. Ten vznikne tak, že z i závorek vybereme a a ze zbylých b. Tj. sčítanec albn~l tam bude (™)-krát. 10. Tradiční trik s přihrádkami. Do 6 přihrádek rozdělujeme 15 předmětů. Každou konfiguraci tedy můžeme zakódovat jako posloupnost patnácti 0 (míčky) a pěti 1 (oddělovače přihrádek). Tzn. celkový počet určíme tak, že vybereme 5 míst v dvacetičlenné posloupnosti kam dáme 1 (oddělovač). Tj. (25°). Liší se pouze tím, že na začátku dáme každému dítěti po jednom míčku a poté řešíme stejnou úlohu jako byla předchozí pro 6 dětí a 9 míčků. Odpověď (g4) možností. 11. V podstatě se jedná o stejnou úlohu jako byla předchozí. Hodnota Xj značí kolik míčků (jednotek) dostane i-té dítě, přičemž celkový počet míčků (jednotek) je n. Tedy ("^J^1) řešení v množině celých nezáporných čísel. V množině přirozených čísel nejdříve „rozdáme všem po míčku". Tj. pro k > n nemá rovnice řešení. Pro k < n máme (^Z{) řešení. 12. Přidáme k + 1 proměnnou xk+i = n — (xi + .. .xj.) a převedeme na předchozí úlohu. Tedy v množině celých nezáporných čísel má nerovnice ("^ ) řešení. V množině přirozených čísel: nejdříve „rozdáme všem po míčku". A poté řešíme úlohu stejným trikem jako pro nezáporná čísla. Tj. pro k > n nemá nerovnice řešení. Pro k < n máme (™) řešení. 13. Označme postupně „přírůstky" x\ = a\ — 1,X2 = a-^ — «i, • • -Xk = ak~«fc-i- Protože naopak z posloupnosti (xi, X2, • • • Xk) je původní posloupnost (ai, 02,... aj.) jednoznačně určena vztahy a\ = 1 + xi, 02 = 1 + x\ + X2,..., afc = 1 + x\ + X2 + • • • + Xfc, je počet posloupností stejný jako počet řešení nerovnosti 1 + xi + x2 + • • • + x/. < n v množině nezáporných celých čísel (nerovnost jsme dostali z podmínky ak