0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN V tejto kapitole zavedieme niektoré základné logické a množinové pojmy a dohodneme sa na štandardnej symbolike, ktorú budeme ďalej používať. Nebudeme však systema- ticky budovať axiomatickú teóriu množín, práve naopak, s množinami budeme narábať skôr intutívne. Čitateľ, ktorý základné množinové pojmy ovláda, môže túto kapitolu vynechať, prípadne ju len letmo prelistovať, aby sa oboznámil s našou terminológiou a symbolikou. 0.1. Logické spojky a kvantifikátory Kvôli prehľadnosti budeme niektoré matematické tvrdenia zapisovať v symbolickej po- dobe ako matematické formuly. S príkladmi rôznych formúl sa ešte stretneme. V tejto chvíli sa zameriame len na spôsob, ako možno z daných tvrdení či formúl tvoriť nové pomocou logických spojok a kvantifikátorov. Nech P, Q sú ľubovoľné tvrdenia. (a) Tvrdenie, ktoré je pravdivé práve vtedy, keď tvrdenie P je nepravdivé, nazývame negáciou tvrdenia P, značíme ho P a čítame ho " nie P", prípadne " non P". (b) Tvrdenie, ktoré je pravdivé práve vtedy, keď sú pravdivé obe tvrdenia P, Q, na- zývame konjunkciou alebo logickým súčinom tvrdení P, Q, značíme ho P & Q a čítame " P a zároveň Q", krátko len " P a Q", prípadne " P et Q". (c) Tvrdenie, ktoré je pravdivé práve vtedy, keď je pravdivé aspoň jedno z tvrdení P, Q, nazývame alternatívou alebo disjunkciou či logickým súčtom tvrdení P, Q, značíme ho P Q, a čítame " P alebo Q", prípadne " P vel Q". (d) Tvrdenie P Q skrátene označujeme P Q a nazývame ho implikáciou tvr- dení P, Q. Výraz P Q čítame " ak P, tak Q" alebo " z P vyplýva Q", prípadne " P implikuje Q". Tvrdenie P nazývame predpokladom a tvrdenie Q záverom im- plikácie P Q. Uvedomte si, že implikácia P Q je nepravdivá jedine v tom prípade, ak predpoklad P je pravdivý a záver Q je nepravdivý. (e) Tvrdenie (P Q) & (Q P) skrátene označujeme P Q a nazývame ho ekvivalenciou tvrdení P, Q. Výraz P Q čítame " P práve vtedy, keď Q", prípadne " P je ekvivalentné s Q". Zrejme ekvivalencia P Q je pravdivá vte- dy a len vtedy, keď tvrdenia P, Q sú zároveň obe pravdivé alebo zároveň obe nepravdivé. Znaky , &, , , nazývame logickými spojkami. V literatúre sa možno tiež stretnúť s označením P , -P alebo P pre negáciu, P Q pre konjunciu, P Q alebo P Q pre implikáciu a P Q alebo P Q pre ekvivalenciu. Okrem tvrdení zapisujeme formulami aj vlastnosti objektov a vzťahy medzi nimi. Na tento účel používame formuly s voľnými premennými. Označujeme ich P(x), Q(x, y), 1 2 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA R(x1, . . . , xn) a pod. Dosadením konkrétnych objektov do formúl namiesto voľných pre- menných dostávame tvrdenia. Napríklad, ak Q(x, y) je formula s voľnými premennými x, y a a, b sú nejaké objekty, tak Q(a, b) je tvrdenie, ktoré je pravdivé práve vtedy, keď sa objekty a, b nachádzajú vo vzťahu označenom formulou Q. Zrejme aj na formuly s voľnými premennými možno aplikovať logické spojky, ktoré si pritom zachovajú svoj doterajší význam. Popri logických spojkách možno z formúl tvoriť nové formuly či tvrdenia aj pomocou kvantifikátorov. Nech P(x) je ľubovoľná formula. (a) Tvrdenie " existuje x také, že P(x)" skrátene zapisujeme ( x)P(x). (b) Tvrdenie " pre každé (pre všetky) x platí P(x)" skrátene zapisujeme ( x)P(x). Znaky resp. sú kvantifikátory; nazývame existenčný a univerzálny alebo tiež vše- obecný kvantifikátor. Zrejme premenná x už nie je vo formulách ( x)P(x) a ( x)P(x) voľná ale viazaná; ak x je jediná voľná premenná vo formule P(x), tak ( x)P(x) a ( x)P(x) sú tvrdenia. Oba uvedené kvantifikátory sú zviazané pravidlami negácie kvan- tifikovaných formúl: ( x)P(x) ( x)P(x), ( x)P(x) ( x)P(x). Pomocou existenčného a univerzálneho kvantifikátora už vieme vyjadriť i kvantifiká- tor jednoznačnej existencie. Ak P(x) je nejaká vlastnosť, tak tvrdenie " existuje práve jedno x také, že P(x)", t. j. tvrdenie ( x)(P(x) & ( y)(P(y) y = x)), skrátene zapisujeme v tvare (!x)P(x). Toto tvrdenie je zrejme ekvivalentné s tvrdením ( x)( y)(P(y) y = x). 0.2. Množiny Pod množinou rozumieme ľubovoľné jednoznačne vymedzené zoskupenie nejakých (čas- to i značne rôznorodých) objektov ­ prvkov množiny ­ chápané ako jediný objekt. Množiny budeme väčšinou značiť veľkými latinskými písmenami, ich prvky malými písmenami. Tvrdenie " objekt x je prvkom množiny X", zapisujeme x X; hovoríme tiež, že x patrí do množiny X. Tvrdenie " objekt x nie je prvkom množiny X", t. j. x nepatrí do množiny X, zapisujeme x / X. Množina je jednoznačne zadaná zoskupením svojich prvkov. Preto dve množiny, ne- závisle od spôsobu ich zadania, považujeme za totožné, ak majú tie isté prvky. Pre ľubovoľné množiny X, Y teda platí X = Y ( x)(x X x Y ). Túto vlastnosť množín nazývame extenzionalitou. 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 3 Hovoríme, že množina X je podmnožinou množiny Y , označenie X Y , ak každý prvok množiny X patrí aj do množiny Y , t. j. X Y ( x)(x X x Y ). Vzťah nazývame vzťahom inklúzie Extenzionalitu množín teraz možno skrátene vy- jadriť v tvare konjunkcie dvoch inklúzií X = Y X Y & Y X. Kvantifikácie uvedené v predchádzajúcom paragrafe sa nazývajú neohraničené, lebo oblasť pôsobnosti jednotlivých kvantifikátorov v nich nebola nijako ohraničená. V mate- matike (i v bežnom živote) sa však častejšie vyskytujú ohraničené kvantifikácie, v kto- rých je oblasť pôsobnosti príslušného kvantifikátora ohraničená nejakou množinou X. Ide o kvantifikácie tvaru ( x X), ( x X) a (!x X), ktoré čítame postupne " existuje x z množiny X", " pre každé (pre všetky) x z množiny X", resp. " existuje práve jedno (jediné) x z množiny X". Tieto kvantifikácie možno vyjadriť pomocou neo- hraničených kvantifikácii nasledujúcim spôsobom: Ak P(x) je ľubovoľná vlastnosť a X je množina, kladieme ( x X)P(x) ( x)(x X & P(x)), ( x X)P(x) ( x)(x X P(x)), (!x X)P(x) x X P(x) & ( y X)(P(y) y = x) . V poslednom prípade môžeme tiež použiť vyjadrenie (!x X)P(x) ( x X)( y X)(P(y) y = x). Množinu nazývame konečnou, ak ju možno zadať vymenovaním všetkých jej prvkov. Ak X je konečná množina a x1, x2, . . . , xn sú všetky jej prvky, píšeme X = {x1, x2, . . . , xn}. Z extenzionality potom vyplýva, že nezáleží na poradí vymenovania prvkov množiny X. Taktiež sa môže stať, že X má menej než n prvkov ­ v takom prípade sa niektoré z prvkov x1, . . . , xn opakujú a v zápise množiny X môžeme (no nemusíme) opaku- júce sa prvky až na jeden z nich vynechať. Napríklad {x, y} = {y, x}, a ak x = y, tak {x, y} = {x} = {y}. Okrem množín, ktoré majú nejaké prvky, zavádzame aj tzv. prázdnu množinu , ktorá neobsahuje nijaký prvok. Z extenzionality vyplýva, že prázdna množina je touto podmienkou jednoznačne určená. Popri konečných množinách však v matematike často pracujeme i s nekonečnými množinami, t. j. takými, ktoré nemožno zadať vymenovaním všetkých ich jednotlivých prvkov. Takéto množiny zvykneme zadávať nejakou charakteristickou vlastnosťou. Ak P(x) je nejaká vlastnosť, píšeme X = {x; P(x)}, 4 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA čím myslíme, že pre ľubovoľné x platí x X práve vtedy, keď x spĺňa P(x). Z ex- tenzionality vyplýva, že takto definovaná množina X je určená jednoznačne. Napríklad vlastnosťou " x je párne celé číslo" je určená množina všetkých párnych celých čísel. Poznamenajme, že z rovnosti X = {x; P(x)} ešte nijako nevyplýva, že množina X je nekonečná ­ rovnako dobre môže byť aj konečná, dokonca prázdna. Na tomto mieste je potrebné poznamenať, že uvedený princíp, ktorý nám umožňu- je zadávať množiny akýmikoľvek vlastnosťami ich prvkov, vedie k logickým sporom, a je preto v uvedenej intuitívnej a neobmedzenej podobe nepoužiteľný. Keďže sa však nehodláme púšťať do jeho upresňovania, čo by si vyžiadalo vybudovať základy axio- matickej teórie množín, nezostáva nám než čitateľovi vopred zaručiť, že všetky prípady použitia tohto princípu, ktoré sa v tomto texte vyskytnú, budú plne legálne z hľadiska teórie množín, a požiadať ho o dôveru. Zatiaľ stačí, ak prezradíme, že všetky množiny netvoria množinu, t. j. neexistuje množina všetkých množín. To znamená, že vlastnosťou " x je množina" nie je vymedzená nijaká množina. Najčastejšie budeme spomínaný princíp používať na vymedzovanie podmnožín neja- kej vopred danej množiny pomocou vlastností popísaných matematickými formulami. Ak M je množina a P(x) je nejaká (matematická) vlastnosť, tak existuje množina X všetkých tých prvkov x množiny M, ktoré majú vlastnosť P(x), t. j. množina X = {x M; P(x)} = {x; x M & P(x)}. Nech X, Y sú ľubovoľné množiny. Prienikom, zjednotením, a rozdielom množín X, Y nazývame porade nasledujúce množiny: X Y = {x; x X & x Y }, X Y = {x; x X x Y }, X Y = {x; x X & x / Y }. Množiny X, Y nazývame disjunktné, ak X Y = . Čitateľovi prenechávame, aby si sám premyslel základné vlastnosti uvedených množinových operácií. Pod usporiadanou dvojicou objektov x, y rozumieme objekt označovaný (x, y), taký, že pre všetky x, y, u, v platí: (x, y) = (u, v) (x = u & y = v). Uvedomme si, že nepotrebujeme vedieť, čo je " naozaj" usporiadaná dvojica (x, y), dô- ležitá je len uvedená vlastnosť. Analogicky zavádzame pre ľubovoľné celé číslo n 2 usporiadanú n-ticu (x1, . . . , xn) tak, že pre všetky x1, . . . , xn, y1, . . . , yn platí (x1, . . . , xn) = (y1, . . . , yn) (x1 = y1 & . . . & xn = yn). Množiny X × Y = {(x, y); x X & y Y }, X1 × . . . × Xn = {(x1, . . . , xn); x1 X1 & . . . & xn Xn} 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 5 nazývame karteziánskym súčinom množín X, Y , resp. množín X1, . . . , Xn. V prípade, že X1 = = Xn = X, píšeme X1 × . . . Xn = Xn . Pre úplnosť ešte kladieme X1 = X, X0 = {}. Xn nazývame n-tou karteziánskou mocninou množiny X. Počet prvkov konečnej množiny X budeme značiť # X. Taktiež prázdna množina je konečná a platí # = 0. Pre nekonečnú množinu X píšeme # X = . Zrejme pre ľubovoľné konečné množiny X, Y platí # (X Y ) = # X + # Y - # (X Y ), # (X × Y ) = # X # Y. Z poslednej rovnosti vyplýva, že # Xn = (# X)n pre každé celé číslo n 0 a konečnú množinu X. 0.3. Zobrazenia Zobrazením alebo tiež funkciou z množiny X do množiny Y rozumieme ľubovoľný pred- pis, ktorý každému prvku x množiny X priradí jednoznačne určený prvok y množiny Y . Zápis f : X Y označuje, že f je zobrazenie (funkcia) z X do Y . Ten jednoznačne určený prvok y Y , ktorý zobrazenie f priradí prvku x X, budeme značiť f(x), prípadne len fx alebo fx. Vo vzťahu y = f(x) nazývame x nezávisle premennou alebo argumentom a y závisle premennou alebo funkčnou hodnotou funkcie f. Píšeme tiež f : x y. Dve zobrazenia f, g: X Y sa rovnajú, ak pre každé x X platí f(x) = g(x). Množinu všetkých zobrazení z množiny X do množiny Y budeme označovať Y X ; teda Y X = {f; f : X Y }. Toto označenie je motivované vzorcom pre počet prvkov množiny Y X . Pre konečné množiny X, Y totiž platí # Y X = (# Y )(# X) . (Samostatne si rozmyslite prečo!) Zobrazenie f : X X sa nazýva transformáciou množiny X alebo tiež unárnou (t. j. jednomiestnou) operáciou na množine X. Zobrazenie f : X Y sa nazýva prosté alebo tiež injektívne či injekcia, ak rôznym prvkom x1, x2 X priraďuje rôzne prvky f(x1), f(x2) Y , t. j. ak platí ( x1, x2 X)(x1 = x2 f(x1) = f(x2)). 6 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA Uvedenú podmienku možno ekvivalentne vyjadriť v tvare ( x1, x2 X)(f(x1) = f(x2) x1 = x2). Zobrazenie f : X Y sa nazýva zobrazenie na množinu Y alebo tiež surjektívne či surjekcia, ak na každý prvok množiny Y sa zobrazí nejaký prvok množiny X, t. j. ak platí ( y Y )( x X)(y = f(x)). Hovoríme, že f : X Y je prosté zobrazenie X na Y alebo tiež bijektívne zobrazenie či bijekcia, ak f je zároveň prosté a na, t. j. injektívne i surjektívne. Ešte inak to môžeme vyjadriť podmienkou ( y Y )(!x X)(y = f(x)). Namiesto uvedených pojmov niekedy tiež hovoríme, že f je vzájomne jednoznačné zo- brazenie množiny X na množinu Y . Ak f : X Y je bijekcia, tak existuje jednoznačne určené zobrazenie g: Y X, ktoré každému y Y priradí ten jediný prvok x X, pre ktorý platí y = f(x). Toto zobrazenie nazývame inverzným zobrazením k zobrazeniu f a označujeme ho f-1 . Zrejme f-1 : Y X je tiež bijekcia a pre všetky x X, y Y platí f-1 f(x) = x, f f-1 (y) = y. Nech f : X Y , g: Y Z sú zobrazenia. Kompozíciou zobrazení f, g alebo aj zloženým zobrazením z f a g rozumieme zobrazenie označené ako g f : X Z, dané pre každé x X predpisom (g f)(x) = g(f(x)). Zložené zobrazenie možno znázorniť pomocou tzv. komutatívneho diagramu X Y Z f gg f (Všimnite si, že zobrazenie g f zapisujeme " v obrátenom poradí" ­ najprv totiž na prvok x aplikujeme f a až potom g. Núti nás k tomu zaužívaná konvencia, podľa ktorej argument x píšeme napravo od funkcie f. Poznamenajme, že niektorí autori dávajú prednosť " prirodzenému poradiu" a kompozíciu zobrazení f : X Y , g: Y Z, zapisujú ako f g. Kvôli tomu však opúšťajú spomínanú konvenciu a namiesto f(x) píšu xf. V tomto duchu fungujú napr. niektoré kalkulačky.) Skladanie zobrazení je asociatívne v nasledujúcom zmysle: ak f : X Y , g: Y Z a h: Z W sú zobrazenia, tak h (g f) = (h g) f. Ľahko totiž nahliadneme, že jedno i druhé zobrazenie priradí prvku x X prvok h(g(f(x))) W. 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 7 Na každej množine X máme definované identické zobrazenie idX : X X, nazývané tiež identita na X, také, že idX(x) = x pre každé x X. Zrejme idX je bijekcia pre každé X, a pre ľubovoľné zobrazenie f : X Y platí f idX = f = idY f. Pre f : X X kladieme f2 = f f, f3 = f f f, atď. Kvôli úplnosti definujeme aj f1 = f, f0 = idX. Zobrazenie fn nazývame n-tou iteráciou zobrazenia f. Ak f : X Y je bijekcia, tak k nej inverzné zobrazenie f-1 : Y X teraz môžeme charakterizovať rovnosťami f-1 f = idX, f f-1 = idY . Čitateľ sám ľahko nahliadne, že pre ľubovoľné zobrazenia f : X Y , g: Y Z platí: (a) Ak f, g sú injektívne, tak aj g f je injektívne. (b) Ak f, g sú surjektívne, tak aj g f je surjektívne. (c) Ak f, g sú bijektívne, tak aj g f je bijektívne. (d) Ak g f je injektívne, tak aj f je injektívne. (e) Ak g f je surjektívne, tak aj g je surjektívne. (f) Ak g f je bijektívne, tak f je injektívne a g je surjektívne. Podmienka (c) nás oprávňuje zaviesť pre bijekcie f : X X aj záporné iterácie f-n = f-1 n = fn -1 . Nech f : X Y je nejaké zobrazenie a A X. Zúžením zobrazenia f na množinu A nazývame zobrazenie f A: A Y také, že (f A)(x) = f(x) pre každé x A. Obrazom množiny A v zobrazení f nazývame množinu f(A) = {f(x); x A} Y. Špeciálne, množinu f(X) nazývame obrazom zobrazenia f a značíme ju Im f = f(X) = {f(x); x X}. Pre f : X Y a A X platí Im(f A) = f(A); zrejme f je surjekcia práve vtedy, keď Im f = Y , Podobne, vzorom množiny B Y v zobrazení f : X Y nazývame množinu f-1 (B) = {x X; f(x) B} X. Pre ľubovoľné A X, B Y možno jednoducho overiť inklúzie A f-1 f(A) , f f-1 (B) B. 8 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA 0.4. Binárne operácie Ak X, Y , Z sú množiny, tak zobrazenie f : X × Y Z nazývame binárnou (t. j. dvojmiestnou) operáciou na množinách X, Y s hodnotami v množine Z. Binárne ope- rácie väčšinou označujeme znakmi umiestňovanými medzi hodnoty argumentov, ako napr +, , , a pod. Hodnotu takej operácie na dvojici prvkov x X, y Y potom označujeme x + y, x y (prípadne len xy), x y, x y a pod. Podobným spôsobom možno zaviesť aj n-miestne operácie X1 × . . . × Xn Y , prípadne Xn Y , či Xn X pre ľubovoľné celé číslo n 0. Najčastejšie budeme pracovať s binárnymi operáciami tvaru f : X × X X, ktoré nazývame jednoducho binárnymi operáciami na množine X. Binárna operácia na množine X sa nazýva asociatívna, ak pre všetky x, y, z X platí x (y z) = (x y) z. Asociativita operácie nám dovoľuje vynechávať zátvorky a písať len x y z. Podobne si možno počínať i v prípade viacerých argumentov. Binárna operácia na množine X sa nazýva komutatívna, ak pre všetky x, y X platí x y = y x. Prvok e X sa nazýva neutrálny prvok binárnej operácie na množine X, ak pre všetky x X platí x e = e x = x. Zrejme neutrálny prvok operácie (ak existuje) je určený jednoznačne. Keby totiž e1, e2 X boli dva neutrálne prvky, tak nevyhnutne e1 = e1 e2 = e2. Ak binárna operácia na množine X má neutrálny prvok e a k danému prvku x X existuje prvok y X taký, že x y = y x = e, hovoríme, že y je inverzný prvok k prvku x. Ak je asociatívna binárna operácia na X, tak aj inverzný prvok k danému prvku x X (pokiaľ existuje) je určený jednoznačne. Keby totiž y1, y2 boli dva inverzné prvky k x, tak y1 = y1 e = y1 (x y2) = (y1 x) y2 = e y2 = y2. Napríklad pre ľubovoľnú množinu X kompozícia je asociatívna binárna operácia na množine XX všetkých transformácií množiny X. Zrejme ak # X 2, tak táto operácia nie je komutatívna. Identické zobrazenie idX XX je neutrálnym prvkom operácie . K danému zobrazeniu f XX existuje inverzný prvok práve vtedy, keď f je bijekcia; v tom prípade je ním inverzné zobrazenie f-1 XX . Binárnu operáciu na konečnej množine X možno zadať pomocou tzv. multiplika- tívnej tabuľky, ktorej stĺpce i riadky sú označené prvkami množiny X. Do poľa tabuľky ležiaceho v priesečníku x-tého riadku a y-tého stĺpca vpíšeme hodnotu x y. 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 9 Napr. tabuľkami + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 sú zadané dve asociatívne a komutatívne operácie + a na množine {0, 1, 2, 3, 4}. Ďalej 0 je neutrálny prvok operácie + a 1 je neutrálny prvok operácie . Navyše ku každému prvku a tejto množiny existuje inverzný prvok vzhľadom na operáciu + : k prvkom 0, 1, 2, 3, 4 sú to postupne prvky 0, 4, 3, 2, 1. Pokiaľ ide o operáciu , vidíme, že k prvku 0 neexistuje inverzný prvok; k prvkom 1, 2, 3 však inverzné prvky existujú: sú to postupne 1, 3, 2. Komutativitu binárnej operácie možno ľahko nahliadnuť z jej multiplikatívnej ta- buľky ­ prejaví sa symetriou tabuľky podľa hlavnej diagonály spájajúcej ľavý horný a pravý dolný roh. Taktiež neutrálny prvok možno odhaliť na prvý pohľad, lebo v jeho riadku i stĺpci sa zreproduje riadok resp. stĺpec zo záhlavia tabuľky. Ak už poznáme neutrálny prvok, možno overiť aj existenciu inverzného k danému ­ treba nájsť neutrálny prvok v riadku i v stĺpci daného prvku. Ak sa nám to podarí pre dvojicu polí tabuľky, ktoré ležia v stĺpci resp. riadku toho istého prvku, tak ide o hľadaný inverzný prvok. Asociatívnosť, žiaľ, tak jednoducho nahliadnuť nemožno. 0.5. Permutácie Kým znalosť predchádzajúcich paragrafov je nevyhnutným predpokladom, aby čitateľ mohol začať so štúdiom kapitoly 1, tento paragraf budeme potrebovať až neskôr, keď začneme preberať determinanty. Nech X je ľubovoľná množina. Permutáciou množiny X rozumieme ľubovoľné bijek- tívne zobrazenie : X X. Množinu všetkých permutácií množiny X značíme S(X). Ak X je konečná množina, tak počet prvkov množiny S(X) je daný známym vzťahom # S(X) = (# X)! , kde n! = 1 2 . . . n je faktoriál prirodzeného čísla n (pritom 0! = 1! = 1). Uvedomme si, že transformácia f : X X konečnej množiny X je injektívna práve vtedy, keď je surjektívna. Jedna i druhá podmienka totiž hovorí, že množina f(X) X má rovnaký počet prvkov ako X. Teda už jedna z uvedených podmienok je postačujúca na to, aby f bola permutáciou konečnej množiny X. Keďže zloženie dvoch permutácií , S(X) dáva opäť permutáciu množiny X, kompozícia je asociatívna binárna operácia na množine S(X). Ľahko sa možno presvedčiť, že ­ okrem prípadu, keď # X 2, ­ táto operácia nie je komutatívna. Zrej- me idX S(X) je neutrálny prvok tejto operácie a inverzným prvkom k permutácii S(X) je inverzná permutácia -1 S(X). 10 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA Pre X = {1, 2, . . . , n} namiesto S(X) píšeme Sn. Permutáciu Sn zvyčajne zapi- sujeme v tvare = 1 2 . . . n (1) (2) . . . (n) . Prvky množiny S3, t. j. permutácie množiny {1, 2, 3}, si môžeme predstaviť ako sy- metrie rovnostranného trojuholníka s vrcholmi označenými číslami 1, 2, 3. 1 2 3 -1 3 2 1 Obr. 0.1. Symetrie rovnostrannho trojuholnka Ak si identickú permutáciu tejto množiny označíme ako , otočenia okolo ťažiska trojuholníka proti smeru resp. v smere hodinových ručičiek o uhol /3 ako resp. -1 , a osovú súmernosť podľa osi prechádzajúcej i-tým vrcholom a stredom protiľahlej strany ako i, pre i = 1, 2, 3, tak množina permutácií S3 bude pozostávať z permutácií = 1 2 3 1 2 3 , = 1 2 3 2 3 1 , -1 = 1 2 3 3 1 2 , 1 = 1 2 3 1 3 2 , 2 = 1 2 3 3 2 1 , 3 = 1 2 3 2 1 3 . Multiplikatívna tabuľka binárnej operácie na množine S3 vyzerá takto: -1 1 2 3 -1 1 2 3 -1 3 1 2 -1 -1 2 3 1 1 1 2 3 -1 2 2 3 1 -1 3 3 1 2 -1 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 11 Permutáciu S(X) nazývame transpozíciou, ak existujú x, y X také, že x = y, (x) = y, (y) = x a (z) = z pre každé z X {x, y}. Inak povedané, transpozícia je výmena dvoch prvkov množiny X. Zrejme 1, 2, 3 S3 sú transpozície. Z názoru je zrejmé (dôkaz je v cvičení 10), že každú permutáciu konečnej množiny X možno získať postupnými výmenami dvojíc prvkov, teda každá taká permutácia je kompozíciou transpozícií. Tento rozklad na transpozície nie je jednoznačný: napr. S3 možno zapísať ako , t. j. kompozíciu 0 transpozícií, a taktiež ako = 1 1 = 2 2 = 3 3, t. j. aspoň troma ďalšími spôsobmi ako kompozíciu dvoch transpozícií. Dĺžkou permutácie konečnej množiny X nazveme najmenší počet transpozícií, na kompozícíu ktorých možno rozložiť, a označíme ju ||. Samotná dlžka || nie je dô- ležitá, význam má len parita tohto čísla, t. j. vlastne výraz sgn = (-1)|| , ktorý nazývame znakom, prípadne znamienkom permutácie . Permutácia konečnej množiny X sa nazýva párna resp. nepárna, ak číslo || je párne resp. nepárne, t. j. ak jej znak je 1 resp. -1. Z nasledujúcej vety vyplýva, že pri určovaní znamienka permutácie môžeme použiť jej ľubovoľný rozklad na transpozície = 1 . . .k a nemusíme sa starať o to, či tento rozklad je naozaj najkratší ­ pre ľubovoľný taký rozklad totiž platí (-1)|| = (-1)k . 0.5.1. Veta. Nech X je konečná množina. Potom pre ľubovoľné , S(X) platí (-1)|| = (-1)|| (-1)|| . Dôkaz. Zrejme stačí dokázať uvedenú rovnosť pre prípad, keď je transpozícia a X = {1, 2, . . . , n}. Pre každé Sn označme p() súčin všetkých rozdielov tvaru (j) - (i), kde 1 i < j n. Zrejme pre všetky Sn majú výrazy p() rovnakú absolútnu hodnotu a líšia sa nanajvýš znamienkom. Toto znamienko závisí od parity počtu záporných členov v súčine p(). Člen (j)-(i) je záporný práve vtedy, keď i < j a (i) > (j), ­ každú takú dvojicu (i, j) nazývame inverziou permutácie . Identita idX má 0 inverzií a p(idX) = 1n-1 2n-2 . . . (n - 1)1 = 1! 2! . . . (n - 1)! > 0. Stačí teda dokázať, že počet inverzií permutácií a sa líší o nepárnu hodnotu. Nech 1 k < l n sú tie dva prvky, ktoré vymieňa transpozícia . Potom = 1 . . . k . . . l . . . n (1) . . . (k) . . . (l) . . . (n) , = 1 . . . k . . . l . . . n (1) . . . (l) . . . (k) . . . (n) . Inverzie (i, j) permutácie , v ktorých nevystupuje k ani l, sú tiež inverziami permutácie . Inverzie, v ktorých vystupujú prvky i, k, a i, l, kde i = k, l, alebo obe súčasne vzniknú alebo súčasne zaniknú v oproti . Konečne, pokiaľ (k, l) nebola inverziou v , stane sa ňou v ; pokiaľ ňou bola, táto inverzia v zanikne. Teda celkový rozdiel počtu inverzií permutácií a je nepárny. 12 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA 0.6. Ekvivalencie a rozklady Podobne ako predošlý, i tento paragraf môže čitateľ zatiaľ preskočiť. Jeho znalosť bude potrebná až neskôr, v súvislosti s niektorými otázkami teórie grúp. S pojmom ekviva- lencie sa síce stretneme už predtým, dovtedy ho však nebudeme systematicky využívať. Nech je nejaký dvojmiestny vzťah, do ktorého vstupujú prvky nejakého oboru objektov M (tento obor môže, ale nemusí byť množinou). Zápisom x y značíme, že prvky x, y M sa nachádzajú vo vzťahu ; ak sa x, y M nenachádzajú v tomto vzťahu, píšeme x y. Hovoríme, že vzťah je na obore M (a) reflexívny, ak pre všetky x M platí x x; (b) symetrický, ak pre všetky x, y M platí x y y x; (c) tranzitívny, ak pre všetky x, y, z M platí x y & y z x z. Vzťah , ktorý je reflexívny, symetrický a tranzitívny na obore M, nazývame vzťahom ekvivalencie alebo len krátko ekvivalenciou na obore M. Ekvivalencie budeme väčšinou značiť znakmi , , a pod. Každý vzťah ekvivalencie na nejakej množine či obore objektov M predstavuje isté hľadisko, z ktorého považujeme niektoré prvky z M za rovnocenné, t. j. ekvivalentné, a iné nie. Napr. na množine všetkých hracích guličiek v danej jamke možno zaviesť vzťah ekvivalencie, v ktorom sa nachádzajú ľubovoľné dve guličky práve vtedy, keď majú rovnakú farbu. Vzťah, v ktorom sa nachádzajú dve takéto guličky práve vtedy, keď majú rovnakú hmotnosť, je iným príkladom ekvivalencie na tejto množine. Jedným dychom však poznamenajme, že uvedené príklady neslobodno brať príliš vážne, lebo rovnocennosť sa v nich mieša s podobnosťou, ­ " naozajstné" ekvivalen- cie predstavujú len v značne idealizovanom prípade. S reflexívnosťou a symetriou nie je problém, v reálnom živote však zvykne zlyhať tranzitívnosť. Môžeme sa napríklad zhod- núť, že guličky a, b majú rovnakú farbu, a takisto majú rovnakú farbu guličky b, c. No farba guličiek a, c sa nám už rovnakou zdať nemusí. Podobne môžeme v rámci presnosti našich váh dospieť k záveru, že guličky p, q ako aj guličky q, r majú rovnakú hmotnosť. Avšak hmotnosť guličiek p, r sa nám už vážením môže podariť rozlíšiť. Lepším prí- kladom ekvivalencie je tak vzťah na množine všetkých bankoviek danej meny, v ktorom sa nachádzajú dve bankovky práve vtedy, keď majú rovnakú nominálnu hodnotu. Na rozdiel od reálneho života sa v matematike nemusíme trápiť podobnými ťažkos- ťami. Všetky ekvivalencie, s ktorými sa tu stretneme, budú mať v plnej miere všetky tri uvedené vlastnosti. Ešte jeden príklad za všetky: vzťahom x y |x| = |y| je definovaná ekvivalencia " mať rovnakú absolútnu hodnotu" na množine C všetkých komplexných čísel. Nech je ekvivalencia na množine X. Pre x X označme ~x = {u X; u x} množinu všetkých prvkov u X ekvivalentných s x, ktorú nazývame triedou alebo blokom ekvivalencie prvku x. Zrejme pre ľubovoľné x X platí x ~x. Ľahko tiež 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 13 možno dokázať (skúste sami), že pre všetky x, y X platí x y ~x = ~y x ~y y ~x ~x ~y = . Množinu X/ = {~x; x X} všetkých tried ekvivalencie prvkov množiny X nazývame faktorovou množinou množiny X podľa ekvivalencie . (Podotýkame, že v zhode s paragrafom 0.2 sa každá trieda ~x nachádza v množine X/ iba raz, i keď prvkov y X, pre ktoré platí ~x = ~y, môže byť mnoho.) Priradením x ~x je definované surjektívne zobrazenie X X/, ktoré nazývame prirodzenou alebo tiež kanonickou projekciou množiny X na faktorovú množinu X/. Na faktorovú množinu X/ sa možno dívať dvojakým spôsobom. Jednak ako na výsledok stotožnenia či zlepenia navzájom ekvivalentných prvkov množiny X; v takom prípade sa na bloky ~x dívame predovšetkým ako na prvky, ktoré vznikli " stiahnutím" celej triedy ~x do jediného bodu, a vedome si nevšímame fakt, že sú to zároveň množiny. Použitím názvu " faktorová množina" naznačujeme, že v danej chvíli dávame tomuto pohľadu prednosť. Na druhej strane sa na množinu X/ možno dívať ako na rozklad množiny X na navzájom disjunktné neprázdne množiny ~x. Rozkladom množiny X nazývame ľubovoľný systém (t. j. množinu) jej neprázdnych podmnožín R taký, že každý prvok množiny X padne do práve jednej množiny zo sys- tému R. Inými slovami, systém R neprázdnych podmnožín množiny X je jej rozkladom práve vtedy, keď spĺňa nasledujúce dve podmienky: (1) zjednotením všetkých množín A R je celá množina X, t. j. ( x X)( A R)(x A); (2) množiny z R sú navzájom disjunktné, t. j. ( A, B R)(A = B A B = ). Ľahko možno nahliadnuť, že faktorová množina X/ množiny X podľa ekvivalencie je zároveň rozkladom množiny X, ktorý je tvorený triedami navzájom ekvivalentných prvkov. Taktiež naopak, každý rozklad R množiny X určuje predpisom x R y ( A R)(x, y A) ekvivalenciu na množine X. Inak povedané, prvky x, y X sú vo vzťahu ekvivalencie určenej rozkladom R práve vtedy, keď sa nachádzajú v tej istej (jednoznačne určenej) množine z tohto rozkladu. Čitateľovi prenechávame, aby si samostane overil, že takto definovaný vzťah R je reflexívny, symetrický a tranzitívny, t. j. má všetky tri poža- dované vlastnosti ekvivalencie, ako aj rovnosť X/R = R, t. j. že rozklad (faktorová množina) určený ekvivalenciou R splýva s pôvodným rozkladom R. 0.6.1. Príklad. Rozklad prislúchajúci k spomínanej ekvivalencii x y |x| = |y| na množine C je vlastne rozkladom komplexnej roviny na navzájom sústredné kružnice so stredom v počiatku 0 a ľubovoľným polomerom r 0 (kružnicu s nulovým polomerom prirodzene stotožňujeme s jej stredom). 14 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA 0.7. O matematických dôkazoch Matematika je veda vybudovaná prevažne (hoci nie výlučne) deduktívne. To znamená, že v tej-ktorej matematickej teórii vychádzame z určitých základných pojmov, ktoré považujeme za intuitívne jasné vďaka istým s nimi spojeným názorným predstavám. Ďalšie pojmy potom definujeme pomocou pojmov základných alebo skôr definovaných. Základné pojmy označujú základné objekty, ktoré tvoria predmet nášho štúdia, alebo určité základné vzťahy medzi nimi. Tieto objekty a vzťahy sú charakterizované istými východzími tvrdeniami, ktorým hovoríme axiómy. V najjednoduchších prípadoch je platnosť axióm jasná z názoru, ktorý stojí v pozadí príslušnej teórie. V zložitejších prípadoch však môžu názorné predstavy zlyhať ­ vtedy sa na axiómy dívame ako na implicitné definície základných pojmov. To znamená, že rezignujeme na otázku, čo " naozaj" označujú základné pojmy. Môžu označovať čokoľvek, čo spĺňa dané axiómy ­ to je všetko, čo o nich predpokladáme. Zisk z takéhoto prístupu spočíva v univerzálnosti matematiky ­ aj výsledky matematických teórií sa potom vzťahujú na veľmi rôznorodé oblasti reality. Totiž na tie, v ktorých možno interpretovať základné pojmy danej teórie tak, že sú pritom splnené jej axiómy. Pri deduktívnej výstavbe nejakej teórie vyvodzujeme ďalšie poznatky z jej axióm logickými prostriedkami, t. j. dokazujeme ich. Týmto dokázaným poznatkom hovoríme vety, tvrdenia, lemy a dôsledky, čím naznačujeme rôzny stupeň dôležitosti, ktorý im pri- pisujeme. Názvom veta označujeme tie najdôležitejšie z nich, menej dôležité nazývame tvrdeniami a tvrdenia pomocného charakteru označujeme ako lemy. Dôsledky, ako už sa- motný názov napovedá, pripájame ako bezprostredné dôsledky niektorých viet, tvrdení či liem, pokiaľ ich význam nedosahuje úroveň viet. Poznamenajme, že toto rozdelenie má značne subjektívny charakter a vývoj ho často zvykne prekonať. Mnohé vety časom upadajú do zabudnutia, kým naopak mnohé lemy postupne nadobúdajú na význame. Základným prostriedkom odvodzovania nových poznatkov v deduktívnej teórii je dô- kaz. V tomto paragrafe sa veľmi stručne zoznámime s hlavnými typmi matematických dôkazov: s priamym dôkazom, s nepriamym dôkazom a s dôkazom sporom. Uvidíme, že toto rozdelenie tak trochu súvisí so stratégiou vedenia príslušného dôkazu. V nasledu- júcom paragrafe sa ešte zoznámime s dôkazom matematickou indukciou. Väčšina matematických tvrdení má tvar implikácie P Q, t. j. tvrdí sa v nich, že z predpokladu P vyplýva záver Q. Pritom predpoklad P je často konjunkciou nejakých dielčích predpokladov, čiže má tvar P1 & . . . & Pn. Na tomto mieste sa obmedzíme na niekoľko poznámok o dôkazoch tvrdení takéhoto tvaru. 0.7.1. Priamy dôkaz. Pri priamom dôkaze implikácie P Q dokazujeme (či sa aspoň pokúšame dokázať) záver Q z predpokladu P. Spočiatku sa snažíme dokázať priamo záver Q z daných axióm a už skôr dokázaných tvrdení. Postupujeme pri tom tak ďaleko, ako sa len dá, pričom jedným očkom stále poškuľujeme po predpoklade P, či dielčích predpokladoch P1, . . . , Pn. Vo chvíli, keď už nevieme ako ďalej, siahneme po tom z dielčích predpokladov Pi, ktorý nám umožní pohnúť sa dopredu. Opäť postupujeme ďalej a vo vhodnej chvíli zasa použijeme niektorý dielčí predpoklad Pj (nie nevyhnutne rôzny od Pi). Ak sme úspešní, nakoniec sa nám podarí dospieť k záveru Q, čím dôkaz končí. Ak sme neúspešní, musíme to skúsiť inak, prípadne sa zamyslieť nad otázkou, či spomínaná implikácia vôbec platí. 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 15 Môže sa stať, že pri našom úspešnom dôkaze sme nepoužili všetky dielčie predpoklady P1, . . . , Pn, ale povedzme prvý a posledný z nich sme nepotrebovali. To znamená, že miesto pôvodného tvrdenia (P1 & P2 & . . . & Pn-1 & Pn) Q sme dokázali silnejšie tvrdenie (P2 & . . . & Pn-1) Q. 0.7.2. Nepriamy dôkaz. Pri nepriamom dôkaze implikácie P Q dokazujeme miesto nej logicky ekvivalentnú tzv. transponovanú implikáciu Q P práve opí- sanou metódou priameho dôkazu. Za tým účelom býva často užitočné (pokiaľ to ide) rozčleniť predpoklad Q na konjunkciu dielčích predpokladov R1 & . . . & Rm. Ak pô- vodný predpoklad P bol konjunkciou dielčích predpokladov P1 & . . . & Pn, tak jeho negácia P je ekvivalentná s alternatívou P1 . . . Pn. Potom transponovaná implikácia Q P je logicky ekvivalentná s ľubovoľnou z implikácií (Q & P1 & . . . & Pi-1 & Pi+1 & . . . & Pn) Pi, kde 1 i n. Nový záver Pi sa, samozrejme, usilujeme vybrať čo najvýhodnejšie, na čo neexistuje jednoznačný recept, no časom sa nám azda podarí nadobudnúť cit, ktorým sa budeme môcť riadiť. 0.7.3. Dôkaz sporom. Dôkaz sporom do istej miery pripomína nepriamy dôkaz a často sa s ním zvykne zamieňať. Najmä začiatočník by mal k nemu siahnuť až vtedy, keď sa mu priamy ani nepriamy dôkaz nedarí, prípadne keď v ňom skrsne podozrenie, že dokazované tvrdenie neplatí. Namiesto dokazovanej implikácie P Q prijmeme predpoklad P & Q, ktorý je logicky ekvivalentný s jej negáciou (P Q). Tento predpoklad sa usilujeme doviesť k sporu, čím sa myslí nejaký logicky absurdný záver, ako napr. x = x, alebo spor s niektorým z pôvodných predpokladov P, Q, prípadne spor s niektorou z axióm alebo s niektorým zo skôr dokázaných tvrdení. Na rozdiel od priameho alebo nepriameho dôkazu, dôkaz sporom nemá vopred stano- vený smer určený nejakým známym záverom ­ ten by sa mal objaviť až v jeho priebehu. Ak sa ani pokus doviesť k sporu predpoklad P & Q neskončí úspešne, je namieste pokúsiť sa ho dokázať, to znamená vyvrátiť pôvodnú hypotézu P Q. 0.7.4. Dôkaz ekvivalencie. Niekedy sa nám môže podariť dokázať ekvivalenciu P Q postupnosťou logicky ekvivalentných krokov, no to je skôr výnimka než pravidlo. Vo všeobecnosti si jej dôkaz vyžaduje dokázať zvlášť každú z implikácií P Q, Q P. Pritom na každú z nich možno použiť ľubovoľnú z troch skôr spomínaných metód. Často sa jedna z uvedených implikácií dokazuje priamo a druhá nepriamo, teda dôkaz uvedenej ekvivalencie pozostáva napr. z priamych dôkazov implikácií P Q a P Q. V našom kurze sa neraz stretneme s vetami, v ktorých sa tvrdí ekvivalencia viacerých podmienok P1, . . . , Pn. V tom je zahrnutých n(n - 1) jednotlivých implikácií Pi Pj pre rôzne i, j n. Dokazovať ich všetky by pre n 3 bolo značne neefektívne a taktiež zbytočné. Stačí totiž dokázať n implikácií tvoriacich cyklus P(1) P(2) . . . P(n-1) P(n) P(1), kde je ľubovoľná permutácia množiny indexov {1, . . . , n}, ktorú si volíme tak, aby to bolo čo najvýhodnejšie. S príkladmi všetkých uvedených typov dôkazov sa budeme v našom kurze neustále stretávať. 16 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA 0.8. Matematická indukcia a rekurzia Množinu všetkých nezáporných celých čísel značíme N = {0, 1, 2, . . . , } a nazývame ju tiež množinou všetkých prirodzených čísel. 0.8.1. Dôkaz matematickou indukciou. Platnosť nejakého tvrdenia P(n) pre všet- ky prirodzené čísla, t. j. tvrdenie ( n N)P(n) sa obvykle dokazuje matematickou indukciou. Dôkaz indukciou spočíva v dôkaze dvoch tvrdení: nato, aby sme dokázali, že každé prirodzené číslo n má vlastnosť P, stačí dokázať, že platí 1 P(0), t. j. 0 má vlastnosť P; 2 ( n N)(P(n) P(n + 1)), t. j. ak n je ľubovoľné prirodzené číslo, ktoré má vlastnosť P, tak aj číslo n +1 má vlastnosť P. Štruktúru dôkazu matematickou indukciou tak možno zhrnúť do schémy P(0) & ( n N)(P(n) P(n + 1)) ( n N)P(n). Bod 2 vlastne tvrdí platnosť všetkých implikácií P(0) P(1), P(1) P(2), P(2) P(3), . . . . Z bodu 1 a prvej z nich vyplýva P(1), z toho spolu s druhou implikáciou dostávame P(2), z čoho pomocou tretej implikácie plynie P(3), atď. Princíp matematickej indukcie je logicky ekvivalentný so zdanlivo očividným prin- cípom dobrého usporiadania, ktorý tvrdí, že každá neprázdna množina A N má najmenší prvok. Keďže pre väčšinu študentov býva tento princíp ľahšie prijateľný než princíp indukcie, predvedieme ako možno princíp indukcie z neho dokázať. Dôkaz prin- cípu dobrého usporiadania z princípu indukcie prenechávame na rozmyslenie čitateľovi. Predpokladajme teda platnosť princípu dobrého usporiadania. Nech P je vlastnosť taká, že platí P(0) a ( n N)(P(n) P(n + 1)). Označme A = {n N; P(n)}. Ak neplatí ( n N)P(n), tak A = . Nech m je najmenší prvok množiny A. Potom zrejme m = 0 a m - 1 / A, teda platí P(m - 1). No keďže P(m - 1) P(m), platí P(m), čiže m / A, čo je spor. Z pedagogických dôvodov sa budeme (najmä spočiatku) pri dôkazoch indukciou od- volávať radšej na princíp dobrého usporiadania než na princíp indukcie, a tomu tiež podriadime redakciu dôkazu. Poznámka. (a) Niekedy je potrebné miesto počiatočného tvrdenia 1 osobitne dokázať niekoľko prvých tvrdení P(0), P(1), . . . , P(k) a potom prejsť k dôkazu modifikovaného tvrdenia 2 , totiž ( n k)(P(n) P(n + 1)). (b) Indukciou možno dokazovať aj tvrdenia tvaru ( n m)P(n), kde m je nejaké pevné prirodzené číslo. Stačí dokázať mierne upravené verzie tvrdení 1 a 2 : P(m) a ( n m)(P(n) P(n + 1)). (c) Pri dôkaze indukciou možno bod 2 nahradiť tvrdením ( n N) (P(0) & . . . & P(n)) P(n + 1) . Inak povedané, pri dôkaze záveru P(n + 1) v bode 2 sa nemusíme opierať len o pred- poklad P(n), ale v prípade potreby môžeme ako predpoklady použiť všetky predchá- dzajúce tvrdenia P(0), . . . , P(n). Takýto dôkaz indukciou sa vlastne riadi schémou ( n N) ( k < n)P(k) P(n) ( n N)P(n). 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 17 Rozmyslite si, ako je predpoklad 1 , t. j. tvrdenie P(0), už zahrnutý v predpoklade novej schémy pre n = 0, t. j. v tvrdení ( k < 0)(P(k) P(0)). Ďalej si premyslite, ako možno transpozíciou uvedenej implikácie priamo dostať matematickú formuláciu princípu dobrého usporiadania. 0.8.2. Rekurzia. Princíp matematickej indukcie sa používa nielen na dôkazy tvrdení o prirodzených číslach. Možno ho použiť aj na konštrukciu rôznych, či už konečných alebo nekonečných postupností. V takom prípade miesto indukcie budeme radšej hovo- riť o postupnosti definovanej či zostrojenej rekurziou. Nech X je množina a F je zobrazenie, ktoré každej konečnej postupnosti, (uspo- riadanej n-tici) (x1, . . . , xn) prvkov z X (akejkoľvek dĺžky n N) priradí nejaký pr- vok F(x1, . . . , xn) X. Pomocou zobrazenia F možno zostrojiť nekonečnú postupnosť (an) n=0 prvkov z X tak, že položíme a0 = F(), an+1 = F(a0, a1, . . . , an) pre každé n N. V takom prípade, hovoríme, že postupnosť (an) je definovaná rekurziou pomocou zobrazenia F. Druhú rovnosť možno samozrejme zapísať v tvare an = F(a0, a1, . . . , an-1) pre n > 0. Taktiež možno definíciu rekurziou obmedziť len na nejaký počiatočný úsek 0, 1, . . . , n množiny prirodzených čísel a dostať tak rekurziou konečnú postupnosť (a0, a1, . . . , an). Niekedy rekurziu začíname nie od nuly ale od jednotky, prípadne od ľubovoľného pri- rodzeného čísla k. Prvým členom postupnosti (an) zostrojenej rekurziou pomocou zobrazenia F je prvok a0 = F() X. Ďalšie členy potom vyzerajú takto: a1 = F(a0), a2 = F(a0, a1), a3 = F(a0, a1, a2), . . . , an = F(a0, . . . , an-1), an+1 = F(a0, . . . , an), atď. Najčastejšie sa stretáme s prípadom, keď sa pri rekurzívnej konštrukcii člena an+1 nepoužíva celá predchádzajúca časť postupnosti (a0, . . . , an) ale len jej posledný člen an. Napríklad v aritmetickej postupnosti reálnych čísel s počiatočným členom a0 a diferenciou d platí an+1 = an + d; podobne rekurentný vzťah pre geometrickú postup- nosť reálnych čísel s počiatočným členom a0 a kvocientom q má tvar an+1 = qan. Iným známym číselným príkladom je tzv. Fibonacciho postupnosť (n) n=0, ktorej rekurzívna definícia 0 = 1 = 1, n+2 = n + n+1 používa dva predchádzajúce členy. Rozmyslite si, ako táto definícia zapadá do našej všeobecnej schémy. 0.8.3. Príklad. Bellove čísla sú definované rekurziou B0 = 1, Bn+1 = n k=0 n k Bk, pri ktorej sa využívajú všetky predchádzajúce členy. Pre istotu pripomíname, že n k = n! k!(n - k)! = n(n - 1) . . . (n - k + 1) k! 18 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA označuje binomický koeficient alebo kombinačné číslo udávajúce počet všetkých k-prvkových podmnožín n-prvkovej množiny. Vypočítame niekoľko počiatočných hodnôt Bellových čísel: B0 = 1, B1 = 0 0 B0 = 1, B2 = 1 0 B0 + 1 1 B1 = 2, B3 = 2 0 B0 + 2 1 B1 + 2 2 B2 = 5, B4 = 3 0 B0 + 3 1 B1 + 3 2 B2 + 3 3 B3 = 15, B5 = 4 0 B0 + 4 1 B1 + 4 2 B2 + 4 3 B3 + 4 4 B4 = 52, B6 = 5 0 B0 + 5 1 B1 + 5 2 B2 + 5 3 B3 + 5 4 B4 + 5 5 B5 = 203, . . . Matematickou indukciou teraz dokážeme, že počet všetkých rozkladov n-prvkovej množiny (teda aj ekvivalencií na n-prvkovej množine) je rovný číslu Bn. Zrejme na prázdnej možine existuje jediný rozklad R = . Predpokladajme teraz, že pre každé k n existuje práve Bk rozkladov k-prvkovej množiny. Všetky rozklady (n+1)-prvkovej množiny {0, 1, . . . , n} možno získať nasledujúcim spôsobom: (1) zvolíme si ľubovoľné k n a ľubovoľnú k-prvkovú podmnožinu A {1, . . . , n} ­ to pre dané k možno urobiť práve n k spôsobmi; (2) vezmeme ľubovoľný rozklad R množiny A ­ ten podľa indukčného predpokladu možno vybrať práve Bk spôsobmi ­ a množinu A = {0, 1, . . . , n} A pridáme k pôvodnému rozkladu R. Zrejme sme takto získali nejaký rozklad RA = R {A } (n + 1)-prvkovej množiny {0, 1, . . . , n}, pričom každý rozklad S množiny {0, 1, . . . , n} má tvar S = RA pre jed- noznačne určenú dvojicu (R, A). Všetkých rozkladov (n + 1)-prvkovej množiny teda je n k=0 n k Bk = Bn+1. Cvičenia 1. Pre ľubovoľné množiny X, Y sú nasledujúce štyri podmienky ekvivalentné: (i) X Y , (ii) X Y = X, (iii) X Y = Y , (iv) X Y = . Dokážte. 2. Vzťah inklúzie je reflexívny a tranzitívny, t. j. pre ľubovoľné množiny X, Y , Z platí: (a) X X; (b) X Y & Y Z X Z Dokážte. Nájdite príklad dosvedčujúci, že nie je symetrický. 3. Nech Z = {. . . , -2, -1, 0, 1, 2, . . . } označuje množinu všetkých celých čísel. Pre každé 0 = n Z označme nZ = {nx; x Z} množinu všetkých celých čísel deliteľných číslom n. Dokážte, že pre ľubovoľné nenulové celé čísla m, n platí 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 19 (a) mZ nZ m je násobkom n; (b) mZ = nZ |m| = |n|; (c) mZ nZ = kZ, kde k je najmenší spoločný násobok čísel m a n; (d) Môže pre niektoré m, n nastať rovnosť mZ nZ = , prípadne mZ nZ = {0}? Zdôvodnite. 4. Pre ľubovoľné množiny X, Y , Z platí X Y = Y X, X Y = Y X, X (Y Z) = (X Y ) Z, X (Y Z) = (X Y ) Z, X X = X, X X = X, X = , X = X, X (Y Z) = (X Y ) (X Z), X (Y Z) = (X Y ) (X Z), X X = , X = X, X (Y X) = , X (Y X) = X Y, (X Y ) Z = (X Z) (Y Z), (X Y ) Z = (X Z) (Y Z), X (Y Z) = (X Y ) (X Z), X (Y Z) = (X Y ) (X Z), (X Y ) Z = X (Y Z), X (Y Z) = (X Y ) (X Z), (X Y ) Z = (X Z) Y, (X Y ) Z = (X Z) (Y Z). Dokážte. Pomenujte niektoré z uvedených vlastností binárnych operácií , a (komutatívnosť, asociatívnosť, . . . ). 5. Pre ľubovoľné množiny X, Y , Z platí X × (Y Z) = (X × Y ) (X × Z), X × (Y Z) = (X × Y ) (X × Z), X × (Y Z) = (X × Y ) (X × Z), X × = . Dokážte. Napíšte analogické vzťahy distributívnosti karteziánskeho súčinu vzhľadom na operácie prieniku, zjednotenia a množinového rozdielu pri násobení sprava. 6. Nech X, Y , Z sú ľubovoľné množiny. Nájdite čo najprirodzenejšiu bijekciu a k nej inverzné zobrazenie medzi každou z nasledujúcich dvojíc množín (množina P(X) všetkých podmnožín množiny X z časti (f) sa nazýva potenčná množina množiny X): (a) X × Y , Y × X; (b) X × (Y × Z), (X × Y ) × Z; (c) (X × Y )Z , XZ × Y Z ; (d) XY ×Z , XY Z ; (e) Xn, X{1,...,n}; (f) {0, 1}X , P(X) = {A; A X}; (g) XY Z , XY × XZ Y ; (h) XY × XZ , X(Y ×{0})(Z×{1}). 7. Nech R označuje množinu všetkých reálnych čísel. Funkcie f, g, h: R R sú dané predpismi f(x) = (x + 1)2, g(x) = 1 - sin 2x, h(x) = e-x. Napíšte a zjednodušte predpisy pre zložené funkcie f f, f g, g f, f h, h f, g h, h g, f g h, h g f, g f h a g h f. 8. Nech f : X Y , g : Y Z sú ľubovoľné zobrazenia. Dokážte postupne nasledujúce tvrdenia: (a) Ak f, g sú injektívne, tak aj g f je injektívne. (b) Ak f, g sú surjektívne, tak aj g f je surjektívne. (c) Ak f, g sú bijektívne, tak aj g f je bijektívne. (d) Ak g f je injektívne, tak aj f je injektívne. (e) Ak g f je surjektívne, tak aj g je surjektívne. (f) Ak g f je bijektívne, tak f je injektívne a g je surjektívne. Na príklade ukážte, že v prípade (f) g nemusí byť injektívne ani f surjektívne. Čo z toho vyplýva pre prípady (d) a (e)? 9. Pre ľubovoľné zobrazenia f : X Y , g : Y Z a množiny A X, B Z dokážte rovnosti: (a) (g f)(A) = g(f(A)); (b) (g f)-1(B) = f-1(g-1(B)). 10. Nech f : X Y je ľubovoľné zobrazenie. Potom pre všetky A, B X, C, D Y platí (a) A B f(A) f(B); (b) C D f-1(C) f-1(D); 20 PAVOL ZLATOŠ: LINEÁRNA ALGEBRA A GEOMETRIA (c) f(A B) f(A) f(B); (d) f-1(C D) = f-1(C) f-1(D); (e) f(A B) = f(A) f(B); (f) f-1(C D) = f-1(C) f-1(D); (g) f(A B) f(A) f(B); (h) f-1(C D) = f-1(C) f-1(D); (i) f-1(f(A)) A; (j) f f-1(C) C. Dokážte. Na príkladoch sa presvedčte, že inklúzie v prípadoch (c), (g), (i) a (j) nemožno zameniť rovnosťami. Ukážte, že rovnosť pre všetky A, B X je v ľubovoľnom z prípadov (c), (g) a (i) ekvivalentná s injektívnoťou zobrazenia f. Podobne je rovnosť pre každé C Y v prípade (j) ekvivalentná so surjektívnosťou f. 11. Nech f : X Y , g : Y Z sú bijektívne zobrazenia. Potom (g f)-1 = f-1 g-1. Dokážte. Odvoďte z toho, že pre každú permutáciu Sn platí || = |-1| a sgn = sgn -1. 12. (a) Sformulujte pojmy ľavého a pravého neutrálneho prvku binárnej operácie na množine X. (b) Nech x y = y pre všetky x, y X. Je táto binárna operácia na množine X asociatívna resp. komutatívna? Nájdite všetky ľavé a všetky pravé neutrálne prvky operácie . (c) Predpokladajme, že e je jediným neutrálnym prvkom (či už ľavým, pravým alebo oboj- stranným) binárnej operácie na množine X. Sformulujte pojmy ľavého a pravého inverzného prvku k danému prvku x X. (d) Pomocou multiplikatívnej tabuľky nájdite príklad (neasociatívnej) binárnej operácie na množine X, ktorá má jediný (obojstranný) neutrálny prvok e, pričom niektorý prvok a X má jediný ľavý inverzný a dva rôzne pravé inverzné prvky, a iný prvok b X má jediný ľavý inverzný no žiadny pravý inverzný prvok. Aké situácie môžu ešte nastať? (Pozri cvičenie 18.) 13. Nech = 1 2 3 4 3 4 1 2 , = 1 2 3 4 2 3 1 4 sú permutácie množiny {1, 2, 3, 4}. Vypočítajte permutácie -1, -1 , , -1, -1 a -1 . 14. Nech 1 i n N. Permutácia Sn sa nazýva i-cyklus, ak na nejakej i-prvkovej množine {a1, a2, . . . , ai} {1, 2, . . . , n} operuje cyklicky podľa schémy : a1 a2 . . . ai a1 a na zvyšku množiny {1, . . . , n} identicky, t. j. (a) = a pre a {1, . . . , n} {a1, . . . , ai}. Skrátene píšeme = (a1, . . . , ai). Dva cykly = (a1, . . . , ai), = (b1, . . . , bj) sa nazývajú disjunktné, ak {a1, . . . , ai}{b1, . . . , bj} = . Zrejme identickú permutáciu možno považovať za 1-cyklus a každá transpozícia je 2-cyklus. Dokážte postupne nasledujúce tvrdenia: (a) Nech , Sn sú dva cykly. Potom = práve vtedy, keď cykly , sú disjunktné alebo aspoň jeden z nich je 1-cyklus. (b) Každá permutácia Sn, je kompozíciou disjunktných cyklov = 1 . . . k. Ak do tejto kompozície zahrnieme aj všetky 1-cykly, tak uvedený rozklad je určený jednoznačne až na poradie jednotlivých cyklov. (Návod: Vytvorte cyklus (1, (1), 2(1), . . . , i-1(1)). Na zvyšku množiny {1, . . . , n}, ak nejaký zostal, postup opakujte.) (c) Každý cyklus je kompozíciou transpozícií (napr. (1, 2, . . . , n) = (1, n) . . . (1, 3) (1, 2)). (d) Každá permutácia Sn je kompozíciou transpozícií. (e) Dĺžka i-cyklu je || = i - 1 a jeho znak je sgn = (-1)i-1. (f) Nech = 1 . . . k je rozklad permutácie na disjunktné cykly, pričom j je ij-cyklus. Potom dĺžka permutácie je || = i1 + . . . + ik - k a jej znak je sgn = (-1)i1+...+ik-k. Ak uvedený rozklad zahŕňa aj všetky 1-cykly, tak || = n - k a sgn = (-1)n-k. 15. (a) Rozložte každú z permutácií zo zadania aj výsledkov v cvičení 13 na kompozíciu disjunktných cyklov (vrátane 1-cyklov) a pre každú z nich určte jej dĺžku a znamienko. (b) Spočítajte pre každú z uvedených permutácií počet jej inverzií a porovnajte s jej dĺžkou. Presvedčte sa, že obe čísla sa nemusia rovnať, no vždy majú rovnakú paritu. (c) Rozložte permutáciu = (1, 3, 5, 7) (1, 2) (2, 4, 6, 8) (4, 5, 6) S10 na disjunktné cykly (vrátane 1-cyklov) a určte jej dĺžku a znamienko. 16. (a) Nech n Z (pozri cvičenie 3). Dokážte, že vzťahom x n y x-y nZ je definovaná ekvi- valencia na množine Z. Túto ekvivalenciu značíme tiež x y mod n a nazývame ju kongruenciou modulo n. 0. ZÁKLADNÉ POJMY Z LOGIKY A TEÓRIE MNOŽÍN 21 (b) Predpokladajme, že n > 0, a označme Zn = {0, 1, . . . , n - 1} = {x Z; 0 x < n}. Potom ( x Z)(!z Zn)(x n z). Dokážte. Toto jednoznačne určené z Zn nazývame zvyškom po delení čísla x číslom n. (c) Pre ľubovoľné n Z platí ( x, y, u, v Z)(x n y & u n v x + u n y + v & xu n yv). (d) Ako vyzerajú triedy rozkladu množiny Z podľa kongruencie n? 17. Matematickou indukciou dokážte nasledujúce vzorce: (a) n i=1 i = 1 + 2 + . . . + n = 1 2 n(n + 1); (b) n j=1 j(j + 1) = 1 2 + 2 3 + . . . + n(n + 1) = 1 3 n(n + 1)(n + 2); (c) n k=1 k2 = 12 + 22 + . . . + n2 = 1 6 n(n + 1)(2n + 1); (d) n k=0 qk = 1 + q + q2 + . . . + qn = qn+1 -1 q-1 , (q = 1); (e) n p=1 sin px = sin x + sin 2x + . . . + sin nx = sin(nx/2) sin((n+1)x/2) sin(x/2) , (x = 2k, k Z); (f) n p=0 cos px = cos 0 + cos x + . . . + cos nx = cos(nx/2) sin((n+1)x/2) sin(x/2) , (x = 2k, k Z); (g) n = 1+ 5 n+1 - 1- 5 n+1 2n+1 5 , (n sú Fibonacciho čísla). 18. (a) Priamym výpočtom overte, že binomické koeficienty n k = n! k!(n-k)! vyhovujú rovnosti n k = n n-k a pravidlám Pascalovho trojuholníka, t. j. n 0 = n n = 1 a n+1 k = n k-1 + n k pre 1 k n. (b) Označme C(n, k) počet všetkých k-prvkových podmnožín n-prvkovej množiny. Kombinato- rickou úvahou dokážte, že aj tzv. kombinačné čísla C(n, k) vyhovujú pravidlám Pascalovho tro- juholníka, t. j. C(n, 0) = C(n, n) = 1 a C(n + 1, k) = C(n, k - 1) + C(n, k) pre 1 k n. (c) Na základe (a) a (b) odvoďte známy vzorec C(n, k) = n k . Kde treba pritom použiť matema- tickú indukciu? (d) Pre k > n dodefinujme n k = C(n, k) = 0. Predpisom n k = C(n, k) je tak definovaná binárna operácia na množine N. Je táto operácia komutatívna resp. asociatívna? Má nejaký ľavý resp. pravý neutrálny prvok? (Pozri cvičenie 12.) Ako je to s prípadnými ľavými či pravými inverznými prvkami? (e) Riešte úlohu (d) aj pre binárnu operáciu n ˇ k = C(n + k, k) = (n+k)! n! k! na množine N. 19. Matematickou indukciou dokážte princíp dobrého usporiadania množiny N, podľa ktorého každá neprázdna podmnožina A množiny N má najmenší prvok. (Návod: Transponujte implikáciu ( n N) ( k < n)P(k) P(n) ( n N)P(n) a za P(n) dosaďte vlastnosť n / A.)