1. Základy matematiky

1. Základy matematiky

1A. V´ yroková logika

1. Z´ aklady matematiky ´ rokova ´ logika 1A. Vy Logika se v ˇceˇstinˇe bˇeˇznˇe pouˇz´ıv´ a ve smyslu myˇslenková cesta, která vede k urˇcit´ ym závˇer˚ um. Logika patˇr´ı k základ˚ um matematiky. Jako vˇedn´ı obor Matematická logika vznikla v 19. stolet´ı. Jej´ım zakladatelem byl anglick´ y matematik G. Boole (1815–1864). Boole prosadil algebraické pojet´ı logiky a zavedl logické spojky. K dalˇs´ım tv˚ urc˚ um booleovské logiky patˇril J. Venn (1834–1923). Rozˇs´ıˇren´ım této tzv. v´ yrokové logiky je predikátová logika, která se zab´ yv´ a dokazov´ an´ım matematick´ ych tvrzen´ı. Jej´ı vznik je spjat s nˇemeck´ ym matematikem G. Fregem (1848–1925). Frege zavedl v logice pojem kvantifikátoru. Jedn´ım z nejv´ yznamnˇejˇs´ıch logik˚ u vˇsech dob byl brnˇensk´ y rodák Kurt Gödel (1906–1978), jehoˇz vˇeta o u ´plnosti predikátové logiky prvn´ıho ˇrádu a vˇety o ne´ uplnosti axiomatick´ ych formáln´ıch systém˚ u s aritmetikou v´ yraznˇe ovlivnily v´ yvoj matematiky. V´ yroky Základn´ım pojmem logiky je v´ yrok. Intuitivnˇe ho lze definovat jako: Definice 1.1. V´ yrok je tvrzen´ı, o nˇemˇz má smysl ˇr´ıci, zda je pravdivé nebo nepravdivé. Bud’ A v´ yrok. Je-li A pravdiv´ y, zapisujeme tuto skuteˇcnost symbolicky p(A) = 1, je-li A nepravdiv´ y, p´ıˇseme p(A) = 0. Symboly 0, 1 se naz´ yvaj´ı pravdivostn´ı hodnoty. V´ yrok je tedy oznamovac´ı vˇeta, i kdyˇz nejsme schopni rozhodnout, zda je pravdivá. Tázac´ı ani rozkazovac´ı vˇeta nen´ı v´ yrok. Pˇ r´ıklad 1.2. Rozhodnˇete o pravdivosti následuj´ıc´ıch v´ yrok˚ u: √ 2 ˇ (a) A := Plat´ı √ = 2.“ (b) B := C´ıslo 51 je prvoˇc´ıslo.“ ” ” 2 √ √ 2 2 2 2 √ 2 ˇ sen´ı: (a) Zˇrejmˇe p(A) = 1, nebot’ √ = √ √ = = 2. (b) Zˇrejmˇe p(B) = 0, nebot’ 51 = 3 · 17. Reˇ 2 2 2 2 Spojov´ an´ı v´ yrok˚ u Jednotlivé v´ yroky lze spojovat ve sloˇzené v´ yroky pomoc´ı logick´ ych spojek (funktor˚ u). Pˇredmˇetem studia v´ yrokové logiky je studium závislosti pravdivostn´ı hodnoty sloˇzeného v´ yroku na zp˚ usobu spojen´ı a na pravdivostn´ıch hodnotách jednotliv´ ych v´ yrok˚ u. V´ yrok se naz´ yv´ a element´ arn´ı, nebo téˇz atomárn´ı, neobsahuje-li logické spojky. Napˇr´ıklad v´ yroky A, B jsou atomárn´ı. Rozhodov´ an´ı o pravdivosti atomárn´ıho v´ yroku pˇr´ısluˇs´ı odpov´ıdaj´ıc´ı vˇedecké discipl´ınˇe, která zkoumá shodu jeho obsahu s objektivn´ı realitou. Definice 1.3. (Logick´ e spojky) Bud’ A v´ yrok. Negac´ı v´ yroku A nazveme v´ yrok A′ , kter´ y má opaˇcnou ′ ′ pravdivostn´ı hodnotu, tj. A je nepravdiv´ y, pokud v´ yrok A je pravdiv´ y a A je pravdiv´ y pokud A je nepravdiv´ y. Negace se ˇcasto znaˇc´ı také non A nebo ¬A. Definici negace lze také zapsat tabulkou: p(A) 1 0

p(A′ ) 0 . 1

(1.1)

Pro spojován´ı dvou v´ yrok˚ u pouˇz´ıv´ ame logické spojky, zejména: konjunkce ∧, disjunkce ∨, implikace ⇒ a ekvivalence ⇔. Tyto spojky definujeme tabulkou pravdivostn´ıch hodnot vypsán´ım vˇsech existuj´ıc´ıch kombinac´ı. Bud’te A, B v´ yroky, pravdivost v´ yrok˚ u spojen´ ych tˇemito spojkami je dána tabulkou p(A) 1 1 0 0

p(B) 1 0 1 0

p(A ∧ B) 1 0 0 0

p(A ∨ B) 1 1 1 0

p(A ⇒ B) 1 0 1 1

p(A ⇔ B) 1 0 0 1

(1.2)

V následuj´ıc´ı tabulce uvedeme název spojky, jej´ı oznaˇcen´ı, slovn´ı vyjádˇren´ı a odpov´ıdaj´ıc´ı logick´ y v´ yznam. n´ azev spojky konjunkce disjunkce implikace ekvivalence

oznaˇcen´ı A∧B A∨B A⇒B A⇔B

´ FSI VUT v Brnˇe Studijn´ı text UM

slovn´ı vyjádˇren´ı A a souˇcasnˇe B A nebo B jestliˇze A, pak B A právˇe tehdy, kdyˇz B

logick´ y v´ yznam souˇcasnˇe plat´ı A i B plat´ı aspoˇ n jeden z A, B z A plyne B A a B jsou ekvivalentn´ı 1



Pˇri vyhodnocov´ an´ı pravdivostn´ı hodnoty sloˇzeného v´ yroku se zachovává následuj´ıc´ı poˇrad´ı operac´ı: ′ , ∧, ∨, ⇒, ⇔. Pokud chceme toto poˇrad´ı zmˇenit, pˇrid´ ame závorky. Speciálnˇe pro implikaci se uˇz´ıv´ a následuj´ıc´ı terminologie. V implikaci A ⇒ B se v´ yrok A naz´ yvá pˇ redpoklad nebo premisa a B z´ avˇ er implikace. Slovnˇe lze implikaci A ⇒ B vyjádˇrit také: A je postaˇ cuj´ıc´ı podm´ınkou pro B nebo B je nutnou podm´ınkou pro A. Implikace B ′ ⇒ A′ se naz´ yvá obmˇ enou implikace nebo obmˇ enˇ enou implikac´ı a je ekvivalentn´ı p˚ uvodn´ı implikaci A ⇒ B. Pozor, implikace B ⇒ A se naz´ yvá obr´ acen´ a implikace, ale nen´ı ekvivalentn´ı implikaci A ⇒ B. Pro u ´plnost uved’me jeˇstˇe spojkou alternativa ∨, která má v´ yznam bud’ A, nebo B“ a je pravdiv´ a pokud ” je pravdiv´ y právˇe jeden z v´ yrok˚ u A a B. Teoretick´ y v´ yznam má Sheffer˚ uv symbol |, kter´ y je pravdiv´ y jenom, kdyˇz oba v´ yroky A a B jsou nepravdivé. ˇ ıkáme, ˇze systém spojek Pozn´ amky: Vˇsech moˇzn´ ych logick´ ych spojek, které spojuj´ı dva v´ yroky A, B je 16. R´ je u ´ pln´ y, kdyˇz staˇc´ı k definov´ an´ı vˇsech 16-ti spojek, tj. pomoc´ı závorek a spojek lze popsat libovolnou logickou situaci. Systém logick´ ych spojek ′ , ∧, ∨, ⇒, ⇔ je u ´pln´ y. Lze dokázat, ˇze k vytvoˇren´ı u ´plného systému staˇc´ı vz´ıt pouze dvˇe spojky: negaci a jednu ze spojek ∧, ∨, ⇒. Dokonce lze dokázat, ˇze vˇsechny logické spojky lze popsat pomoc´ı jediné spojky: Shefferova symbolu. Analogicky existuj´ı logické spojky spojuj´ıc´ı tˇri v´ yroky A, B, C. Vˇseobecnˇe je známa napˇr´ıklad spojka if A ” then B else C“ pouˇz´ıvan´ a v programov´ an´ı. ( ) Pˇ r´ıklad: Urˇcete pravdivostn´ı hodnotu v´ yroku: (2 · 3 = 6) ∨ (3 · 4 = 11) ⇒ (2 < 1). ˇ sen´ı: Jedná se o sloˇzen´ Reˇ y v´ yrok, kter´ y je tvoˇren tˇremi atomárn´ımi v´ yroky A, B, C, kde A je 2 · 3 = 6“, ” B je 3 · 4 = 11“ a C je 2 < 1“. Urˇ c ´ ıme jejich pravdivostn´ ı hodnoty. Zˇ r ejmˇe p(A) = 1, p(B) = 0 a p(C) = 0. (( ) ” ” ) ( ) Odtud plyne p (2 · 3 = 6) ∨ (3 · 4 = 11) ⇒ (2 < 1) = p (1 ∨ 0) ⇒ 0 = p(1 ⇒ 0) = 0. Sloˇzen´ y v´ yrok je tedy nepravdiv´ y.

V´ yrokov´ e formy, promˇ enn´ e a kvantifik´ atory

√ Matematické objekty s jednoznaˇcnˇe stanoven´ ym v´ yznamem, napˇr. 0, 1, π, 2 naz´ yváme konstanty. Objekty, které nemaj´ı jednoznaˇcnˇe stanoven´ y v´ yznam, napˇr. x, y, z, naz´ yváme promˇ enn´ e. Definice 1.4. V´ yrokov´ a forma je tvrzen´ı obsahuj´ıc´ı promˇenné, z nˇehoˇz se po dosazen´ı konstant za promˇenné stane v´ yrok. V´ yrokovou formu A s promˇennou x m˚ uˇzeme zapsat A(x)

