1 Matematika jako část logiky

1

Matematika jako ˇ c´ ast logiky

Matematika, kterou jste se uˇcili na stˇredn´ı ˇskole, byla sp´ıˇse matematikou praktickou. To znamen´a, ˇze obsahovala hlavnˇe n´avody jak poˇc´ıtat s ˇc´ısly, jak upravovat r˚ uzn´e v´ yrazy (napˇr. algebraick´e nebo v´ yrazy s goniometrick´ ymi funkcemi) nebo jak vyˇreˇsit nˇejakou konkr´etn´ı soustavu line´arn´ıch rovnic. Nicm´enˇe souˇcasn´a matematika nen´ı vˇeda, kter´a by se snaˇzila ˇreˇsit r˚ uzn´e typy konkr´etn´ıch u ´loh. N´ avody na ˇreˇsen´ı tˇechto u ´loh jsou obvykle jen d˚ usledkem nˇejak´e matematick´e teorie. Matematickou teorii dostaneme tak, ˇze naˇse objekty z´ajmu, kter´e chceme studovat (napˇr. pˇr´ımky a body v rovinˇe), pop´ıˇseme mnoˇzinou tzv. axiom˚ u (tj. tvrzen´ı o kter´ ych v´ıme, ˇze je naˇse studovan´e objekty splˇ nuj´ı, napˇr. kaˇzd´ a dvojice ruzn´ ych bod˚ u urˇcuje pr´avˇe jednu pˇr´ımku). Hlavn´ım u ´kolem matematika potom je hledat jin´ a tvrzen´ı, kter´a z tˇechto axiom˚ u plynou (tzn. jsou pravdiv´a v dan´e teorii, protoˇze o axiomech v´ıme, ˇze plat´ı). Matematiku m˚ uˇzeme tedy obecnˇe popsat, jako vˇedu, kter´a se snaˇz´ı nach´azet pravdiv´a tvrzen´ı v jednotliv´ ych matematick´ ych teori´ıch. Je to tedy ˇc´ast logiky, protoˇze logika je vˇedou, kter´a popisuje pravidla spr´ avn´eho usuzov´ an´ı (tzn. jak z nˇejak´ ych pravdiv´ ych tvrzen´ı vyvozovat jin´ a pravdiv´a tvrzen´ı).

1.1

Logika

Naˇs´ım u ´kolem v tomto kurzu bude objevovat pravdiv´a tvrzen´ı v jedn´e konkr´etn´ı matematick´e teorii (v teorii line´arn´ıch prostor˚ u). Co to tedy tvrzen´ı je? Tvrzen´ı je vˇeta, kter´a je bud’ pravdiv´a nebo nepravdiv´a. Pˇr´ıklady mohou b´ yt: ˇ ıslo 10 je dˇeliteln´e ˇc´ıslem 3.” 1. “C´ 2. “Existuje nekoneˇcnˇe mnoho prvoˇc´ısel.” 3. “Kaˇzd´ yu ´hel m˚ uˇze b´ yt roztˇretˇen pomoc´ı prav´ıtka a kruˇz´ıtka.” Prvn´ı tvrzen´ı je evidentnˇe nepravdiv´e. Druh´e je pravdiv´e, jak uk´azal slavn´ y matematik Euclides. Posledn´ı je pˇr´ıklad nepravdiv´eho v´ yroku, jehoˇz nepravdivost dok´ azal Galois. Samozˇrejmˇe v bˇeˇzn´em jazyce m´ame spoustu vˇet, kter´ ym nelze pˇriˇradit ˇz´adnou pravdivostn´ı hodnotu (tj. nejsou to tvrzen´ı v naˇsem smyslu) napˇr: 1. Citoslovce: “Mlask.” 2. T´azac´ı vˇety: “Chceˇs mˇe kotˇe?” 3. Pˇr´ıkazy: “Chlastej!” Sloˇzitˇejˇs´ı tvrzen´ı se obvykle skl´ adaj´ı z jednoduˇsˇs´ıch tvrzen´ıch pomoc´ı logick´ ych spojek (napˇr. ˇc´ıslo 5 je lich´e nebo sud´e). Pravdivost takov´eho tvrzen´ı potom z´ aleˇz´ı na pravdivosti onˇech jednoduˇsˇs´ıch tvrzen´ıch a na logick´ ych spojk´ach, kter´e byly v dan´em pˇr´ıpadˇe pouˇzity. Ukaˇzme si tedy jednotliv´e logick´e spojky, se kter´ ymi se budeme v matematice st´ale potk´avat. Negace M´ame-li nˇejak´e tvrzen´ı T , m˚ uˇzeme z nˇeho s pomoc´ı negace vyrobit opaˇcn´e tvrzen´ı (symbolicky ho znaˇc´ıme ¬T ), kter´e plat´ı, kdyˇz neplat´ı T a neplat´ı, kdyˇz T plat´ı. Napˇr. pokud T je tvrzen´ı “5 je prvoˇc´ıslo”, pak ¬T je tvrzen´ı “5 nen´ı prvoˇc´ıslo”. Schematicky m˚ uˇzeme tuto skuteˇcnost zapsat pomoc´ı n´asleduj´ıc´ı tabulky, kde 0 pˇredstavuje fakt, ˇze dan´e tvrzen´ı nen´ı pravdiv´e a 1, ˇze pravdiv´e je: ¬T 1 0

T 0 1

1

Konjunkce Mˇejme dvˇe tvrzen´ı A, B. Konjunkce tˇechto tvrzen´ı (symbolicky ji znaˇc´ıme A ∧ B) je tvrzen´ı, kter´e plat´ı pouze v pˇr´ıpadˇe, kdy plat´ı obˇe tvrzen´ı A a B. Ve vˇsech ostatn´ıch pˇr´ıpadech je nepravdiv´e. Tvrzen´ı A ∧ B obvykle ˇcteme jako “A a B” nebo “A a tak´e B” nebo “A a z´aroveˇ n B”. Napˇr. tvrzen´ı “7 je prvoˇc´ıslo a tak´e 3 je prvoˇc´ıslo” je pravdiv´e a tvrzen´ı “7 je prvoˇc´ıslo a 4 je prvoˇc´ıslo” je nepravdiv´e, protoˇze 4 nen´ı prvoˇc´ıslo. Zp˚ usob jak´ ym konjunkce pracuje m˚ uˇzeme opˇet zn´ azornit tabulkou: A 0 0 1 1

A∧B 0 0 0 1

B 0 1 0 1

Disjunkce Mˇejme dvˇe tvrzen´ı A, B. Disjunkce tˇechto tvrzen´ı (symbolicky ji znaˇc´ıme A ∨ B) je tvrzen´ı, kter´e neplat´ı pouze v pˇr´ıpadˇe, kdy neplat´ı obˇe tvrzen´ı A a B. Ve vˇsech ostatn´ıch pˇr´ıpadech je pravdiv´e. Tvrzen´ı A ∨ B obvykle ˇcteme jako “A nebo B”. Napˇr. tvrzen´ı “7 je prvoˇc´ıslo nebo 4 je prvoˇc´ıslo” je pravdiv´e a tvrzen´ı “6 je prvoˇc´ıslo nebo 4 je prvoˇc´ıslo” je nepravdiv´e, protoˇze ani 6 ani 4 nen´ı prvoˇc´ıslo. Zp˚ usob jak´ ym disjunkce pracuje m˚ uˇzeme opˇet zn´ azornit tabulkou: A 0 0 1 1

A∨B 0 1 1 1

B 0 1 0 1

Vˇsimˇete si, ˇze matematika spojku “nebo” pouˇz´ıv´a ve sluˇcovac´ı v´ yznamu, tj. pravdivost jedn´e ˇc´asti disjukce staˇc´ı na pravdivost cel´e disjunkce (ale mohou platit klidnˇe obˇe dvˇe). Kdeˇzto v bˇeˇzn´em jazyce pouˇz´ıv´ame nˇekdy spojku “nebo” i ve vyluˇcovac´ım v´ yznamu. Napˇr. vˇetou “K obˇedu si d´am gul´aˇs nebo sv´ıˇckovou.” obvykle m´ın´ıme, ˇze si d´ame jen jedno z tˇechto dvou j´ıdel a ne obˇe z´aroveˇ n. Implikace Mˇejme opˇet dvˇe tvrzen´ı A, B. Implikace tˇechto tvrzen´ı (symbolicky ji znaˇc´ıme A ⇒ B) je tvrzen´ı, kter´e neplat´ı pouze v pˇr´ıpadˇe, kdy plat´ı tvrzen´ı A a neplat´ı B. Ve vˇsech ostatn´ıch pˇr´ıpadech je pravdiv´e. Zp˚ usob jak´ ym implikace pracuje m˚ uˇzeme opˇet zn´ azornit tabulkou: A 0 0 1 1

A⇒B 1 1 0 1

B 0 1 0 1

Tvrzen´ı A ⇒ B obvykle ˇcteme jako “Kdyˇz A, pak B” nebo “Jestliˇze A, potom B” nebo “Z A plyne B” nebo “Necht’ A. Pak B”. Napˇr. tvrzen´ı “Kdyˇz je ˇc´ıslo x sud´e, pak je dˇeliteln´e 2” je pravdiv´e a tvrzen´ı “Kdyˇz je ˇc´ıslo x lich´e, pak je dˇeliteln´e 2” je nepravdiv´e. Implikace je pro pochopen´ı obvykle sloˇzitˇejˇs´ı, protoˇze nen´ı jasn´e, proˇc 0 ⇒ 0 a 0 ⇒ 1 jsou pravdiv´a tvrzen´ı. D˚ uvod proˇc je implikace definov´ ana, tak jak je, pokus´ıme osvˇetlit na n´asleduj´ıc´ım pˇr´ıkladˇe. Necht’ A je tvrzen´ı “Student Boˇrislav Nemrava mi d´a mili´on korun ˇcesk´ ych” a B je tvrzen´ı “D´am panu Boˇrislavu Nemravovi na konci semetru jedniˇcku z algebry”. Pokud tvrd´ım, ˇze tvrzen´ı A ⇒ B (tj. “Kdyˇz mi student Boˇrislav Nemrava d´a mili´on korun ˇcesk´ ych, pak d´am panu Boˇrislavu Nemravovi na konci semetru jedniˇcku z algebry”) je pravdiv´e, v kter´ ych pˇr´ıpadech lˇzu? Zˇrejmˇe jen v pˇr´ıpadˇe, kdy dostanu pen´ıze a jedniˇcku na konci semestru ned´am. V pˇr´ıpadech, kdy ˇz´adn´e 2

