IBOOO Úvod do informatiky — príklady na procvičení Sada 4 — Řešení
Upozornění
Vzorová řešení dostáváte k dispozici, abyste mohli zkontrolovat správnost svých řešení. Můžete je použít i jako návody k řešení jednotlivých příkladů tak, že je budete číst po částech a budete se snažit další krok provést vždy sami. Příklady ztratí veškerý svůj smysl, pokud se je budete učit jako básničku. Snažte se nad nimi přemýšlet a vyřešit je sami, než se podíváte do vzorových řešení.
Téma
Vlastnosti funkcí. Mohutnost množin. Důkazové techniky.
Příklad 1.
Pro následující množiny A a. B rozhodněte, které tvrzení z \A\ = \B\, \A\ < \B\, \A\ > \B\ platí, a své tvrzení dokažte.
a)  A je množina všech sudých přirozených čísel, i? je množina všech lichých celých čísel.
b)  Nechť m,n G No- A je množina všech přirozených čísel větších než m, B je množina všech přirozených čísel větších než n.
c)  Nechť m,nGNo, m<n. A je množina všech přirozených čísel menších než n, B je množina všech celých čísel větších než m.
d)  A = No, B je množina všech lichých přirozených prvočísel. Nápověda: využijte tvrzení, že ke každému prvočíslu p existuje prvočíslo q, p < q. Zkuste toto tvrzení i dokázat.
e)  A = {n2 \ne N0}, B = {n3 \ n e N0}
f)  A = {n3 + 1 \ n E Z}, B = {n2 + 1 \ n E Z}
g)  A = {n2 + 1 | n G No}, B = {(m + 3)2 | m G N0}
h) A = No, B = (0,1) C K. Množina B je tedy otevřený interval reálných čísel.
Řešení
Nejprve si uvědomme, jak je možné jednotlivá tvrzení dokázat. Rovnost \A\ = \B\ dokážeme tak, že nalezneme bijekci / : A —► B. Nerovnost \A\ < \B\ bychom dokázali tak, že bychom nalezli injekci / : A —► B. Pokud máme ukázat ostrou nerovnost \A\ < \B\, potom musíme nalézt injekci / : A —► B a dokázat, že neexistuje bijekce g : A —► B.
Pokud hovoříme o „nalezení bijekce", rozumíme tím definici vhodné funkce a důkaz, že tato funkce je bijektivní (tj. injektivní a surjektivní). Podobně pro injekci. a) Platí \A\ = \B\. Mějme funkci / : A —► B definovanou pro všechna n G No předpisy
f {An) = 2n+l f (An+ 2) = -2n- 1
tj- / = {(4w, 2n + 1), (An + 2, — 2n — 1) | n G No}. Uvědomte si, nebo lépe dokažte, že tato relace je skutečně totální funkce z množiny A do množiny B. Zbývá ukázat, že je to bijekce.
1
Připomeňte si definici injektivní funkce. Nechť x, y E A, x ^ y jsou libovolné. Rozlišením čtyř případů podle toho, zda x = An nebo x = An+ 2 pro nějaké n E No, resp. zda y = 4m nebo y = 4m + 2 pro nějaké m G No ověřte, že potom platí f (x) ^ f (y)-
Připomeňte si definici surjektivní funkce. Nechť z G B je libovolné. Pokud z > 0, potom z = 2n+ 1 pro nějaké n G No a tedy z = /(4n), tedy z je obrazem nějakého prvku z A ve funkci /. Případ, kdy z < 0 dokončete analogicky sami.
b)  Platí \A\ = \B\. Bez újmy na obecnosti předpokládejme, že m < n. Definujme funkci / : A —► B předpisem f(x) = x + n — m. Důkaz, že / je bijekce, je snadný. Proveďte jej detailně sami.
Dobře si promyslete, jak by důkaz vypadal, kdybychom předpokládali m > n.
c)  Platí \A\ < \B\. Zde si dovolíme luxus a prohlásíme, že tvrzení je zřejmé, protože A je množina konečná, zatímco B je množina nekonečná.
Pokud bychom tvrzení chtěli dokázat na úrovni funkcí, potom příslušná injekce by byla podobná funkci z předchozího příkladu. Dále bychom sporem dokázali, že neexistuje surjektivní funkce z A do B. Důkaz si vyzkoušejte.
d)  Platí \A\ = \B\. Definujme funkci / : A —► B předpisem f(n) = pn, kde pn je n-té liché prvočíslo. Protože jediným prvočíslem, které není liché, je číslo 2, a protože platí tvrzení z nápovědy, je funkce / dobře definovaná pro každé n. Důkaz, že / je bijekce je opět snadný. Proveďte jej detailně sami. Důkaz tvrzení z nápovědy lze nalézt v literatuře.
e)  Platí \A\ = \B\. Definujme funkci / : A —► B následovně:
f = {(n2,n3) \neN0}
Důkaz, že / je bijekce bude podobný jako pro první dvojici množin A a B.
Nechť x, y G A, x ^ y. Potom z definice A existují m, n E No, m ^ n takové, že x = m2 a y = n2. Potom z definice / platí f (x) = m3 a f (y) = n3, takže f (x) ^ f(y)-Funkce / je injektivní.
Nechť z E B. Potom z definice B existuje n E No takové, že y = n3. Přitom jistě platí, že n2 E A, takže f (n2) = n3 = y. Funkce / je surjektivní.
f)  Platí \A\ = \B\, důkaz však nebude tak přímočarý jako v předchozím příkladě. Využijeme následující tvrzení. Nechť f\ : X —► Y, J2 : Y —► Z jsou bijekce. Potom
jsou bijekcemi i f\~ a /2 °/i- Tato tvrzení jste v podstatě dokazovali na písemce. Pokud se vám důkaz stále nedaří, jistě jej naleznete v literatuře.
Nejprve si uvědomme, žen2 + l = (—n)2 + l pro všechna n E Z, ale n3 + l ^ (—n)3 + l pro žádné n E Z, n ^ 0. Z první rovnosti plyne, že B = {n2 + 1 | n E No}.
Definujme funkce / : Z —► A a g : No —► B předpisy
f(n) = n3 + 1, n E Z g (n) = n2 + 1, n E No
Obě funkce / i g jsou bijektivní. Detailně to dokažte. Dále víme (z přednášky), že existuje bijekce h : Z —► No- Najděte ji. Nápověda: Funkce z přednášky nepovažuje nulu za přirozené číslo, je však možné ji snadno upravit. Dokažte, že upravená funkce je bijekce.
Nyní g o h o /_1 je hledaná bijekce z A do B.
g)  Platí \A\ = \B\. Důkaz je zcela analogický jako v případě e).
h) Platí \A\ < \B\. Injekcí, která potvrzuje, že \A\ < \B\, je funkce / : A —► B definovaná předpisem f(n) = (n + 2)_1. Důkaz, že nerovnost je striktní, zde neuvedeme, neboť lze nalézt v mnohé literatuře.
2
Příklad 2.
a)  Dokažte, že pro každé n E No, n > 1, existuje m G No takové, že 2m — 1 > n.
b)  Dokažte, že pro každé n E No, n > 1, existuje m G No takové, že 2m — 1 < n.
c)  Dokažte, že pro každé n E No, n > 1, existuje m G No takové, že 2m — 1 = n.
Řešení
a)  Budeme dokazovat silnější tvrzení: pro každé n E No, n > 1, platí 2n — 1 > n. Pro každé n tedy řekneme, jak vypadá vhodné m, čímž potvrdíme jeho existenci. K důkazu silnějšího tvrzení použijeme indukci.
Základní krok. Pro n = 2 tvrzení platí, protože 3 > 2.
Indukční krok. Nechť pro nějaké n G No, n > 1, platí 2n — 1 > n. (Toto je indukční předpoklad.) Tedy platí 2n > n + 1. Potom
2n+i -i = 2-2n -l>2(n + l)-l = 2n+l>n+l
První nerovnost plyne z indukčního předpokladu. Druhá nerovnost platí, protože n > 0. Nyní dokažte, že pro každé n E No existuje m G No takové, že 2m — 1 > n. Jedná se tedy o zobecnění původního tvrzení, neklademe zvláštní požadavky na číslo n. Nápověda: zvolte vhodné silnější tvrzení.
b)  Toto tvrzení je triviální a věřím, že se jej nikdo nepokusil dokázat indukcí. Pro každé n E No, n > 1, totiž můžeme položit m = 0 a bude platit
2° - 1 = 0 < 1 < n
Je možné toto tvrzení zobecnit jako v předchozím případě?
c)  Toto tvrzení neplatí. Například pro n = 4 vhodné m neexistuje.
3