Pˇ r´ıklad: Tvrzen´ı A := 3x je sudé“, je v´ yroková forma. Zvol´ıme-li x = 1, pak p(A, x = 1) = 0, zat´ımco pro ” x = 2 je p(A, x = 2) = 1. Pˇri zápisu v´ yrokové formy A(x) := 3x je sudé“ lze psát p(A(1)) = 0, p(A(2)) = 1. ” Z v´ yrokové formy lze utvoˇrit v´ yrok t´ım, ˇze vˇsechny promˇenné ve formˇe váˇzeme omezuj´ıc´ımi podm´ınkami, které jednoznaˇcnˇe specifikuj´ıc´ı hodnoty vˇsech promˇenn´ ych. Tyto podm´ınky se naz´ yvaj´ı kvantifikátory. Definice 1.5. V matematice se nejˇcastˇeji pouˇz´ıvaj´ı následuj´ıc´ı dva kvantifikátory: 1. obecn´ y kvantifik´ ator, kter´ y se oznaˇcuje ∀ a ˇcte se pro kaˇ zd´ e“ a ” 2. existenˇ cn´ı kvantifik´ ator ∃, kter´ y má v´ yznam existuje aspoˇ n jeden“. ” Tyto kvantifik´ atory doplˇ nuj´ı promˇennou a mnoˇzinu, napˇr´ıklad ∀ x ∈ X plat´ı A(x)“ nebo ∃ x ∈ X, ˇze plat´ı ” ” A(x)“, kde X je mnoˇzina a A(x) v´ yrokov´ a forma s promˇennou x. V´ yrokové formy mohou m´ıt v´ıce promˇenn´ ych, které lze r˚ uznˇe kvantifikovat, pˇriˇcemˇz z´ aleˇ z´ı na poˇrad´ı. Kvantifikac´ı vˇsech promˇenn´ ych dostáv´ ame v´ yrok. Pokud je mnoˇzina zˇrejmá z kontextu, lze ji vynechat. Pˇ r´ıklad 1.6. Zjistˇete pravdivost následuj´ıc´ıch v´ yrok˚ u: (a) A := ∀ x ∈ R : x2 > 0“ – slovnˇe Pro kaˇzdé reálné ˇc´ıslo x plat´ı x2 > 0“ (neplat´ı pro x = 0) ” ” (b) B := ∃ n ∈ Z : n2 = 2“ – slovnˇe Existuje celé ˇc´ıslo n, pro které plat´ı n2 = 2“ (neplat´ı) ” ” (c) C := ∀ a, b ∈ R : (a + b)2 = a2 + 2ab + b2“ (plat´ı) ” (d) D := ∃ e ∈ R ∀x ∈ R : e · x = x“ (plat´ı, e = 1) ” (e) E := ∀ x ∈ R ∃ q ∈ R : x + q = 0“ (plat´ı, q = −x) ” (f) F := ∃ q ∈ R ∀x ∈ R : x + q = 0“ (z´ amˇenou poˇrad´ı kvantifik´ ator˚ u výrok neplat´ı). ” ´ FSI VUT v Brnˇe Studijn´ı text UM

2



Kvantifikátor˚ u existuje nekoneˇcnˇe mnoho. Pˇr´ıkladem dalˇs´ıho kvantifikátoru je kvantifikátor ∃! s v´ yznamem existuje pr´ avˇ e jeden. Podobnˇe existuj´ı kvantifikátory právˇe dva, právˇe tˇri, atd. Nejbˇeˇznˇeji pouˇz´ıvané kvantifikátory vyuˇz´ıvaj´ı slovn´ıch spojen´ı aspoˇ n, právˇe a nejv´ yˇse.

Negace v´ yrok˚ u s kvantifik´ atory Pˇri negaci v´ yroku se kvantifik´ ator ∀ mˇen´ı na ∃, kvantifikátor ∃ na ∀ (mnoˇ zina se pˇ ritom nemˇ en´ı) a následuj´ıc´ı v´ yrokov´ a forma se neguje: Vˇ eta 1.7. (Negace v´ yrok˚ u s kvantifik´ atory) Bud’ A(x) v´ yroková forma s promˇennou x ∈ X, potom ∀ x ∈ X plat´ı A(x)“ je v´ yrok ∃ x ∈ X ˇze plat´ı A(x)′“, ” ” (b) negac´ı v´ yroku ∃ x ∈ X, ˇze plat´ı A(x)“ je v´ yrok ∀ x ∈ X plat´ı A(x)′“, ” ” kde A(x)′ je negace formy A(x). Stejné pravidlo plat´ı i pro v´ yroky s v´ıce kvantifikátory. (a) negac´ı v´ yroku

Pˇ r´ıklad: Negac´ı v´ yroku Vˇsichni studenti skupiny udˇelali zkouˇsku z Matematiky.“ dostaneme v´ yrok ” Existuje (alespoˇ n jeden) student skupiny, kter´ y zkouˇsku z Matematiky neudˇelal.“ ” Podobnˇe negac´ı v´ yroku se dvˇema kvantifikátory: Existuje (alespoˇ n jeden) student skupiny, kter´ y udˇelal ” vˇsechny zkouˇsky“ dostáv´ ame v´ yrok Kaˇzd´ y student skupiny alespoˇ n jednu zkouˇsku neudˇelal“, pˇriˇcemˇz vˇzdy ” plat´ı v´ yrok a negace v´ yroku neplat´ı, nebo obrácenˇe. Pˇ r´ıklad 1.8. Negujte v´ yroky A, B, C, D, E, F z pˇredchoz´ıho pˇr´ıkladu! ˇ sen´ı: Reˇ (a) A′ := ∃ x ∈ R : x2 ≤ 0“ – (plat´ı, x = 0) ” (b) B ′ := ∀ n ∈ Z : n2 ̸= 2“ – (plat´ı) ” (c) C ′ := ∃ a, b ∈ R : (a + b)2 ̸= a2 + 2ab + b2“ (neplat´ı) ” (d) D′ := ∀ e ∈ R ∃x ∈ R : e · x ̸= x“ (neplat´ı, napˇr. e = 1) ” (e) E ′ := ∃ x ∈ R ∀ q ∈ R : x + q ̸= 0“ (neplat´ı); a zmˇenou poˇrad´ı kvantifikátor˚ u: ” ′ (f) F := ∀ q ∈ R ∃x ∈ R : x + q ̸= 0“ (plat´ı). ”

Tautologie D˚ uleˇzit´ ym problémem je také rovnost v´ yrok˚ u, zda ˇr´ıkaj´ı totéˇz, uved’me pˇr´ıklad: ˇarka a Iva ˇcekaj´ı na svoje kamarády Petra, Honzu a Jirku. S´ ˇarka tvrd´ı: Pˇrijde-li Petr a Honza, Pˇ r´ıklad 1.9. S´ pˇrijde i Jirka. Iva ˇr´ık´ a: Já si mysl´ım, ˇze kdyˇz pˇrijde Petr a nepˇrijde Jirka, nepˇrijde ani Honza. Na to pov´ıdá ˇarka: To ale ˇr´ık´ S´ aˇs totéˇz co já. Rozhodnˇete, zda obˇe skuteˇcnˇe ˇr´ıkaj´ı totéˇz. ˇ sen´ı: Nejprve provedeme vhodné oznaˇcen´ı atomárn´ıch v´ Reˇ yrok˚ u. Symbolem A oznaˇcme v´ yrok Petr pˇrijde“, ” symbolem B oznaˇcme v´ yrok Honza pˇrijde“ a dále C oznaˇcme v´ yrok Jirka pˇrijde“. V provedeném oznaˇcen´ı ” ” ˇarky a Ivy tvar: X := (A ∧ B) ⇒ C a Y := (A ∧ C ′ ) ⇒ B ′ . Aby S´ ˇarka a Iva ˇr´ıkaly totéˇz mus´ı maj´ı v´ ypovˇedi S´ b´ yt X ⇔ Y tautologie. Sestav´ıme tabulku pravdivostn´ıch hodnot. A 1 1 1 1 0 0 0 0

B 1 1 0 0 1 1 0 0

C 1 0 1 0 1 0 1 0

A∧B 1 1 0 0 0 0 0 0

A ∧ C′ 0 1 0 1 0 0 0 0

X 1 0 1 1 1 1 1 1

Y 1 0 1 1 1 1 1 1

X⇔Y 1 1 1 1 1 1 1 1

ˇarka a Iva ˇr´ıkaj´ı skuteˇcnˇe totéˇz. Z tabulky hodnot vypl´ yv´ a, ˇze X ⇔ Y , coˇz znamená, ˇze S´ ´ FSI VUT v Brnˇe Studijn´ı text UM

3



Definice 1.10. V´ yrokov´ a forma, jej´ıˇz promˇenn´ ymi jsou v´ yroky, se naz´ yvá tautologie, pokud po dosazen´ı libovolné kombinace pravdivostn´ıch hodnot v´ yrok˚ u za promˇenné dostáváme pravdiv´ y v´ yrok. Naopak, v´ yrokov´ a forma, která je nepravdiv´ y bez ohledu na pravdivost jeho ˇcást´ı se naz´ yvá kontradikce. V ostatn´ıch pˇr´ıpadech se forma naz´ yv´ a splniteln´ a. Sloˇzené v´ yroky A, B se naz´ yvaj´ı logicky ekvivalentn´ı, coˇz zapisujeme A = B, kdyˇz ve vˇsech pˇr´ıpadech plat´ı A ⇔ B; tj. je to tautologie. Pˇ r´ıklad: Formy A ∧ B a B ∧ A jsou logicky ekvivalentn´ı, plat´ı A ∧ B = B ∧ A a forma (A ∧ B) ⇔ (B ∧ A) je tautologie. Dalˇs´ı d˚ uleˇzité tautologie uvád´ı následuj´ıc´ı vˇeta: Vˇ eta 1.11. Následuj´ıc´ı v´ yrokové formy jsou tautologie: (a) (A ⇒ B) ⇐⇒ (B ′ ⇒ A′ ). ( ) (b) (A ⇒ B) ∧ (B ⇒ C) =⇒ (A ⇒ C). ( ) (c) (A ⇔ B) ⇐⇒ (A ⇒ B) ∧ (B ⇒ A) . Pozn´ amky: Uvedené tautologie maj´ı zásadn´ı v´ yznam. Tvoˇr´ı základ teorie d˚ ukaz˚ u. Tvrzen´ı a ˇr´ık´ a, ˇze d˚ ukaz implikace je ekvivalentn´ı d˚ ukazu jej´ı obmˇeny. Vlastnost b se naz´ yv´ a tranzitivita implikace. Matematickou indukc´ı m˚ uˇzeme tvrzen´ı b rozˇs´ıˇrit na libovoln´ y koneˇcn´ y poˇcet v´ yrokov´ ych promˇenn´ ych A1 , . . . , An , coˇz lze vyjádˇrit tautologi´ı [(A1 ⇒ A2 ) ∧ . . . ∧ (An−1 ⇒ An )] ⇒ (A1 ⇒ An ). ˇ ast c ˇr´ıká, ˇze d˚ C´ ukaz ekvivalentnosti dvou tvrzen´ı dokáˇzeme d˚ ukazem implikace a obrácené implikace. Pro negace sloˇzen´ ych v´ yrok˚ u plat´ı následuj´ıc´ı pravidla: Vˇ eta 1.12. Plat´ı následuj´ıc´ı vztahy pro negace sloˇzen´ ych v´ yrok˚ u: (a) (A′ )′ = A

— (zákon vylouˇcen´ı tˇret´ıho).

′