pen´ıze nedostanu, m˚ uˇzu d´at zn´ amku, jakou chci, protoˇze nejsem v´ az´an on´ım u ´platkem a tud´ıˇz neporuˇsuji platnost sv´eho tvrzen´ı A ⇒ B. D˚ uvod proˇc implikace A ⇒ B, kde tvrzen´ı A je nepravdiv´e, je pravdiv´a, lze vysvˇetlit i na naˇsem pˇredchoz´ım pˇr´ıkladu “Kdyˇz je ˇc´ıslo x sud´e, pak je dˇeliteln´e 2”. Chceme totiˇz aby takov´eto tvrzen´ı platilo pro vˇsechna cel´a ˇc´ısla, tzn. mus´ı platit jak pro x = 2, tak i pro x = 3. Ekvivalence Mˇejme opˇet dvˇe tvrzen´ı A, B. Ekvivalence tˇechto tvrzen´ı (symbolicky ji znaˇc´ıme A ⇔ B) je tvrzen´ı, kter´e plat´ı pouze v pˇr´ıpadech, kdy bud’ plat´ı obˇe tvrzen´ı A, B z´aroveˇ n nebo z´aroveˇ n neplat´ı. Ve vˇsech ostatn´ıch pˇr´ıpadech je nepravdiv´e. Zp˚ usob jak´ ym ekvivalence pracuje m˚ uˇzeme opˇet zn´ azornit tabulkou: A 0 0 1 1

A⇔B 1 0 0 1

B 0 1 0 1

Tvrzen´ı A ⇔ B obvykle ˇcteme jako “A pr´avˇe tehdy, kdyˇz B”. Pˇr´ıkladem ekvivalence je napˇr. ˇ ıslo x je dˇeliteln´e prvoˇc´ıslem p pr´avˇe tehdy, kdyˇz x2 je dˇeliteln´e p2 ”. tvrzen´ı: “C´ Kvantifik´ atory Pˇr´ıklady tvrzen´ı s implikac´ı a ekvivalenc´ı obsahovaly libovoln´e, ale pevn´e ˇc´ıslo x. Oznaˇcme jako A(x) tvrzen´ı “Kdyˇz je ˇc´ıslo x sud´e, pak je dˇeliteln´e 2”. Symbol “x” v z´avork´ach za A naznaˇcuje, ˇze pravdivost tohoto tvrzen´ı bude z´aviset na ˇc´ısle, kter´e za x dosad´ıme. Kdyby jsme nyn´ı chtˇeli nˇejak´ ym zp˚ usobem zapsat skuteˇcnost, ˇze A(x) je pravdiv´e pro vˇsechny cel´a ˇc´ısla x, museli bychom s naˇs´ım souˇcasn´ ym apar´ atem ps´ at, tvrzen´ı A(0) ∧ A(1) ∧ A(2) ∧ . . . je pravdiv´e, tj. tvrzen´ı plat´ı pro x = 0, x = 1, x = 2, atd. To samozˇrejmˇe nen´ı moc praktick´e, proto logika obsahuje dalˇs´ı prvky, kter´ ym se ˇr´ık´a kvantifik´ atory. Kvantifik´ atory m´ame dva: prvn´ı “pro vˇsechny” (znaˇc´ı se symbolicky ∀) a druh´ y “existuje” (znaˇc´ı se symbolicky ∃). Jestliˇze tedy m´ame tvrzen´ı A(x), kter´e je z´avisl´e na x, m˚ uˇzeme z nˇeho vyrobit dvˇe tvrzen´ı: 1. “Pro vˇsechna x je A(x) pravdiv´e”. Symbolicky zapisujeme jako (∀x)A(x). Tvrzen´ı (∀x)A(x) je pravdiv´e kdyˇz A(x) pravdiv´e pro libovoln´e x a nepravdiv´e kdyˇz existuje takov´e x, ˇze A(x) pro nˇej nen´ı pravdiv´e. Napˇr. “Pro vˇsechna cel´a ˇc´ısla x plat´ı: kdyˇz x je sud´e, pak je dˇeliteln´e 2” je pravdiv´e tvrzen´ı a “Pro vˇsechna cel´a ˇc´ısla x plat´ı: kdyˇz x je lich´e, pak je dˇeliteln´e 3” je nepravdiv´e, protoˇze 5 je lich´e a nen´ı dˇeliteln´e 3. 2. “Existuje x takov´e, ˇze A(x) je pravdiv´e”. Symbolicky zapisujeme jako (∃x)A(x). Tvrzen´ı (∃x)A(x) je pravdiv´e, kdyˇz existuje alespoˇ n jedno x takov´e, ˇze tvrzen´ı A(x) pro nˇej plat´ı a nepravdiv´e, kdyˇz takov´e x neexistuje. Napˇr. “Existuje cel´e ˇc´ıslo vˇetˇs´ı neˇz 100” je pravdiv´e tvrzen´ı, protoˇze napˇr. 101 je cel´e ˇc´ıslo vˇetˇs´ı neˇz 100. Naopak tvrzen´ı “Existuje re´aln´e ˇc´ıslo jehoˇz druh´ a mocnina je z´aporn´ a” je nepravdiv´e. Pokud v symbolick´em z´apisu kvantifik´ ator˚ u chceme pˇresnˇe stanovit odkud x poch´az´ı, udˇel´ame to n´asledovnˇe. Oznaˇcme mnoˇzinu re´ aln´ ych ˇc´ısel R a mnoˇzinu komplexn´ıch ˇc´ısel C. Posledn´ı pˇr´ıklad m˚ uˇzeme potom zapisovat takto: (∃x ∈ R)(x2 < 0). Toto tvrzen´ı nen´ı pravdiv´e. Naopak (∃x ∈ C)(x2 < 0) je pˇr´ıkladem pravdiv´eho tvrzen´ı, protoˇze i2 = −1. Obdobn´ y z´apis se pouˇz´ıv´a i s kvantifik´ atorem ∀ napˇr.: (∀x ∈ R)A(x).

1.2

Definice, vˇ eta, d˚ ukaz

Nyn´ı m´ame vymezen zakladn´ı jazyk (tj. logick´e spojky a kvantifik´ atory), kter´ y matematika pouˇz´ıv´a. Z´aroveˇ n jsme i stanovili, co jednotliv´e prvky tohoto jazyka znamenaj´ı (tj. v´ıme, jak urˇcit pravdivost 3

sloˇzen´ ych tvrzen´ı, kdyˇz zn´ ame pravdivost jeho podˇc´ast´ı). Jak uˇz bylo v u ´vodu ˇreˇceno, matematika se zab´ yv´a hled´ an´ım pravdiv´ ych tvrzen´ı, kter´e plynou axiom˚ u (tj. tvrzen´ı, kter´a jsme prohl´asili za pravdiv´a, protoˇze v´ıme, ˇze naˇse studovan´e objekty je urˇcitˇe splˇ nuj´ı). Bohuˇzel ˇz´adn´ y obecn´ y postup, jak tyto pravdiv´a tvrzen´ı hledat neexistuje, takˇze vˇzdy z´aleˇz´ı na schopnostech konkretn´ıho matematika, jak´ a tvrzen´ı z axiom˚ u odvod´ı. Nicm´enˇe, kdyˇz uˇz najde nˇejak´e zaj´ımav´e tvrzen´ı, kter´e mu pˇrijde pravdiv´e v dan´e teorii, mus´ı dok´ azat, ˇze to tak vskutku je. Pak teprve m˚ uˇze prohl´asit, ˇze jeho nalezen´e tvrzen´ı je pravdiv´e. Metod, jak nˇejak´e tvrzen´ı dok´ azat m´ame nˇekolik. Protoˇze vˇetˇsina matematick´ ych tvrzen´ı je ve tvaru implikace nebo ekvivalence, zamˇeˇr´ıme se na d˚ ukazy tvrzen´ı typu A ⇒ B a A ⇔ B. Ve skuteˇcnosti se staˇc´ı zamˇeˇrit jenom na tvrzen´ı typu A ⇒ B, protoˇze d˚ ukaz tvrzen´ı A ⇔ B lze pˇrev´est na d˚ ukaz dvou implikac´ı. M˚ uˇzeme se totiˇz snadno pomoc´ı tabulky pˇresvˇedˇcit, ˇze tvrzen´ı A ⇔ B je ekvivalentn´ı s tvrzen´ım (A ⇒ B) ∧ (B ⇒ A), tj. kdyˇz plat´ı jedno, plat´ı i druh´e a naopak. A 0 0 1 1

B 0 1 0 1

A⇔B 1 0 0 1

A⇒B 1 1 0 1

B⇒A 1 0 1 1

(A ⇒ B) ∧ (B ⇒ A) 1 0 0 1

