IB112 Základy matematiky
Základy naivní teorie množin, relace, zobrazení, číselné obory
Jan Strejček
Obsah
■ Množiny
m základní operace
■ Russellův paradox
■ Relace
m 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 R
■ Mohutnost
■ spocetnost a nespocetnost
■ Cantorova veta
■ princip inkluze a exkluze
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, cí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 prvku. Zápis
■ a g A znaCí a je prvkem množiny A. ma G A znaCí a není prvkem množiny A. m 0 znaCí prázdnou množinu.
m {a, b, c} zapisuje množinu obsahující práve 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 opet množina.
Příklady množin
■ {a, b}
m {a}, {{a}}, {{{a}}}, {a, {a}, {{a}}}
■ {x | x je přirozené číslo delitelné 3}
■ N = {1, 2,3,...} - množina všech přirozených čísel
m Z = {..., -2, -1,0,1, 2,...} - množina všech celých Čísel
■ Q - množina všech racionálních Čísel
■ R - množina všech reálných císel
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
5/65
Russelluv paradox
■ Proč je uvedená definice množiny označena jako naivní?
■ Protože existují soubory prvkU, které nelze považovat za množinu. Jeden takový soubor popsal Bertrandem Russellem (1872-1970) v roce 1901.
Russelluv paradox
Množina X se nazývá normální, jestliže X g 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 g N a tedy N je normální.
V seriózní teorii množin se za množiny považují pouze soubory prvku, které vznikly z prázdné množiny pomocí sady axiomu.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory 6/65
Vztahy mezi množinami
Definice (Podmnožina)
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žine B, psáno A = B, pokud platí A c Ba B c A.
■ 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í: A u B = {x | x e A nebo x e B} m průnik: A n B = {x | x e A a x e B}
m rozdíl: A \ B = {x | x e A a x e B}
m symetrický rozdíl: A + B = (A \ B) u (B \ A)
■ Nechť A c M. Doplněk A (vzhledem k nosné množine M) je množina A = M \ A.
■ Dopinek se nazývá také komplement.
m Množiny A a B jsou disjunktní, pokud A n B = 0. V opaCném případe 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
A u B = B u A
■ asociativní      A n (B n C) = (A n B) n C
A u (B u C) = (A u B) u C
■ idempotentní      A n A = A
AuA=A
Dále platí distributivní zákony
A u (B n C) = (A u B) n (A u C) A n (B u C) = (A n B) u (A n C)
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, Číselné obory 9/65
Vlastnosti množinových operací
U doplnku velmi záleží na nosné množine M:
■ A = {a}, M = {a}: A = 0
■ A = {a}, M = {a, b}: A = {b}
m A = {a}, M = {a, b, c}: A = {b, c}
Pro doplněk dále platí
■ A = A
m De Morganovy zákony      A n B = A u B
A u B = A n B
De Morganovy zákony lze dále zobecnit
A n (B n C) = (A n B) u (A n C) A n (B u C) = (A n B) n (A n C)
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, Číselné obory
10/65
Zobecnění průniku a sjednocení
Definice (Zobecnený průnik a sjednocení)
Necht Ai je množina pro každé i e I = 0. Definujeme
P| Ai =  {x I x e Ai pro každé i e I}
i el
[jAi =  {x I x e Ai pro nejaké i e I}.
i el
m Príklad: U€n{2í} = {2,4,6,...}
■ Dále se definůje (jie0 Ai = 0.
■ Je-li dána nosná množina M, lze definovat i f|/e0 Ai = M.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
11/65
Uspořádaná dvojice
Definice (Uspořádaná dvojice)
Uspořádanou dvojici (a, b) definujeme jako množinu {{a}, {a, b}}.
■ Platí (a, b) = (c, d) práve 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í, císelné obory 12/65
Kartézský soůcin
Definice (Kartézský soůcin)
Kartézský soudn množin A, B je množina
A x B = {(a, b) I a e A, b e B}.
Príklad: {a, b} x {c, d} = {(a, c), (a, d), (b, c), (b, d)} Pro každoů množinu A platí 0 x A = A x 0 = 0. Obecne neplatí A x B = B x A (komůtativita). Obecne neplatí A x (B x C) = (A x B) x C (asociativita).
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
13/65
Uspořádaná k-tice
Definice (Usporádaná k-tice)
Pro každé k e N definujeme uspořádanou k-tici (a1, a2,..., ak) induktívne:
■ (aO = a1
■ (a1,..., ai, ai+1) = ((a1,..., ai), ai+1)
■ Platí (a1,..., ak) = (b1,..., bk) práve když ai = bi pro všechna 1 < i < k.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
14/65
Kartézský součin více množin
Definice (Kartézský soucin více množin)
Necht k g N. Kartézská součin množin A1,..., Akje množina A1 x ... x Ak = {(a1,..., ak) | ai g Ai pro každé 1 < i < k}.
■ Pro k = 2 se uvedená definice shoduje s puvodní definicí kartézského soucinu.
■ Lze definovat i mocniny: A3 = A x A x A.
■ Definujeme A0 = {0}.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, cí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.
P (A) = {B | B c A}.
Nekdy se používá značení 2A místo P (A) Príklad: P ({a, b}) = {0, {a}, {b}, {a, b}} P(0) = {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í, císelné obory
17/65
Relace
Definice (Relace)
Necht n e N. n-ární relace (nebo relace arity n nebo jen relace) R je podmnožina kartézského součinu
R c A1 x ... x An.
m Je-li A1 = ... = An = A, mluvíme o n-ární relaci na množine 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í, cí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.
■ Definiční obor relace R c A x B jemnožina
{a e A | existuje b e B tak, že (a, b) e R}.
m Obor hodnot relace R c A x B je množina
{b e B | existuje a e A tak, že (a, b) e R}.
■ Alternativní notace (a, b) e R: aRb nebo R (a, b)
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
19/65
Identita a inverzní relace
Definice
Identita na množine A je binární relace
idA = {(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) e R} c B x A.
m Platí (R-1)-1 = R.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory 20/65
Skládání relací
Definice (Skládání relací)
Necht R c A x B aS c B x C 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}.
m S o R se čte jako "S po R".
■ Platí S o R c A x C.
■ Skládání relací je asociativní: T o (S o R) = (T o S) o R
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, cí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) e R pro každé a e A,
■ symetrická, pokud (a, b) e R implikuje (b, a) e R,
m tranzitivní, pokud (a, b), (b, c) e R implikuje (a, c) e R, m antisymetrická, pokud (a, b), (b, a) e R implikuje a = b,
m úplná, pokud pro každé a, b e A platí (a, b) e R nebo
(b, a) e R,
m univerzální, pokud pro každé a, b e A platí (a, b), (b, a) e R.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
22/65
Príklady
Příklad
■ Uvažte binární relaci R na množine A = {1, 2}:
R = {(1,1), (1,2), (2,1), (2,2)}
■ Jaké vlastnosti má tato relace?
■ Zmení se odpoved', uvážíme-li tutéž relaci na množine A1 = {1,2,3}?
Příklad
■ Uvažte binární relaci inkluze (c) na množine P ({a, b}). m 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í, ccíselné obory
23/65
Ekvivalence
Definice (Ekvivalence)
Relace R c A x A se nazývá ekvivalence, jestliže R je reflexivní, symetrická a tranzitivní.
Definice
Bud' R ekvivalence na A. Pro a e A položíme
Ra = {b e A I (a, b) e R}. Množinu Ra nazýváme tčída relace
ekvivalence R urccená prvkem a.
Příklad
■ Uvažte relaci R na N: (x, y) e R       x mod 4 = y mod 4.
■ Kolik existůje různých tříd ekvivalence?
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
24/65
Vlastnosti tríd ekvivalence
Veta
Buď R ekvivalence na A a a e A. Pak platí: ľl a e Ra
12 Ra = Rb <^=> (a, b) e R
13 Ra n Rb = 0        Ra = Rb
Důkaz
jl Plyne z reflexivity.
□
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
25/65
Vlastnosti tríd ekvivalence
Bud' R ekvivalence naAaa e A. Pak platí:
11 a e Ra
12 Ra = Rb <=> (a, b) e R
|s| Ra n Rb = 0 <=> Ra = Rb
Důkaz
^ Nechť Ra = Rb. Jelikož a e Ra = Rb, platí (b, a) e R. Ze symetrie pak plyne i (a, b) e R.
Necht (a, b) e R. Pak pro každé c e Rb platí (b, c) e R. Z tranzitivity plyne (a, c) e R a tudíž c e Ra. Tedy Rb c Ra. Ze symetrie R pak plyne i Ra c Rb.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
26/65
Vlastnosti tríd ekvivalence
Veřta
Bud' R ekvivalence naAaa e A. Pak platí:
11 a e Ra
12 Ra = Rb <=> (a, b) e R
|s| Ra n Rb = 0 <=> Ra = Rb
Důkaz
^ Necht Ra n Rb = 0. Pak existuje c e Ra n Rb a proto
(a, c), (b, c) e R. Ze symetrie a tranzitivity plyne (a, b) e R a
tedy Ra = Rb.
Implikace "<=" je zřejmá.
□
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
27/65
Rozklad
Definice (Rozklad)
Rozklad R množiny A je množina Rcp (A) splnující m pro každé X e R platí X = 0,
Ux GRX = A m pro každé X1, X2 e R platí X1 n X2 = 0       X1 = X2.
X e R se nazývá tčída rozkladu R.
m {A} je nejhrubší rozklad množiny A (má pouze 1 trídu).
■ {{x} I x e A} je nejjemnejší rozklad.
■ Ukážeme, že rozklady presne odpovídají relacím ekvivalence.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, ccíselné obory
28/65
Ekvivalence príslušná rozkladu
Veta
Necht R je rozklaď množiny A. Pak relace
RR = {(a, b) | existuje X e R splnujícía, b e X} je ekvivalence na A.
m RR se nazývá ekvivalence příslušná rozkladu R.
m Ekvivalence příslušná nejjemnejší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í, císelné obory
29/65
Rozklad príslušný ekvivalenci
veta
Necht R je ekvivalence na množine A =   Pak množina
A/R = {Ra | a e A} je rozkladem množinyA.
m A/R se nazývá faktorová množina relace ekvivalence R na A. ■ A/R se také nazývá rozklad příslušný ekvivalenci R.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
30/65
Vztah ekvivalencí a rozkladu
Veřta	
Necht A je neprázdná množina.	
■ Je-li R ekvivalence na A, pak R =	RA/R.
■ Je-li R rozklad množiny A, pak R	= A/Rn.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
31/65
Uspořádání
Definice (Uspořádání)
Relace R c A x A se nazývá (CásteCné) 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 znacíme <.
■ a < b je zkrácený zápis pro a < b a a = b.
■ Je-li a < b nebo b < a, pak rekneme, že a, b jsou srovnetelné.
■ V opacném případe jsou a, b nesrovnatelné.
■ Příklad uspořádání na N: a ^ b pokud a je delitel b.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, cí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árne uspočádaná množina, pokud < je lineární uspořádání na A.
Příklady
■ Lineárne uspořádané množiny: (N, <), (Z, <), (Q, <), (R, <),... (< znací prirozené usporádání na příslušném císelném oboru)
■ Usporádaná množina (P({a, b, c}), c)
■ Usporádaná množina (N, {(1, i), (i, i) | i e N})
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
33/65
Príklad
Příklad
■ Uvažme množinu P({1, 2,..., 10}) s relací ^ definovanou pro X, Y e P({1,2,..., 10}) jako
X ^ Y pokud X má nejvýše tolik prvku jako Y.
■ Je (P({1,2,..., 10}), ^) uspořádaná množina?
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
34/65
Hasseův diagram
■ Grafická reprezentace konecných usporádaných množin.
■ Použil Henry Gustav Vogt v roce 1895, zpopularizoval Helmut Hasse (1898-1979)
Hasseuv diagram reprezentující uspořádanou množinu (A, <) je graf, kde
■ vrcholy jsou prvky A
■ z a vede hrana nahoru do b, pokud a < b, a = b a neexistuje c splnující a < c < b.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
35/65
Hasseův diagram: příklady
Potencřní množina množiny {a, b, c} s relací inkluze (podmnožina), t.j. (P({a, b, c}), c).
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
36/65
Hasseův diagram: příklady
Potencřní množina množiny {a, b, c} s relací inkl ze (podmnožina), t.j. (P({a, b, c}), c).
{a, b, c}
{a, b}
{b, c} {a, c}
{c}
0
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
37/65
Hasseův diagram: příklady
Množina všech delitelu císla 60 uspořádaných relací delitelnost.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory 38/65
Hasseův diagram: příklady
Množina všech dělitelů čísla 60 uspořádaných relací dělitelnost.
30
60
20
15 ^^^10 6
12
3
4
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
39/65
Nejvetší, nejmenší, maximální a minimální prvek
Definice
Necht (A, <) je uspořádané množina. Prvek a e A je
■ nejvetší, jestliže pro všechna b e A platí b < a,
■ nejmenší, jestliže pro všechna b e A platí a < b,
■ maximální, jestliže pro všechna b e A platí a < b => a = b,
■ minimální, jestliže pro všechna b e A platí b < a => a = b.
■ Existuje-li v množine nejvetší prvek, pak je jediný. Navíc je i maximální a neexistuje jiný maximální prvek.
■ Existuje-li v lineárne uspořádané množine maximální prvek, pak je to i prvek nejveřtší.
■ Analogie platí i pro nejmenší a minimální prvky.
■ Existují usp. množiny bez nejvetšího a bez maximálního prvku? A co množiny bez nejvetšího prvku, ale s maximálními prvky?
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory 40/65
Zobrazení
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
41/65
Zobrazení
Definice (Zobrazení)
Zobrazení množiny A ďo množiny B, psáno f: A — B je relace f c A x B taková, že pro kažďé a e A existuje práve jeďno b e B splnující (a, b) e f.
Množinu všech zobrazení z Aďo B znaccíme BA.
m Místo (a, b) e f obvykle píšeme f (a) = b, a je vzor, b obraz.
m Nekdy se místo "práve jedno" požaduje "nejvýše jedno". Tím se definuje ccásteccné zobrazení neboli zobrazení z A do B. Pokud pro a e A neexistuje b e B splnující (a, b) e f, ríkáme, ža zobrazení f není pro a definováno a píšeme f (a) = ±.
m Chceme-li zduraznit, že zobrazení není cástecné, nazveme ho totální.
m Zobrazení se také nazývá funkce.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory 42/65
Injekce a surjekce
Definice (Injekce a surjekce)
Zobrazení f: A — B se nazývá
■ prosté (injektivní, injekce), jestliže f(a1) = f(a2) => a1 = a2,
■ zobrazení A na množinu B (surjektivní, surjekce), jestliže pro každé b e B existuje a e A splnující f (a) = b,
Příklady
■ f: N — N, kde f (x) = 2x je prosté, ale není surjektivní.
■ f: N — {1}, kde f(x) = 1 je surjektivní, ale není prosté.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
43/65
Bijekce
Definice (Injekce a sůrjekce)
Zobrazení f: A — B se nazývá bijektivní nebo bijekce, jestliže je soucasne 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 jsoů izomorfní.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
44/65
Poznámky
■ Pojmy definicní obor, obor hodnot zustá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 stejne jako skládání relací.
■ Identita na A je bijekce.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
45/65
Vlastnosti bijekcí
veta
Necht f: A — Bag : B — C jsou bijekce. Platí m f-1 o f = idA a f o f-1 = idB, m (f-1)-1 = f,
m g o f je bijekce a (g o f)-1 = g-1 o f-1, m f o idA = f = idB o f.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
46/65
Číselné obory N, Z, Q a R
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
47/65
Konstrukce prirozených císel
Definice (Prirozená císla)
Necht 0 znacíprázdnou množinu 0. Přirozená císla lze definovat induktivne jako množiny:
n = {0,1,2,..., n - 1}
Znacíme N = {1, 2,3,4,...} a w = {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í, císelné obory
48/65
Uspořádání a operace na přirozených císlech
Množina odpovídající n má práve n prvku. Toho využijeme při definici usporádání a operací.
■ uspočádání
n < m       existuje injekce f: n — m
m scítání
n + m = k pro k ^ ({0} x n) u ({1} x m)
m násobení
n • m = k pro k = (n x m)
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
49/65
Konstrukce celých císel
Definice (Celá ccísla)
Necht ~ je relace na množine u x u definovaná následovne:
(a, b) ~ (c, d)       a + d = c + b
Relace ~ je ekvivalence. Z je rozklad (u x u)/ ~, tedy celé císlo je třída rozkladu (u x u)/ ~.
m Trídu ekvivalence obsahující (a, b) oznacíme (a, b). m Trída (a, b) reprezentuje celé císlo a - b.
m Nezavisí na výberu reprezentanta:
(a, b) ~ (c, d) => a - b = c - d
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
50/65
Uspořádání a operace na celých císlech
Pomocí reprezentantu definujeme uspořádání a operace nad Z:
■ uspořádání
(a, b) < (c, d)       a + d < b + c
m scítání
(a, b) + (c, d) = (a + c, b + d)
■ násobení
(a, b) • (c, d) = (ac + bd, ad + bc)
Meli bychom dokázat, že v uvedené definice nezávisí na výberu reprezentantu, např. pro scítání platí:
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
51/65
Konstrukce racionálních císel
Definice (Racionální císla)
Necht ~ je relace na množine Z x (Z \ {0}) definovaná následovne:
(a, b) ~ (c, d)       ad = cb
Relace ~ je ekvivalence. Q je rozklad (Z x (Z \ {0}))/ ~, tedy racionálnícíslo je trída rozkladu (Z x (Z \ {0}))/ ~.
■ Trídu ekvivalence obsahující (a, b) oznacíme (a, b).
■ Trída (a, b) reprezentuje racionální císlo ^.
■ Nezavisí na výberu reprezentanta: (a, b) ~ (c, d) => ^ = d
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory 52/65
Uspořádání a operace na racionálních císlech
Pomocí reprezentantu definujeme i usporádání a operace nad Q: ■ uspočádání
(a, b) < (c, d)       ad < bc
scítání
(a, b) + (c, d) = (ad + bc, bd)
■ násobení
(a, b) • (c, d) = (ac, bd)
Meli bychom dokázat, že v uvedené definice nezávisí na výberu reprezentantu, např. pro scítání platí:
(Í ď) ~ [d, V)} (ad + bc, bd) - (a ď + b c', b ď)
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
53/65
Konstrůkce reálných císel
Definice
Řez v množine Q je dvojice (X, Y), kde X, Y c Q spinují: □ x n Y = 0
B X U Y = Q
13 pro všechna x e X a y e Y platí x < y.
Řezy v Q jsou jednoho z následujících tcí typu:
m mezera: X nemá nejvetšíprvek a Y nemá nejmenšíprvek
m dedekindovský rez l.druhu: X má nejvetší prvek a Y nemá nejmenší prvek
m dedekindovský Cez 2.druhu: X nemá nejvetší prvek a Y má nejmenší prvek
R je množina všech crezuu, které jsou mezerami nebo dedekindovskými Cezy 1. druhu.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
54/65
Vlastnosti reálných císel
■ Mezery odpovídají iracionálním císlum, dedekindovské rezy 1. druhu racionálním císlum.
■ Neexistují rezy (X, Y), kde X má nejvetší prvek a Y nejmenší prvek. (Protože Q je hustá množina.)
■ Rez (X, Y) reprezentuje nejmenší císlo r e R splnující x < r pro všechna x e X.
■ Kupříkladu n odpovídá mezeře
({x e Q I x < n}, {x e Q | x > n}).
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
55/65
Uspořádání a operace na reálných císlech
usporcádání
(X, Y) < (X1, Y') <=> X c X1
sccítání
(X, Y) + (X, Y') = (X + X', Y + Y')
násobení
(X, Y) • (X1, Y') = (X • X', Y • Y')
kde
X + Y = {x + y | x e X, y e Y} X • Y = {x • y I x e X, y e Y}
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
56/65
Mohutnost
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
57/65
Mohutnost množiny
Definice
Jestliže existuje bijekce mezi množinami A, B (tj. A = B), pak také ríkámé, že A a B mají stejnou mohutnost.
Definice (Konecnost)
Množina A je konecná, jestliže má stejnou mohutnost jako nekterá z množin n = {0,1, 2,..., n - 1}, kde n e w. V opacném prípade je množina nekonečná.
■ Mohutností množiny A rozumíme "pocet prvku v množine A" a znacíme |A|.
■ Pro konecné množiny platí |A x B| = |A| • |B|.
■ Množiny Z a 2Z = {2x | x e 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í, císelné obory
58/65
Spocetné množiny
Definice (Spocetnost)
Množina, která má stejnou mohutnost jako uu se nazývá spocetná. Množina, která je konecná nebo spocetná se nazývá nejvýše spocetná. Ostatní množiny jsou nespocetné.
Neřkdy se jako spocřetná množina oznacřuje každá množina, která má stejnou mohutnost jako libovolná podmnožina u, tedy i každá konecřná množina je spocřetná.
Hrátky s nekonecnem: spocetný hotel.
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
59/65
Spocetné množiny
MnožinyN a Z jsou spoccetné. Důkaz
Existůjí bijekce f: u — N a g : u — Z dané předpisem:
í    2      je-li n sůdé
f(x) =x +1       g(n) = \     2 |í
-■n+1    je-li n liché
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
□
60/65
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 i-tém řádku jsou seřazeny všečhny vykráčené zlomky s čitatelem i.
I 1   i  i i
1 2    3    4    • • '
2 2    2 2
2 3    5    7    ^ ^ ^
3 3 3 3 3    2    4 5
Čísla seřadíme do posloupnosti po diagonáláčh: 1, ^, 2, 3,2, 3,.... Nyní stačí číslu z w přiřadit číslo z Q+ na príslušné poziči. Tím je popsána bijekče a Q+ je spočetná. □
IB112 Základy matematiky: Základy naivní teorie množin, relače, zobrazení, číselné obory 61/65
Cantorova veta
veta (Cantorova veta)
Množiny A a P (A) nikdy nemají stejnou mohutnost.
Důkaz
Nechť A a P (A) mají stejnou mohutnost, tj. nechť f: A — P (A) je bijekce. Položme
B = {a e A | a e f (a)}.
Jelikož B c A a f je bijekce, musí existovat b e A takové, že f(b) = B. Pak platí
b e B       b e B
a to je spor.
Tedy existují množiny, které jsou nespocetné: napr. P (N). (Tato množina zjevner není konecrná.)
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
62/65
Mohutnost reálných cřísel
veta
Množina R je nespočetná. Důkaz
Ukážeme, že i interval reálných císel [0,1] je nespocetný. Predpokládáme, že existuje bijekce f: u —[0,1]. Následující (nekonecná) tabulka tedy obsahuje všechna císla z [0,1].
f(0) = 0, 5 10 ... f(1) = 0, 4 13 ... f(2)  = 0,  8 2 4 ...
~    =  0,  6  2  5 ...
Zkonstruujeme císlo r, které se bude lišit od každého císla v tabulce (alespon v císlici na diagonále). Jelikož r je císlo z [0,1] a není v tabulce, dostáváme spor. □
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory 63/65
Princip inkluze a exkluze
Veřta (Princip inkluze a exkluze)
Pro libovolné konecné množiny A, B, C platí:
\Au BI = \A\ + \B\ — \An BI IA u B u C \ = \ A\ + \ B\ + \ C \ — \A n B\ — \B n C \ — \A n C \ + \A n B n C\
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
64/65
Princip inkluze a exkluze
Slouží pro praktické výpocty poctu prvku v množine ci v pnůniku. Lze zobecnit pro libovolný pocet konecných množin
A1, A2, ■ ■ ■, An:
U Ai
i =1
E (-D'""1
0=/c{1,2.,...,n}
Ai
ie/
IB112 Základy matematiky: Základy naivní teorie množin, relace, zobrazení, císelné obory
65/65