(b) (A ∧ B) = A′ ∨ B ′ , (c) (A ∨ B)′ = A′ ∧ B ′ , (d) (A ⇒ B)′ = A ∧ B ′ , (e) (A ⇔ B)′ = (A ∨ B) ∧ (A′ ∨ B ′ ) . Nˇekteré vlastnosti operac´ı maj´ı sv˚ uj název: Definice 1.13. Bud’te dány symboly ◦, ∗. Pak následuj´ıc´ı zákony naz´ yváme: (a) a ◦ b = b ◦ a

— komutativn´ı z´ akon.

(b) a ◦ (b ◦ c) = (a ◦ b) ◦ c

— asociativn´ı z´ akon.

(c) a ◦ (b ∗ c) = (a ◦ b) ∗ (a ◦ c)

— distributivn´ı z´ akon.

I logické spojky splˇ nuj´ı v´ yˇse uvedené zákony: Vˇ eta 1.14. Pro logické spojky ∧, ∨ plat´ı komutativn´ı, asociativn´ı a distributivn´ı zákony: (a) A ∧ B = B ∧ A,

A ∨ B = B ∨ A,

(b) A ∧ (B ∧ C) = (A ∧ B) ∧ C,

A ∨ (B ∨ C) = (A ∨ B) ∨ C,

(c) A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C),


A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C).

4


1B. D˚ ukazy v matematice

1B. D˚ ukazy v matematice Matematická tvrzen´ı maj´ı ˇcasto tvar implikac´ı, nebo ekvivalenc´ı. Ve vˇetˇe tvaru A ⇒ B se A naz´ yvá pˇredpoklad a B tvrzen´ı vˇety nebo závˇer. Existuj´ı tˇri základn´ı moˇznosti d˚ ukazu implikace: pˇr´ım´ y, nepˇr´ım´ y a sporem. V krátkosti si nyn´ı vysvˇetl´ıme, jak´ y je logick´ y základ tˇechto d˚ ukaz˚ u a v ˇcem spoˇc´ıvaj´ı. Pozn´ amka. 1.15. Pˇri d˚ ukazu tvrzen´ı v matematice m˚ uˇzeme postupovat tˇremi zp˚ usoby: Pˇ r´ım´ y d˚ ukaz. Chceme-li dokázat implikaci A ⇒ B pˇr´ım´ ym d˚ ukazem, pak se pokus´ıme zkonstruovat tzv. ˇretˇezec implikac´ı A ⇒ A1 , A1 ⇒ A2 , . . . , An ⇒ B. Podle Vˇety 1.11, ˇcásti (b) odtud plyne A ⇒ B. Zápis ˇretˇezce implikac´ı je zvykem zapisovat v kratˇs´ım tvaru A ⇒ A1 ⇒ A2 ⇒ . . . ⇒ An ⇒ B. Nepˇ r´ım´ y d˚ ukaz. Pˇri nepˇr´ımém d˚ ukazu vyuˇzijeme platnost tautologie (a) z Vˇety 1.11. Implikaci B ′ ⇒ A′ potom dokazujeme pˇr´ım´ ym d˚ ukazem. D˚ ukaz sporem. Vych´ az´ıme z pˇredpokladu, ˇze implikace neplat´ı, tj. p(A ∧ B ′ ) = 1 a konstruujeme ˇretˇezec ′ implikac´ı A ∧ B ⇒ A1 , A1 ⇒ A2 , . . . , An ⇒ S, aˇz dojdeme k v´ yroku S, kter´ y logicky pop´ırá p˚ uvodn´ı pˇredpoklad, nebo nˇejak´ y evidentnˇe pravdiv´ y v´ yrok. Spor je situace, kdy nˇejak´ y v´ yrok a jeho negace maj´ı b´ yt souˇcasnˇe pravdivé. Proto pˇredpoklad, ˇze implikace neplat´ı je nepravdiv´ y, a proto implikace plat´ı. Uvedené d˚ ukazové postupy budeme nyn´ı demonstrovat na pˇr´ıkladu. Pˇ r´ıklad 1.16. Dokaˇzte pˇr´ımo, nepˇr´ımo i sporem, ˇze ∀x ∈ N : x ≥ 2 ⇒ 6x + 3 > 13. ˇ sen´ı: Reˇ (a) Pˇ r´ım´ y d˚ ukaz. Jednotlivé kroky d˚ ukazu vyˇzaduj´ı elementárn´ı znalosti o vlastnostech nerovnost´ı. x≥2

⇒

6x ≥ 12

⇒

6x + 1 ≥ 12 + 1

⇒

6x + 1 ≥ 13

⇒

6x + 3 > 13.

Uveden´ y ˇretˇezec implikac´ı tvoˇr´ı d˚ ukaz tvrzen´ı. (b) Nepˇ r´ım´ y d˚ ukaz. Sestroj´ıme obmˇenu p˚ uvodn´ı implikace ∀x ∈ N : 6x + 3 ≤ 13 ⇒ x < 2. Toto tvrzen´ı je logicky ekvivalentn´ı p˚ uvodn´ımu tvrzen´ı. Obmˇenu dokáˇzeme pˇr´ım´ ym d˚ ukazem 6x + 3 ≤ 13

⇒

6x < 10

⇒

6x ≤ 10

⇒

x≤

10 6

⇒

x < 2.

(c) D˚ ukaz sporem. Pˇredpokládejme, ˇze dokazované tvrzen´ı neplat´ı. Pak je ale pravdivá jeho negace. Negace implikace má tvar ∃x ∈ N : x ≥ 2 ∧ 6x + 3 ≤ 13. Z tohoto pˇredpokladu nyn´ı plyne, ˇze existuje x ∈ N takové, ˇze x ≥ 2 ∧ 6x + 3 ≤ 13

⇒

x ≤ 2 ∧ 6x ≤ 10

⇒

x≥2 ∧ x≤

10 , 6

coˇz je spor, nebot’ ˇz´ adné x ∈ N vlastnost x ≥ 2 ∧ x ≤ 10 a. Pˇredpoklad, z nˇehoˇz se ˇretˇezec implikac´ı 6 nem´ odv´ıjel, je tedy nepravdiv´ y. To ale znamená, ˇze je pravdivá jeho negace. Tato negace je vˇsak ekvivalentn´ı p˚ uvodn´ı implikaci. Speciáln´ım, ale v matematice ˇcasto pouˇz´ıvan´ ym d˚ ukazem je d˚ ukaz pomoc´ı principu matematické indukce. Matematick´ a indukce je vˇeta, která umoˇzn ˇuje provádˇet d˚ ukazy tvrzen´ı t´ ykaj´ıc´ıch se mnoˇziny pˇrirozen´ ych ˇc´ısel N = {1, 2, 3, . . . }. D˚ ukaz matematické indukce provedeme sporem. Vˇ eta 1.17. (Matematick´ a indukce) Bud’ V (n) v´ yroková forma promˇenné n ∈ N. ( ( ) ( ) ) ( ) p V (1) = 1 ∧ ∀k ∈ N : p V (k) = 1 =⇒ p(V (k + 1)) = 1 ⇒ ∀n ∈ N : p(V (n)) = 1. ´ FSI VUT v Brnˇe Studijn´ı text UM

(1.3)

5


1B. D˚ ukazy v matematice