Oba sloupce A ⇔ B a (A ⇒ B) ∧ (B ⇒ A) jsou stejn´e, coˇz znamen´a, ˇze obˇe tvrzen´ı jsou ekvivalentn´ı. Pokud tedy chceme dok´ azat tvrzen´ı ve tvaru A ⇔ B, staˇc´ı kdyˇz dok´ aˇzeme, ˇze plat´ı A ⇒ B i B ⇒ A, protoˇze potom mus´ı b´ yt pravdiv´a i jejich konjunkce. Neˇz pˇristoup´ıme k diskuzi jednotliv´ ych typ˚ u d˚ ukaz˚ u, je potˇreba uv´est, ˇze nen´ı v sil´ach tohoto psan´eho materi´alu, vysvˇetlit u ´plnˇe tuto problematiku. Koneckonc˚ u matematici zaˇc´ateˇcn´ıci se uˇc´ı dokazovat tak, ˇze se snaˇz´ı pochopit d˚ ukazy sv´ ych vyspˇelejˇs´ıch koleg˚ u a pak jejich postupy pouˇz´ıvat ve sv´e vlastn´ı pr´ aci. Pˇredpokl´adejme, ˇze chceme dok´ azat tvrzen´ı A ⇒ B. Tvrzen´ı A se obvykle naz´ yv´a pˇredpoklad a tvrzen´ı B z´avˇer. Pˇ r´ım´ y d˚ ukaz Prvn´ı metoda d˚ ukazu je tzv. pˇr´ım´ y d˚ ukaz. Protoˇze jedin´ y pˇr´ıpad, kdy by implikace A ⇒ B nebyla pravdiv´a, je pˇr´ıpad, kdy A je pravdiv´e a B nikoli, staˇc´ı kdyˇz uk´aˇzeme, ˇze tento pˇr´ıpad nenast´av´ a. Tzn. budeme pˇredpokl´adat, ˇze tvrzen´ı A je pravdiv´e a pokus´ıme se uk´azat, ˇze i B mus´ı uˇz b´ yt pravdiv´e. K tomu aby jsme uk´azali, ˇze B uˇz mus´ı b´ yt pravdiv´e m˚ uˇzeme vyuˇz´ıt nejen n´aˇs pˇredpoklad, ˇze A plat´ı, ale i pravdivost axiom˚ u a jin´ ych uˇz dok´ azan´ ych tvrzen´ı v dan´e teorii. Samotn´ y d˚ ukaz potom prob´ıh´a tak, ˇze v´ıcen´ asobnou aplikac´ı korektn´ıch dedukˇcn´ıch pravidel1 na A, axiomy a jiˇz dok´ azan´a tvrzen´ı, odvod´ıme nov´ a tvrzen´ı. Pokud mezi je i tvrzen´ı B m´ame vyhr´ano. Pokus´ıme se pˇr´ım´ y d˚ ukaz ilustrovat na velmi jednoduch´em pˇr´ıkladˇe. Pˇredpokl´adejme, ˇze objekty naˇseho z´ajmu jsou cel´a ˇc´ısla. Konkr´etnˇe n´as bude zaj´ımat jak´e vlastnosti m´a sˇc´ıt´ an´ı cel´ ych ˇc´ısel. D´ale pˇredpokl´adejme, ˇze n´asleduj´ıc´ı tvrzen´ı jsou bud’ naˇse axiomy nebo jiˇz dok´ azan´a tvrzen´ı: 1. Reflexivita rovnosti: a = a 2. Symetrie rovnosti: Kdyˇz a = b, pak b = a. Symbolicky: a = b ⇒ b = a. 3. Transitivita rovnosti: Kdyˇz a = b a b = c, pak a = c. Symbolicky: (a = b ∧ b = c) ⇒ a = c. 4. Jednoznaˇcnost sˇc´ıt´ an´ı: Kdyˇz a = a′ a b = b′ , pak a + b = a′ + b′ . Symbolicky: (a = a′ ∧ b = b′ ) ⇒ a + b = a′ + b′ . 1 Co jsou korektn´ ı dedukˇ cn´ı pravidla n´ am ˇr´ık´ a logika. Uvedeme si jen nˇ ekter´ e pˇr´ıklady. Napˇr. pokud v´ıme, ˇ ze tvrzen´ı C a C ⇒ D jsou pravdiv´ a, m˚ uˇ zeme usoudit, ˇ ze i tvrzen´ı D je pravdiv´ e, protoˇ ze kdyby nebylo, muselo by b´ yt C nebo C ⇒ D nepravdiv´ e. Tomuto dedukˇ cn´ımu pravidlu se ˇr´ık´ a modus ponens. Jin´ ym pˇr´ıkladem je napˇr. dedukˇ cn´ı pravidlo: z pravdivosti C ⇒ D a D ⇒ E odvod’ C ⇒ E (transitivita implikace). Jako posledn´ı uvedeme dedukˇ cn´ı pravidlo generalizace. Pokud uk´ aˇ zeme, ˇ ze nˇejak´ e tvrzen´ı A(x) je pravdiv´ e pro libovoln´ e pevn´ e x, m˚ uˇ zeme odvodit pravdivost tvrzen´ı (∀x)A(x).

4

5. Neutr´ aln´ı prvek: 0 + a = a U vˇsech v´ yˇse uveden´ ych tvrzen´ı pˇredstavuj´ı a, b, c libovoln´a pevn´a cel´a ˇc´ısla. Pomoc´ı tˇechto tvrzen´ı dok´ aˇzeme n´asleduj´ıc´ı tvrzen´ı: Tvrzen´ı 1 Kdyˇz a = 0, pak a + b = b (Symbolicky a = 0 ⇒ a + b = b). D˚ ukaz: Rozdˇel´ıme d˚ ukaz na jednotliv´e kroky a u kaˇzd´eho z nich uvedeme z kter´ ych tvrzen´ı plyne. a) Podle tvrzen´ı 1 v´ıme, ˇze b = b je pravdiv´e. b) Protoˇze dokazujeme implikaci, pˇredpokl´ad´ame, ˇze a = 0 je tak´e pravdiv´e. c) Z krok˚ u a) a b) m˚ uˇzeme odvodit, ˇze je pravdiv´a i konjunkce a = 0 ∧ b = b, protoˇze konjunkce je pravdiv´a, kdyˇz jsou pravdiv´e obˇe jej´ı ˇc´asti. d) Podle tvrzen´ı 4 v´ıme, ˇze (a = 0 ∧ b = b) ⇒ a + b = 0 + b je pravdiv´e. e) Aplikac´ı modus ponens na c) a d) odvod´ıme pravdivost tvrzen´ı a + b = 0 + b. f) Podle tvrzen´ı 5 v´ıme, ˇze 0 + b = b je pravdiv´e. g) Z krok˚ u e) a f) m˚ uˇzeme odvodit stejnˇe jako jsme to udˇelali v kroku c), ˇze je pravdiv´a i konjunkce a + b = 0 + b ∧ 0 + b = b. h) Podle tvrzen´ı 3 v´ıme, ˇze (a + b = 0 + b ∧ 0 + b = b) ⇒ a + b = b je pravdiv´e. i) Aplikac´ı modus ponens na g) a h) odvod´ıme pravdivost tvrzen´ı a + b = b. A t´ım je d˚ ukaz hotov.  Je celkem zˇrejm´e, ˇze takto detailnˇe d˚ ukazy ps´ at nejde, protoˇze by n´am brzo doˇsel pap´ır nebo pamˇet poˇc´ıtaˇce. Proto se d˚ ukazy vˇetˇsinou zkracuj´ı s t´ım, ˇze zkuˇsen´ y ˇcten´ aˇr (pokud bude cht´ıt) jednotliv´e detaily zrekonstruuje s´ am. Tud´ıˇz pˇredchoz´ı d˚ ukaz by se zapisoval asi nˇejak takto: protoˇze pˇredpokl´ad´ame, ˇze a = 0, dostaneme a+b = 0+b = b. Automaticky se tedy napˇr´ıklad pˇredpokl´ad´a, ˇze ˇcten´ aˇr zn´ a vˇsechny vlastnosti rovnosti (reflexivita, symetrie, transitivita). Nepˇ r´ım´ y d˚ ukaz Nepˇr´ım´ y d˚ ukaz tvrzen´ı A ⇒ B prob´ıh´a stejnˇe jako pˇr´ım´ y d˚ ukaz, jen s t´ım rozd´ılem, ˇze se snaˇz´ım m´ısto tvrzen´ı A ⇒ B dok´ azat tvrzen´ı ¬B ⇒ ¬A. Obˇe tvrzen´ı jsou totiˇz ekvivalentn´ı, jak se snadno pˇresvˇedˇc´ıme pomoc´ı tabulky: A 0 0 1 1

B 0 1 0 1

¬A 1 1 0 0

¬B 1 0 1 0

A⇒B 1 1 0 1

¬B ⇒ ¬A 1 1 0 1

Postup opˇet ilustrujeme na pˇr´ıkladˇe. Necht’ objekty naˇseho z´ajmu jsou opˇet cel´a ˇc´ısla. Tentokr´at jiˇz nebudeme uv´ adˇet podrobn´ y d˚ ukaz, ale jen jeho struˇcnou verzi. Tvrzen´ı 2 Necht’ a a b jsou cel´ a ˇc´ısla. Kdyˇz a 6= 0, pak existuje nejv´yˇse jedno cel´e ˇc´ıslo x takov´e, ˇze ax = b. Symbolicky: ¬(a = 0) ⇒ ((∃x1 , x2 )(ax1 = b ∧ ax2 = b) ⇒ x1 = x2 ) .

5

D˚ ukaz: Vˇs´ımˇete si, ˇze vˇeta tak´e pˇripouˇst´ı neexistenci x takov´eho, ˇze ax = b. To znamen´a, ˇze bud’ existuje jedno nebo ˇz´adn´e, ale nikdy ne v´ıce. Napˇr. pro a = 2 a b = 3 neexistuje cel´e ˇc´ıslo x tak, ˇze ax = b. Vˇsimˇete si tak´e druh´e ˇc´asti symbolick´eho z´apisu, jak je vyj´ adˇren fakt, ˇze v´ıce neˇz jedno x nem˚ uˇze existovat. Implikace v t´eto druh´e ˇc´asti vlastnˇe ˇr´ık´a, ˇze kdyby existovali dvˇe cel´a ˇc´ısla x1 , x2 , pak uˇz mus´ı b´ yt stejn´ a. D˚ ukaz budeme prov´ adˇet nepˇr´ımo, to znamen´a, ˇze budeme pˇredpokl´adat ˇze neplat´ı z´avˇer tvrzen´ı (∃x1 , x2 )(ax1 = b ∧ ax2 = b) ⇒ x1 = x2 a uk´aˇzeme, ˇze pˇredpoklad ¬(a = 0) neplat´ı tak´e. Co tedy znamen´a, ˇze neplat´ı z´avˇer (∃x1 , x2 )(ax1 = b ∧ ax2 = b) ⇒ x1 = x2 . Vid´ıme, ˇze ˇz´avˇer m´a tvar implikace a ta neplat´ı jen tehdy, kdyˇz plat´ı jej´ı pˇredpoklad tj. (∃x1 , x2 )(ax1 = b ∧ ax2 = b) a neplat´ı jej´ı z´avˇer x1 = x2 . Z platnosti (∃x1 , x2 )(ax1 = b ∧ ax2 = b) tedy v´ıme, ˇze existuj´ı dvˇe cel´a ˇc´ısla x1 a x2 takov´ a, ˇze ax1 = b a ax2 = b. Z neplatnosti x1 = x2 plyne, ˇze x1 6= x2 . Nyn´ı pouˇzijeme bˇeˇzn´e vlastnosti cel´ ych ˇc´ısel a rovnosti. Protoˇze ax1 = b = ax2 , dostaneme 0 = ax1 − ax2 = a(x1 − x2 ). Z nerovnosti x1 6= x2 plyne x1 − x2 6= 0. Jelikoˇz ale a(x1 − x2 ) = 0, mus´ı nutnˇe platit a = 0 a ¬(a = 0) tedy neplat´ı, coˇz jsme mˇeli dok´ azat.  D˚ ukaz indukc´ı D˚ ukaz indukc´ı je metoda, kter´a n´am umoˇzn ˇuje dok´ azat, ˇze nˇejak´e tvrzen´ı plat´ı pro vˇsechna pˇrirozen´ a ˇc´ısla vˇetˇs´ı neˇz nˇejak´e pˇrirozen´e ˇc´ıslo n0 (typicky n0 = 0 nebo n0 = 1). Tˇech je samozˇrejmˇe nekoneˇcnˇe mnoho a proto nen´ı moˇzn´e tvrzen´ı dokazovat pro kaˇzd´e pˇrirozen´e ˇc´ıslo zvl´ aˇst’. Pˇredpokl´adejme, ˇze chceme dok´ azat tvrzen´ı A(x) pro vˇsechna pˇrirozen´ a ˇc´ısla x ≥ n0 . D˚ ukaz indukc´ı prob´ıh´a ve dvou kroc´ıch: 1. Nejprve dok´ aˇzeme, ˇze tvrzen´ı A(n0 ) je pravdiv´e. 2. N´ aslednˇe pro libovoln´e pevn´e pˇrirozen´e ˇc´ıslo n ≥ n0 pˇredpokl´ad´ame, ˇze tvrzen´ı A(x) plat´ı pro vˇsechna x takov´ a, ˇze n0 ≤ x ≤ n. Z tohoto pˇredpokladu mus´ıme uk´azat, ˇze i tvrzen´ı A(n + 1) je pravdiv´e2 . Aplikaci d˚ ukazu indukc´ı si uk´aˇzeme na pˇr´ıkladˇe. Tvrzen´ı 3 Necht’ n je pˇrirozen´e ˇc´ıslo vˇetˇs´ı nebo rovno 1. Pak 1 + 2 + 3 + ··· + n =

