FUNDAMENTALNI PRIKLADY PRO CVICENI 1-6 PARAGRAF 1: zakladni logicke pojmy a matemat. indukce [1.1.B12b]Matematickou indukci dokazte, ze plati pro vsechna prirozena: 2n-1 n! (1) DUKAZ: Pro n = 1 plati 20 1!, tedy 1 = 1, coz plati. Predpokladejme tedy, ze tvrzeni plati pro n - 1 (indukcni predpoklad), tedy 2n-2 (n - 1)!. Dokazme, ze odtud plyne (1). Plati n! = n(n - 1)! 2 2n-2 = 2n-1 . Nerovnost uvnitr je platna z indukcniho predpokladu a z toho, ze n 2. [1.1.B13]Necht n znaci libovolne prirozene cislo. Uvazme tvrzeni: 2 + 4 + 6 + + 2n = (n + 2)(n - 1). (2) Pak ukazte, ze: a) uvedene tvrzeni neplati pro zadne prirozene n b) uvedene tvrzeni lze 'dokazať matematickou indukci, vynechame - li v ni 1. krok (tzn. vidime, ze 1. krok nelze pri dukazu matematickou indukci vypustit). DUKAZ: a) Staci si na leve strane rovnosti (2) povsimnout, ze soucet prvniho a posledniho, druheho a predposledniho je porad stejne cislo (napr. pro 2+4+6+8+10+12, je 2+12=14,4+10=14, 6+8=14 atd.), tedy obecne pro n liche bude soucet na leve strane rovnice (2) roven (2 + 2n)n-1 2 + 2+2n 2 = n2 + n, coz neni rovno (n + 2)(n - 1). Pro n sude bude soucet take (2 + 2n)n 2 = n2 + n. Tim je dukaz dokoncen. b) Pokud v matemat. indukci vynechame 1.krok, rovnost skutecne 'dokazeme', tedy necht tvrzeni plati pro n - 1 (indukcni predpoklad) 2 + 4 + 6 + + 2(n - 1) = (n + 1)(n - 2). Dokazeme, ze plati 2 + 4 + 6 + + 2n = (n + 1)(n - 2). Tedy musime dokazat (n + 1)(n - 2) + 2n = (n + 2)(n - 1), coz je n2 + n - 2 = n2 + n - 2. Dukaz timto zpusobem je ale nespravny, protoze jsme prave vynechali prvni krok. [1.1.B15]Posloupnost prirozenych cisel u1, u2, u3, . . . je definovana rekuretne takto: u1 = 1, u2 = 1, un+2 = un+1 + un pro n 1 (tato posloupnost se nazyva Fibonacciho posloupnost a jeji cleny se nazyvaji Fibonacciho cisla). Dokazte, ze plati: un+s = un-1 us + un us+1 pro n 2 cele , s N. (Navod: dukaz vedte matematickou indukci vzhledem k s.) DUKAZ: Pro s = 1 dostavame un+1 = un-1u1+unu2, kde u1 = 1, u2 = 1, tedy un+1 = un-1+un, coz je Fibonacciho posloupnost. Predpokladejme, ze rovnost plati pro s - 1, tedy plati, ze un+s-1 = un-1 us-1 + un us (indukcni predpoklad). Dokazme, ze odtud plyne un+s = un-1 us +un us+1. Predevsim plati, ze un+s = un+s-1 +un+s-2. Dosadme z indukcniho predpokladu za un+s-1, un+s-2 a pocitejme. un+s = un+s-1 + un+s-2 = un-1 us-1 + un us + un-1 us-2 + un us-1 = un-1 (us-1 + us-2) + un (us + us-1) = un-1 us + un us+1, a dukaz je dokoncen. PARAGRAF 2: zakladni mnozinove pojmy [1.2.B3] Necht An, Bn(n N) jsou mnoziny, splnujici podminky: An An+1, Bn Bn+1 pro kazde n N. (3) Potom: a) dokazte, ze n=1(An Bn) = n=1 An n=1 Bn b) ukazte, ze predchozi rovnost neplati, vynechame-li predpoklad (3). Navod: Dukaz vedte neprimo. DUKAZ: a) Nejdrive dokazme n=1(AnBn) n=1 An n=1 Bn, tedy (z definice podmnoziny) x ( n=1 An n=1 Bn) x n=1(An Bn). Necht x ( n=1 An n=1 Bn) (x n=1 An) (x n=1 Bn) (n : x An) (n : x Bn) n : (x An x Bn) n : x (An Bn) x ( n=1(An Bn), coz jsme meli dokazat. Nyni dokazme n=1(An Bn) n=1 An n=1 Bn, tedy x n=1(An Bn) x ( n=1 An n=1 Bn), ale neprimo. Budeme tedy dokazovat: x / ( n=1 An n=1 Bn) x / n=1(An Bn). Postupne dostavame x / ( n=1 An n=1 Bn) (x / n=1 An) (x / n=1 Bn) (k : x / Ak) (l : x / Bl) (diky podmince (3) nyni najdeme spolecny index m =max(k, l) tak, ze) m : (x / Am) (x / Bm) m : x / (Am Bm) x / n=1(An Bn), coz jsme meli dokazat. b) Kdybychom nepredpokladali (3) nebylo by mozne nalezt spolecny index m, a tak pokracovat v dalsich implikacich. Na prikladu si skutecne overte, ze index m za danych podminek lze nalezt. [1.2.B7b] Dokazte, ze plati: A ÷ C = B ÷ C A = B. DUKAZ: Dokazujme neprimo tedy A = B A ÷ C = B ÷ C = ((A - C) (C - A)) = ((B -C)(C -B)). S nerovnosti mnozin A a B plyne existence prvku x, ktery je v A a neni v B (pripadne obracene, ale to je jen otazka znaceni), tedy x : x A x / B. Nyni mohou nastat dve moznosti, bud x C, anebo x / C. Necht x C, pak x / (A - C) x / (C - A), ale x / (B - C) x (C - B), tedy plati, ze ((A - C) (C - A)) = ((B - C) (C - B)). Pokud x / C, pak x (A - C) x / (C - A), ale x / (B-C)x / (C-B), tedy opet plati, ze ((A-C)(C-A)) = ((B-C)(C-B)). Tim je dukaz ukoncen. [1.2.B14a]Necht A, B, C, D jsou mnoziny. Dokazte, ze plati: (A B) × (C D) = (A × C) (A × D) (B × C) (B × D). DUKAZ: Primo, obe implikace. Necht [x, y] ((A B) × (C D)) (definice kartezkeho soucinu) (x (A B)) (y (C D)) ((x A) (x B)) ((y C) (y D)) (((x A) (x B)) (y C)) (((x A) (x B)) (y D)) ((x A)(y C))((x B)(y C))((x A)(y D))((x B)(y D)) (definice kartezkeho soucinu) [x, y] (A × C) (B × C) (A × D) (B × D), a tim je dukaz ukoncen. PARAGRAF 3: zakladni vlastnosti celych cisel [1.3.B5b] Necht m je prirozene cislo; a, b, c Z. Dokazte, ze plati: a b(mod m) b c(mod m) a c(mod m). DUKAZ: Dukaz povedeme primo, tedy predpoklad rika, ze existuji q1, q2 Z tak, ze (b = q1m + a) (c = q2m + b), a mame dokazat, ze odtud plyne existence q3 Z, ze c = q3m + a. Z predpokladu plyne, ze c = q2m + b = q2m + q1m + a = (q2 + q1)m + a, tedy q3 = q1+q2, a protoze soucet celych cisel je opet cele cislo, je existence q3 dokazana, a tim dukaz ukoncen. (Zkuste si priklad). PARAGRAF 5: zobrazeni [1.5.B9c]Necht f : A B, g : B C jsou zobrazeni. Dokazte, ze plati: g f je injektivni f je injektivni. DUKAZ: Z definice injektivity plati, ze pro x1, x2 Df , x1 = x2 g(f(x1)) = g(f(x2)). To je predpoklad, tedy chceme dokazat, ze (x1, x2 Df , x1 = x2 g(f(x1)) = g(f(x2))) (x1, x2 Df , x1 = x2 f(x1) = f(x2)). To ale musi vzdy platit, protoze pokud by platilo, ze f(x1)) = f(x2) a soucastne x1 = x2, pak by jediny bod f(x1) = f(x2) byl zobrazen na dve funkcni hodnoty g(f(x1)), g(f(x2)), coz je spor s predpokladem, ze g je zobrazeni. [1.5.B10b] Necht f : A B je zobrazeni. Dokazte, ze plati: f je surjektivni existuje zobrazeni h : B A tak, ze f h = idB (Navod: pri dukazu '' hledane zobrazeni h primo zkonstruujte). DUKAZ: Nejdriv ''. Z existence zobrazeni h : B A takoveho, ze f h = idB je nutno dokazat surjektivitu f, tedy ze pro y Bx A : f(x) = y. Pokud ale takove zobrazeni h existuje, pak symbolicky lze psat h(B) A a f(h(B)) = B, tedy zobrazeni f je jiste surjektivni. Nyni ''. Predpokladejme, ze f je surjektivni a zkonstruujeme zobrazeni h s pozadovanymi vlastnostmi. Uvedomme si, ze surjektivita f znamena, ze vsechny prvky v B musi mit svuj vzor, a protoze f je zobrazeni musi byt v A vsechny prvky zobrazeny. Pokud by tedy f byla bijekce, h bychom zkonstruovali tak, ze pokud b = f(a), tak h(b) = a, tedy h by byla inverze k f. Dejme tomu, ze f neni bijekce. Pak se aspon dva prvky z A musi zobrazit na jeden prvek z B. Zobrazeni h pak zkonstuujeme tak, ze pro a1 = a2 A : f(a1) = f(a2) = b bude h(b) = a1, kde a1 je zvoleno pevne. O a2 se jiz nemusime starat. Pro b B bude platit h(b) = a1 a f(a1) = b, tedy f(h(b)) = b, tedy f h je identita na B. PARAGRAF: komplexni cisla Dokazte cos( ) = cos() cos() sin() sin() a sin( ) = sin() cos() cos() sin(). DUKAZ: Obecne plati (a1 + ia2)(b1 + ib2) = (a1b1 - a2b2) + i(a2b1 + a1b2)n a take obecne plati (cos() + i sin())(cos() + i sin()) = cos( + ) + i sin( + ). Nyni dosadme za a1 = cos(), a2 = sin(), b1 = cos() = cos(), b2 = sin() = sin(). Dostaneme cos( ) + i sin( ) = cos() cos() - sin() sin() + i(sin() cos() + cos() sin()) = cos() cos() sin() sin() + i(sin() cos() cos() sin()) a porovnanim realnych a komplexnich casti vyrazu na zacatku a konci rovnice dostavame tvrzeni. PARAGRAF 6: usporadane mnoziny [Priklad] Dokazte, ze lim inf an lim sup an. DUKAZ: Mejme posloupnost prvku an a oznacme cn = inf{ak, k n} a dn = sup{ak, k n}. Infimum je podle definice nejvetsi horni zavora, supremum nejmensi dolni zavora. Pro vsechna n tedy plati, ze cn dn a podle vety o limitach musi platit, ze limn cn limndn , z cehoz plyne tvrzeni. Jeste lepe je to patrne na priklade. Mejme posloupnost an = (-1)n 1 n . Posloupnost hornich zavor je d1 = sup{-1 1 , 1 2 , -1 3 , 1 4 , -1 5 , 1 6 , . . . } = 1 2 d2 = sup{1 2 , -1 3 , 1 4 , -1 5 , 1 6 , . . . } = 1 2 d3 = sup{-1 3 , 1 4 , -1 5 , 1 6 , . . . } = 1 4 d4 = sup{1 4 , -1 5 , 1 6 , . . . } = 1 4 d5 = sup{-1 5 , 1 6 , . . . } = 1 6 a dolnich zavor je c1 = inf{-1 1 , 1 2 , -1 3 , 1 4 , -1 5 , 1 6 , . . . } = -1 1 c2 = inf{1 2 , -1 3 , 1 4 , -1 5 , 1 6 , . . . } = -1 3 c3 = inf{-1 3 , 1 4 , -1 5 , 1 6 , . . . } = -1 3 c4 = inf{1 4 , -1 5 , 1 6 , . . . } = -1 5 c5 = inf{-1 5 , 1 6 , . . . } = -1 5 0 20 40 60 80 100 -1 -0.5 0 0.5 posloupnost (-1) n *(1/n) Figure 1: Vsimnete si zajimave skutecnosti, ze infimum (minimum) zmensujici se mnoziny se muze jen zvetsovat, zatimco supremum (maximum) zmensujici se mnoziny se muze jen zmensovat. Z obrazku je take patrne, ze limn an = 0. PARAGRAF 7: ekvivalence a rozklady PARAGRAF 8: zakladni algebraicke struktury [Priklad 2.76a] Dokazte, ze algebraicke struktury (Z, +, , 0, 1) (Q, +, , 0, 1) (R, +, , 0, 1) (C, +, , 0, 1) jsou do sebe vnorene obory integrity, z nichz posledni tri jsou dokonce pole nekonecne charakteristiky. DUKAZ: Nejprve zopakujme vlastnosti oboru integrity (treba pro (Z, +, , 0, 1) ). 1. (Z, +, 0) je abelovska grupa, tedy - 1a. (Z, +) je grupoid - 1b. existuje jednotkovy prvek - 1c. ke kazdemu prvku v a N existuje inverzni prvek a-1 2. (Z, ) je pologrupa 3. plati distributivni zakony, tedy pro libovolne a, b, c : (a + b) c = a c + b c a c (a + b) = c a + c b 4. (Z, , 1) monoid 5. (Z, ) musi byt komutativni pologrupa 6. neexistuje delitel nuly Jednotlive vlastnosti dokazme pro (Z, +, , 0, 1). 1a. pro a, b Z : a + b Z a je urceno jednoznacne 1b. musi existovat e Z tak, ze a Z : a + e = e + a = a, skutecne je to e = 0 1c. pro a Z musi existovat a-1 Z tak, ze a + a-1 = a-1 + a = e, skutecne je to a-1 = -a 2. operace + musi byt v (Z, +) asociativni, tedy pro a, b, c Z : a+(b+c) = (a+b)+c, coz skutecne plati 3. pro cela cisla plati distributivni zakony 4. operace musi byt asociativni (plati a, b, c Z : a (b c) = (a b) c), navic musi existovat e Z tak, ze a Z : a e = e a = a, skutecne je to e = 1 5. pro a, b, c Z : a (b c) = (a b) c a a b = b a, coz pro cela cisla plati 6. nesmi v Z existovat a = 0, b = 0 tak, aby a b = 0, coz pro cela cisla plati. Z 1.-6. plyne, ze (Z, +, , 0, 1) je obor integrity. Neni to ale pole, protoze (Z, +, , 0, 1) je sice okruh s jednotkou, ale (Z-{0}, 1) neni abelovska grupa (v mnozine celych cisel nejsou inverzni prvky vzhledem k nasobeni, to jsou totiz pro cela cisla uz zlomky). Pro ostatni algebraicke struktury (Q, +, , 0, 1) (R, +, , 0, 1) (C, +, , 0, 1) plati, ze jsou komutativnim telesem, takze to jsou pole. Je take jasne, ze maji nekonecnou charakteristiku ((Z, +, , 0, 1) ma take nekonecnou charakteristiku, ale pouze jako obor integrity). Pro zadne prirozene n z techto mnozin totiz neplati, ze n 1 = 0. [Priklad 2.76b] (ZN , , , 0, 1) je komutativnim okruhem s jednotkou, ktery neni podokruhem zadneho z okruhu v prikladu 2.76a. (ZN , , , 0, 1) je oborem intergrity, jen kdyz N je prvocislo. Pak je to dokonce pole. DUKAZ: 1. Dokazme, ze (ZN , , , 0, 1) je komutativnim okruhem s jednotkou. Mnozina ZN = {0, 1, . . . , N - 1} je mnozina cisel, ktere vzniknou jako zbytky po deleni celeho cisla cislem N. Dokazujeme pro tuto mnozinu vlastnosti z prikladu 2.76a. 1a. pro a, b ZN : a b ZN a je urceno jednoznacne 1b. musi existovat e ZN tak, ze a ZN : a e = e a = a, skutecne je to e = 0 1c. pro a ZN musi existovat a-1 ZN tak, ze a a-1 = a-1 a = e, skutecne je to a-1 = N - a 2. operace musi byt v (ZN , ) asociativni, tedy pro a, b, c ZN : a (b c) = (a b) c, coz skutecne plati 3. pro cisla ze ZN plati distributivni zakony 4. operace musi byt asociativni (plati a, b, c ZN : a (b c) = (a b) c, navic musi existovat e ZN tak, ze a ZN : a e = e a = a, skutecne je to e = 1 5. pro a, b, c ZN : a (b c) = (a b) c a a b = b a Nektere rovnice nejsou primo videt, pomuzeme si tedy prikladem pro Z3 = {0, 1, 2}. ad 1a. 0 0 = 0, 0 1 = 1, 0 2 = 2, 1 1 = 2, 1 2 = 0, 2 2 = 1, tedy 1a plati ad 1b. zrejme ad 1c. 0 3 = 0, 1 2 = 0, 2 1 = 0, 3 0 = 0, tedy 1c plati ad 2 (1 2) 2 = 2 = 1 (2 2) napriklad, plati i pro ostatni ad 3 0 = 2 (1 2) = (2 1) (2 2) = 2 1 = 0 napriklad ad 4 1 = 2 (2 1) = (2 2) 1 = 1 napriklad, dale a 1 = a ad 5 overeno ve ad4 a dale 2 = 2 1 = 1 2 = 2 2. (ZN , , , 0, 1) nemuze byt podokruh, protoze (ZN , ) neni dokonce ani podgrupoid (Z, +). Pro (ZN , +) plati, ze + neni operace, napr. pro Z3 bude 2 + 2 = 4 / Z3. 3. (ZN , , , 0, 1) je oborem intergrity jen kdyz N je prvocislo. Overme si, ze kdyz N je provocislo, pak neexistuje delitel 0, tedy nesmi v ZN existovat a = 0, b = 0 tak, aby a b = 0. Nejlepe na priklade. Pro Z3 = {0, 1, 2} vzdy je 1 1 = 1 = 0, 2 1 = 2 = 0, ale pro Z4 = {0, 1, 2, 3} je napriklad 2 2 = 0, takze to neni obor integrity. 4. Podle chytre vety plati, ze kazdy konecny obor integrity je pole. (Overte si to ale na tomto priklade detailne). PARAGRAF 9: vektorove prostory, podprostory, prime soucty prostoru, baze a dimenze prostoru [3.1.B8] Necht V1 a V2 jsou vektorove prostory na ciselnym telesem T. Pro libovolne (u1, u2), (v1, v2) V1 × V2 a t T definujeme: (u1, u2) + (v1, v2) = (u1 + v1, u2 + v2) resp. t(u1, u2) = (tu1, tu2). Dokazte, ze pak je V1 × V2 je vektorovy prostor nad T. DUKAZ: Postupujeme podle definice vektoroveho prostoru. Zrejme plati, ze t(u1, u2) = (tu1, tu2) V1 × V2. Dale (V1 × V2, +, 0) musi byt abelovska grupa. Skutecne (u1 + v1, u2 + v2) V1 × V2, protoze V1 a V2 jsou vektorove prostory, jednotkovy a opacny prvek ve V1 × V2 rovnez musi existovat. Staci poskladat do usporadane dvojice jednotkove a opacne prvky z jednotlivych V1 a V2. Nakonec overme distributivni zakon vzhledem ke scitani vektoru (ostatni jsou analogice). t((u1, u2) + (v1, v2)) = t(u1 + v1, u2 + v2) = (t(u1 + v1), t(u2 + v2)) = (tu1 + tv1, tu2 + tv2) = (tu1, tu2) + (tv1, tv2) = t(u1, u2) + t(v1, v2). Prvni rovnost je dana definici scitani ve V1×V2, druha je dana definici nasobeni skalarem ve V1 × V2, treti je dana distributivnim zakonem vzhledem ke scitani vektoru v jednotlivych V1 a V2, ctvrta je dana opet definici scitani ve V1 × V2, pata je dana definici nasobeni skalarem ve V1 × V2. Dodejme, ze tento priklad ma velky teoreticky vyznam, protoze rika, ze kartezky soucin vektorovych prostoru je opet vektorovym prostorem ovsem vetsi dimenze. [3.2.B4] Rozhodnete, zda podmnozina W Rn je podprostorem vektoroveho prostoru Rn , je-li W = {(x1, x2, . . . , xn) |x1 + x2 + + xn = 0}. DUKAZ: Musi ve W lezet nulovy prvek (0, 0, . . . , 0), coz plati, protoze 0 + 0 + + 0 = 0, zbyva overit, jestli pro libovolne a, b R a libovolne (x1, x2, . . . , xn), (y1, y2, . . . , yn) W, plati a(x1, x2, . . . , xn) + b(y1, y2, . . . , yn) W. Pocitejme tedy a(x1, x2, . . . , xn) + b(y1, y2, . . . , yn) = (ax1, ax2, . . . , axn)+(by1, by2, . . . , byn) = (ax1+by1, ax2+by2, . . . , axn+ byn). Musime dokazat, ze ax1 + by1 + ax2 + by2 + + axn + byn = 0. To ale plati, pokud vytkneme a, b a dosadime za x1 + x2 + + xn = 0 a y1 + y2 + + yn = 0. [3.2.B16b] Ve vektorovem prostoru V jsou dany podprostory W1 a W2. Rozhodnete, zda soucet W1 + W2 je primym souctem, je-li: V = R3 , W1 = {(x, y, z)|x - 2y - 3z = 0}, W2 = {(x, y, z)|x = z}. DUKAZ: Aby prostor V byl primym souctem prostoru W1 a W2, musi byt prunikem W1 a W2 pocatek a soucet dimenzi prostoru W1 a W2 musi dat dimenzi V . To ale v tomto pripade neplati, protoze W1 je rovina v trojrozmernem prostoru s normalovym vektorem (1, -2, -3) a W2 je rovina v trojrozmernem prostoru s normalovym vektorem (1, 0, -1). Jde tedy o ruznobezne roviny v trojrozmernem prostoru, a ty musi mit za spolecny prunik primku. Navic soucet dimenzi rovin 2 + 2 = 4, coz neni tri. [3.3.B14] Ve vektorovem prostoru RR ( scitani funkci je dano jako soucet funkcnich hodnot v jednotlivych argumentech a nasobeni funkce skalarem jako soucin skalaru a jednotlivych funkcnich hodnot ) jsou dany vektory ( tj. zobrazeni R R ) f, g, h. Dokazte, ze vektory f, g, h jsou linearne zavisle. Pritom: f = sin x, g = cos x, h = cos(x + 3 ). DUKAZ: Linearni zavislost tri vektoru znamena, ze aspon jeden z nich lze vyjadrit jako linearni kombinaci ostatnich, tedy musi existovat a, b R tak, ze napr. af +bg = h. Pocitejme a sin x + b cos x = cos x cos 3 - sin x sin 3 = cos(x + 3 ). Odtud plyne, ze a = - 3 2 a b = 1 2 , takze vektory jsou linearne zavisle. [3.4.B6] Naleznete bazi a dimenzi vektoroveho prostoru V , je-li: V = K×K, nad tlesem R. Scitani a nasobeni vektoru cislem je definovano po slozkach. RESENI: Musime umet vyjadrit jakoukoliv usporadanou dvojici (a + bi, c + di). To muzeme naprikad tak, ze a(1, 0) + b(i, 0) + c(0, 1) + d(0, i) = (a + bi, c + di). Dimenze je tedy 4 a bazi tvori 4 vektory (1, 0), (i, 0), (0, 1), (0, i).