( ) D˚ ukaz. Tvrzen´ı dokáˇzeme sporem. ( ) Pˇredpokládejme, ˇze existuje ˇc´ıslo k ∈ N, takové, ˇze p V (k) = 0. Odtud plyne, ˇz)e mnoˇzina M = {k; p V (k) = 0} je neprázdn´ ( (a a symbolem ) m oznaˇcme jej´ı nejmenˇs´ı prvek. Protoˇze p(V (1) ) = 1 je m > 1 a protoˇze m − 1 ∈ / M plat´ı p V (m − 1) = 1. Z indukˇcn´ıho pˇredpokladu ale plyne p V (m) = 1, coˇz je spor. ( ) Pozn´ amka. 1.18. D˚ ukaz tvrzen´ı ∀n ∈ N : p V (n) = 1“ pomoc´ı matematické indukce se skládá ze tˇr´ı ˇcást´ı: ” ( ) (a) Dokáˇzeme, ˇze je p V (1) = 1. (Pozn. Obecnˇeji plat´ı, ˇze dokáˇzeme platnost formule pro nejmenˇs´ı pˇr´ıpustné n a nejˇcastˇeji je to právˇe ˇc´ıslo 1.) (b) Dokáˇzeme, ˇze plat´ı implikace ∀k ∈ N : p(V (k)) = 1 ⇒ p(V (k + 1)) = 1. (c) Odvol´ ame se na Vˇetu 1.17 o matematické indukci, podle které je nyn´ı tvrzen´ı V (n) pravdivé pro kaˇzdé pˇrirozené ˇc´ıslo n. Postup vysvˇetl´ıme na pˇr´ıkladu: ˇ Pˇ r´ıklad 1.19. Rekneme, ˇze a dˇel´ı b a p´ıˇseme a|b, kdyˇz existuje ˇc´ıslo c tak, ˇze b = ac. Pomoc´ı matematické indukce dokaˇzte následuj´ıc´ı tvrzen´ı ∀k ∈ N : 7|62k − 8“. ” D˚ ukaz. Tvrzen´ı dokáˇzeme ve tˇrech kroc´ıch: (a) Nejprve dokáˇzeme, ˇze tvrzen´ı je pravdivé pro k = 1. V´ yrok V (1) má tvar 7|62 − 8 = 28. Plat´ı ale 28 = 4 · 7. Tedy tvrzen´ı pro k = 1 plat´ı. (b) Pˇredpokládejme nyn´ı, ˇze tvrzen´ı je pravdivé pro libovolné pevnˇe zvolené ˇc´ıslo k a dokaˇzme, ˇze plat´ı rovnˇeˇz pro k + 1. Oznaˇcme V (k + 1) = 7|62(k+1) − 8. Je tˇreba dokázat, ˇze ∀k ∈ N : 7|62k − 8 ⇒ 7|62(k+1) − 8. ˇ ıslo 62(k+1) − 8 z v´ C´ yroku V (k + 1), jehoˇz dˇelitelnost ˇc´ıslem 7 máme dokázat, uprav´ıme na tvar 62(k+1) − 8 = 62k+2 − 8 = 62 · 62k − 8 = 36 · 62k − 8 = (62k − 8) + 35 · 62k . Prvn´ı ˇclen souˇctu (62k − 8) + 35 · 62k je dˇeliteln´ y ˇc´ıslem 7 podle indukˇcn´ıho pˇredpokladu, dˇelitelnost druhého ˇclene je zˇrejm´ a, nebot’ 7|35. Protoˇze jsou ˇc´ıslem 7 dˇelitelné oba ˇcleny je j´ım dˇeliteln´ y i jejich souˇcet a to bylo tˇreba dokázat. (c) Podle Vˇety 1.17 o matematické indukci je tvrzen´ı pravdivé pro kaˇzdé pˇrirozené ˇc´ıslo n. Deduktivn´ı u ´vahou naz´ yv´ ame takovou u ´vahu, pˇri n´ıˇz z obecného tvrzen´ı vyvozujeme zvláˇstn´ı, individuáln´ı. Podstata dedukce je tedy v tom, ˇze zvláˇstn´ı pˇr´ıpad zahrnuje pod obecn´ y princip. Matematické u ´vahy jsou pˇreváˇznˇe deduktivn´ı.


6


1C. Základn´ı mnoˇzinové pojmy

´ kladn´ı mnoˇ ´ pojmy 1C. Za zinove Vedle logiky základn´ım kamenem matematiky je teorie mnoˇzin. Za jej´ıho zakladatele je povaˇzován nˇemeck´ y matematik G. Cantor (1845–1918). Základn´ı problematikou, kterou se teorie mnoˇzin zab´ yvala, byly otázky t´ ykaj´ıc´ı se vlastnost´ı nekoneˇcna, zejména srovnáván´ı r˚ uzn´ ych velikost´ı nekoneˇcna. Ukázalo se vˇsak, ˇze v teorii mnoˇzin lze modelovat i jiné matematické teorie a to tak, ˇze se kaˇzdému matematickému objektu pˇriˇrad´ı urˇcitá mnoˇzina, která ho reprezentuje. V tomto smyslu se teorie mnoˇzin stala základem celé matematiky. S jistou nadsázkou lze ˇr´ıci, ˇze se teorie mnoˇzin narodila 7. 12. 1873. Toho dne totiˇz G. Cantor nalezl odpovˇed’ na otázku, zda lze vˇsechna reáln´ a ˇc´ısla z nˇejakého intervalu (a, b) spoˇc´ıtat v tom smyslu, ˇze je lze bijektivnˇe zobrazit na mnoˇzinu vˇsech pˇrirozen´ ych ˇc´ısel. Ke svému pˇrekvapen´ı zjistil, ˇze takové zobrazen´ı neexistuje. Otázku, zda má smysl porovn´ avat nekoneˇcné systémy podle velikosti, si poloˇzil napˇr´ıklad jiˇz v roce 1638 jeden z géni˚ u té doby, Galileo Galilei. Ten vypsal ˇradu ˇc´ısel 1, 2, 3, 4, . . . a jejich druh´ ych mocnin 1, 4, 9, 16, . . . a uvˇedomil si, ˇze mezi tˇemito mnoˇzinami existuje bijekce. To by vˇsak znamenalo, ˇze jsou uvedené systémy ˇc´ısel stejnˇe velké. Tento závˇer se mu jevil naprosto absurdn´ı. Pop´ıral totiˇz jeden ze základn´ıch Eukleidov´ ych logick´ ych axiom˚ u, kter´ y ˇr´ık´ a, ˇze celek je vˇzdy vˇetˇs´ı neˇz jeho ˇcást. Galilei proto dospˇel k závˇeru, ˇze pro nekoneˇcné systémy nemá otázka o jejich velikosti ˇz´ adn´ y smysl. Na konci svého ˇzivota sepsal B. Bolzano (1781–1848) matematickofilozofické d´ılo Paradoxy nekoneˇcna. Vyˇslo posmrtnˇe v roce 1851. V tomto d´ıle dospˇel na práh teorie mnoˇzin. Na pˇrelomu 19. a 20. stolet´ı se objevily v teorii mnoˇzin antinomie (rozpory mezi zákony), které si vynutily novou metodiku v´ ystavby matematick´ ych teori´ı. Nejobvyklejˇs´ı metodou se stala axiomatická v´ ystavba. Definice 1.20. (intuitivn´ı) (a) Mnoˇ zina je souhrn libovoln´ ych r˚ uzn´ ych (navzájem rozliˇsiteln´ ych) objekt˚ u. (b) Jednotlivé objekty nazveme prvky mnoˇ ziny a shrnován´ı v jeden celek oznaˇc´ıme pomoc´ı sloˇzen´ ych závorek. V mnoˇzinov´ ych závork´ ach nez´ aleˇ z´ı na poˇ rad´ı, v jakém prvky zap´ıˇseme. Nezáleˇz´ı ani na tom, kolikrát prvek v mnoˇzinˇe zap´ıˇseme. Pro pˇrehlednost budeme zapisovat kaˇzd´ y prvek pouze jednou. (c) Mnoˇziny zpravidla oznaˇcujeme velk´ ymi p´ısmeny a jejich prvky mal´ ymi p´ısmeny. (d) Zápis a ∈ A znamen´ a, ˇze objekt a je prvkem mnoˇ ziny A. (e) Negace v´ yroku a ∈ A p´ıˇseme a ∈ / A. ˇ (f) Rekneme, ˇze mnoˇ ziny A, B jsou si rovny, kdyˇz maj´ı tytéˇz prvky. Pak p´ıˇseme A = B. ˇ (g) Rekneme, ˇze mnoˇzina A je podmnoˇ zinou mnoˇ ziny B, kdyˇz kaˇzd´ y prvek mnoˇziny A je prvkem mnoˇziny B. Pak p´ıˇseme A ⊂ B. Symbol ⊂ se naz´ yvá znak inkluze nebo také znak podmnoˇziny. (h) Mnoˇzinu lze zadat v´ yˇ ctem prvk˚ u, tj. napsán´ım seznamu, napˇr. {1, 2, 3} nebo pomoc´ı charakteristick´ e vlastnosti, napˇr. {x ∈ N : x ≤ 3}. (i) Symbolem ∅ oznaˇcujeme mnoˇzinu, která nemá ˇzádn´ y prvek. Naz´ yváme ji pr´ azdn´ a mnoˇ zina. Vedle symbolu ⊂ se uˇz´ıv´ a i symbol ⊃ ve v´ yznamu A ⊂ B právˇe kdyˇz B ⊂ A. Nˇekdy se m´ısto ⊂ p´ıˇse symbol ⊆, aby se zd˚ uraznilo, ˇze inkluze pˇripouˇst´ı i moˇznost rovnosti mnoˇzin a zat´ımco a v´ yznam tzv. vlastn´ı inkluze, tj. kaˇzd´ y prvek z A je i v B a existuje prvek z B, kter´ y nen´ı v symbol A ⊂ B m´ A analogicky k nerovnostem a ≤ b a a < b. Základn´ı vlastnosti inkluze shrneme ve vˇetˇe: Vˇ eta 1.21. Pro libovolné mnoˇziny A, B, C plat´ı: (a) ∅ ⊂ A. (b) A ⊂ A. (c) A ⊂ B ∧ B ⊂ C ⇒ A ⊂ C

— tranzitivita inkluze.

(d) A ⊂ B ∧ B ⊂ A ⇔ A = B. Tvrzen´ı a a b jsou zˇrejm´ a a c znamen´ a tranzitivitu inkluze. Tvrzen´ı d má zásadn´ı v´ yznam pro d˚ ukazy mnoˇzinov´ ych rovnost´ı. Chceme-li dokázat, ˇze A = B, tak postupujeme tak, ˇze dokáˇzeme, ˇze A ⊂ B a B ⊂ A. ´ FSI VUT v Brnˇe Studijn´ı text UM

7



Odtud podle (d) jiˇz plyne, ˇze A = B. Pˇ r´ıklad: Rozhodnˇete, které z v´ yrok˚ u jsou pravdivé: • Mnoˇzina {∅} nem´ a ˇz´ adn´ y prvek“ (Nen´ı pravdivý, mnoˇzina m´ a prvek ∅.) ” • {1, 1} = {1}“ (Plat´ı, prvek m˚ uˇze být zaps´ an v´ıckr´ at.) ” • {1} ⊂ {1}“ (Plat´ı.) ” (Plat´ı.) • {1, 2} = {2, 1}“ ” Russel˚ uv paradox (1903). 1.22. N´ asleduj´ıc´ı u ´vaha je typick´ ym pˇr´ıkladem, kter´ y se objevil na poˇcátku 20. stolet´ı v souvislosti se tˇret´ı kriz´ı matematiky. Bud’ A libovolná mnoˇzina. Pak nastane právˇe jedna z moˇznost´ı bud’ A ∈ A nebo A ∈ / A. Vˇsechny mnoˇziny rozdˇel´ıme do dvou skupin X = {A; A ∈ A}, Y = {B; B ∈ / B}. Je zˇrejmé, ˇze ˇzádná mnoˇzina nem˚ uˇze patˇrit do X i Y souˇcasnˇe a ˇze X, Y jsou také mnoˇziny. Uvaˇzme nyn´ı Y . Protoˇze Y je mnoˇzina, mus´ı sama leˇzet v X nebo Y . Pˇripust’me nejprve Y ∈ X. Pak ale podle definice X plat´ı Y ∈ Y , coˇz je spor, nebot’ Y nem˚ uˇze leˇzet v X i Y . Pˇripust’me tedy, ˇze Y ∈ Y . Pak ale z definice Y plyne Y ∈ / Y , coˇz je rovnˇeˇz spor, protoˇze Y nem˚ uˇze leˇzet a souˇcasnˇe neleˇzet v Y . Vzniká neˇreˇsitelná situace na u ´rovni intuitivn´ı teorie mnoˇzin. Pojem mnoˇziny v intuitivn´ım smyslu se ukázal pˇr´ıliˇs ˇsirok´ y. Problém spoˇc´ıvá ve tvorbˇe mnoˇzin: nutno ji omezit jist´ ymi pravidly.

Definice 1.23. Mezi mnoˇzinami A, B definujeme následuj´ıc´ı základn´ı operace: (a) Pr˚ unik A ∩ B := {x : x ∈ A ∧ x ∈ B}. (b) Sjednocen´ı A ∪ B := {x : x ∈ A ∨ x ∈ B}. (c) Rozd´ıl mnoˇ zin A \ B := {x : x ∈ A ∧ x ∈ / B}. (d) Pro mnoˇziny A, B doplnˇ ek (komplement) A v Z je rozd´ıl Z \ A. ˇ Casto se rozd´ıl mnoˇzin m´ısto A \ B p´ıˇse A − B. Pokud je Z dan´ a základn´ı mnoˇzina m´ısto Z \ A p´ıˇseme jenom Ac . Vˇ eta 1.24. Pro mnoˇzinové operace ∩, ∪ plat´ı komutativn´ı asociativn´ı a distributivn´ı zákon: (a) A ∩ B = B ∩ A,

A ∪ B = B ∪ A,

(b) A ∩ (B ∩ C) = (A ∩ B) ∩ C,

A ∪ (B ∪ C) = (A ∪ B) ∪ C ,

(c) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C),

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) .