n(n + 1) . 2

D˚ ukaz: D˚ ukaz budeme prov´ adˇet indukc´ı pro n0 = 1. V prvn´ım kroku mus´ıme ovˇeˇrit, ˇze tvrzen´ı plat´ı pro n = 1. To je ale zˇrejm´e, protoˇze 1 = 1(1+1) . V druh´em kroku si vezmeme libovoln´e 2 pevn´e n ≥ 1 a z pˇredpokladu platnosti tvrzen´ı pro vˇsechna pˇrirozen´ a ˇc´ısla x splˇ nuj´ıc´ı 1 ≤ x ≤ n dok´ aˇzeme, ˇze tvrzen´ı plat´ı i pro n+1 . N´ am konkr´etnˇe v tomto pˇr´ıpadˇe bude staˇcit jen pˇredpoklad, ˇze tvrzen´ı plat´ı pro x = n. Nyn´ı uk´aˇzeme, ˇze tvrzen´ı je platn´e i pro n + 1: 1 + 2 + 3 + · · · + n + (n + 1) =

n(n + 1) + 2(n + 1) (n + 1)(n + 2) n(n + 1) + (n + 1) = = . 2 2 2

V prvn´ı rovnosti jsme pouˇzili fakt, ˇze tvrzen´ı je platn´e pro n. Pak jsme jiˇz jen upravili v´ ysledn´ y v´ yraz tak, aby bylo patrn´e, ˇze prav´ a strana rovnosti m´a tvar prav´e strany tvrzen´ı pro n + 1.  Uk´aˇzeme si jeˇstˇe jeden pˇr´ıklad. Tvrzen´ı 4 Kaˇzd´e pˇrirozen´e ˇc´ıslo n ≥ 2 je bud’ prvoˇc´ıslo nebo lze vyj´ adˇrit jako souˇcin prvoˇc´ısel. 2 Velmi ˇ casto se jako druh´ y krok indukce uv´ ad´ı toto: pro libovoln´ e pevn´ e n ≥ n0 dokaˇ zte z pˇredpokladu platnosti A(n) tvrzen´ı A(n + 1), tj. mus´ıme dok´ azat platnost implikace A(n) ⇒ A(n + 1). Obˇ e formulace jsou ekvivalentn´ı.

6

D˚ ukaz: D˚ ukaz budeme opˇet prov´ adˇet indukc´ı, tentokr´ at ale pro n0 ≥ 2. Prvn´ı krok je jednoduch´ y. Mus´ıme ovˇeˇrit, ˇze tvrzen´ı plat´ı pro n = 2. To je ale zˇrejm´e, protoˇze 2 je prvoˇc´ıslo. Pˇredpokl´adejme tedy nyn´ı, ˇze tvrzen´ı plat´ı pro vˇsechna pˇrirozen´ a ˇc´ısla x splˇ nuj´ıc´ı 2 ≤ x ≤ n. Uk´aˇzeme, ˇze tvrzen´ı plat´ı i pro n + 1. Pokud n + 1 je prvoˇc´ıslo, pak tvrzen´ı plat´ı. Takˇze zb´ yv´a akor´ at uk´azat, ˇze tvrzen´ı plat´ı i pro pˇr´ıpad, kdy n + 1 nen´ı prvoˇc´ıslo. Jestliˇze ale n + 1 nen´ı prvoˇc´ıslo, je moˇzno ho vyj´ adˇrit, jako souˇcin dvou menˇs´ıch pˇrirozen´ ych ˇc´ısel p, q, tj. n + 1 = pq a 2 ≤ p, q < n + 1. Z naˇseho pˇredpokladu tedy plyne, ˇze tvrzen´ı plat´ı pro p i q. Tudiˇz p i q lze vyj´ adˇrit jako souˇcin prvoˇc´ısel. Protoˇze n + 1 = pq, vid´ıme, ˇze i n + 1 lze vyj´ adˇrit jako souˇcin prvoˇc´ısel.  K posledn´ımu tvrzen´ı dodejme, ˇze jsme dok´ azali ˇc´ast d˚ uleˇzit´eho tvrzen´ı z aritmetiky, kter´e se naz´ yv´a Z´ akladn´ı vˇeta aritmetiky. Tvrzen´ı 5 (Z´ akladn´ı vˇ eta aritmetiky) Kaˇzd´e pˇrirozen´e ˇc´ıslo n ≥ 2 je bud’ prvoˇc´ıslo nebo lze vyj´ adˇrit jednoznaˇcnˇe jako souˇcin prvoˇc´ısel. D˚ ukaz tohoto tvrzen´ı uv´ adˇet nebudeme. Vˇsimˇete si, ˇze my jsme v pˇredchoz´ım d˚ ukazu uk´azali, ˇze rozklad na prvoˇc´ısla je moˇzno udˇelat, ale neuk´ azali jsme, ˇze to jde udˇelat jen jedn´ım zp˚ usobem. To, ˇze to jde pr´ avˇe jedn´ım zp˚ usobem, je obsahem Z´ akladn´ı vˇety aritmetiky. Tento fakt je v t´eto vˇetˇe vyj´ adˇren slovem “jednoznaˇcnˇe”. D˚ ukaz sporem Dalˇs´ım typick´ ym d˚ ukazov´ ym postupem je d˚ ukaz sporem. U d˚ ukazu sporem vˇzdy pˇredpokl´ad´ame, ˇze n´ami dokazovan´e tvzen´ı neplat´ı a odvod´ıme z tohoto pˇredpokladu spor (tj. nˇejak´e nepravdiv´e tvrzen´ı). Cheme-li tedy dok´ azat implikaci A ⇒ B, pˇredpokl´ad´ame, ˇze A ⇒ B neplat´ı, coˇz znamen´a, ˇze plat´ı pˇredpoklad A a neplat´ı z´avˇer B (tj. pˇredpokl´ad´ame, ˇze plat´ı A ∧ ¬B). Pokud se n´am podaˇr´ı z tohoto pˇredpokladu vyvodit spor je d˚ ukaz hotov. T´ımto postupem tedy chceme uk´azat, ˇze nem˚ uˇze nastat pˇr´ıpad, kdy by platil pˇredpoklad implikace a neplatil z´ avˇer. √ ˇ ıslo 2 nen´ı racion´ aln´ı. Tvrzen´ı 6 C´ D˚ ukaz: Toto tvrzen´ı na prvn´ı pohled nevypad´ a jako implikace. Nicm´enˇe kdyˇz si ho vyj´ adˇr´ıme √ symbolicky nˇejakou tu implikaci objev´ıme. Tvrzen´ı, ˇze ˇc´ıslo 2 nen´ı √ racion´ aln´ı, vlastnˇe ˇr´ık´a, ˇze at’ uˇz si vezmeme jak´ekoli racion´ aln´ı ˇc´ıslo x, tak urˇcitˇe bude platit x 6= 2. Dokazovan´e tvrzen´ı tedy m˚ uˇzeme zapsat takto: √ (∀x)(x ∈ Q ⇒ x 6= 2) .

Tento v´ yraz ˇr´ık´a√ , ˇze pro vˇsechna ˇc´ısla x, kdyˇz x patˇr´ı do mnoˇziny racion´ aln´ıch ˇc´ısel Q, tak uˇz mus´ı platit x 6= 2. Pokud tedy chceme toto tvrzen´ı dok´ azat sporem, budeme √ pˇredpokl´adat, ˇze neplat´ı. To ale znamen´a, ˇze mus´ı existovat racion´ aln´ı ˇc´ıslo x takov´e, ˇze x = 2. ˇ Reknˇ eme si nejprve, co znamen´a, ˇze nˇejak´e ˇc´ıslo x je racion´ aln´ı. Asi ze stˇredn´ı ˇskoly v´ıte,√ˇze je moˇzno ho vyj´ adˇrit jako pod´ıl dvou cel´ ych ˇc´ısel p, q, tj. x = pq . Takˇze mus´ı tedy platit pq = 2. Upravou pˇredchoz´ı rovnosti dostaneme: p2 = 2q 2 .

(1)

ˇ ıslo p lze podle Tvrzen´ı 5 m˚ C´ uˇzeme vyj´ adˇrit jako souˇcin prvoˇc´ısel. Vezmeme vˇsechny dvojky, co se v tomto souˇcinu nach´azej´ı a vyj´ adˇr´ıme p jako p = 2k p′ , kde k je poˇcet onˇech dvojek a p′ uˇz nen´ı dˇeliteln´e dvˇemi. Podobnˇe to udˇel´ame s q, kter´e vyj´ adˇr´ıme jako q = 2n q ′ , kde n je poˇcet dvojek v q. Ted’ dosad´ıme za p, q do rovnice (1) a dostaneme: (2k p′ )2 = 2(2n q ′ )2 . Podle Z´ akladn´ı vˇety aritmetiky (Tvrzen´ı 5) mus´ı b´ yt poˇcet dvojek na obou stran´ach pˇredchoz´ı rovnosti stejn´ y, protoˇze ani p′ ani q ′ nen´ı dˇeliteln´e dvˇemi. Na lev´e stranˇe m´ame 2k dvojek a na prav´e stranˇe m´ame 2n + 1 dvojek. Mus´ı tedy platit 2k = 2n + 1, ale to nen´ı zˇrejmˇe moˇzno, protoˇze sud´e ˇc´ıslo 2k se nem˚ uˇze rovnat lich´emu 2n + 1. A to je onen k´ yˇzen´ y spor. 

7

