Nekonečno v matematice: 1. Potenciální 2. Aktuální Potenciální nekonečno vyjadřuje pouze možnost neustálého „zvětšování“ konečných množin. Existují pouze konečné množiny. Aktuální nekonečno, které bylo uznáno až v 19. století v díle Bernarda Bolzana „Paradoxy nekonečna“ (1851), znamená, že můžeme uvažovat a matematicky počítat s nekonečnou množinou jako celkem. To vedlo k rozvoji matematiky, zejména matematické analýzy. Cantorův axiom spojitosti: Průnik do sebe zařazených úseček je neprázdný. Konstrukce iracionálních čísel: víme, že uspořádání množiny racionálních čísel je husté, tzn. mezi každá dvě různá racionální čísla lze „vložit“ další racionální číslo. Např. mezi čísly a určitě existuje racionální číslo . Zdá se tedy, že číselná osa je „zcela vyplněná“ obrazy racionálních čísel. To však není pravda, na číselné ose jsou ještě mezery. Např. číslo , které určitě existuje (délka úhlopříčky ve čtverci o straně 1), není racionální. Důkaz: Provedeme sporem. Nechť = , kde p, q jsou celá nenulová kladná čísla a platí D (p, q) = 1 (jsou nesoudělná). Pak p = q Þ p^2 = 2q^2 Þ p^2^ je sudé číslo Þ p je sudé číslo, tedy p = 2u. Dosadíme do vztahu p = q. Potom platí 2u = q Þ q = u Þ q^2 = 2u^2 Þ q^2^ je sudé číslo Þ q je sudé číslo, tedy q = 2v. Srovnáme-li vztahy p = 2u, q = 2v, dostáváme spor s předpokladem, že čísla p, q jsou nesoudělná. Předpoklad = tedy neplatí, číslo nelze vyjádřit zlomkem a tedy není racionální. -------------------------------------------------------------------- Existují tedy iracionální čísla. Je jich nekonečně mnoho a jejich desetinný rozvoj je nekonečný a neperiodický. Každá mezera na číselné ose reálných čísel vyjadřuje jedno číslo iracionální. Platí R = Q È I. Určení hodnoty iracionálního čísla můžeme provést užitím Cantorova principu spojitosti tak, že postupně aproximujeme hledané iracionální číslo na číselné ose zleva a zprava racionálními čísly (tím vytváříme posloupnost do sebe zařazených úseček), přičemž po provedení nekonečně mnoha aproximací obdržíme hledané iracionální číslo (je třeba uznání aktuálního nekonečna). Je zřejmé, že nekonečně mnoho aproximací nelze v praxi provést. Po konečně mnoha krocích, až dosáhneme požadované přesnosti, proces ukončíme. Určíme . 1^2 = 1; 2^2 = 4, tedy 1 < < 2 (1,4)^2 = 1,96; (1,5)^2 = 2,25 , tedy 1,4 < < 1,5 (1,41)^2 = 1,9881; (1,42)^2 = 2,0164 , tedy 1,41 < < 1,42 (1,414)^2 = 1,999396; (1,415)^2 = 2,002225 , tedy 1,414 < < 1,415 (1,4141)^2 = 1,99967881; (1,4143)^2 = 2,00024449 , tedy 1,4141 < < 1,4143 atd. Proces postupné aproximace iracionálního čísla lze i programovat. Příkladem může být přibližné určení čísla Eulerova čísla e. Víme, že 2 < e < 4 . Dále z matematické analýzy víme, že platí: = e, = e, přičemž první z těchto posloupností je rostoucí s prvním členem 2, druhá z těchto posloupností je klesající s prvním členem 4. Obecně tedy můžeme Eulerovo číslo aproximovat pro n Î N pomocí nerovností < e < . Třetím příkladem na užití Cantorova principu spojitosti je Jordanova teorie míry. Z geometrie víte, že obsah jakéhokoliv nepravidelného útvaru lze určit tak, že jej „položíme“ na čtvercovou síť a postupně počítáme jádra a obaly. Jádro je množina všech čtverců sítě, které jsou „celé“ podmnožinou daného útvaru, zatímco obal je množina všech čtverco sítě, které mají s daným útvarem alespoň jeden společná vnitřní bod (překrývají se). V prvním kroku (např. začneme se čtverci o délce strany 1) je J[1 ]< O[1]. To může být hodně nepřesné. Proto zjemníme síť a ve druhém kroku J[1 ]< J[2 ], O[1 ]> O[2 ]. Opět platí nerovnost J[2 ]< O[2 ], ale rozdíl těchto hodnot je menší. Představíme-li si obrazy hodnot jader a obalů na číselné ose, jde opět o vnořené intervaly. Při každém zjemnění sítě se hodnota J[n ]posune doprava a hodnota O[n ]se posune doleva. Vždy platí J[n ]< O[n ], ale tyto hodnoty se při každém zjemnění sítě k sobě přiblíží. Kdybychom provedli proces zjemnění nekonečně krát, obdrželi bychom přesnou hodnotu obsahu daného tělesa. „Počítání“ s nekonečnými soubory Uznání aktuálního nekonečna umožnilo řadu významných matematických objevů. Poznali jste např. konstrukci kardinálních čísel konečných množin, která začínala předpokladem „nechť M je systém všech konečných množin“. Kdybychom neuznali aktuální nekonečno, byla by celá konstrukce kardinálních čísel nemožná. Dalším objevem byla konstrukce iracionálních čísel. Prakticky je můžeme aproximovat zleva a zprava pouze několikrát; teprve až provedeme nekonečný počet aproximací, určíme iracionální číslo přesně. Tento postup jste použili také u Jordanovy míry v rovině. Velký význam má definice určitého integrálu. Nyní uvedeme několik ukázek toho, jak ošidné je počítání s nekonečnými soubory. Příklad 1: Vypočítejte 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + . . . Takto zadaný součet neexistuje, resp. přerovnáním této řady lze dostat různé výsledky: a) (1 - 1) + (1 - 1) + (1 - 1) + . . . = 0 b) 1 + (- 1 + 1) + (- 1 + 1) + . . . = 1 c) označme součet zadané řady jako S, tedy 1 - 1 + 1 - 1 + . . . = S. Současně ale platí S = 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + . . . = = 1 - (1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + . . .) = 1 - S. Odtud S = 1 - S, tedy S = . Příklad 2: Sečtěte řadu + + + . . . Tato řada součet má. Je to geometrická řada s prvním členem a koeficientem , její součet je roven 1. Příklad 3: Sečtěte řadu + + + + + + + . . . Tato řada se nazývá harmonická a její zvláštností je, že diverguje, tzn. její součet je nekonečný, přestože se její n-tý člen blíží k nule. Kardinální čísla nekonečných množin: Jestliže jsme uznali aktuální nekonečno, musíme si položit otázku, zda teorie kardinálních čísel platí i pro nekonečné množiny. Odpověď je pozitivní, teorie kardinálních čísel platí obecně. Jaké je tedy kardinální číslo množiny N všech přirozených čísel? Žádné přirozené číslo to být nemůže. Existuje zvláštní symbol, „alef nula“, . Píšeme tedy | N | = . Totéž kardinální číslo, alef nula, mají rovněž všechny množiny ekvivalentní s množinou N. Takové množiny nazýváme spočetné. Existují i větší kardinální čísla nekonečných množin, např. množina všech reálných čísel R má mohutnost kontinua (označujeme c). Všechna tvrzení, které znáte ze 2. ročníku pro konečné množiny, platí i pro nekonečné množiny. Např. Nechť A, B jsou libovolné množiny. Pak definujeme | A | < | B |, právě když existuje prosté zobrazení celé množiny A do množiny B (nikoliv na celou množinu B). Nechť A, B jsou libovolné množiny, nechť platí A Ç B = . Pak | A | + | B | = | A È B | . Nechť A, B jsou libovolné množiny. Pak | A | × | B | = | A ´ B | . Početní spoje existují i s nekonečnými kardinálními čísly, např. + 1 = , 2 × , + = , apod. Vzhledem k účelu Vašeho studia se tímto dále nemusíme zabývat. Antinomie (paradoxy) teorie množin – 3. krize matematiky Už víte, že množina je synonymem pro skupinu, stádo, hejno, … Víte, že ji lze definovat výčtem prvků nebo jejich charakteristickou vlastností. Podle teorie Georga Cantora je množina úplně určena, jestliže můžeme o každém prvku a každé množině jednoznačně rozhodnout, zda prvek do množiny patří či nikoliv. Pro každý objekt x a každou množinu A tedy platí právě jeden ze vztahů x Î A, x Ï A. Tato představa je zcela jasná a proto způsobilo velký rozruch, když se na počátku 20. století objevily paradoxy, které tuto představu porušily. Uvedeme příklad Russelova paradoxu: „Nechť v jistém městě jsou pouze činžovní bytové domy. Každý dům má na starosti domovník, který buď v domě bydlí v domovnickém bytě (tzv. interní domovník), nebo v domě, o který pečuje, nebydlí a dochází tam jen do práce (tzv. externí domovník). Bylo rozhodnuto, že bude na náklady města postaven nový dům, do kterého se musí nastěhovat všichni externí údržbáři a nesmí tam bydlet nikdo jiný. Sami promyslete, že domovník tohoto nového domu nemůže ve městě nalézt ubytování.“ Množinu A zde tvoří obyvatelé nového domu A a prvek x je domovník nového domu A. Ze vztahů x Î A, x Ï A neplatí zřejmě ani jeden, tím je porušena Cantorova představa o množinách. Co teď? Teorie množin musí být vybudována jinak, tj. axiomaticky. Existují dvě možnosti, kterými se dále nemusíme zabývat. Znázornění množin: 1. Vennovy diagramy. Znáte a používáte je po celou dobu studia. Vennovy diagramy existují pro libovolný počet množin. Pro více než tři množiny jsou však nepřehledné, protože pro čtyři a více množin již nemohou být znázorněny kruhy (elipsami), ale uzavřenými křivkami. Na obrázku je ukázka Vennova diagramu pro 5 množin. 2. Karnaughovy diagramy Tyto diagramy se používají zejména v elektrotechnice. Výhodou je, že zobrazujeme množiny v „pravoúhlém“ systému, nevýhodou je pak to, že od páté množiny se obrazy množin dělí na části. Opět následuje ilustrace pro 6 množin. Pro 6 množin existuje v diagramu skutečně 64 elementárních polí. Využijeme-li označení užívané v šachu, pak červeně vybarvené políčko C6 označuje průnik všech šesti množin (prvky v tomto poli patří do všech šesti množin), zatímco černě vybarvené pole H1 obsahuje doplněk sjednocení všech šesti množin (toto pole neobsahuje prvky ani jedné z šesti množin). Modře šrafované pole G7 obsahuje prvky množin A, E, F, neobsahuje prvky množin B, C, D. Princip inkluze a exkluze (zapojení a vypojení) Účinným prostředkem při řešení úloh je tzv. princip inkluze a Exkluze. Uvedeme pouze formulace pro n = 2 a n = 3. A) n = 2. Nechť A, B jsou libovolné množiny v základní množině M. Ve Vennově diagramu pro tyto dvě množiny označme potřebné počty prvků množin takto: Počet prvků množiny M… m; Počet prvků množiny A … a; Počet prvků množiny B … b; Počet prvků množiny A È B … s; Počet prvků množiny A Ç B … p; Počet prvků množiny M - (A È B) … o. Pak platí: o = m - a - b + p Jestliže nyní bude množina M - (A È B) prázdná, tj. o = 0, pak zřejmě místo m můžeme psát s (každý prvek základní množiny nyní leží v množině A nebo v množině B). Potom 0 = s - a - b + p, a odtud s = a + b - p. Tuto rovnici běžně využíváte při řešení slovních úloh, v nichž množiny mají společné prvky. Předpokládáme-li navíc také p = 0, dostaneme s = a + b, což je známé sčítání kardinálních čísel. Příklad: Na třídní akademii bylo 20 účinkujících, každý z nich zpíval nebo tancoval. Zpívalo 15 dětí, tancovalo 12 dětí. Kolik dětí zpívalo i tancovalo? Řešení podle vzorce: s = 20, a = 15, b = 12, p = ? p = a + b - s = 15 + 12 - 20 = 7 Zpívalo i tancovalo 7 žáků. Poznamenejme, že takto s žáky úlohu řešit nelze (šlo by o formalismus). Didakticky je nutno volit jiný postup. B) n = 3. Nechť A, B, C jsou libovolné množiny v základní množině M. Ve Vennově diagramu pro tyto tři množiny označme potřebné počty prvků množin takto: Počet prvků množiny M… m; Počet prvků množiny A … a; Počet prvků množiny B … b; Počet prvků množiny C … c; Počet prvků množiny A È B È C … s; Počet prvků množiny A Ç B … p[1]; Počet prvků množiny A Ç C … p[2]; Počet prvků množiny B Ç C … p[3]; Počet prvků množiny A Ç B Ç C … p; Počet prvků množiny M - (A È B È C) … o. Pak platí: o = m - a - b - c + p[1 ]+ p[2 ][ ]+ p[3 ]- p Jestliže nyní bude množina M - (A È B È C) prázdná, tj. o = 0, pak zřejmě místo m můžeme psát s (každý prvek základní množiny nyní leží v množině A nebo v množině B nebo v množině C). Potom 0 = s - a - b - c + p[1 ]+ p[2 ][ ]+ p[3 ]- p, a odtud s = a + b + c - p[1 ]- p[2 ][ ]- p[3 ]+ p. Příklad 1. Kolik přirozených čísel od 1 do 500 není dělitelných ani třemi, ani pěti, ani sedmi. Řešení: Písmenem M označíme množinu všech přirozených čísel od 1 do 500, tedy o = 500. Dále označíme: A = {n Î M; n je dělitelné třemi}; B = {n Î M; n je dělitelné pěti}; C = {n Î M; n je dělitelné sedmi}; A Ç B = {n Î M; n je dělitelné třemi a pěti, tj. číslem 15}; A Ç C = {n Î M; n je dělitelné třemi a sedmi, tj. číslem 21}; B Ç C = {n Î M; n je dělitelné pěti a sedmi, tj. číslem 35}; A Ç B Ç C ={n Î M; n je dělitelné pěti, třemi a sedmi, tj. číslem 105} V zavedeném označení m = 500, a = 166, b = 100, c = 71, p[1 ]=33, p[2 ]= 23, p[3 ]= 14, p = 4, o = ? Po dosazení o = 500 - 166 - 100 -71 + 33 + 23 + 14 - 4 = 229. Hledaných čísel je 229. Příklad 2. V jistém závodě zhotovili následující přehled o svých zaměstnancích V závodě pracuje celkem 250 mužů a 200 žen. Předepsanou kvalifikaci má 160 mužů a 140 žen. Do práce dojíždí 180 mužů a 100 žen. Kvalifikovaných mužů dojíždí 150, kvalifikovaných žen 20. Dokážeme, že uvedené hlášení je nepravdivé. Řešení. V závodě pracuje celkem 450 zaměstnanců. Označme nyní možné množiny následovně: A označuje množinu mužů, B označuje množinu kvalifikovaných pracujících, C množinu dojíždějících. Z hlášení plyne: m = 450, a = 250, b = 300, c = 280, p[1 ]= 160, p[2 ]= 180, p[3 ]= 170, p = 150. Po dosazení do principu máme o = 450 − 250 − 300 − 280 + 160 + 180 + 170 − 150 = −20, což není možné. Proto musí být alespoň jeden údaj v hlášení chybný. Dirichletův princip. Německý matematik Peter Gustav Lejeune Dirichlet žil v letech 1805–1859. Studoval v Berlíně, v Gőttingenu a v Paříži. V letech 1822 –1827 působil v Paříži jako domácí učitel, od roku 1827 byl docentem na univerzitě ve Vratislavi, od roku 1829 v Berlíně. Po smrti K. Gausse v roce 1855 přešel na jeho místo do Gőttingenu. Zabýval se teorií čísel, matematickou analýzou a matematickou fyzikou a ve všech těchto oborech dosáhl významných výsledků. Mezi jeho žáky patřili např. Riemann, Dedekind a Kronecker. Princip, nesoucí jeho jméno, uvedl Dirichlet v roce 1834 pod názvem Schubfachprinzip (zásuvkový princip). Pod označením zásuvkový princip je dodnes používán např. v italštině (principio dei cassetti). V angličtině je naproti tomu běžnější označení princip holubníku (pigeonhole principle). Uvedeme tři formulace Dirichletova principu. Formulace 1: Umístíme-li m předmětů do n přihrádek (m, n Î N), pak pro m > n existuje alespoň jedna přihrádka obsahující alespoň dva předměty. Formulace 2: Umístíme-li nk+1 předmětů do n přihrádek (k, n Î N), pak existuje alespoň jedna přihrádka obsahující alespoň k+1 předmětů. Formulace 3: Je-li součet n reálných čísel x[1], x[2], …, x[n] roven číslu S, pak pro alespoň jedno číslo iÎ {1,…, n} platí nerovnost x[i] £ a pro alespoň jedno jÎ {1,…, n} platí x[j] ³ . Příklad 1: V podniku pracuje 400 osob. Dokažte, že alespoň dvě osoby mají narozeniny ve stejný den v roce. Ř: Počítejme i s přestupnými roky. Možností pro oslavu narozenin v roce je tedy 366. Zavedeme 366 přihrádek, do nichž budeme zařazovat pracovníky podle data narození. Protože počet pracovníků je větší než počet přihrádek, musí existovat přihrádka obsahující alespoň dvě osoby. Tito lidé mají narozeniny ve stejný den v roce. Příklad 2: Konference se zúčastnilo 40 delegátů ze 13 zemí. Dokažte, že alespoň z jedné země přijela delegace, která měla alespoň čtyři členy. Ř: Rozdělíme delegáty do přihrádek podle toho, z jaké země pocházejí. Přihrádek bude proto 13. Delegátů je ale 40, což je více než 3. 13 = 39. Proto existuje přihrádka obsahující alespoň čtyři členy, tj. alespoň jedna země vyslala nejméně čtyřčlennou delegaci. Příklad 3: V krabici je 5 kuliček bílých, 5 červených a 5 modrých. Kolik kuliček musíme potmě vybrat z krabice, abychom vybrali určitě dvě kuličky stejné barvy? Ř: Máme kuličky tří barev, je tedy možno po vytažení rozmístit vytažené kuličky do tří přihrádek podle barvy. Chceme-li mít zaručeno, že v jedné přihrádce budou alespoň dvě kuličky, musíme vytáhnout víc kuliček, než je přihrádek. Stačí tedy vybrat náhodně 4 kuličky. Příklad 4: Dokažte, že v každém trojúhelníku je alespoň jeden vnitřní úhel větší nebo roven 60°. Ř: Využijeme formulace 3. Pro vnitřní úhly a, b, g v trojúhelníku platí a + b + g = 180°. Proto musí existovat alespoň jeden úhel, jehož velikost je větší nebo rovna = 60°. Příklad 5: Je dáno 10 přirozených čísel. Dokažte, že z nich můžeme vybrat dvě tak, že jejich rozdíl je dělitelný číslem 9. Ř: Rozdělíme daná čísla do zbytkových tříd podle zbytků při dělení číslem 9. Těchto zbytkových tříd je 9 (zbytky 0 až 8). Protože ale čísel je 10, musí ležet v jedné třídě alespoň dvě čísla. Ta dávají po dělení 9 týž zbytek, jejich rozdíl je tedy dělitelný 9. Poznamenejme, že jsme dokázali pouze existenci takových dvou čísel. Určit, která dvě čísla splňují danou podmínku, může být velmi pracné. Příklad 6: Číselná tabulka 3´ 3 je libovolně vyplněna čísly 0, 1, 2. Dokažte, že pro jakýkoliv způsob rozmístění těchto čísel v tabulce jsou vždy dva z osmi součtů (tři sloupce, tři řádky a dvě hlavní diagonály) stejné. Ř: Uvedeme příklad. 2 0 1 2 1 2 0 1 0 Součty jsou 3, 5, 1, 4, 2, 3, 2, 3, tj. obsahuje stejné dvojice. Z daných tří čísel zřejmě nelze dostat jiné součty než 0, 1, 2, 3, 4, 5, 6, což je 7 možností. Výsledných součtů je ale 8, dva tedy nutně musí být stejné. Příklad 7: Nechť je dán rozklad množiny M = {1,2,3,…,9} na tři třídy. Dokažte, že součin všech čísel v alespoň jedné ze tříd je větší než 71. Ř: Součin všech přirozených čísel od 1 do 9 je roven 362 880. Kdyby v každé ze tří tříd rozkladu byl součin čísel menší nebo roven 71, pak by součin všech devíti čísel nepřevyšoval 71^3 = 357 911, což je spor. Příklad 8: V zahradě tvaru obdélníka o rozměrech 20m ´ 15m chceme vysázet stromy. Vzdálenost mezi libovolnými dvěma stromy má být větší než 5m. Dokažte, že stromů lze vysadit nejvýše 25. Ř: Připusťme, že v zahradě bude více než 25 stromů. Rozdělíme zahradu na obdélníky o rozměrech 4m ´ 3m. Takových obdélníků je právě 25. Proto musí v jednom z nich být alespoň dva stromy, jejich vzdálenost je však menší než 5m (velikost úhlopříčky je 5m). Příklad 9: Na večírku je přítomných n osob. Dokažte, že dva účastníci večírku znají stejný počet lidí (relace „znát“ je symetrická, tzn. zná-li jedna osoba druhou, zná i druhá první). Ř: Každý člověk může znát od 0 do n - 1 osob. Podle toho všechny přítomné rozdělíme do přihrádek. Je tedy n přihrádek i n osob. Dirichletův princip nelze přímo použít, využijeme však jinou úvahu. Připusťme, že v každé přihrádce je jediný člověk. To ale není možné, neboť by existovala osoba, která nezná nikoho a současně osoba, která zná všechny. Proto musí být v jedné přihrádce alespoň dva lidé, kteří tedy znají stejný počet účastníků. Příklad 10: V prostoru je dáno 9 bodů s celočíselnými souřadnicemi. Dokažte, že z nich lze vybrat alespoň dva body tak, že střed jimi určené úsečky má celočíselné souřadnice. Ř: Při řešení využijeme skutečnosti, že součet dvou sudých čísel i součet dvou lichých čísel je sudé číslo. Souřadnice bodů v prostoru je podle předpokladu uspořádaná trojice celých čísel, která mohou být sudá nebo lichá. Podle parity existuje pro tři souřadnice osm možností: [L,L,L], [L,L,S], [L,S,L], [S,L,L], [L,S,S], [S,L,S], [S,S,L], [S,S,S]. Bodů je ale zadáno devět, tzn. dva z nich budou mít stejnou paritu všech tří souřadnic. Střed úsečky ohraničené těmito dvěma krajními body bude mít rovněž celočíselné souřadnice. Kombinatorika Matematické soutěže: Mat. olympiáda a Klokan.