Definice 1.25. Mnoˇ zina vˇ sech podmnoˇ zin mnoˇziny A, tj. {X : X ⊂ A} se oznaˇcuje exp(A) nebo 2A . Pˇ r´ıklad: Pro A = {a, b, c} je exp(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. Obecnˇe, je-li mnoˇzina A koneˇcn´ a a má n prvk˚ u, potom exp(A) má 2n prvk˚ u. Kart´ ezsk´ y souˇ cin Jak v teorii mnoˇzin zavést kartézsk´ y souˇcin mnoˇzin? Uspoˇrádanou dvojici prvk˚ u a, b definujeme jako mnoˇzinu [a, b] := {{a}, {a, b}}. Pro libovolné mnoˇziny A, B pak kartézsk´ y souˇcin mnoˇzin A, B je mnoˇzina vˇsech uspoˇr´ adan´ ych dvojic prvk˚ u z A a B, tj. A × B := {[a, b] : a ∈ A ∧ b ∈ B}. V tomto pojet´ı pro kartézsk´ y souˇcin neplat´ı asociativn´ı zákon: A × (B × C) ̸= (A × B) × C, protoˇze uvedené mnoˇziny maj´ı jiné prvky. Napˇr´ıklad pro A = {a}, B = {b}, C = {c} je A × (B × C) = {[a, [b, c]]} a (A × B) × C = {[[a, b], c]}.


8



Proto pro praxi zavedeme dohodu, ˇze vnitˇrn´ı závorky odbouráme. Pak m˚ uˇzeme psát A × B × C = {[a, b, c]} a asociativn´ı zákon bude platit i pro kartézsk´ y souˇcin. Pojem uspoˇrádané dvojice, trojice, atd. a kartézského souˇcinu mnoˇzin budeme uˇz´ıvat intuitivnˇe bez vnitˇrn´ıch závorek: Definice 1.26. (a) Uspoˇ r´ adan´ a dvojice prvk˚ u a, b je dvojice prvk˚ u, kdy záleˇz´ı na poˇrad´ı, zapisujeme [a, b], tj. [a, b] a [b, a] jsou r˚ uzné dvojice. Obecnˇe uspoˇ r´ adan´ a n-tice je soubor n prvk˚ u, ve kterém je urˇceno, kter´ y prvek je prvn´ı, druh´ y, . . . n-t´ y, zapisujeme [a1 , a2 , a3 , . . . , an ]. Prvky v n-tici se mohou opakovat. (b) Kart´ ezsk´ y souˇ cin mnoˇzin A a B je mnoˇzina vˇsech uspoˇrádan´ ych dvojic [a, b], kde a ∈ A a b ∈ B: A × B = {[a, b] : a ∈ A ∧ b ∈ B} (c) Podobnˇe zavedeme kartézsk´ y souˇcin n mnoˇzin A1 , A2 , . . . , An : A1 × A2 · · · × An := {[a1 , . . . , an ] : a1 ∈ A1 ∧ a2 ∈ A2 ∧ . . . ∧ an ∈ An }. Jestliˇze mnoˇzina Ai má ki prvk˚ u, potom jejich kartézsk´ y souˇcin má k1 k2 , ·, kn prvk˚ u. M´ısto A × A p´ıˇseme A2 , m´ısto A × A × A × B × C × C m˚ uˇzeme psát A3 × B × C 2 . V tomto pojet´ı uˇz kartézsk´ y souˇcin je asociativn´ı. Kartézsk´ y souˇcin vˇsak nen´ı komutativn´ı, A×B ̸= B×A.


9


1D. Základn´ı ˇc´ıselné mnoˇziny

´ kladn´ı c ˇ´ıselne ´ mnoˇ 1D. Za ziny Za základn´ı ˇc´ıselné mnoˇziny povaˇzujeme ˇc´ısla pˇrirozená N, ˇc´ısla celá Z, ˇc´ısla racionáln´ı Q, ˇc´ısla reálná R a ˇc´ısla komplexn´ı C, která lze seˇradit pomoc´ı inkluze N ⊂ Z ⊂ Q ⊂ R ⊂ C. Pˇ rirozen´ aˇ c´ısla Vych´ az´ıme z mnoˇziny pˇrirozen´ ych ˇc´ısel. Formáln´ı matematická definice pˇrirozen´ ych ˇc´ısel je zaloˇzena na tzv. Peanov´ ych axiomech: (a) Existuje ˇc´ıslo 1. (b) Kaˇzdé pˇrirozené ˇc´ıslo a m´ a následn´ıka, oznaˇceného jako S(a). (c) Neexistuje pˇrirozené ˇc´ıslo, jehoˇz následn´ıkem by byla 0. (d) R˚ uzná pˇrirozen´ a ˇc´ısla maj´ı r˚ uzné následn´ıky: pokud a ̸= b, pak S(a) ̸= S(b). (e) Pokud nˇejakou vlastnost splˇ nuje jak ˇc´ıslo 0, tak i kaˇzdé ˇc´ıslo, které je následn´ıkem nˇejakého ˇc´ısla, které tuto vlastnost splˇ nuje, pak tuto vlastnost splˇ nuj´ı vˇsechna pˇrirozená ˇc´ısla. (Tento axiom zajiˇst’uje platnost d˚ ukaz˚ u technikou matematické indukce.) Pojem mnoˇziny pˇrirozen´ ych ˇc´ısel vˇsak nen´ı jednotn´ y, jsou urˇcité d˚ uvody pˇridat nulu k pˇrirozen´ ym ˇc´ısl˚ um, obvykle se vˇsak nula za pˇrirozené ˇc´ıslo nepovaˇzuje. Definice 1.27. Nekoneˇcnou mnoˇ zinu pˇ rirozen´ ych ˇ c´ısel oznaˇcujeme N := {1, 2, 3, 4, 5, 6, 7, . . . }, jej´ı prvky oznaˇcujeme obvykle p´ısmeny m, n, i, j, k, lze uˇz´ıt i jiná p´ısmena. Mnoˇzina N je uspoˇr´ ad´ ana: pro kaˇzdé dvˇe r˚ uzná ˇc´ısla m, n plat´ı bud’ m < n nebo n < m. Operace sˇc´ıtán´ı m + n i násoben´ı m · n (zkrácenˇe m n) je definována pro kaˇzdé dvˇe pˇrirozená ˇc´ısla m, n. Operace odˇc´ıt´ an´ı m − n je definov´ ana jen pokud m > n. el´ı“ m, tj. existuje k ∈ N, ˇze m = nk. Operace dˇelen´ı m : n je definov´ ana, jen pokud n dˇ ” Nˇekdy se k pˇrirozen´ ym ˇc´ısl˚ um pˇrid´ av´ a i nula, pak p´ıˇseme N0 := {0} ∪ N = {0, 1, 2, 3, . . . }. Cel´ aˇ c´ısla Abychom mohli ˇc´ısla odeˇc´ıtat bez omezen´ı, pˇridáváme záporná celá ˇc´ısla a nulu: Definice 1.28. Mnoˇ zinu cel´ ych ˇ c´ısel Z dostaneme pˇridán´ım nuly a cel´ ych záporn´ ych ˇc´ısel: Z := {1, 2, 3, . . . } ∪ {0} ∪ {−1, −2, −3, . . . } = {0, 1, −1, 2, = 2, 3, −3, . . . } jej´ı prvky opˇet oznaˇcujeme obvykle p´ısmeny m, n, i, j, k. Mnoˇzina Z je také uspoˇrádaná. Operace sˇc´ıtán´ı m + n, násoben´ı mn i odˇc´ıtán´ı m − n jsou definována vˇsechny dvojice cel´ ych ˇc´ısel. Operace dˇelen´ı m : n je definov´ ana jen pro n ̸= 0 a pokud n dˇ el´ı“ m, tj. existuje k ∈ N, ˇze m = nk. ” Racion´ aln´ı ˇ c´ısla Abychom odstranili omezen´ı na dˇelen´ı, pˇridáme zlomky. Dostáváme tak racionáln´ı ˇc´ısla: Definice 1.29. Mnoˇ zinu racion´ aln´ıch ˇ c´ısel oznaˇcujeme Q. Je to vlastnˇe mnoˇzina vˇsech zlomk˚ u, s nenulov´ ym jmenovatelem. Pro jednoznaˇcnost vyjádˇren´ı poˇzadujeme, aby ve jmenovateli zlomku m/n bylo pˇrirozené ˇc´ıslo n > 0 a aby ˇc´ısla m a n byla nesoudˇelná: jejich nejvˇetˇs´ı spoleˇcn´ y dˇelitel D(m, n) byl 1. } {m : m ∈ Z ∧ n ∈ N ∧ D(m, n) = 1 , Q := n Racionáln´ı ˇc´ısla oznaˇcujeme obvykle p´ısmeny x, y, z, p, q, r, a, b, c, d, . . . . Mnoˇzina Q je také uspoˇrádan´ a. Operace sˇc´ıtán´ı x + y, odˇc´ıt´ an´ı x − y a násoben´ı xy jsou definované pro kaˇzdé dvˇe celá ˇc´ısla x, y. Operace dˇelen´ı x : y je definov´ ana, pokud y ̸= 0. Operace se zlomky Je to sice uˇcivo ze základn´ı ˇskoly, najdou se vˇsak studenti, kteˇr´ı tyto operace neovládaj´ı. Patˇr´ı mezi nˇe napˇr´ıklad stˇrihaˇci zlomk˚ u“ kteˇr´ı poˇc´ıtaj´ı podle pravidel“: ” ” 1 1 a + b a b 1 = + , (a + b)−1 = a−1 + b−1 , = + , (a + b)−1 = a−1 + b−1 . 2+3 2 3 c+d c d Dosazen´ım konkrétn´ıch ˇc´ısel za a, b, c, d snadno ovˇeˇr´ıte, ˇze v´ yˇ se uveden´ a pravidla“ neplat´ı. ” ´ FSI VUT v Brnˇe Studijn´ı text UM

10



Pˇripomeˇ nme spr´ avn´ a“ pravidla: ” Vˇ eta 1.30. Pro racionáln´ı reáln´ a i komplexn´ı ˇc´ısla a, b, c, d plat´ı následuj´ıc´ı pravidla: a c ad + bc + = , b d bd a b c d

≡

a c ad − bc − = , b d bd

a c a d ad : = · = b d b c bc

a c ac · = b d bd

pro b ̸= 0 a d ̸= 0,

pro b ̸= 0 a c ̸= 0 a d ̸= 0.

Re´ aln´ aˇ c´ısla Odmocnina z vˇetˇsiny pˇrirozen´ ych ˇc´ısel 2, 3, 5, 6, 7, . . . nen´ı ˇc´ıslo pˇrirozené, ani racionáln´ı, leˇz´ı vˇsak na ˇc´ıselné ose mezi racionáln´ımi ˇc´ısly. Mnoˇzinu reáln´ ych ˇc´ısel tak dostaneme z racionáln´ıch ˇc´ısel vyplnˇen´ım“ ” dˇer mezi racionáln´ımi ˇc´ısly pomoc´ı tzv. iracionáln´ıch ˇc´ısel, které nelze vyjádˇrit zlomkem m n , kde m ∈ Z, n ∈ N. √ √ √ Jsou to napˇr´ıklad odmocniny 2, 3, 5, . . . , a také ˇc´ısla π, e a dalˇs´ı. Reálná ˇc´ısla vych´ azej´ı z geometrické pˇredstavy bod˚ u na pˇr´ımce. Matematická definice zavad´ı reálná ˇc´ısla ˇ pomoc´ı tzv. Dedekindov´ ych ˇrez˚ u. Uved’me hlavn´ı myˇslenku. Rezem nazveme mnoˇzinu racionáln´ıch ˇc´ısel Q rozˇrezanou“ na podmnoˇzinu A a jej´ı doplnˇek Q \ A tak, ˇze pro kaˇzdé a ∈ A a b ∈ Q \ A plat´ı a < b. Mnoˇzina ” A je tak vˇzdy interval racionáln´ıch ˇc´ısel od −∞. Vˇsechny ˇrezy lze rozdˇelit do tˇr´ı druh˚ u: (a) A má maximáln´ı prvek q ∈ Q — tj. A = (−∞, q⟩ ∩ Q, (b) Q \ A má minimáln´ı prvek q ∈ Q — potom A = (−∞, q) ∩ Q, (c) A nem´ a maximáln´ı prvek ani Q \ A nemá minimáln´ı prvek. ˇ ˇ Rezy prvn´ıho druhu ztotoˇzn´ıme s racionáln´ım ˇc´ıslem q, které je maximem A. Rezy druhého druhu nebudeme ˇ uvaˇzovat, protoˇze by urˇcovaly stejné racionáln´ı ˇc´ıslo q. Rez, kde A nemá nejvˇetˇs´ı prvek, ani Q \ A nemá nejmenˇs´ı prvek, definuje nové √ tzv. iracionáln´ı ˇc´ıslo r. Napˇr´ıklad ˇrez A := (−∞, 0) ∪ {q ∈ Q : q 2 ≤ 2} tak definuje ˇ tzv. iracionáln´ı ˇc´ıslo 2. Rezy prvn´ıho a tˇret´ıho druhu jsou uspoˇrádané podle inkluze, coˇz dává uspoˇrádán´ı odpov´ıdaj´ıc´ıch reáln´ ych ˇc´ısel. V´ yjimeˇcné ˇrezy, kde A = ∅ a A = Q nepovaˇzujeme za reálná ˇc´ısla, prvn´ı odpov´ıdá symbolu −∞, druh´ y symbolu ∞. Dále nutno pomoc´ı ˇrez˚ u definovat operace sˇc´ıtán´ı, odˇc´ıtán´ı, násoben´ı i dˇelen´ı reáln´ ych ˇc´ısel. Definice 1.31. Mnoˇ zinu re´ aln´ ych ˇ c´ısel oznaˇcujeme symbolem R, jako u racionáln´ıch ˇc´ısel jej´ı prvky obvykle oznaˇcujeme p´ısmeny x, y, z, p, q, r, a, b, c, d, . . . Pro −∞ < a < b < ∞ definujeme otevˇrené, uzavˇrené intervaly (a, b) := {x ∈ R : a < x < b}

⟨a, b⟩ := {x ∈ R : a ≤ x ≤ b},

a polouzavˇrené (polootevˇrené) intervaly (a, b⟩ := {x ∈ R : a < x ≤ b} a ⟨a, b) := {x ∈ R : a ≤ x < b}. V pˇr´ıpadˇe otevˇreného“ konce pˇripouˇst´ıme a = −∞ nebo b = ∞. ” − − Podmnoˇziny se oznaˇcuj´ı R+ := (0, ∞) a podobnˇe R+ 0 := ⟨0, ∞), R := (−∞, 0) a R0 := (−∞, 0⟩. ∗ Mnoˇzinu reáln´ ych ˇc´ısel rozˇs´ıˇrenou o symboly −∞, ∞ znaˇc´ıme R := R ∪ {−∞, ∞}. Stejnˇe jako u racionáln´ıch ˇc´ısel reáln´ a ˇc´ısla tvoˇr´ı mnoˇzinu uspoˇrádanou. Operace sˇc´ıtán´ı x + y, odˇc´ıtán´ı x − y, násoben´ı xy a dˇelen´ı x : y jsou definov´ any pro vˇsechny dvojice reáln´ ych ˇc´ısel, jen pˇri dˇelen´ı y ̸= 0. Pro otevˇren´ y a uzavˇren´ y interval se uˇz´ıvaj´ı také hranaté závorky: ]a, b[ znamená (a, b) a [a, b] znamená ⟨a, b⟩.

Maximum, supremum, minimum a infimum Omezená (ohraniˇcen´ a) podmnoˇzina M mnoˇziny reáln´ ych ˇc´ısel R m˚ uˇze m´ıt své maximum: je to nejvˇetˇs´ı prvek m mnoˇziny M , tj. m := max(M ) ⇐⇒ m ∈ M ∧ ∀x ∈ M plat´ı x ≤ m. Otevˇren´ y interval (0, 2) tak nemá maximum, protoˇze pravá mez 2, kandidát na maximum, uˇz nen´ı v M a nem˚ uˇze b´ yt proto maximum. Abychom tuto nepˇr´ıjemnost odstranili, zavedeme pojem supremum, které je rovno maximu, v pˇr´ıpadˇe, ˇze maximum existuje. Je to nejmenˇs´ı horn´ı závora“, tj. ˇc´ıslo, které je vˇetˇs´ı nebo rovno neˇz ” vˇsechna ˇc´ısla mnoˇziny M . Omezená podmnoˇzina také nemus´ı m´ıt své minimum, napˇr´ıklad opˇet interval (0, 2). Podobn´ ymi u ´vahami zobecnˇen´ım pojmu minimum dostaneme pojem infimum: je to nejvˇetˇs´ı doln´ı závora“, tj. ” ˇc´ıslo menˇs´ı nebo rovno neˇz vˇsechna ˇc´ısla mnoˇziny M .


11



Definice 1.32. Bud’ M neprázdn´ a omezená podmnoˇzina mnoˇziny reáln´ ych ˇc´ısel R. Potom ˇrekneme: ˇ ıslo h je horn´ı z´ (a) C´ avora mnoˇziny M , jestliˇze ∀x ∈ M plat´ı x ≤ h. ˇ (b) C´ıslo s je supremum mnoˇziny M jestliˇze s je nejmenˇs´ı horn´ı závora, p´ıˇseme s = sup M . ˇ ıslo d je doln´ı z´ (c) C´ avora mnoˇziny M , jestliˇze ∀x ∈ M plat´ı x ≥ d. ˇ ıslo i je infimum mnoˇziny M , jestliˇze i je nejvˇetˇs´ı horn´ı závora, p´ıˇseme i = inf M . (d) C´ (e) Pokud mnoˇzina M nen´ı omezená (ohraniˇcená) shora, poloˇz´ıme sup(M ) = ∞. (f) Pokud mnoˇzina M nen´ı omezená (ohraniˇcená) zdola, poloˇz´ıme inf(M ) = −∞. (g) V pˇr´ıpadˇe prázdné mnoˇziny M = ∅ poloˇz´ıme sup(M ) = −∞ a inf(M ) = ∞. Definice suprema a infima je sloˇzitˇejˇs´ı neˇz definice maxima a minima, pojmy supremum a infimum maj´ı vˇsak lepˇs´ı vlastnosti: vˇzdy existuj´ı. Vˇ eta 1.33. Uvaˇzujme libovolné podmnoˇziny M, M1 , M2 , . . . mnoˇziny reáln´ ych ˇc´ısel. (a) Kaˇzdá podmnoˇzina M mnoˇziny reáln´ ych ˇc´ısel R má svoje supremum a infimum. (b) Pro kaˇzdou neprázdnou M plat´ı −∞ ≤ inf(M ) ≤ sup(M ) ≤ ∞. (c) Plat´ı sup(M1 ∪ M2 ) = max(sup(M1 ), sup(M2 )). (d) Plat´ı inf(M1 ∪ M2 ) = min(inf(M1 ), inf(M2 )). Komplexn´ı ˇ c´ısla Podnˇetem pro rozˇs´ıˇren´ı reáln´ ych ˇc´ısel byla skuteˇcnost, ˇze kvadratické rovnice a x2 +b x+c = 0 s reáln´ ymi koeficienty v pˇr´ıpadˇe záporného diskriminantu D := b2 −4ac < 0 nemaj´ı v oboru reáln´ ych ˇc´ısel ˇreˇsen´ı. Rozˇs´ıˇren´ı spoˇc´ıv´ a v tom, ˇze k reálné ˇc´ asti pˇridáme tzv. imaginárn´ı ˇcást. Komplexn´ı ˇc´ısla tak nelze znázornit na reálné pˇr´ımce, ale v tzv. komplexn´ı rovinˇe. Definice 1.34. Komplexn´ı ˇc´ıslo z = [x, y] lze reprezentovat uspoˇrádanou dvojici reáln´ ych ˇc´ısel x, y, kde x se naz´ yvá re´ aln´ a ˇ c´ ast a y je imagin´ arn´ı ˇ c´ a√st. Zapisujeme ho ve tvaru z = x + iy, kde i oznaˇcuje jednotku imaginárn´ı ˇcásti ˇcasto nepˇresnˇe psané i = −1. Mnoˇzinu komplexn´ıch ˇc´ısel C lze ztotoˇznit s rovinou R2 . Komplexn´ı ˇc´ıslo a jeho sloˇzky obvykle zapisujeme p´ısmeny z ≡ [x, y] ≡ x + iy, také w ≡ [u, v] ≡ u + iv. Komplexn´ı ˇc´ısla nelze rozumnˇe“ uspoˇr´ adat, mnoˇzina komplexn´ıch ˇc´ısel C netvoˇr´ı uspoˇrádanou mnoˇzinu. ” Operace sˇc´ıtán´ı a odˇc´ıt´ an´ı jsou definov´ any po sloˇzkách: pro zi ≡ [xi , yi ] ≡ xi + iyi poloˇz´ıme z1 + z2 := [x1 + x2 , y1 + y2 ] ≡ (x1 + x2 ) + i(y1 + y2 ), z1 − z2 := [x1 − x2 , y1 − y2 ] ≡ (x1 − x2 ) + i(y1 − y2 ). Z vlastnosti i · 1 = 1 · i = i a i · i = −1 lze odvodit pravidlo pro násoben´ı: z1 · z2 := [x1 x2 − y1 y2 , x1 y2 + x2 y1 ] ≡ (x1 x2 − y1 y2 ) + i(x1 y2 + x2 y1 ) . ˇ ıslo z := [x, −y] ≡ x − iy se naz´ C´ yv´ a ˇc´ıslo komplexnˇe sdruˇzené k ˇc´ıslu z = [x, y]. Operace násoben´ı je rozˇs´ıˇren´ım operace násoben´ı reáln´ ym ˇc´ıslem: pokud z1 := [r, 0] je reálné ˇc´ıslo, potom z1 · z2 = [r, 0] · [x2 , y2 ] = [rx2 , ry2 ]. Absolutn´ı hodnota

Vzdálenost“ ˇc´ısla od nuly naz´ yváme absolutn´ı hodnotou. ”

Definice 1.35. Pro nezáporné ˇc´ıslo (celé, racionáln´ı i reálné) ˇc´ıslo je√absolutn´ı hodnota |x| stejné ˇc´ıslo x. Pro 2 záporné ˇc´ıslo x < 0 je |x| y pro komplexn´ı ˇc´ıslo z = [x, y] √ = −x, tj. ˇc´ıslo kladné. Plat´ √ ı vzorec |x| = x , kter´ nutno doplnit na |z| = x2 + y 2 , také plat´ı |z| = z · z. Vˇ eta 1.36. Operace sˇc´ıt´ an´ı a násoben´ı na reáln´ ych i komplexn´ıch ˇc´ıslech jsou asociativn´ı, komutativn´ı a jsou spojeny distributivn´ım zákonem. Pro absolutn´ı hodnotu plat´ı |xy| = |x| · |y| a |x + y| ≤ |x| + |y|.


12


1E. Relace

1E. Relace Definice 1.37. Bud’te dvˇe neprázdné mnoˇziny A a B, které nemus´ı b´ yt r˚ uzné. Bin´ arn´ı relac´ı R mezi mnoˇ zinami A, B nazveme libovolnou podmnoˇzinou R kartézského souˇcinu A × B R ⊂ A × B := {[a, b] : a ∈ A ∧ b ∈ B} Je-li A = B mluv´ıme o bin´ arn´ı relaci na mnoˇ zinˇ e A. Binárn´ı relace R urˇcuje dvˇe v´ yznaˇcné mnoˇziny: Definiˇ cn´ı obor relace R: D(R) := {a ∈ A ∃ b ∈ B : [a, b] ∈ R} Obor hodnot relace R: H(R) := {b ∈ B ∃ a ∈ A : [a, b] ∈ R}. Pˇr´ıkladem binárn´ı relace je tzv. relaˇcn´ı datab´ aze, která strukturuje data ve formˇe tabulek. Napˇr´ıklad relace R ⊂ A × B, kde A je mnoˇzina zamˇestnanc˚ u, B mnoˇzina vozidel a relace R vyjadˇruje, kdo s kter´ ym vozidlem má právo jezdit. Binárn´ı relace R na mnoˇzinˇe A mohou m´ıt ˇradu v´ yznamn´ ych vlastnost´ı. Nejd˚ uleˇzitˇejˇs´ı z nich pop´ıˇseme v následuj´ıc´ı definici: Definice 1.38. Bud’ R binárn´ı relace na mnoˇzinˇe A. Nazveme ji (a) reflexivn´ı, pokud ∀a ∈ A : [a, a] ∈ R, (b) symetrick´ a, pokud ∀a, b ∈ A : [a, b] ∈ R ⇒ [b, a] ∈ R, (c) antisymetrick´ a, pokud ∀a, b ∈ A : [a, b] ∈ R ∧ [b, a] ∈ R ⇒ a = b, (d) tranzitivn´ı, pokud ∀a, b, c ∈ A : [a, b] ∈ R ∧ [b, c] ∈ R ⇒ [a, c] ∈ R, (e) ekvivalence, pokud je reflexivn´ı, symetrická a tranzitivn´ı. Pˇ r´ıklad: Na mnoˇzin´ ach N, Z, Q, R máme pˇrirozenou relaci R neostré nerovnosti ≤“ definovanou [x, y] ∈ R ” jestliˇze x < y. Tato relace je reflexivn´ı, antisymetrická a tranzitivn´ı. Neostrá nerovnost <“ je tranzitivn´ı, nen´ı ” symetrická ani reflexivn´ı. Pˇ r´ıklad: Mezi koneˇcn´ ymi mnoˇzinami N m˚ uˇzeme zavést relaci R poˇctu prvk˚ u: [A, B] ∈ R pokud mnoˇziny A a B maj´ı stejn´ y poˇcet prvk˚ u. Tato relace je reflexivn´ı, symetrická a tranzitivn´ı, je proto ekvivalenc´ı. Definice 1.39. Bud’ R ⊂ A × B. Relaci R−1 nazveme relac´ı inverzn´ı k relaci R, pokud je podmnoˇzinou B × A a plat´ı [b, a] ∈ R−1 právˇe kdyˇz [a, b] ∈ R. Pˇ r´ıklad: Relace ≥“ je inverzn´ı k relaci ≤“ a >“ je inverzn´ı k relaci <“. Je-li relace R na mnoˇzinˇe A ” ” ” ” symetrická, R−1 = R. Pojem binárn´ı relace lze zobecnit na relaci mezi v´ıce mnoˇzinami: Definice 1.40. n-´ arn´ı relac´ı rozum´ıme libovolnou podmnoˇzinu kartézského souˇcinu A1 × A2 × · · · An , kde A1 , A2 , . . . , An jsou neprázdné ne nutnˇe r˚ uzné mnoˇziny.


13


1F. Zobrazen´ı

1F. Zobrazen´ı Zobrazen´ı je základn´ım pojmem v matematice. Po formáln´ı stránce je to relace F, ve které pro kaˇzdé a ∈ A existuje nejv´ yˇse jedno b ∈ B, ˇze [a, b] ∈ F . Jazykem matematiky to zapisujeme následovnˇe: Definice 1.41. Zobrazen´ım z mnoˇziny A do mnoˇziny B nazveme relaci F, která splˇ nuje ∀ a ∈ A ∀ b ∈ B : ([a, b1 ] ∈ F ∧ [a, b2 ] ∈ F

=⇒

b1 = b2 ).

M´ısto F ⊂ A × B uˇz´ıv´ ame zápisu f : A → B a m´ısto [a, b] ∈ F p´ıˇseme b = f (a), nebo a 7→ f (a). Prvek a se pˇritom naz´ yv´ a vzor prvku b v zobrazen´ı f a b ˇr´ıkáme obraz prvku a v zobrazen´ı f . Funkc´ı obvykle rozum´ıme zobrazen´ı, kde mnoˇzina B je ˇc´ıselná. Pojem definiˇcn´ı obor a obor hodnot relace pˇreneseme na zobrazen´ı: Definice 1.42. Vˇsechna a ∈ A, pro které existuje b ∈ B takové, ˇze f (a) = b, tj. [a, b] ∈ F, tvoˇr´ı mnoˇzinu, které ˇr´ıkáme definiˇ cn´ı obor zobrazen´ı f a znaˇc´ıme D(f ). Vˇsechna b ∈ B, pro které existuje a ∈ A takové, ˇze f (a) = b, tj. [a, b] ∈ F, tvoˇr´ı mnoˇzinu, které ˇr´ıkáme obor hodnot zobrazen´ı f a znaˇc´ıme ji H(f ). Definice 1.43. (Skl´ ad´ an´ı zobrazen´ı) Bud’te A, B, C mnoˇziny a f : A → B a g : B → C zobrazen´ı. Pokud H(f ) ⊂ D(g) existuje sloˇzené zobrazen´ı g ◦ f : A → C definované vztahem (g ◦ f )(x) = g(f (x)), ∀ x ∈ D(f ). D˚ uleˇzit´ ymi vlastnostmi zobrazen´ı jsou následuj´ıc´ı pojmy: Definice 1.44. Zobrazen´ı f : A → B (definované na celém A, tj. D(f ) = A) nazveme (a) prost´ e neboli injektivn´ı nebo injekce jestliˇze kaˇzd´ y obraz má jenom jeden vzor, tj. ∀ a 1 , a2 ∈ A a ∀ b ∈ B

plat´ı b = f (a1 ), b = f (a2 ) ⇒ a1 = a2 .

(b) na neboli surjektivn´ı nebo surjekce jestliˇze obor hodnot funkce je celá mnoˇzina B, tj. H(f ) = B. (c) vz´ ajemnˇ e jednoznaˇ cn´ e neboli bijektivn´ı nebo bijekce jestliˇze je injektivn´ı i surjektivn´ı. ˇ ıkáme, ˇze f je bijekce mnoˇzin A a B. R´ Skládán´ı zobrazen´ı (pokud je definované) je asociativn´ı: (f ◦ g) ◦ h = f ◦ (g ◦ h). Kaˇzdá binárn´ı relace R ⊂ A × B má svoji inverzn´ı relaci R−1 ⊂ B × A. Pro bijektivn´ı zobrazen´ı f : A → B stejn´ ym zp˚ usobem definujeme inverzn´ı zobrazen´ı f −1 : B → A. Definice 1.45. Bud’ f : A → B vz´ ajemnˇe jednoznaˇcné zobrazen´ı mezi mnoˇzinami A a B Potom zobrazen´ı f −1 nazveme zobrazen´ım inverzn´ım k zobrazen´ı f jestliˇze pˇr´ısluˇsná relace F −1 je inverzn´ı k relaci F, tj. ∀ a ∈ A ∀ b ∈ B : f −1 (b) = a ⇐⇒ f (a) = b . Pokud zobrazen´ı f definované na Df ⊂ B je prosté, lze definovat inverzn´ı zobrazen´ı f −1 na D(f −1 ) = H(f ) s oborem hodnot H(f −1 ) = D(f ). Pozn´ amky: (a) Skládán´ı zobrazen´ı (pokud je definované) je asociativn´ı: (f ◦ g) ◦ h = f ◦ (g ◦ h), nen´ı vˇsak komutativn´ı, g ◦ f nemus´ı b´ yt v˚ ubec definované. (b) Zvláˇstn´ım pˇr´ıpadem zobrazen´ı je identické zobrazen´ı IM na mnoˇzinˇe M . Je to zobrazen´ı z M do M , které nic nedˇel´ a“, tj. D(IM ) = H(IM ) = M a IM (x) = x , ∀ x ∈ M . ” (c) Identické zobrazen´ı je bijektivn´ı z M na M , má inverzn´ı zobrazen´ı, které je stejné, tj. (IM )−1 = IM . P˚ usob´ı jako neutráln´ı prvek: pro f : A → B plat´ı f = IA ◦ f = f ◦ IB . (d) Inverzn´ı zobrazen´ı m˚ uˇzeme definovat vztahem f −1 ◦ f = IB a f ◦ f−1 = IB . Dalˇs´ı u ´vahy budeme prov´ adˇet pro následuj´ıc´ı ˇ c´ıseln´ e mnoˇ ziny: mnoˇzinu pˇ rirozen´ ych ˇ c´ısel N, mnoˇzinu cel´ ych ˇ c´ısel Z, mnoˇzinu racion´ aln´ıch ˇ c´ısel Q a mnoˇzinu re´ aln´ ych ˇ c´ısel R. ´ FSI VUT v Brnˇe Studijn´ı text UM

14


1G. Mohutnost mnoˇzin

1G. Mohutnost mnoˇ zin Která ze dvou mnoˇzin má v´ıc prvk˚ u? V pˇr´ıpadˇe koneˇcn´ ych mnoˇzin staˇc´ı porovnat poˇcty prvk˚ u obou mnoˇzin. V pˇr´ıpadˇe nekoneˇcn´ ych mnoˇzin se mnoˇziny porovnávaj´ı pomoc´ı bijektivn´ıho zobrazen´ı: Pˇ r´ıklad: V pˇr´ıpadˇe bijekce kaˇzdému prvku mnoˇziny A odpov´ıdá právˇe jeden prvek mnoˇziny B; jsou-li mnoˇziny A a B koneˇcné, maj´ı nutnˇe stejn´ y poˇcet prvk˚ u; jsou-li nekoneˇcné a existuje-li mezi nimi bijekce, m˚ uˇzeme také ˇr´ıci, ˇze maj´ı stejnˇe“ prvk˚ u, pˇresnˇeji ˇr´ık´ ame, ˇze maj´ı stejnou mohutnost. ” Povˇsimnˇeme si nˇekter´ ych mnoˇzin, které maj´ı stejnou mohutnost jako mnoˇzina pˇrirozen´ ych ˇc´ısel N, tedy jejich prvky lze pˇrirozen´ ymi ˇc´ısly oindexovat. Pˇritom jedna m˚ uˇze b´ yt vlastn´ı podmnoˇzinou druhé a pˇresto má stejnou mohutnost. Je to je napˇr´ıklad mnoˇzina vˇsech kladn´ ych sud´ ych ˇc´ısel {2, 4, 6, 8, 10, . . . }, kdy bijekc´ı je zobrazen´ı a 7→ 2a. Také mnoˇzinu vˇsech cel´ ych ˇc´ısel Z lze oindexovat pˇrirozen´ ymi ˇc´ısly, pokud ji seˇrad´ıme do posloupnosti {0, −1, 1, −2, 2, −3, 3, −4, 4, −5, 5, . . . }. Pˇrekvapivé vˇsak je, ˇze stejnou mohutnost má i mnoˇzina vˇsech racionáln´ıch ˇc´ısel Q, coˇz lze dokázat následovnˇe: ˇ ıslo 0 zap´ıˇseme jako 0 ). racionáln´ı ˇc´ıslo zap´ıˇseme ve tvaru pq , kde p je celé, q pˇrirozené a p, q jsou nesoudˇelná. C´ 1 p Kaˇzdému ˇc´ıslu q nyn´ı pˇriˇrad´ıme tzv. výˇsku r = |p| + q. Protoˇze poˇcet racionáln´ıch ˇc´ısel s konkrétn´ı v´ yˇskou je koneˇcn´ y, jejich oindexován´ı definujeme tak, ˇze nejdˇr´ıve vyp´ıˇseme vˇsechna ˇc´ısla s v´ yˇskou r = 1, pak s v´ yˇskou r = 2, r = 3, r = 4, atd. T´ımto zp˚ usobem dostaneme posloupnost, která obsahuje vˇsechna racionáln´ı ˇc´ısla: { } 0 −1 1 −2 −1 1 2 −3 −1 1 3 −4 −3 −2 −1 1 2 3 4 −5 5 −6 , , , , , , , , , , , , , , , , , ,... , ,... 1 1 1 1 2 2 1 1 3 3 1 1 2 3 4 4 3 2 1 1 1 1 Definice 1.46. Nekoneˇcné mnoˇziny se stejnou mohutnost´ı jako N se naz´ yvaj´ı spoˇ cetn´ e. Mnoˇziny koneˇcné a spoˇcetné se dohromady oznaˇcuj´ı term´ınem nejv´ yˇ se spoˇ cetn´ e. Mnoˇziny, které maj´ı nekoneˇcnˇe mnoho prvk˚ u, ale bijekce s pˇrirozen´ ymi ˇc´ısly neexistuje naz´ yváme mnoˇziny nespoˇ cetn´ e. Pˇ r´ıklad: Dokaˇzme nyn´ı, ˇze mnoˇzina vˇsech reáln´ ych ˇc´ısel R nen´ı spoˇcetná, tj. je nespoˇcetná. Staˇc´ı ovˇsem, kdyˇz dokáˇzeme, ˇze je nespoˇcetn´ a nˇejak´ a ˇc´ ast mnoˇziny R, tedy napˇr. interval [0, 1). Pˇredpokládejme opak, tzn. ˇze vˇsechna ˇc´ısla z intervalu [0, 1) lze nˇejak uspoˇrádat do nekoneˇcné posloupnosti a1 = 0, a11 a12 a13 a14 . . . a1n . . . a2 = 0, a21 a22 a23 a24 . . . a2n . . . a3 = 0, a31 a32 a33 a34 . . . a3n . . . a4 = 0, a41 a42 a43 a44 . . . a4n . . . ... an = 0, an1 an2 an3 an4 . . . ann . . . ... kde aik ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} je k-t´ a ˇc´ıslice v desetinném vyjádˇren´ı ˇc´ısla ai . Sestrojme nyn´ı ˇc´ıslo b = 0, b1 b2 b3 b4 . . . bn . . . takto: je-li aii = 1, klademe bi = 2, je-li aii ̸= 1, klademe bi = 1. ˇ ıslo b takto sestrojené je r˚ C´ uzné od vˇsech ˇc´ısel ai (od a1 se liˇs´ı v prvn´ı ˇc´ıslici za desetinnou ˇcárkou, od a2 se liˇs´ı v druhé ˇc´ıslici za desetinnou ˇc´ arkou, atd.). Protoˇze ale b ∈ [0, 1), mˇelo by b´ yt ve vypsaném seznamu, tzn. mˇelo by b´ yt nˇekter´ ym z ˇc´ısel ai , coˇz je spor. Interval [0, 1) a tud´ıˇz i mnoˇzina R jsou nespoˇcetné mnoˇziny.