Matematick´ y text Nyn´ı se zamˇeˇr´ıme na to jak vypad´ a matematick´ y text. Zaˇcneme terminologi´ı. Matematick´ a tvrzen´ı obvykle pojmenov´ av´ ame r˚ uzn´ ymi jm´eny podle jejich v´ yznamu, sloˇzitosti d˚ ukazu, atd. Uved’me si nˇekolik jmen, se kter´ ymi se m˚ uˇzete v literatuˇre setkat. Hlavn´ı tvrzen´ı se naz´ yvaj´ı Vˇety. Pomocn´ a tvrzen´ı, jejichˇz d˚ ukazy jsou obvykle technick´e, naz´ yv´ame Lemmata. Pokud nˇejak´e tvrzen´ı bezprostˇrednˇe plyne z nˇejak´e vˇety, je oznaˇcov´ ano jako D˚ usledek. Tvrzen´ı, jejichˇz d˚ ukazy jsou velmi jednoduch´e, se naz´ yvaj´ı Pozorov´ an´ı. U pozorov´ an´ı se vˇetˇsinou ani d˚ ukaz neuv´ ad´ı. Jak uˇz jsme zm´ınili na zaˇc´atku, ukolem matematiky je objevovat platn´ a tvrzen´ı v dan´e matematick´e teorii. To znamen´a, ˇze matematick´ y text se pˇrev´ aˇznˇe skl´ ad´a, z tˇechto tvrzen´ı (tj. vˇet, lemmat, d˚ usledk˚ u, pozorov´ an´ı) a jejich d˚ ukaz˚ u. Nicm´enˇe v matematick´e textu se objevuje jeˇstˇe jeden d˚ uleˇzit´ y prvek a to je Definice. V kaˇzd´e teorii m´ame nˇejak´e z´akladn´ı pojmy (napˇr. bod v geometrii nebo ˇc´ıslo v aritmetice), jejichˇz struktura n´as uˇz nezaj´ım´ a, tzn. nezaj´ım´ a n´as napˇr´ıklad, co to je ˇc´ıslo, ale jak´e vz´ ajemn´e vztahy mezi sebou ˇc´ısla splˇ nuj´ı. Nicm´enˇe nen´ı moˇzn´e s tˇemito z´akladn´ımi pojmy vystaˇcit, protoˇze naˇse tvrzen´ı by pak byli velmi dlouh´ a. Proto pomoc´ı definic zav´ ad´ıme pojmy nov´e. Ukaˇzme si pˇr´ıklady. Definice 1 Cel´e ˇc´ıslo x naz´yv´ ame kladn´e, pokud plat´ı x > 0. Definice 2 Cel´e ˇc´ıslo x naz´yv´ ame lich´e, pokud lze vyj´ adˇrit jako dvojn´ asobek nˇejak´eho cel´eho ˇc´ısla n plus 1, tj. x = 2n + 1. V prvn´ı definici jsme zavedli pojem kladn´eho cel´eho ˇc´ısla a v druh´e lich´eho. Po zaveden´ı nov´ ych pojm˚ u je moˇzn´e tyto pojmy pouˇz´ıvat v dalˇs´ım textu, v podstatˇe jako zkratky. Napˇr. m˚ uˇzeme zformulovat tvrzen´ı “pro vˇsechna lich´a cel´a ˇc´ısla plat´ı ...”. To je samozˇrejmˇe u ´spornˇejˇs´ı neˇz kdybychom psali “pro vˇsechna cel´a ˇc´ısla, kter´a lze lze vyj´ adˇrit jako dvojn´ asobek nˇejak´eho cel´eho ˇc´ısla n plus 1, plat´ı ...”.

1.3

Teorie mnoˇ zin

Z´akladn´ı matematickou teori´ı, ve kter´e pracuje dnes vˇetˇsina matematik˚ u, je teorie mnoˇzin. Z´akladn´ı pojem t´eto teorie je pojem mnoˇzina. Mnoˇzina m´a pˇredstavovat jak´ ysi soubor prvk˚ u. Pokud chceme mluvit o nˇejak´e konkr´etn´ı mnoˇzinˇe, je potˇreba ji nˇejak zapsat. To lze udˇelat nˇekolika zp˚ usoby. Koneˇcn´e mnoˇziny lze zapsat v´ yˇctem, napˇr. {1, 5, 3, 100}. I nekoneˇcn´e mnoˇziny m˚ uˇzeme nˇekdy zapsat v´ yˇctem, napˇr. mnoˇzina vˇsech lich´ ych kladn´ ych ˇc´ısel lze vyj´ adˇrit jako {1, 3, 5, 7, 9, . . .}, s t´ım, ˇze ˇcten´ aˇr z prvn´ıch nˇekolika prvk˚ u pochop´ı o jakou mnoˇzinu jde. Pro nˇekter´e d˚ uleˇzit´e mnoˇziny m´ame obvykle vyhrazeny speci´aln´ı symboly. Mnoˇzinu pˇrirozen´ ych ˇc´ısel budeme znaˇcit N, mnoˇzinu cel´ ych ˇc´ısel Z, mnoˇzinu racion´ aln´ıch ˇc´ısel Q, mnoˇzinu re´ aln´ ych ˇc´ısel R a mnoˇzinu komplexn´ıch ˇc´ısel C. Dalˇs´ı speci´aln´ı symbol m´ame pro mnoˇzinu, kter´a neobsahuje ˇz´adn´e prvky (tzv. pr´azdn´a mnoˇzina). Znaˇc´ı se obvykle ∅ nebo {}. Fakt, ˇze nˇejak´ y prvek x√n´aleˇz´ı do√mnoˇziny M , budeme znaˇcit x ∈ M . Opaˇcn´e tvrzen´ı budeme znaˇcit x 6∈ M . Tak napˇr. 2 ∈ R a 2 6∈ Q. Jin´ y zp˚ usob, jak zapsat mnoˇzinu, je pomoc´ı nˇejak´eho tvrzen´ı A(x), kter´e plat´ı pro ty prvky x, kter´e do mnoˇziny maj´ı patˇrit, a pro ostatn´ı neplat´ı. Mnoˇzinu pak zap´ıˇseme {x | A(x)} a ˇcteme jako “mnoˇzina vˇsech x, kter´a splˇ nuj´ı A(x)”. Napˇr. {x | x ∈ R a x2 − 2x + 1 ≥ 0} je mnoˇzina vˇsech re´ aln´ ych ˇc´ısel x, kter´a splˇ nuj´ı nerovnici x2 − 2x + 1 ≥ 0. Nˇekdy zkr´ acenˇe p´ıˇseme nalevo od symbolu | odkud se prvky x berou. Napˇr. {x ∈ R | x2 + 1 = 0} je mnoˇzina vˇsech re´aln´ ych ˇc´ısel x, kter´e splˇ nuj´ı rovnici x2 + 1 = 0. Asi pro v´ as nebude pˇrekvapen´ı, ˇze tato mnoˇzina je pr´azdn´a, protoˇze ˇz´adn´e re´ aln´e ˇc´ıslo splˇ nuj´ıc´ı rovnici x2 + 1 = 0 neexistuje. Naopak mnoˇzina {x ∈ C | x2 + 1 = 0} nen´ı pr´azdn´ a a obsahuje dvˇe komplexn´ı ˇc´ısla i a −i. Jeden z axiom˚ u teorie mnoˇzin je tzv. axiom extensionality. Ten ˇr´ık´a, ˇze dvˇe mnoˇziny se rovnaj´ı pr´avˇe tehdy, kdyˇz maj´ı stejn´e prvky. To znamen´a, ˇze kdyˇz chceme uk´azat, ˇze dvˇe mnoˇziny X,Y se rovnaj´ı, mus´ıme pro libovoln´ y prvek x uk´azat, ˇze kdyˇz patˇr´ı do mnoˇziny X, pak patˇr´ı i do mnoˇziny Y a pokud patˇr´ı do Y , pak patˇr´ı tak´e do X. Symbolicky zaps´ano mus´ıme uk´azat platnost tohoto tvrzen´ı: (x ∈ X ⇒ x ∈ Y ) ∧ (x ∈ Y ⇒ x ∈ X) . 8

To je moˇzno pˇrepsat pomoc´ı ekvivalence takto: prvek x patˇr´ı do mnoˇziny X pr´avˇe tehdy, kdyˇz patˇr´ı do Y . Symbolicky: x∈X ⇔ x∈Y . Z axiomu extensionality plynou nˇekter´ a z´akladn´ı pozorov´ an´ı o mnoˇzin´ach. Napˇr. nez´aleˇz´ı na poˇrad´ı v jak´em prvky ve v´ yˇctu uv´ad´ıme, tj. {1, 3} = {3, 1}. Nebo nem´ a smysl uvaˇzovat, ˇze by nˇejak´a mnoˇzina obsahovala nˇejak´ y prvek v´ıcekr´ at, protoˇze {7, 7} = {7}. Kromˇe rovnosti mezi mnoˇzinami pouˇz´ıv´a matematika jeˇstˇe pojem inkluze. Chceme-li nˇejak vyj´ adˇrit, ˇze vˇsechny prvky mnoˇziny X patˇr´ı i do mnoˇziny Y , zapisujeme tuto skuteˇcnost X ⊆ Y a ˇcteme X je podmnoˇzinou Y . Pokud tedy chceme pro nˇejak´e dvˇe mnoˇziny X, Y , dok´ azat, ˇze X ⊆ Y plat´ı, mus´ıme uk´ azat, ˇze pro libovon´e x ∈ X, plat´ı i x ∈ Y , tj. uk´azat platnost implikace x ∈ X ⇒ x ∈ Y . Pomoc´ı inkluze ⊆ m˚ uˇzeme vyj´ adˇrit rovnost dvou mnoˇzin takto: X = Y pr´avˇe tehdy, kdyˇz X ⊆ Y a z´aroveˇ n Y ⊆ X. S mnoˇzinami m˚ uˇzeme tak´e dˇelat r˚ uzn´e operace. Z´ akladn´ı operace jsou pr˚ unik a sjednocen´ı. Mˇejme dvˇe mnoˇziny X a Y . Pr˚ unik X a Y znaˇc´ıme X ∩ Y a sjednocen´ı X a Y znaˇc´ıme X ∪ Y . Mnoˇziny X ∩ Y a X ∪ Y jsou potom definov´ any n´asledovnˇe: X ∩Y

X ∪Y

= {x | x ∈ X ∧ x ∈ Y } ,

= {x | x ∈ X ∨ x ∈ Y } .

