IB112 Základy matematiky Základy naivní teorie množin, relace, zobrazení, číselné obory Jan Strejček Obsah ■ Množiny u základní operace ■ Russellův paradox ■ Relace u skládání relací ■ ekvivalence a rozklad množiny ■ uspořádání, Hasseův diagram ■ Zobrazení ■ injekce, surjekce, bijekce ■ Číselné obory N, Z, Q a M ■ Mohutnost ■ spočetnost a nespočetnost ■ Cantorova věta ■ princip inkluze a exkluze IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 2/65 Množiny IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 3/65 Množina ■ Množina je základní pojem matematiky. ■ Teorii množin vybudoval Georg Cantor (1845-1918) v roce 1872. ■ Naivní pohled: Množina je soubor prvků. Zápis ■ a g A značí a je prvkem množiny A. m a 0 A značí a není prvkem množiny A. m 0 značí prázdnou množinu. m {a, b, c} zapisuje množinu obsahující právě prvky a, b, c. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 4/65 Množina ■ Množina může být prvkem množiny. ■ Ve skutečnosti v teorii množin neexistuje nic jiného než množiny tedy každý prvek a množiny A je opět množina. Příklady množin ■ {a,b} {a}, {{a}}, {{{a}}}, {a, {a}, {{a}}} ■ {x | x je přirozené číslo dělitelné 3} ■ N = {1,2,3,...} - množina všech přirozených čísel ■ Z = {..., -2, -1,0,1,2,...} - množina všech celých čísel ■ Q - množina všech racionálních čísel m R - množina všech reálných čísel IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 5/65 Russellův paradox ■ Proč je uvedená definice množiny označena jako naivní? ■ Protože existují soubory prvků, které nelze považovat za množinu. Jeden takový soubor popsal Bertrandem Russellem (1872-1970) v roce 1901. Russellův paradox Množina X se nazývá normální, jestliže X 0 X. Nechť N je množina všech normálních množin. Je-li N normální, pak N e N a tedy N není normální. Není-li N normální, pak N 0 N a tedy N je normální. V seriózní teorii množin se za množiny považují pouze soubory prvků, které vznikly z prázdné množiny pomocí sady axiomů. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 6/65 Vztahy mezi množinami Množina A je podmnožina množiny B, psáno A c B, jestliže každý prvek z A je i prvkem z B. ■ Pokud A c B, pak také říkáme, že B je nadmnožinou A. ■ Pro každou množinu A platí 0 c A a A c /A. ■ Vztah c nazýváme také inkluze. Definice (Rovnost) Množina A je rovna množině B, psáno A = B, pokud platí A c B a B c A. m Množiny jsou shodné, pokud mají stejné prvky. ■ A je vlastní pomnožinou B, psáno A c B, pokud A c B a A ^ B. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 7/65 Operace na množinách ■ sjednocení: Au B = {x | x e A nebo xě8) ■ průnik: AnB = {x\xeAaxeB} m rozdíl: A\B = {x\xeAax^B} m symetrický rozdíl: A 4- B = (A\ B) u (S \ /A) Nechť /A c M. Doplněk A (vzhledem k nosné množině M) je množina A = M \ A. m Doplněk se nazývá také komplement. m Množiny A a B jsou disjunktní, pokud /A n fí = 0. V opačném případě se množiny nazývají incidentní. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 8/65 Vlastnosti množinových operací Průnik a sjednocení jsou ■ komutativní A n B = B n A Au B = BuA m asociativní A n (B n C) = (/A n B) n C Zlu(fiuC) = (/lufi)uC ■ idempotentní AnA = A AuA = A Dále platí distributivní zákony Au{BnC) = {AuB)n{AuC) An{BuC) = {AnB)u{AnC) IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 9/65 Vlastnosti množinových operací U doplňku velmi záleží na nosné množině M: m A = {á},M = {a}:A = <& m A = {a},M = {a,b}:A = {b} m A = {a}, M = {a,b,c}:A = {b, c} Pro doplněk dále platí m=A = A m De Morganovyzákony An B = Au B AuB=AnB De Morganovy zákony lze dále zobecnit A\{BnC) = {A\B)u{A\C) A\{BuC) = {A\B)n{A\C) IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 10/65 Zobecnění průniku a sjednocení Definice (Zobecněný průnik a sjednocení) Nechť A, je množina pro každé i e / / 0. Definujeme P| A = {x I x £ A pro /caždé / e /} /e/ U A = {x I x £ A pro nějaké i e /}. /e/ ■ Příklad: U/eN{2/'} = {2,4,6,...} ■ Dále se definuje U/e0 A = 0- ■ Je-li dána nosná množina M, lze definovat i f|/e0 A = M. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 11/65 Uspořádaná dvojice Uspořádanou dvojici (a, b) definujeme jako množinu {{a}, {a, b}}. ■ Platí (a, b) = (c, d) právě když a = c a b = d. ■ Jaká množina je dvojice (a, a)? IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 12/65 Kartézský součin Definice (Kartézský součin) Kartézský součin množin A, B je množina A x B = {{a,b) \aeA,beB}. ■ Příklad: {a, b} x {c, d} = {{a, c), (a, d), {b, c), {b, d)} m Pro každou množinu A platí 0x/A = /Ax0 = 0. ■ Obecně neplatí A x B = B x A (komutativita). ■ Obecně neplatí A x (B x C) = (A x B) x C (asociativita). IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 13/65 Uspořádaná k-tice Definice (Uspořádaná k-tice) Pro každé k e N definujeme uspořádanou k-tici (a-i, a2,..., a^) induktivně: ■ (ai) = aA ■ (^1> ■ ■ ■, 3j, a,+^) = ((ai,..., a,-), a/+i) ■ Platí (a-i,..., a/r) = (fy,..., /fy) právě když a, = £>,- pro všechna 1 < i< k. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 14/65 Kartézský součin více množin Definice (Kartézský součin více množin) Nechťk 6 N. Kartézská součin množin A-\,... ,Ak je množina A-\ x ... x Ak = {(a-i,..., a/r) | a,- e pro každé 1 < / < /c}. ■ Pro k = 2 se uvedená definice shoduje s původní definicí kartézského součinu. ■ Lze definovat i mocniny: A3 = A x A x A. m Definujeme A° = {0}. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 15/65 Potenční množina Definice (Potenční množina) Potenční množninu množiny A definujeme jako množinu všech podmnožin množiny A, t.j. V(A) = {B | B c A}. ■ Někdy se používá značení 2A místo V (A) m Příklad: V({a, b}) = {0, {a}, {b}, {a, b}} m V{%) = {0} IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 16/65 Relace IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 17/65 Relace Definice (Relace) Nechť neN. n-ární relace (nebo relace arity n nebo jen relace) R je podmnožina kartézského součinu R c AA x ... x An. m Je-li = ... = An = A, mluvíme o n-ární relaci na množině A. m Unární relace je relace arity 1 R c A, tj. podmnožina. ■ Dále se budeme zabývat jen binárními relacemi. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 18/65 Binární relace, definiční obor, obor hodnot ■ Binární relace (mezi množinami A, B) je relace R c A x B. m Definiční obor relace flC/Axfíjemnožina {a g /A | existuje b g B tak, že (a, £>) g fí}. ■ Obor hodnot relace c /A x fíje množina {b g fí | existuje a g /A tak, že (a, £>) g R}. m Alternativní notace (a, b) g fí: a/?/? nebo R(a, b) IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 19/65 Identita a inverzní relace Definice Identita na množině A je binární relace id a = {(a, ä) \ a e A} c A x A. Definice (Inverzní relace) Inverzní relací k relaci R c A x B rozumíme relaci R-1 = {(b, a) \ {a,b)eR}cBx A. m Platí 1) 1 = R. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 20/65 Skládání relací Definice (Skládání relací) Nechť RcAxBaScBxC jsou relace. Jejich složením rozumíme relaci S o R = {(a, c) | existuje b e B splňující (a, b) e R a (b, c) e S}. ■ S o R se čte jako "S po R". m Platí So R GAxC. Skládání relací je asociativní: T o (S o R) = (T o S) o IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 21/65 Vlastnosti relací Definice (Vlastnosti relací) Relace R c A x A na množine A se nazývá ■ reflexivní, pokud platí (a, a) g R pro každé a g A, ■ symetrická, pokud {a, b) g R implikuje (b, a) g R, ■ tranzitivní, pokud (a, b), (b, c) g R implikuje (a, c) g R, ■ antisymetrická, pokud (a, b), (b, a) g R implikuje a = b, ■ úplná, pokud pro každé a, b e A platí {a,b) g R nebo {b, a) g R, m univerzální, pokud pro každé a, b g A platí (a, b), (b, a) g R. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 22/65 Příklady Příklad ■ Uvažte binární relaci R na množine A = {1,2}: fl = {(1,1),(1,2),(2,1),(2,2)} ■ Jaké vlastnosti má tato relace? ■ Změní se odpověď, uvážíme-li tutéž relaci na množině A' = {1,2,3}? Příklad ■ Uvažte binární relaci inkluze (c) na množině V({a,b}). ■ Vypište všechny prvky této binární relace. ■ Jaké vlastnosti má tato relace? IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 23/65 Ekvivalence Definice (Ekvivalence) Relace R c Ax A se nazývá ekvivalence, jestliže R je reflexivní, symetrická a tranzitivní. Definice Buď R ekvivalence na A. Pro a e A položíme Ra = {b g A\ {a,b) e R}. Množinu Ra nazýváme třída relace ekvivalence R určená prvkem a. Příklad ■ Uvažte relaci R na N: (x, y) e R - x mod 4 = y mod 4. ■ Kolik existuje různých tříd ekvivalence? IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 24/65 Vlastnosti tříd ekvivalence Buď R ekvivalence na A a a e A. Pak platí: Daefía B Ra = Rb ^ (a, b)eR Q RaC\Rb^% ^ Ra = Rb Důkaz O Plyne z reflexivity. □ IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 25/65 Vlastnosti tříd ekvivalence Věta Buď R ekvivalence na A a a e A. Pak platí: Daefía B Ra = Rb ^ (a, b)eR Q RaC\Rb^% ^ Ra = Rb Důkaz B Nechť Ra = Rb. Jelikož a g Ra = Rb, platí (£>, a) g R Ze symetrie pak plyne i (a, £>) g R. Nechť (a, £>) g R. Pak pro každé c g Rb platí (£>, c) g R. Z tranzitivity plyne (a, c) g a tudíž c g fla. Tedy Rb c /?a. Ze symetrie pak plyne i fla Q Rb- IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 26/65 Vlastnosti tříd ekvivalence Buď R ekvivalence na A a a e A. Pak platí: B Ra = Rb ^ (a, b)eR Q RaC\Rb^% Ra = Rb Důkaz B Nechť Ran Rb^ 0. Pak existuje c e Rat~) Rb a proto (a, c), (£>, c) g R. Ze symetrie a tranzitivity plyne (a, £>) g R a tedy fla = flb- Implikace je zřejmá. □ IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 27/65 Rozklad Definice (Rozklad) Rozklad"R množiny A je množina 1ZQV{A) splňující m pro každé X e R platí X / 0, ■ Uxenx = A ■ pro každé X:,X2eTZ platí X^ nX2/(3 =>- X: = X2. X g TZ se nazývá třída rozkladu TI. m {A} je nejhrubší rozklad množiny A (má pouze 1 třídu). ■ {{x} | x g A} je nejjemnější rozklad. ■ Ukážeme, že rozklady přesně odpovídají relacím ekvivalence. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 28/65 Ekvivalence příslušná rozkladu Věta Nechť TZ je rozklad množiny A. Pak relace Rtz = {(a, b) | existuje X e TZ splňující a, b e X} je ekvivalence na A. m Rjz se nazývá ekvivalence příslušná rozkladu TZ. m Ekvivalence příslušná nejjemnějšímu rozkladu je identita. ■ Ekvivalence příslušná nejhrubšímu rozkladu je univerzální relace. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 29/65 Rozklad příslušný ekvivalenci Nechť R je ekvivalence na množině A^%. Pak množina A/R = {Ra \a&A} je rozkladem množiny A. ■ A/R se nazývá faktorová množina relace ekvivalence R na A. m A/R se také nazývá rozklad příslušný ekvivalenci R. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 30/65 Vztah ekvivalencí a rozkladů Věta Nechť A je neprázdná množina. ■ Je-li R ekvivalence na A, pak R = Ra/r- ■ Je-li 1Z rozklad množiny A, pak 1Z = A/Rn. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 31/65 Uspořádání Definice (Uspořádání) Relace R c Ax A se nazývá (částečné) uspořádání na A, jestliže R je reflexivní, antisymetrická a tranzitivní. Je-li relace R navíc úplná, nazývá se lineární uspořádání nebo totální uspořádání na A. ■ Uspořádání obvykle značíme <. ■ a < b je zkrácený zápis pro a < b a a ^ b. ■ Je-li a < b nebo b < a, pak řekneme, že a, b jsou srovnetelné. ■ V opačném případě jsou a, b nesrovnatelné. m Příklad uspořádání na N: a ^ b pokud a je dělitel b. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 32/65 Uspořádaná množina Definice Dvojice (A, <) se nazývá uspořádaná množina, pokud < je uspořádání na A. Dvojice (A, <) se nazývá lineárně uspořádaná množina, pokud < je lineární uspořádání na A. Příklady ■ Lineárně uspořádané množiny: (N, <), (Z, <), (Q, <), (R, <),... (< značí přirozené uspořádání na příslušném číselném oboru) ■ Uspořádaná množina {V({a, b, c}), c) ■ Uspořádaná množina (N, {(1, /'), (/', /') | / g N}) IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 33/65 Příklad Příklad ■ Uvažme množinu V({\, 2,..., 10}) s relací < definovanou pro X, / g ^({1,2,..., 10}) jako X - a = b, ■ minimální, jestliže pro všechna b e A platí b < a =>- a = £>. ■ Existuje-li v množině největší prvek, pak je jediný. Navíc je i maximální a neexistuje jiný maximální prvek. ■ Existuje-li v lineárně uspořádané množině maximální prvek, pak je to i prvek největší. ■ Analogie platí i pro nejmenší a minimální prvky. ■ Existují usp. množiny bez největšího a bez maximálního prvků? A co množiny bez největšího prvku, ale s maximálními prvky? IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 40/65 Zobrazení IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory Zobrazení Definice (Zobrazení) Zobrazení množiny A do množiny B, psáno f : A^- B je relace f c A x B taková, že pro každé a g A existuje právě jedno b g B splňující (a, b) g f. Množinu všech zobrazení z A do B značíme BA. m Místo (a, b) £ f obvykle píšeme f (a) = b, a je vzor, b obraz. Někdy se místo "právě jedno" požaduje "nejvýše jedno". Tím se definuje částečné zobrazení neboli zobrazení z A do B. Pokud pro a g A neexistuje b g B splňující (a, b) g f, říkáme, ža zobrazení f není pro a definováno a píšeme ŕ(a) = _L. ■ Chceme-li zdůraznit, že zobrazení není částečné, nazveme ho totálni. m Zobrazení se také nazývá funkce. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 42/65 Injekce a surjekce Definice (Injekce a surjekce) Zobrazení f : A^- B se nazývá ■ prosté (injektivní, injekce), jestliže f(a-\) = f(a2) =>- a-i = a2, ■ zobrazení A na množinu B (surjektivní, surjekce), jestliže pro každé b e B existuje a g A splňující f (a) = b, Příklady ■ f : N N, kde ŕ(x) = 2x je prosté, ale není surjektivní. ■ f: N {1}, kde ŕ(x) = 1 je surjektivní, ale není prosté. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 43/65 Bijekce Definice (Injekce a surjekce) Zobrazení f: A^- B se nazývá bijektivní nebo bijekce, jestliže je současně prosté i surjektivní. Množiny A, B nazveme izomorfní, jestliže existuje bijekce f : A ^ B, píšeme A = B. Příklady ■ f : {1,2,3} {3,4,5}, kde f(x) = x + 2 je bijekce. ■ Množiny N a Z jsou izomorfní. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 44/65 Poznámky ■ Pojmy definiční obor, obor hodnot zůstávají stejné jako u relací. ■ Inverzní relace k zobrazení nemusí být zobrazení. ■ Inverzní relace k bijekci je bijekce. ■ Skládání zobrazení se definuje stejně jako skládání relací. ■ Identita na A je bijekce. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 45/65 Vlastnosti bijekcí Věta Nechť f: B a g : B ->• C jsou bijekce. Platí m ŕ~1 o f = íóa afof-A = íób, m g o f je bijekce a (g o f)~A = f~A o g~A, m f o ícIa = f = ide ° f. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 46/65 Číselné obory N, Z, Q a M IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory Konstrukce přirozených čísel Definice (Přirozená čísla) Nechť 0 značí prázdnou množinu 0 i. Přirozená čísla lze definovat induktivně jako množiny: n = {0,1,2, Značíme N = {1,2,3,4,...} a cj = {0,1,2,3,...}. 0 = 0 1 = {0} 2 = {0,{0}} 3 = {0,{0},{0,{0}}} 4 = {0,{0},{0,{0}},{0,{0},{0,{0}}}} IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 48/65 Uspořádání a operace na přirozených číslech Množina odpovídající n má právě n prvků. Toho využijeme při definici uspořádání a operací. ■ uspořádání n < m <;=>- existuje injekce f: n m m sčítání n + m = k pro /c ^ ({0} x n) U ({1} x m) ■ násobení n ■ m = k pro k = (n x m) IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 49/65 Konstrukce celých čísel Definice (Celá čísla) Nechť ~ je relace na množině lo x lo definovaná následovně: (a, b) ~ (c, d) ) označíme (a, £>). ■ Třída (a, £>) reprezentuje celé číslo a-b. ■ Nezávisí na výběru reprezentanta: (a, /?) ~ (c, d) =>- a - b = c - d IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 50/65 Uspořádání a operace na celých číslech Pomocí reprezentantů definujeme uspořádání a operace nad Z: ■ uspořádání (a,b) < (c,d) a + d < b+ c ■ sčítání _ _ _ (a, b) + (c, d) = (a + c,b+ d) m násobení (a, b) ■ (c, d) = (ac + bd, ad + bc) Měli bychom dokázat, že v uvedené definice nezávisí na výběru reprezentantů, např. pro sčítání platí: IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 51/65 Konstrukce racionálních čísel Definice (Racionální čísla) Nechť ~ je relace na množině Z x (Z \ {0}) definovaná následovně: (a, b) ~ (c, d) ) označíme (a, £>). ■ Třída (a,/?) reprezentuje racionální číslo f. Nezávisí na výběru reprezentanta: (a, £>) ~ (c, d) = IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 52/65 Uspořádání a operace na racionálních číslech Pomocí reprezentantů definujeme i uspořádání a operace nad Q ■ uspořádání (a, b) < (c, d) ad < bc m sčítání _ _ _ (a, b) + (c, d) = {ad + bc, bd) ■ násobení _ _ _ (a, b) ■ (c, d) = (ac, bd) Měli bychom dokázat, že v uvedené definice nezávisí na výběru reprezentantů, např. pro sčítání platí: {ad + bc, bd) ~ (a/ď + bfcf, tíď) IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory (a,Ď)~(a',/y) 1 (c,cO~(ď,ď) / Konstrukce reálných čísel Řez v množině Q je dvojice (X, Y), kde X, Y c Q splňují: B pro všechna x g X a y g V platí x < y. Řezy v Q y'soív jednoho z následujících tří typů: m mezera: X nemá největší prvek a Y nemá nejmenší prvek m dedekindovský řez 1.druhu: X má největší prvek a Y nemá nejmenší prvek m dedekindovský řez 2.druhu: X nemá největší prvek a Y má nejmenší prvek R je množina všech řezů, které jsou mezerami nebo dedekindovskými řezy 1. druhu. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 54/65 Vlastnosti reálných čísel ■ Mezery odpovídají iracionálním číslům, dedekindovské řezy 1. druhu racionálním číslům. ■ Neexistují řezy (X, Y), kde X má největší prvek a Y nejmenší prvek. (Protože q je hustá množina.) ■ Řez (X, Y) reprezentuje nejmenší číslo r g M splňující x < r pro všechna x g X. ■ Kupříkladu -k odpovídá mezeře {{x g q | x < tt}, {x g q I x > vr}). IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 55/65 Uspořádání a operace na reálných číslech uspořádání {X, Y) < {X', ť) ^Xc X sčítání {X, Y) + {X', Y') = {X + X',Y+ Y) násobení {X, Y) ■ (X', Y') = {XX',Y ■ Y) kde X+Y = {x + y\xeX,yeY} XY = {x • y | x g X, y g Y} IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 56/65 Mohutnost IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 57/65 Mohutnost množiny Definice Jestliže existuje bijekce mezi množinami A, B (tj. A = B), pak také říkáme, že A a B mají stejnou mohutnost. Definice (Konečnost) Množina A je konečná, jestliže má stejnou mohutnost jako některá z množin n = {0,1,2,..., n - 1}, kde n g u. V opačném případě je množina nekonečná. m Mohutností množiny A rozumíme "počet prvků v množině A" a značíme \A\. m Pro konečné množiny platí \A x B\ = \A\ ■ \B\. m Množiny Z a 2Z = {2x | x g Z} mají stejnou mohutnost neboť zobrazení f -. Z 2Z dané předpisem f(x) = 2x je bijekce. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 58/65 Spočetné množiny Definice (Spočetnost) Množina, která má stejnou mohutnost jako lo se nazývá spočetná. Množina, která je konečná nebo spočetná se nazývá nejvýše spočetná. Ostatní množiny jsou nespočetné. Někdy se jako spočetná množina označuje každá množina, která má stejnou mohutnost jako libovolná podmnožina u, tedy i každá konečná množina je spočetná. Hrátky s nekonečnem: spočetný hotel. IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 59/65 Spočetné množiny Množiny N a Z jsou spočetné. Důkaz Existují bijekce í:tj-íNag:u f(x) = x+^ g(n) = \ Z dané předpisem: i? je-li /i sudé je-li n liché IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory Spočetnost racionálních čísel Věta Množina Q je spočetná. Důkaz Stačí dokázat pro kladná rac. čísla Q+ (dále dle důkazu pro Z). Reprezentujme Q+ nekonečnou tabulkou: v /-tém řádku jsou seřazeny všechny vykráčené zlomky s čitatelem /'. 2 2 2 3 5 7 3 3 3 2 4 5 Čísla seřadíme do posloupnosti po diagonálách: 1, \, 2, 1, |, 3,.... Nyní stačí číslu z u přiřadit číslo z Q+ na příslušné pozici. Tím je popsána bijekce a Q+ je spočetná. □ IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 61/65 Cantorova věta Věta (Cantorova věta) Množiny A a V (A) nikdy nemají stejnou mohutnost. Důkaz Nechť A a V (A) mají stejnou mohutnost, tj. nechť f : A ->• je bijekce. Položme B = {aeA\ a#f{a)}. Jelikož B c /A a f je bijekce, musí existovat £> g A takové, že f(b) = B. Pak platí b&B a to je spor. □ Tedy existují množiny, které jsou nespočetné: např. V(N). (Tato množina zjevně není konečná.) IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 62/65 Mohutnost reálných čísel Množina R je nespočetná. Důkaz Ukážeme, že i interval reálných čísel [0,1] je nespočetný. Předpokládáme, že existuje bijekce f: u ->•[0,1]. Následující (nekonečná) tabulka tedy obsahuje všechna čísla z [0,1]. r = 0, 6 2 5 ... Zkonstruujeme číslo r, které se bude lišit od každého čísla v tabulce (alespoň v číslici na diagonále). Jelikož r je číslo z [0,1] a není v f(0) f(2) 0, 5 1 0 0, 4 1 3 0, 8 2 4 tabulce, dostáváme spor. □ IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 63/65 Princip inkluze a exkluze Věta (Princip inkluze a exkluze) Pro libovolné konečné množiny A, B, C platí: \AUB\ = \A\ + \B\ -\AnB\ |^ueuC| = |^| + |e| + |C|-|^ne|-|enC|-|^nC| + |^nenC IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 64/65 Princip inkluze a exkluze Slouží pro praktické výpočty počtu prvků v množině či v průniku. Lze zobecnit pro libovolný počet konečných množin A,,AZ,...,A„: U a 0^/c{1,2.,...,í7} n a iel IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, číselné obory 65/65