15


1H. Algebraické struktury

´ struktury 1H. Algebraicke Pojem zobrazen´ı nám umoˇzn ˇuje korektnˇe (pokud nechceme akceptovat intuitivn´ı definice jako matice je tabulka ˇc´ısel uspoˇr´ adan´ ych do ˇr´ adk˚ u a sloupc˚ u“ a funkce je pˇredpis“) zavést ˇradu dalˇs´ıch pojm˚ u: ” ” Re´ aln´ a matice s m ˇr´ adky a n sloupci je zobrazen´ı A : {1, . . . , m} × {1, . . . , n} → R. Re´ aln´ a funkce re´ aln´ e promˇ enn´ e je zobrazen´ı f : R → R. Také základn´ı pojem operace je definov´ an pomoc´ı pojmu relace a zobrazen´ı: Definice 1.47. Bin´ arn´ı operac´ı na mnoˇzinˇe A nazveme zobrazen´ı f z A × A do A f :A×A→A

f : [a1 , a2 ] 7→ f (a1 , a2 ) = a

pˇriˇcemˇz m´ısto f (a1 , a2 ) = a nebo [a1 , a2 , a] ∈ F p´ıˇseme a1 ∗ a2 = a a symbol ∗ lze nahradit ⋆, ◦, •, . . . . V obecnˇejˇs´ım pojet´ı n-´ arn´ı operac´ı z A1 × A2 × · · · × AN do A rozum´ıme zobrazen´ı f : A1 × A2 × · · · × An → An+1 . ˇ Casto A1 = A2 = · · · = An = An+1 , potom mluv´ıme o n-árn´ı operaci na mnoˇzinˇe A. Pozn´ amky: Operace m˚ uˇze m´ıt n = 1, 2, 3, . . . tzv. argument˚ u. Pro n = 1 pˇr´ıkladem 1-´ arn´ı operace zvané un´ arn´ı je opaˇcn´ a hodnota −r re´ alného ˇc´ısla r. Pro n = 2 se operace naz´ yvá bin´ arn´ı, pˇr´ıkladem je souˇcet dvou ˇc´ısel. Pro n = 3 se 3-árn´ı operac´ı naz´ yv´ a tern´ arn´ı, atd. Také konstanty, napˇr´ıklad 0 a 1 lze povaˇzovat za n = 0 nul´ arn´ı operaci. Definice 1.48. Algebraickou strukturou rozum´ıme mnoˇzinu A spolu s nˇejak´ ymi operacemi na n´ı. Pozn´ amky: Definice operace na mnoˇzinˇe A zajiˇst’uje, ˇze neomezené uˇzit´ı operace nevede nikdy k vybˇehnut´ı“ ” z mnoˇziny A, ˇr´ıkáme, ˇze struktura je tyto operace uzavˇrená. Vyˇsetˇrován´ım obecn´ ych vlastnost´ı algebraick´ ych struktur se zab´ yvá ˇcást matematiky zvaná algebra. Základn´ı strukturou studovanou v algebˇre je grupa, uved’me jej´ı definici: Definice (G1) (G2) (G3)