Pr˚ unik X ∩ Y tedy obsahuje prvky, kter´e patˇr´ı do obou mnoˇzin z´aroveˇ n a sjednocen´ı X ∪ Y obsahuje prvky, kter´e patˇr´ı alespoˇ n do jedn´e z mnoˇzin. Napˇr. {0, 1, 3, π} ∩ {0, π, 4} = {0, π} a {0, 1, 3, π} ∪ {0, π, 4} = {0, 1, 3, π, 4}. Posledn´ı operac´ı s mnoˇzinami, o kter´e se zm´ın´ıme, je operace kart´ezsk´eho souˇcinu. M´ameli nˇejak´e dva prvky x a y, symbolem (x, y) budeme znaˇcit tzv. uspoˇra´danou dvojici. Slovem uspoˇra´danou d´av´ ame najevo, ˇze na poˇrad´ı prvk˚ u v (x, y) z´aleˇz´ı. Napˇr. (3, 5) 6= (5, 3). Kart´ezsk´ y souˇcin dvou mnoˇzin X a Y (znaˇc´ıme X × Y ) je potom mnoˇzina: X × Y = {(x, y) | x ∈ X ∧ y ∈ Y } . Kart´ezsk´ y souˇcin X × Y je tedy mnoˇzina vˇsech uspoˇra´dan´ ych dvojic (x, y), jejichˇz prvn´ı sloˇzka je z mnoˇziny X a druh´ a z mnoˇziny Y . Pokud X = Y , p´ıˇseme m´ısto X × X jen X 2 . Opakovan´ ym pouˇzit´ım kart´ezsk´eho souˇcinu m˚ uˇzeme vyr´ abˇet mnoˇziny uspoˇra´dan´ ych n-tic. Napˇr. X × X × X × X = {(x1 , x2 , x3 , x4 ) | x1 , x2 , x3 , x4 ∈ X} je mnoˇzina vˇsech uspoˇra´dan´ ych ˇctveˇric prvk˚ u z X. Tuto mnoˇzinu znaˇc´ıme zkr´ acenˇe X 4 . Podobnˇe X n znaˇc´ı mnoˇzinu uspoˇra´dan´ ych n-tic prvk˚ u z X, kde n ∈ N.

1.4

Zobrazen´ı

Nyn´ı pˇristoup´ıme k jednomu z nejz´ asadnˇejˇs´ıch pojm˚ u cel´e matematiky a t´ım je pojem zobrazen´ı. Tento pojem zavedeme v n´asleduj´ıc´ı definici: Definice 3 Necht’ X a Y jsou mnoˇziny. Podmnoˇzinu f kart´ezsk´eho souˇcinu X ×Y (tj. f ⊆ X ×Y ) nazveme zobrazen´ı z mnoˇziny X do mnoˇziny Y , pokud ke kaˇzd´emu x ∈ X existuje pr´ avˇe jedna uspoˇra ´dan´ a dvojice (x, y) ∈ f . Fakt, ˇze f je zobrazen´ı z mnoˇziny X do mnoˇziny Y znaˇc´ıme f : X → Y . Mnoˇzinu X naz´yv´ ame definiˇcn´ı obor a mnoˇzinu Y obor hodnot. Zobrazen´ı se tak´e nˇekdy ˇr´ık´ a funkce. Vˇsimˇete si, ˇze pro r˚ uzn´e prvky y 6= y ′ z mnoˇziny Y nem˚ uˇze nastat pˇr´ıpad, kdy (x, y) ∈ f a z´aroveˇ n ′ (x, y ) ∈ f . Pokud tedy pro nˇejak´e pevn´e x ∈ X plat´ı (x, y) ∈ f , je prvek y uˇz jednoznaˇcnˇe urˇcen, a m˚ uˇzeme si ho pojmenovat hodnota f v bodˇe x a oznaˇcit symbolem f (x). To znamen´a, ˇze dvojice (x, f (x)) jsou pr´ avˇe ty dvojice, kter´e patˇr´ı do f . Jin´ ymi slovy mnoˇzinu uspoˇra´dan´ ych dvojic f m˚ uˇzeme vyj´ adˇrit tak´e takto: {(x, f (x)) ∈ X × Y | x ∈ X}. Pˇr´ıklady zobrazen´ı mohou napˇr. b´ yt: g = {(x, y) ∈ R × R | y = x2 } 9

nebo h = {(x, y) ∈ N × R | y =

√

x} .

Zobrazen´ı g je zobrazen´ı z mnoˇziny re´ aln´ ych ˇc´ısel do mnoˇziny re´ aln´ ych ˇc´ısel a zobrazen´ı h je zobrazen´ı z mnoˇziny pˇrirozen´ ych ˇc´ısel do mnoˇziny re´ aln´ ych ˇc´ısel. Pokud chceme nˇejak´e zobrazen´ı definovat mus´ıme vlastnˇe definovat jakousi mnoˇzinu uspoˇra´dan´ ych dvojic. Nicm´enˇe, protoˇze kaˇzd´e zobrazen´ı f m´a tu vlastnost, ˇze ke kaˇzd´emu prvku x definiˇcn´ıho oboru existuje pr´avˇe jedna hodnota y z oboru hodnot, takov´ a, ˇze (x, y) patˇr´ı do f , nedefinujeme obvykle zobrazen´ı jako mnoˇzinu uspoˇra´dan´ ych dvojic, ale jen pˇredpisem, kter´ y kaˇzd´emu prvku z definiˇcn´ıho oboru pˇriˇrad´ı jeden prvek z oboru hodnot. Takˇze v´ yˇse uveden´e pˇr´ıklady zob2 razen´ı bychom √ tedy bˇeˇznˇe definovali takto: g : R → R takov´e, ˇze g(x) = x a h : N → R takov´e, yrazy g : R → R, h : N √→ R n´am totiˇz pˇresnˇe specifikuj´ı definiˇcn´ı obory a ˇze h(x) = x. V´ obory hodnot, a v´ yrazy g(x) = x2 , h(x) = x zase pˇresnˇe definuj´ı, kter´e uspoˇra´dan´e dvojice do zobrazen´ı patˇr´ı. S naˇs´ı definic´ı zobrazen´ı jako mnoˇziny m˚ uˇzeme lehce zodpovˇedˇet ot´ azku, kdy se dvˇe zobrazen´ı f : X → Y , g : X → Y rovnaj´ı. Vˇ eta 1 Necht’ f : X → Y , g : X → Y jsou zobrazen´ı. Pokud pro vˇsechny x ∈ X plat´ı f (x) = g(x), pak f = g. D˚ ukaz: Chceme dok´ azat, ˇze pokud pro vˇsechny x ∈ X plat´ı f (x) = g(x), pak f a g se rovnaj´ı. Protoˇze f a g jsou mnoˇziny, staˇc´ı uk´azat, ˇze maj´ı stejn´e prvky (viz axiom extensionality). Pˇripomeˇ nme, ˇze kaˇzd´ y prvek f lze vyj´ adˇrit, jako uspoˇra´danou dvojici (x, f (x)) ∈ X × Y . Vezmeme tedy libovoln´ y prvek (x, f (x)) z f a uk´aˇzeme, ˇze patˇr´ı tak´e do g. Z pˇredpokladu f (x) = g(x), dostaneme (x, f (x)) = (x, g(x)), protoˇze dvˇe uspoˇra´dan´e dvojice se rovnaj´ı, kdyˇz maj´ı stejn´e odpov´ıdaj´ıc´ı sloˇzky. Ale dvojice (x, g(x)) patˇr´ı do g. Takˇze jsme uk´azali, ˇze f ⊆ g. Inkluzi g ⊆ f lze dok´ azat obdobnˇe.  Pokud m´ame na oboru hodnot definov´ any nˇejak´e operace (napˇr. sˇc´ıt´ an´ı nebo n´asoben´ı), m˚ uˇzeme tyto operace pˇren´est i na zobrazen´ı. Necht’ f : X → R a g : X → R jsou zobrazen´ı z mnoˇziny X do mnoˇziny re´ aln´ ych ˇc´ısel. Re´ aln´ a ˇc´ısla jak zn´ amo um´ıme sˇc´ıtat a n´asobit. Nyn´ı budeme definovat pomoc´ı sˇc´ıt´ an´ı a n´asoben´ı re´ aln´ ych ˇc´ısel nov´ a zobrazen´ı f + g a f g pˇredstavuj´ıc´ı souˇcet a souˇcin zobrazen´ı f a g. Definice 4 Necht’ f : X → R, g : X → R jsou zobrazen´ı a c je re´ aln´e ˇc´ıslo. Definujeme zobrazen´ı f + g : X → R, f g : X → R a cf : X → R takto: (f + g)(x) (f g)(x) (cf )(x)

= f (x) + g(x) = f (x)g(x) = cf (x)

Zobrazen´ı f + g tedy pˇriˇrazuje prvku x z mnoˇziny X souˇcet re´ aln´ ych ˇc´ısel f (x) a g(x). Zobrazen´ı f g pˇriˇrazuje prvku x jejich souˇcin. A zobrazen´ı cf pˇriˇrazuje prvku x souˇcin re´aln´ ych ˇc´ısel c a f (x). Protoˇze sˇc´ıt´ an´ı a n´asoben´ı re´ aln´ ych ˇc´ısel splˇ nuje r˚ uzn´e vlastnosti (napˇr. a + b = b + a pro vˇsechna a, b ∈ R), zaj´ım´ a n´as, kter´e z tˇechto vlastnost´ı se pˇrenesou i na operace se zobrazen´ımi. Konstantn´ı zobrazen´ı z mnoˇziny X do mnoˇziny re´ aln´ ych ˇc´ısel R, kter´e kaˇzd´emu x ∈ X pˇriˇrad´ı 0, budeme znaˇcit ¯ 0, tj. ¯ 0 = {(x, 0) ∈ X × R | x ∈ X}. Zˇrejmˇe ¯0 = cf pro libovoln´e zobrazen´ı f a c = 0. Zobrazen´ı cf pro c = −1 budeme znaˇcit −f . Vˇ eta 2 Necht’ f : X → R, g : X → R a h : X → R jsou zobrazen´ı. Potom plat´ı n´ asleduj´ıc´ı tvrzen´ı: 1. Sˇc´ıt´ an´ı zobrazen´ı je komutativn´ı: f + g = g + f . 2. Sˇc´ıt´ an´ı zobrazen´ı je asociativn´ı: f + (g + h) = (f + g) + h. 10

