Množiny, relace, zobrazení
Množiny
Množinou rozumíme každý soubor určitých objektů shrnutých v jeden celek. Zmíněné objekty pak nazýváme prvky dané množiny. Pojem „množina" je tedy synonymem pojmů typu „soubor", „souhrn", apod.
Je-li objekt x prvkem množiny A, píšeme x G A, není-li tomu tak, píšeme x ^ A.
Množina je tedy plně určena svými prvky. To znamená, že dvě množiny A, B považujeme za stejné, právě když jsou tvořeny stejnými prvky. Jinak řečeno, klademe A = B právě když pro každý objekt x platí, že a: je prvkem A tehdy a jen tehdy, když a? je prvkem B. Zapsáno formulí, máme
A = B   <^>   (Vx)(x G A <^>  x G B).
Řekneme, že množina A je podmnožinou množiny £>, jestliže každý prvek množiny A je prvkem množiny B. Pak píšeme A C B a, mluvíme o inkluzi množin. Podrobněji řečeno, klademe A C B právě když pro každý objekt x platí, že je-li x prvkem A, pak x je také prvkem B. Zapsáno formulí, máme tedy
AC B   ^^   {\Jx){x G A => x G B).
To také znamená, že máme
A = B   ^^   (AC B k B C A).
Je jasné, že pak pro libovolné množiny A, B, C platí
(ACB k BCC)  ^ ACC.
Poznamenejme ještě, že místo A C B se někdy píše také B 13 A, a platí-li současně A C B a A ^ B, bývá to krátce zapisováno ve tvaru A c B.
1
Význačnou množinou je prázdná množina, tedy množina, která neobsahuje žádný prvek. Značíme ji 0. V této souvislosti dodejme, že pro libovolnou množinu A máme
AC A       a       icA
Množina A se nazývá konečná, obsahuje-li pouze konečně mnoho různých prvků; v opačném případě je A nekonečná množina.
Pro libovolné dvě množiny A, B definujeme jejich sjednocení AU B jako množinu, která je tvořena těmi prvky, které jsou prvky buď množiny A nebo množiny £>, tedy těmi prvky, které jsou prvky alespoň jedné z množin A, B. To znamená, že klademe
AU B = {x\ x G A V x G B}.
Dále definujeme průnik A n B těchto množin jako množinu, která je tvořena těmi prvky, které jsou současně prvky množiny A i množiny B. To znamená, že klademe
Ar\B = {x\ x e A k x e B}.
Říkáme, že množiny A, B jsou disjunktní, je-li A n B = 0. Konečně definujeme rozdíl A — B množin A, B jako množinu těch prvků množiny A, které nejsou prvky množiny B. To znamená, že klademe
A - B = {x\ x e A k x £ B}.
Platí řada množinových rovností, z nichž pozornost zasluhují zejména následující.
Tvrzení.   Pro libovolné množiny A,B,C platí
AUB = BUA
(komutativita) AHB = BnA                              v                      J
2
{AUB)UC = Au{BUC)
(AnB)nC = An(BnC)                   (asociativita)
AuA = A
(idempotence)
AC\A = A                                    v                    '
AU (B n C) = (AU B) n (AU C)
v          !     v          y     v          y         (distributivita)
An {BuC) = {AnB) u {AnC)       v                7
de Morganova pravidla
A-{BUC) = {A-B)n{A-C)     V                        7
Důkaz. Komutativita, asociativita a idempotence jsou zřejmé. Také ověření zbývajících rovností je snadné. Dokážeme například první z de Morganových pravidel. Ověříme následující dvě inkluze:
A - {B n C) C {A - B) U {A - C): Nechť x G A - {B n C). Pak x G A & x £ B n C. Pak tedy x G A & (x <£ B V x £ C). Pak (x e A & x £ B) V (x e A & x £ C). Pak ovšem x G A-£ V a: G A-C. Takže a: G (A-ß)U(A-C).
{A-B)U{A-C)CA-{Bn C): Nechť z G {A - B) U {A - C). Pak x G A - B V z G A - C. Pak tedy (x e A & x £ B) V (x e A & x £ C). To znamená, žerrGA&f^^BVrr^C). Takže pak x e A & x (£ B n C. Tedy xGA-(ßn(7).
Důkazy ostatních rovností jsou obdobné.
Někdy se nacházíme v situaci, že všechny uvažované množiny jsou podmnožinami nějaké základní množiny M. Pak pro libovolnou množinu ACM množinu M — A značíme krátce A' a nazýváme ji doplněk množiny A v množině M. Všimněme si, že pak pro libovolnou množinu ACM platí například
AUÄ = M,    AnÄ = $   a   A" = A.
3
Relace
Základní konstrukční jednotkou při tvorbě kartézských součinů množin a relací mezi množinami je pojem uspořádané dvojice prvků. Intuitivně mu rozumíme tak, že každým dvěma prvkům a, b přiřadíme nový objekt (a, b), nazývaný uspořádanou dvojicí, v němž záleží na pořadí prvků a, b. Obecněji pro každé k > 2 lze zavést představu uspořádané k-tice prvků tak, že každým k prvkům a\,..., a^ přiřadíme nový objekt (<2i,..., a^), jejich uspořádanou /c-tici, s vyznačeným pořadím těchto prvků.
Pro libovolné dvě množiny A, B definujeme jejich kartézský součin A x B jako množinu, jejímiž prvky jsou právě všechny uspořádané dvojice (a, 6), kde a G A, b G B. To znamená, že klademe
Ax B = {{a,b)\ aeA k be B}.
Je-li A = B, nazýváme množinu A x A kartézským čtvercem množiny A a značíme ji A2. Z uvedené definice je jasné, že množiny A x B a, B x A jsou obecně různé. Dále pro libovolné množiny A,B,C také množiny
{AxB) xC = {{{a,b),c)\ aeA&beB&ceC}, Ax (B x C) = {{a,{b,c))\ a G A & be B & c e C}
jsou formálně různé. Nicméně rozdíl mezi objekty ((a,6),c) a (a, (6, c)) se často přehlíží — obojí lze vnímat jako uspořádanou trojici — a lze tedy mluvit prostě jen o kartézském součinu A x B x C. Takže máme
A x B x C = {(a, 6, c) | a G A & be B & c e C}.
Podobně pro každé k > 2 a libovolné množiny A\,..., Ak definujeme jejich kartézský součin A\ x • • • x Ak jako množinu
Ai x ■ ■ ■ x Ak = {(ah ..., ak) | «i G Ax &   ...  & ak G Ak}.
4
Jestliže Ai = • • • = Ak = A, dostáváme tak definici kartézské mocniny Ak pro všechna k > 2. Navíc klademe také A1 = A.
Platí řada jednoduchých rovností:
Tvrzení.   Pro libovolné množiny A, B, C platí:
(AuB)xC=(AxC)U(Bx C), (AnB)xC=(AxC)n(Bx C), {A- B) x C = {Ax C) - {B x C).
Analogické rovnosti platí i pro C x (A U B), C x [An B) a
C x {A-B).
Důkaz všech rovností je snadný.
Nechť A, B jsou libovolné množiny. Pak libovolná podmnožina g kartézského součinu A x B se nazývá relace mezi množinami A a B. Jsou-li a G A, b G B takové prvky, že (a, b) G g, pak říkáme, že prvek a je v relaci g s prvkem b, a zapisujeme to zpravidla ve tvaru a gb. Jestliže (a, b) ^ g, píšeme obvykle a$b.
Nechť A, B jsou opět libovolné množiny. Pak 0 C A x B, takže 0 je relace mezi množinami A a B a nazývá se prázdná relace mezi A a B. Rovněž celá množina A x B je relací mezi množinami A a B a nazývá se univerzální relace mezi A a B. Nechť dále g C A x B je libovolná relace mezi A a B. Pak definičním oborem Dom g relace g rozumíme množinu
Doni£ = {a G A\ (3b G B)(agb)},
tedy množinu všech těch prvků z A, které jsou v relaci g alespoň s jedním prvkem z B, a oborem hodnot Im g relace g rozumíme množinu
Im g = {b G B | (3a e A)(agb)},
tedy množinu všech těch prvků z B, s nimiž je v relaci g alespoň jeden prvek z A.
5
Definujeme skládání relací. Nechť A, B, C jsou množiny a nechť gCAxBa,r]C B x C jsou relace. V této situaci definujeme relaci 77 o g C A x C vzniklou složením relací g a 77 následujícím způsobem:
77 o g = {(a, c) G A x C | (3b G B)(agb k br]c)}.
Zápis r] o g čteme „77 po g ". Skládání relací je asociativní:
Tvrzení. Nechť A,B,C,D jsou množiny a nechť ^Cylxi], T]CBxC,fiCCxD jsou relace. Pak platí:
(fl o 77) o £ = fj, o (77 o g).
Důkaz. Na obou stranách této rovnosti jsou relace mezi množinami A a D. Dokážeme inkluzi (/i o 77) o g C /j, o (77 o g). Nechť tedy a G A, d G D jsou takové prvky, že (a,d) G (ß°r])og. Pak podle definice skládání relací existuje prvek b e B takový, že (a, b) G g a (6, ď) G fi o 77. Opět podle téže definice existuje prvek c G C takový, že (b, c) G 77 a (c, d) G /i. Pak ovšem (a, c) G 77 o g^ takže (a, ď) G fi o (77 o £>). Opačná inkluze /i o (77 o g) C (/i o 77) o g se dokáže analogicky.
Ke každé relaci g mezi množinami A a, B definujeme inverzní relaci g~l mezi množinami B a, A následovně:
Q~l = {(b,o) <E B x A\ a g b}.
To znamená, že platí
(VaeA)(VbeB)(agb <^>  bg~la).
Odtud okamžitě plyne, že Dom g~l = Im g, Im g~l = Dom g. Dále je jasné, že platí
6
Navíc mezi skládáním relací a inverzními relacemi existuje následující souvislost:
Tvrzení. Nechť A,B,C jsou množiny a nechť g C A x B, r] C B x C jsou relace. Pak platí:
(ľ] o g)~ľ = g~l o r]~l.
Důkaz. Na obou stranách této rovnosti jsou relace mezi množinami C a A. Dokážeme inkluzi (77 o g)~ľ C g~l o t?-1. Nechť a G A, c G C jsou takové prvky, že (c, a) G (77 o £>)_1. Pak (a, c) G 77 o 0. To znamená, že existuje prvek b G B takový, že (a, b) G 0 a (6, c) G 77. Odtud plyne, že (b, a) G £_1 a (c, 6) G 77-1, takže pak (c, a) G g~lor)~l. Opačná inkluze ^_1o77_1 C (r]og)~l se dokáže obdobně obráceným postupem.
Zobrazení
Pojem „zobrazení" nejprve vymezíme následovně. Nechť A, B jsou libovolné množiny. Zobrazením / : A —>■ B množiny A do množiny B rozumíme předpis, který každému prvku a G A přiřazuje právě jeden prvek b G B. Pro takové prvky pak píšeme, že b = f (a), a říkáme, že b je obrazem prvku a při zobrazení /.
Uvedené vymezení daného pojmu ovšem obsahuje blíže nespecifikovaný pojem „předpis". Bylo by vhodné umět se bez tohoto prostředku obejít. Proto uvažujme k danému zobrazení / : A —>■ B relaci g C A x B definovanou formulí
{\/a^A){\/b^B){agb ^^  b = f(a))
a nazývanou graf zobrazení /. Všimněme si, že pak relace g splňuje podmínku
Dom g = A,
7
neboť zobrazení / každému prvku z A přiřazuje nějaký obraz, a dále podmínku
(Vae A)(Vb,b'e B)(agb k agb' =>  b = b'),
neboť zobrazení / každému prvku z A přiřazuje jediný obraz. Přitom relace g zobrazení / kompletně určuje, neboť g je vlastně výčtem všech uspořádaných dvojic (a, b) e A x B takových, že b = f (a).
Na druhé straně libovolnou relaci g C A x B splňující výše uvedené dvě podmínky je možno chápat tímtéž způsobem jako popis určitého zobrazení /, které je pak možno zadat předpisem
(Vae A)(V6g B)(b = f(á)  ^^ agb),
neboť ze zmíněných podmínek plyne, že pak každý prvek z A má svůj obraz a že tento obraz je jediný.
Chceme-li tedy podat definici pojmu „zobrazení" jenom s pomocí pojmů zavedených v teorii množin, nabízí se možnost přímo ztotožnit zobrazení / s jeho grafem g, tak jak byl popsán výše. Takto dostáváme následující množinovou definici daného pojmu:
Nechť A, B jsou libovolné množiny a nechť / C A x B je relace mezi nimi. Řekneme, že / je zobrazení množiny A do množiny B a píšeme / : A —>■ B, jestliže jsou splněny podmínky
Dom f = A
a dále
(VaeA)(Vb,b'eB)(afb&;afb' =>  b = b').
V tom případě, jak bylo uvedeno shora, místo zápisu afb, případně (a, b) G /, zpravidla píšeme b = f (a).
Nechť A, B jsou množiny. Zobrazení / : A —>■ B se nazývá surjekce, nebo též zobrazení na množinu B, platí-li
Imf = B.
8
Při takovém zobrazení / každý prvek b G B má alespoň jeden vzor, tedy prvek a G A takový, že b = f (a).
Zobrazení / : A —>■ B se nazývá injekce, nebo též prosté zobrazení, splňuje-li podmínku
(V6g B)(Va,a'e A)(afb & a'f b => a = ď).
Při takovém zobrazení / každý prvek b G B má nanejvýš jeden vzor, tedy prvek a G A takový, že b = f (a).
Zobrazení / : A —>■ B se nazývá bijekce, nebo též vzájemně jednoznačné zobrazení množiny A na množinu B, j e-li / současně injekce i surjekce.
Nechť A, B jsou množiny a nechť / : A —>■ £> je bijekce. Pak inverzní relace /_1 k relaci / je zase zobrazení. To ihned plyne z předchozích podmínek, neboť požadavky, aby / byla surjekce a injekce, přesně odpovídají podmínkám, které je třeba splnit, aby f~l bylo zobrazení. Máme tedy zobrazení f~l : B —>■ A, které samo je rovněž bijekce, neboť zase požadavky nutné k tomu, aby / bylo zobrazení, znamenají, že f~l je surjekce a injekce. Říkáme, že f~l je inverzní zobrazení k zobrazení /.
Definujeme skládání zobrazení. Poněvadž zobrazení jsou speciální typy relací, definujeme toto skládání stejným způsobem jako skládání relací. Je ale zřejmé, že jsou-li A, B, C množiny a jsou-li / : A —>■ B a g : B —>■ C zobrazení, pak jejich složením dostaneme relaci g o /', která je opět zobrazením g o / : A —>■ C. Přitom toto zobrazení je očividně dáno předpisem
(VaeA)((gof)(a)=g(f(a))).
Připomeňme, že skládání relací, a tedy i skládání zobrazení je asociativní.
Definujme pro libovolnou množinu A zobrazení íÚa '• A —>■ A předpisem
(Va G A)(idA(a) = a).
9
Toto zobrazení se nazývá identita na A. Je jasné, že pak pro libovolné množiny A, B a, pro libovolné zobrazení / : A —>■ B platí
foidA = f = idBo f,
a je-li / navíc bijekce, pak platí také
/_1° / = MA,   f ° f'1 = idB. Důležitý je následující fakt.
Věta.   Nechť A, B jsou množiny a nechť /: A-.B,   g: B-> A
jsou zobrazení. Pak / je bijekce s vlastností, že f~l = g, právě tehdy, když platí g ° f = id a a / o g = idB.
Důkaz. Je-li / bijekce a je-li g = /_1, pak samozřejmě gof = idA a fog = idB.
Nechť naopak zobrazení /, g splňují g°f = id a a fog = idB. Ukážeme nejprve, že / je bijekce. Nechť b G B je libovolný prvek. Položme a = g(b). Pak f(a) = f(g(b)) = idB(b) = b, takže vidíme, že / je surjekce. Nechť dále a, a' G A jsou takové prvky, že f (a) = f (a'). Pak ovšem a = íáIaÍo) = g(f(a)) = g(f(a')) = idA(a') = a', čili a = a', takže / je také injekce. Celkem / je bijekce a existuje tedy inverzní zobrazení /_1, které je rovněž bijekce. Odtud pak dostáváme g = id a ° g = f~l ° / ° g = f~l o idB = f~\ čili p = f-1.
Jsou-li A, B množiny a je-li / : A —>■ B zobrazení, pak množinu Im/ značíme rovněž f (A) a nazýváme ji obraz při zobrazení /.
10