1.49. Algebraick´ a struktura s mnoˇzinou G a binárn´ı operac´ı ∗ se naz´ yvá grupou, jestliˇze plat´ı: Pro vˇsechna a, b, c ∈ G plat´ı (a ∗ b) ∗ c = a ∗ (b ∗ c) (asociativita) Existuje prvek e ∈ G, ˇze pro kaˇzdé a ∈ G plat´ı a ∗ e = e ∗ a = e (existence neutr´ aln´ıho prvku) Pro kaˇzdé a ∈ G existuje b ∈ G, ˇze plat´ı a ∗ b = b ∗ a (existence opaˇ cn´ eho prvku)

Pozn´ amky: (a) Existenci neutráln´ıho prvku – vlastnost (G2) – lze povaˇzovat za nulárn´ı operaci a existenci opaˇcného prvku – (G3) – za unárn´ı operaci. (b) Pˇr´ıkladem grupy je mnoˇzina cel´ ych ˇc´ısel Z s operac´ı sˇc´ıtán´ı: neutráln´ım prvkem je prvek 0, prvku inverzn´ım k prvku a je −a. Podobnˇe mnoˇziny racionáln´ıch Q, reáln´ ych R i komplexn´ıch C ˇc´ısel s operac´ı sˇc´ıtán´ı jsou grupy. Protoˇze sˇc´ıt´ an´ı ˇc´ısel je komutativn´ı, grupy jsou komutativn´ı. (c) Také mnoˇzina nenulov´ ych racionáln´ıch Q \ {0}, reáln´ ych R \ {0} i C \ {0} komplexn´ıch ˇc´ısel s operac´ı násoben´ı jsou komutativn´ı grupy. Neutráln´ım prvkem je ˇc´ıslo 1 a inverzn´ım prvkem k ˇc´ıslu a je ˇc´ıslo a−1 = a1 . (d) Mnoˇzina vˇsech bijektivn´ıch zobrazen´ı z M do M s operac´ı skládán´ı tvoˇr´ı také grupu. Neutráln´ım prvkem je identické zobrazen´ı IM , inverzn´ım prvkem je inverzn´ı zobrazen´ı. Tato grupa vˇsak komutativn´ı nen´ı. Jde o typick´ y postup matematické abstrakce: abstraktn´ı popis algebraick´ ych struktur pak m˚ uˇze b´ yt vyuˇzit v jednotliv´ ych problémech. Napˇr´ıklad vlastnosti grupy lze uplatnit pro ˇc´ıselné mnoˇziny Z, Q, R i C s operac´ı sˇc´ıtán´ı. D˚ uleˇzité jsou i struktury s dvˇema operacemi jakou je okruh, tˇeleso.


16

1. Základy matematiky

Recommend Documents