3. Zobrazen´ı ¯ 0 je neutr´ aln´ı prvek: f + ¯0 = f . 4. (f + (−g))(x) = f (x) − g(x) pro vˇsechna x ∈ X. D˚ ukaz: U prvn´ıch tˇrech tvrzen´ı dokazovan´e vˇety m´ame uk´azat rovnost dvou zobrazen´ı. Podle Vˇety 1 staˇc´ı ovˇeˇrit, ˇze pro libovoln´ y prvek x z mnoˇziny X se hodnoty obou zobrazen´ı v bodˇe x rovnaj´ı. Posledn´ı tvrzen´ı ukazuje, ˇze zobrazen´ı f + (−g) funguje jako rozd´ıl dvou zobrazen´ı. 1. (f + g)(x) = f (x) + g(x) = g(x) + f (x) = (g + f )(x), druh´ a rovnost plyne z komutativity sˇc´ıt´ an´ı re´ aln´ ych ˇc´ısel (tj. a + b = b + a pro vˇsechna a, b ∈ R). 2. (f + (g + h))(x) = f (x) + (g(x) + h(x)) = (f (x) + g(x)) + h(x) = ((f + g) + h)(x), druh´ a rovnost plyne z asociativity sˇc´ıt´ an´ı re´ aln´ ych ˇc´ısel (tj. a + (b + c) = (a + b) + c pro vˇsechna a, b, c ∈ R). 3. (f + ¯ 0)(x) = f (x) + 0 = f (x), druh´ a rovnost plyne z faktu, ˇze a + 0 = a pro vˇsechna a ∈ R. 4. (f + (−g))(x) = f (x) + (−g)(x) = f (x) + (−1)g(x) = f (x) − g(x).  Zobrazen´ı f + (−g) budeme znaˇcit f − g. D´ıky posledn´ımu bodu pˇredchoz´ı vˇety, je toto znaˇcen´ı rozumn´e, protoˇze zobrazen´ı f − g se skuteˇcnˇe chov´ a, jako kdybychom ho definovali pˇrenesen´ım operace rozd´ılu z re´ aln´ ych ˇc´ısel na zobrazen´ı podobnˇe, jako jsme to udˇelali se sˇc´ıt´ an´ım a n´asoben´ım. Podobn´e vlastnosti m´a i n´asoben´ı, jak vypov´ıd´a n´asleduj´ıc´ı vˇeta. Konstantn´ı zobrazen´ı z mnoˇziny X do mnoˇziny re´ aln´ ych ˇc´ısel R, kter´e kaˇzd´emu x ∈ X pˇriˇrad´ı 1, budeme znaˇcit ¯1, ¯ tj. 1 = {(x, 1) ∈ X × R | x ∈ X}. Vˇ eta 3 Necht’ f : X → R, g : X → R a h : X → R jsou zobrazen´ı. Potom plat´ı n´ asleduj´ıc´ı tvrzen´ı: 1. N´ asoben´ı zobrazen´ı je komutativn´ı: f g = gf . 2. N´ asoben´ı zobrazen´ı je asociativn´ı: f (gh) = (f g)h. 3. Zobrazen´ı ¯ 1 je neutr´ aln´ı prvek: f ¯1 = f . 4. N´ asoben´ı zobrazen´ı je distributivn´ı vzhledem ke sˇc´ıt´ an´ı: f (g + h) = f g + f h. D˚ ukaz: U vˇsech tvrzen´ı dokazovan´e vˇety m´ame uk´azat rovnost dvou zobrazen´ı. Podle Vˇety 1 staˇc´ı ovˇeˇrit, ˇze pro libovoln´ y prvek x z mnoˇziny X se hodnoty obou zobrazen´ı v bodˇe x rovnaj´ı. 1. (f g)(x) = f (x)g(x) = g(x)f (x) = (gf )(x), druh´ a rovnost plyne z komutativity n´asoben´ı re´ aln´ ych ˇc´ısel (tj. ab = ba pro vˇsechna a, b ∈ R). 2. (f (gh))(x) = f (x)(g(x)h(x)) = (f (x)g(x))h(x) = ((f g)h)(x), druh´ a rovnost plyne z asociativity n´asoben´ı re´ aln´ ych ˇc´ısel (tj. a(bc) = (ab)c pro vˇsechna a, b, c ∈ R). 3. (f ¯ 1)(x) = f (x) 1 = f (x), druh´ a rovnost plyne z faktu, ˇze a1 = a pro vˇsechna a ∈ R. 4. (f (g + h))(x) = f (x) (g + h)(x) = f (x)(g(x) + h(x)) = f (x)g(x) + f (x)h(x) = (f g)(x) + (f h)(x) = (f g+f h)(x), druh´ a rovnost plyne z distributivity n´asoben´ı re´aln´ ych ˇc´ısel vzhledem ke sˇc´ıt´ an´ı (tj. a(b + c) = ab + ac pro vˇsechna a, b, c ∈ R).  Nakonec si uk´ aˇzeme nˇekter´e vlastnosti funkce cf . Vˇ eta 4 Necht’ f : X → R, g : X → R jsou zobrazen´ı a a, b re´ aln´ a ˇc´ısla. Potom plat´ı n´ asleduj´ıc´ı tvrzen´ı:

11

1. a(bf ) = (ab)f . 2. (a + b)f = af + bf . 3. a(f + g) = af + ag. 4. 1f = f . D˚ ukaz: Vˇsechna tvrzen´ı jsou v podstatˇe zˇrejm´ a a asi byste je dok´ azali dok´ azat sami.

2



Polynomy

V t´eto ˇc´asti se budeme zab´ yvat speci´aln´ımi zobrazen´ımi, kter´e se naz´ yvaj´ı polynomy nebo nˇekdy tak´e mnohoˇcleny. Zaˇcneme tedy definic´ı polynomu. Definice 5 Zobrazen´ı f : R → R se naz´yv´ a re´ aln´y polynom, pokud existuj´ı re´ aln´ a ˇc´ısla a0 , a1 , . . . , an ˇ ısla a0 , a1 , . . . , an se takov´ a, ˇze f (x) = an xn + an−1 xn−1 + · · · + a1 x + a0 pro vˇsechna x ∈ R. C´ naz´yvaj´ı koeficienty polynomu. Fakt, ˇze f (x) = an xn + an−1 xn−1 + · · · + a1 x + a0 struˇcnˇe tak´e zapisujeme: n X ai xi . (2) f (x) = i=0

Podobnˇe zobrazen´ı g : C → C se naz´yv´ a komplexn´ı polynom, pokud existuj´ı komplexn´ı ˇc´ısla b0 , b1 , . . . , bn takov´ a, ˇze g(x) = bn xn + bn−1 xn−1 + · · · + b1 x + b0 pro vˇsechna x ∈ C. Mnoˇzinu re´ aln´ych (komplexn´ıch) polynom˚ u znaˇc´ıme PR (PC ).

Protoˇze polynomy jsou zobrazen´ı do mnoˇziny re´ aln´ ych ˇc´ısel m´ame pro nˇe definov´ any operace sˇc´ıt´ an´ı, n´asoben´ı a n´asoben´ı re´ aln´ ym ˇc´ıslem (viz Definice 4)3 . Automaticky pro nˇe tak´e plat´ı vˇsechny vlastnosti, kter´e jsme dok´ azali ve Vˇet´ach 2, 3 a 4. To, co ovˇsem nev´ıme je, jestli v´ ysledky tˇechto operac´ı budou opˇet polynomy (jestli jsou takzvanˇe uzavˇren´e na operace sˇc´ıt´ an´ı, n´asoben´ı a n´asoben´ı re´ aln´ ym ˇc´ıslem). Napˇr. pokud vyn´ asob´ıme dva polynomy, v´ıme, ˇze v´ ysledek bude zobrazen´ı, ale nev´ıme, jestli to bude polynom. Zaˇcneme nejdˇr´ıve s jednoduch´ ym pozorov´ an´ım. Konstantn´ı zobrazen´ı ¯0 je zˇrejmˇe polynom, protoˇze existuje re´ aln´e ˇc´ıslo (koneckonc˚ u i komplexn´ı) a0 = 0 takov´e, ˇze ¯0(x) = a0 pro vˇsechna x ∈ R. Zobrazen´ı ¯ 0 budeme tedy naz´ yvat nulov´y polynom. Pozorov´ an´ı 1 Necht’ f je re´ aln´y (komplexn´ı) polynom takov´y, ˇze f (x) = an xn + · · · + a1 x + a0 . Potom zˇrejmˇe pro vˇsechna x z definiˇcn´ıho oboru plat´ı f (x)

= an xn + · · · + a1 x + a0 =

= =

0xn+1 + an xn + · · · + a1 x + a0 = 0xn+2 + 0xn+1 + an xn + · · · + a1 x + a0 = · · ·

Pokud tedy bude potˇreba m˚ uˇzeme v´yraz poˇc´ıtaj´ıc´ı hodnotu polynomu f v bodˇe x prot´ ahnout o libovolnou d´elku tak, ˇze pˇridan´e koeficienty poloˇz´ıme rovny nule. To se hod´ı zejm´ena v pˇr´ıpadˇe, kdy chceme, aby dva r˚ uzn´e polynomy mˇely stejn´y poˇcet koeficient˚ u. Nyn´ı jiˇz m˚ uˇzeme dok´ azat, ˇze polynomy jsou skuteˇcnˇe uzavˇren´e na v´ yˇse zm´ınˇen´e operace. Vˇ eta 5 Necht’ f, g jsou re´ aln´e (komplexn´ı) polynomy a c je re´ aln´e (komplexn´ı) ˇc´ıslo. Pak zobrazen´ı f +g, f g a cf jsou opˇet re´ aln´e (komplexn´ı) polynomy (jin´ymi slovy mnoˇzina polynom˚ u je uzavˇren´ a na operace sˇc´ıt´ an´ı, n´ asoben´ı a n´ asoben´ı re´ aln´ym ˇc´ıslem). 3 Podobnˇ e

lze operace zav´ est i pro komplexn´ı polynomy.

12

D˚ ukaz: Vˇeta tvrd´ı, ˇze zobrazen´ı f + g, f g a cf jsou polynomy. Podle definice polynomu mus´ıme tedy uk´azat ve vˇsech tˇrech pˇr´ıpadech existenci koeficient˚ u. Protoˇze f a g jsou polynomy m˚ uˇzeme jejich hodnoty v bodˇe x vyj´ adˇrit takto: n

f (x) = an x + · · · + a1 x + a0 =

n X

i

n

g(x) = bn x + · · · + b1 x + b0 =

ai x ,

i=0

n X

bi xi .

(3)

i=0

Podle Pozorov´ an´ı 1 jsme si mohli dovolit vyj´ adˇrit hodnoty polynom˚ u f i g v bodˇe x se stejn´ ym poˇctem koeficient˚ u. Nyn´ı dok´ aˇzeme postupnˇe, ˇze f + g, f g a cf jsou polynomy. Zaˇcneme zobrazen´ım f + g. (f + g)(x) = f (x) + g(x) =

n X

i

ai x +

n X

i

bi x =

(ai + bi )xi .

i=0

i=0

i=0

n X

Okomentujme pˇredchoz´ı rovnosti. Prvn´ı rovnost je akor´ at definice sˇc´ıt´ an´ı dvou zobrazen´ı (viz Definice 4). Druh´ a rovnost je dosazen´ı za f (x) a g(x) podle rovnice (3). Posledn´ı rovnost plyne z vlastnost´ı re´ aln´ ych (komplexn´ıch) ˇc´ısel. Vid´ıme tedy, ˇze hodnotu zobrazen´ı f + g v bodˇe x jsme schopni vyj´ adˇrit v takov´em tvaru, v jak´em ho ud´ av´ a rovnice (2). Zobrazen´ı f + g je tedy polynom a re´ aln´a (komplexn´ı) ˇc´ısla a0 + b0 , a1 + b1 , . . . , an + bn jsou jeho koeficienty. Podobnˇe uk´ aˇzeme ˇze zobrazen´ı cf je polynom. (cf )(x) = cf (x) = c

n X

i

ai x =

n X

(cai )xi .

i=0

i=0

Koeficienty polynomu cf tedy jsou ˇc´ısla ca0 , ca1 , . . . , can . Nakonec uk´ aˇzeme, ˇze i zobrazen´ı f g je polynom. ! n ! n 2n X X X i i (f g)(x) = f (x)g(x) = ai x bi x = ci xi , i=0

i=0

(4)

i=0

kde pro k = 0, 1, 2, . . . , 2n je ck = a0 bk + a1 bk−1 + · · · + ak−1 b1 + ak b0 =

k X

ai bk−i .

i=0

V´ yraz na prav´e stranˇe rovnice (4) jsme dostali rozn´asoben´ım z´avorek a sdruˇzen´ım ˇclen˚ u se stejnou mocninou u x k sobˇe. Tzn. rozn´asoben´ım tohoto v´ yrazu (an xn +· · ·+a1 x+a0 )(bn xn +· · ·+b1 x+b0 ).  Jednou ze z´akladn´ıch charakteristik polynomu je jeho stupeˇ n. Napiˇsme si jeho definici. Definice 6 Necht’ f je re´ aln´y nebo komplexn´ı polynom takov´y, ˇze f (x) = an xn + an−1 xn−1 + · · · + a1 x + a0 pro vˇsechna x z definiˇcn´ıho oboru. Stupeˇ n polynomu f (oznaˇcujme st f ) je nejvˇetˇs´ı m ∈ N takov´e, ˇze am 6= 0. Stupeˇ n nulov´eho polynomu ¯0 definujeme z technick´ych d˚ uvod˚ u −1. Polynom stupnˇe 0 budeme naz´yvat konstantn´ı. Pm Pn i i Vˇ eta 6 Necht’ f, g jsou polynomy t.ˇz. f (x) = i=0 bi x . Pak f = g p.t.k. i=0 ai x , g(x) = st f = st g a ai = bi pro vˇsechna i ∈ {0, . . . , st f }. D˚ ukaz: Sporem: pokud m 6= n, pak prodlouˇz´ıme f a g na stejn´ y poˇcet koeficient˚ u. M´ame n X

ai xi =

n X i=0

i=0

13

bi xi

n X i=0

n

(ai − bi )xi = 0

Existuje polynom h t.ˇz. h(x) = x + cn−1 xn−1 + · · · + c0 = 0 pro vˇsechna x ∈ R(C).



Vˇ eta 7 Necht’ f a g jsou polynomy. Pak plat´ı: 1. st f ± g ≤ max{st f, st g}. 2. st cf = st f pro c 6= 0. 3. st f g = st f + st g pokud f, g 6= ¯ 0. Vˇ eta 8 Necht’ f, g jsou polynomy a g 6= ¯0. Pak ∃ jednoznaˇcnˇe urˇcen´e polynomy p a z t.ˇz. f = gp+z a st z < st g. D˚ ukaz:  Existence plyne z algoritmu dˇelen´ı polynom˚ u. Jednoznaˇcnost dok´ aˇzeme sporem. Pˇrepoklad´ ame, ˇze existuj´ı polynomy p1 , p2 , z1 , z2 t.ˇz. p1 6= p2 nebo z1 6= z2 a f = gp1 + z1 , f = gp2 + z2 , st z1 < st g , st z2 < st g . gp1 + z1 = gp2 + z2 Protoˇze p1 − p2 6= ¯ 0 a g 6= ¯ 0 m´ame:

g(p1 − p2 ) = z2 − z1

st g(p1 − p2 ) = st g + st (p1 − p2 ) = st (z2 − z1 ) ≤ max{st z2 , st z1 } < st g Jedinˇe kdyˇz st (p2 − p1 ) = −1, tj. p1 = p2 . A tud´ıˇz z2 − z1 = g(p1 − p2 ) = g ¯0 = ¯0  ˇ ık´ Definice 7 Necht’ f, g jsou polynomy. R´ ame, ˇze f je dˇeliteln´y g (g dˇel´ı f ), pokud z = ¯0. Pˇr´ıklad na dˇelen´ı. (2x5 − x4 + 4x3 + 3x2 − x + 1) : (x3 + x2 − x + 1)

3

Hornerovo schema f (x)

= a4 x4 + a3 x3 + a2 x2 + a1 x + a0 = (a4 x + a3 )x3 + a2 x2 + a1 x + a0 = =

((a4 x + a3 )x + a2 )x2 + a1 x + a0 (((a4 x + a3 )x + a2 )x + a1 )x + a0

f (x0 ) = (((a4 x0 + a3 )x0 + a2 )x0 + a1 )x0 + a0

14

b4 b3

= a4 = b4 x0 + a3

b2 b1 b0

= b3 x0 + a2 = b2 x0 + a1 = b1 x0 + a0

Pak f (x) = (x − x0 )(b4 x3 + b3 x2 + b2 x + b1 ) + b0 .

f (x0 ) = b0 ,

a4 x0 b4

a3 b4 x0 b3

a2 b3 x0 b2

a1 b2 x0 b1

a0 b1 x0 b0

Pˇr´ıklad: 2x4 − 3x3 + 5x2 − x + 6 ,

4

x0 = −2

Koˇ reny

Definice 8 Necht’ f je nenulov´y polynom. Re´ aln´e (komplexn´ı) ˇc´ıslo c nazveme koˇrenem f , pokud f (c) = 0. Vˇ eta 9 Komplexn´ı ˇc´ıslo c je koˇrenem polynomu f p.t.k. f je dˇeliteln´y polynomem x − c. D˚ ukaz: (⇒) Necht’ f (c) = 0. f = (x − c)p + z a st z < st (x − c) = 1. Takˇze st z = 0 nebo st z = −1. Polynom z je tedy konstatn´ı, tj. z(x) = b pro nˇejak´e b ∈ R. M´ame tedy: f (x) = (x − c)p(x) + b Protoˇze c je koˇren, dostaneme: 0 = f (c) = (c − c)p(c) + b = 0p(c) + b = b (⇐) Necht’ f (x) = (x − c)p(x). Pak f (c) = (c − c)p(c) = 0. Takˇze c je koˇren.  Definice 9 Necht’ f je polynom. Re´ aln´e (komplexn´ı) ˇc´ıslo c nazveme k-n´ asobn´ym koˇrenem f , ˇ ıslo k se naz´yv´ pokud k je nejvˇetˇs´ı pˇrirozen´e ˇc´ıslo t.ˇz. (x − c)k dˇel´ı f . C´ a n´ asobnost. Vˇ eta 10 (Z´ akladn´ı vˇ eta algebry) Kaˇzd´y f ∈ PC t.ˇz. st f ≥ 1 m´ a alespoˇ n jeden koˇren. D˚ usledek 1 Necht’ f ∈ PC t.ˇz. st f = n ≥ 1 a f (x) =

Pn

i=0

ai xi . Pak

f (x) = an (x − c1 )k1 (x − c2 )k2 · · · (x − cm )km , kde c1 , . . . , cm ∈ C jsou vˇsechny koˇreny f a k1 , . . . , km , m ∈ N takov´e, ˇze n = k1 + k2 + · · · + km . D˚ ukaz: Inkukc´ı podle stupnˇe. 1. Pro n = 1 plat´ı, protoˇze a1 x + a0 = a1 (x +

a0 a1 ).

15

2. Necht’ st f = n. Podle ZVA m´a f koˇren, tj. f = (x − c)k p. Zˇrejmˇe n = st f = st (x − c)k + st p = k + st p st p = n − k Z indukˇcn´ıho pˇredpokladu: p = b(x − c1 )k1 · · · (x − cm )km ,

n − k = k1 + · · · + km .

Dosazen´ım: f = (x − c)k p = b(x − c)k (x − c1 )k1 · · · (x − cm )km Zˇrejmˇe b = an .  Vˇ eta 11 Necht’ f ∈ PC s re´ aln´ymi koeficienty a c = a + bi je jeho k-n´ asobn´y koˇren. Pak c = a − bi je tak´e k-n´ asobn´y koˇren f . D˚ ukaz: Necht’ f (x) = an xn + · · · + a0 . Pak f (x) = an xn + · · · + a0 = an (x)n + · · · + a0 = an (x)n + · · · + a0 = f (x) . Protoˇze f (x) = f (x) a x = x, m´ame f (x) = f (x). f (x)

= f (x) = (x − c)k (bn (x)n + · · · + b0 ) = (x − c)k (bn (x)n + · · · + b0 ) = (x − c)k (bn xn + · · · + b0 )

 D˚ usledek 2 Necht’ f ∈ PR a st f je lich´y. Pak f m´ a alespoˇ n jeden re´ aln´y koˇren. Vˇ eta 12 Necht’ f ∈ PR . Pak f (x) = an (x − c1 )k1 · · · (x − cm )km (x2 + b1 x + d1 )l1 · · · (x2 + br x + dr )lr . D˚ ukaz: f (x) = an (x − c1 )k1 · · · (x − cm )km

uˇzeme je rozn´asobit: Kdyˇz se (x − ci )ki vyskytuje v rci nahoˇre, pak se (x − ci )ki vyskytuje tak´e. M˚ (x − ci )ki (x − ci )ki = (x2 − (ci + ci )x + ci ci )ki = (x2 − 2Re(ci )x + |ci |2 )ki  ˇ Definice 10 Necht’ f ∈ PR . Rekneme, ˇze f je ireducibiln´ı nad tˇelesem R, pokud neexistuj´ı g, h ∈ PR t.ˇz. f = gh a st g, st h ≥ 1. D˚ usledek 3 Nekonstatn´ı polynom f ∈ PR je ireducibiln´ı p.t.k. st f = 1 nebo st f = 2 a f m´ a pouze komplexn´ı koˇreny. Vˇ eta 13 Necht’ f (x) = an xn + · · · + a0 je polynom stupnˇe n a ai ∈ Z. Pokud f ( pq ) = 0, kde a p, q jsou nesoudˇeln´ a, pak p dˇel´ı a0 a q dˇel´ı an . 16

p q

∈Q

D˚ ukaz: Dosad´ıme

p q

do f (x):

0=f

 n  n−1     p p p p = an + a0 + an−1 + · · · + a1 q q q q

Vyn´ asob´ıme q n : an pn + an−1 pn−1 q + · · · + a1 pq n−1 + a0 q n = 0 Tud´ıˇz: an pn = −q(an−1 pn−1 + · · · + a1 pq n−2 + a0 q n−1 )

a0 q n = −p(an pn−1 + an−1 pn−2 q + · · · + a1 q n−1 )

Takˇze q dˇel´ı an pn a protoˇze p, q jsou nesoudˇeln´a, dˇel´ı i an . Podobnˇe p dˇel´ı a0 . Pˇr´ıklad: 3x4 − 2x3 + x2 − 2x + 6 p ∈ {±1, ±2, ±3, ±6} ,

q ∈ {±1, ±3}

p 1 2 ∈ {±1, ±2, ±3, ±6, ± , ± } q 3 3

17