Množiny, relace, zobrazení
Množiny
Množinou rozumíme každý soubor určitých objektů shrnu-
tý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  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 x je prvkem A tehdy a jen tehdy, když
x je prvkem B. Zapsáno formulí, máme
A = B  (x)(x  A  x  B).
Řekneme, že množina A je podmnožinou množiny B, jestliže
každý prvek množiny A je prvkem množiny B. Pak píšeme
A  B a mluvíme o inkluzi množin. Podrobněji řečeno, klade-
me A  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
A  B  (x)(x  A = x  B).
To také znamená, že máme
A = B  (A  B & B  A).
Je jasné, že pak pro libovolné množiny A, B, C platí
(A  B & B  C) = A  C.
Poznamenejme ještě, že místo A  B se někdy píše také B  A,
a platí-li současně A  B a A = B, bývá to krátce zapisováno
ve tvaru A  B.
1
Význačnou množinou je prázdná množina, tedy množina,
která neobsahuje žádný prvek. Značíme ji . V této souvislosti
dodejme, že pro libovolnou množinu A máme
A  A a   A.
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 sjedno-
cení A  B jako množinu, která je tvořena těmi prvky, které
jsou prvky buď množiny A nebo množiny B, tedy těmi prvky,
které jsou prvky alespoň jedné z množin A, B. To znamená, že
klademe
A  B = {x | x  A  x  B}.
Dále definujeme průnik A  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
A  B = {x | x  A & x  B}.
Říkáme, že množiny A, B jsou disjunktní, je-li A  B = .
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 zna-
mená, že klademe
A - B = {x | x  A & 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í
A  B = B  A
A  B = B  A
(komutativita)
2
(A  B)  C = A  (B  C)
(A  B)  C = A  (B  C)
A  A = A
A  A = A
A  (B  C) = (A  B)  (A  C)
A  (B  C) = (A  B)  (A  C)
A - (B  C) = (A - B)  (A - C)
A - (B  C) = (A - B)  (A - C)
(asociativita)
(idempotence)
(distributivita)
(de Morganova pravidla)
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  C)  (A - B)  (A - C):
Nechť x  A - (B  C). Pak x  A & x / B  C.
Pak tedy x  A & (x / B  x / C).
Pak (x  A & x / B)  (x  A & x / C).
Pak ovšem x  A-B  x  A-C. Takže x  (A-B)(A-C).
(A - B)  (A - C)  A - (B  C):
Nechť x  (A - B)  (A - C). Pak x  A - B  x  A - C.
Pak tedy (x  A & x / B)  (x  A & x / C).
To znamená, že x  A & (x / B  x / C).
Takže pak x  A & x / B  C. Tedy x  A - (B  C).
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 libo-
volnou množinu A  M 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 A  M platí například
A  A = M, A  A =  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 a1, . . . , ak přiřadíme nový objekt (a1, . . . , ak),
jejich uspořádanou k-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 × B jako množinu, jejímiž prvky jsou právě všechny
uspořádané dvojice (a, b), kde a  A, b  B. To znamená, že
klademe
A × B = {(a, b) | a  A & b  B}.
Je-li A = B, nazýváme množinu A × A kartézským čtver-
cem množiny A a značíme ji A2
. Z uvedené definice je jasné, že
množiny A × B a B × A jsou obecně různé. Dále pro libovolné
množiny A, B, C také množiny
(A × B) × C = {((a, b), c) | a  A & b  B & c  C},
A × (B × C) = {(a, (b, c)) | a  A & b  B & c  C}
jsou formálně různé. Nicméně rozdíl mezi objekty ((a, b), c) a
(a, (b, 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 × B × C. Takže máme
A × B × C = {(a, b, c) | a  A & b  B & c  C}.
Podobně pro každé k  2 a libovolné množiny A1, . . . , Ak defi-
nujeme jejich kartézský součin A1 ×    × Ak jako množinu
A1 ×    × Ak = {(a1, . . . , ak) | a1  A1 & . . . & ak  Ak}.
4
Jestliže A1 =    = 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í:
(A  B) × C = (A × C)  (B × C),
(A  B) × C = (A × C)  (B × C),
(A - B) × C = (A × C) - (B × C).
Analogické rovnosti platí i pro C × (A  B), C × (A  B) a
C × (A - B).
Důkaz všech rovností je snadný.
Nechť A, B jsou libovolné množiny. Pak libovolná podmno-
žina kartézského součinu A×B se nazývá relace mezi mno-
žinami A a B. Jsou-li a  A, b  B takové prvky, že (a, b)  ,
pak říkáme, že prvek a je v relaci s prvkem b, a zapisujeme to
zpravidla ve tvaru a b. Jestliže (a, b) / , píšeme obvykle a /b.
Nechť A, B jsou opět libovolné množiny. Pak   A × B,
takže  je relace mezi množinami A a B a nazývá se prázdná
relace mezi A a B. Rovněž celá množina A × B je relací mezi
množinami A a B a nazývá se univerzální relace mezi A a B.
Nechť dále  A × B je libovolná relace mezi A a B. Pak
definičním oborem Dom relace rozumíme množinu
Dom = {a  A | (b  B)(a b)},
tedy množinu všech těch prvků z A, které jsou v relaci alespoň
s jedním prvkem z B, a oborem hodnot Im relace rozumíme
množinu
Im = {b  B | (a  A)(a b)},
tedy množinu všech těch prvků z B, s nimiž je v relaci alespoň
jeden prvek z A.
5
Definujeme skládání relací. Nechť A, B, C jsou množiny a
nechť  A × B a   B × C jsou relace. V této situaci
definujeme relaci    A × C vzniklou složením relací a 
následujícím způsobem:
  = {(a, c)  A × C | (b  B)(a b & b  c)}.
Zápis   čteme ,,  po ".
Skládání relací je asociativní:
Tvrzení. Nechť A, B, C, D jsou množiny a nechť  A×B,
  B × C,   C × D jsou relace. Pak platí:
(  )  =   (  ).
Důkaz. Na obou stranách této rovnosti jsou relace mezi
množinami A a D. Dokážeme inkluzi (  )     (  ).
Nechť tedy a  A, d  D jsou takové prvky, že (a, d)  () .
Pak podle definice skládání relací existuje prvek b  B takový, že
(a, b)  a (b, d)  . Opět podle téže definice existuje prvek
c  C takový, že (b, c)   a (c, d)  . Pak ovšem (a, c)    ,
takže (a, d)    (  ). Opačná inkluze   (  )  (  ) 
se dokáže analogicky.
Ke každé relaci mezi množinami A a B definujeme inverzní
relaci -1
mezi množinami B a A následovně:
-1
= {(b, a)  B × A | a b}.
To znamená, že platí
(a  A)(b  B)(a b  b -1
a).
Odtud okamžitě plyne, že Dom -1
= Im , Im -1
= Dom .
Dále je jasné, že platí
( -1
)-1
= .
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ť  A × B,
  B × C jsou relace. Pak platí:
(  )-1
= -1
 -1
.
Důkaz. Na obou stranách této rovnosti jsou relace mezi
množinami C a A. Dokážeme inkluzi (  )-1
 -1
 -1
.
Nechť a  A, c  C jsou takové prvky, že (c, a)  (  )-1
. Pak
(a, c)    . To znamená, že existuje prvek b  B takový, že
(a, b)  a (b, c)  . Odtud plyne, že (b, a)  -1
a (c, b)  -1
,
takže pak (c, a)  -1
-1
. Opačná inkluze -1
-1
 (  )-1
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 f : A  B množiny A
do množiny B rozumíme předpis, který každému prvku a  A
přiřazuje právě jeden prvek b  B. Pro takové prvky pak píšeme,
že b = f(a), a říkáme, že b je obrazem prvku a při zobrazení f.
Uvedené vymezení daného pojmu ovšem obsahuje blíže ne-
specifikovaný pojem ,,předpis". Bylo by vhodné umět se bez
tohoto prostředku obejít. Proto uvažujme k danému zobrazení
f : A  B relaci  A × B definovanou formulí
(a  A)(b  B)(a b  b = f(a))
a nazývanou graf zobrazení f. Všimněme si, že pak relace
splňuje podmínku
Dom = A,
7
neboť zobrazení f každému prvku z A přiřazuje nějaký obraz, a
dále podmínku
(a  A)(b, b  B)(a b & a b = b = b ),
neboť zobrazení f každému prvku z A přiřazuje jediný obraz.
Přitom relace zobrazení f kompletně určuje, neboť je vlastně
výčtem všech uspořádaných dvojic (a, b)  A × B takových, že
b = f(a).
Na druhé straně libovolnou relaci  A × 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í f, které je pak možno zadat předpisem
(a  A)(b  B)(b = f(a)  a b),
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 po-
mocí pojmů zavedených v teorii množin, nabízí se možnost přímo
ztotožnit zobrazení f s jeho grafem , 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ť f  A × B je
relace mezi nimi. Řekneme, že f je zobrazení množiny A do
množiny B a píšeme f : A  B, jestliže jsou splněny podmínky
Dom f = A
a dále
(a  A)(b, b  B)(a f b & a f b = b = b ).
V tom případě, jak bylo uvedeno shora, místo zápisu a f b, pří-
padně (a, b)  f, zpravidla píšeme b = f(a).
Nechť A, B jsou množiny. Zobrazení f : A  B se nazývá
surjekce, nebo též zobrazení na množinu B, platí-li
Im f = B.
8
Při takovém zobrazení f každý prvek b  B má alespoň jeden
vzor, tedy prvek a  A takový, že b = f(a).
Zobrazení f : A  B se nazývá injekce, nebo též prosté
zobrazení, splňuje-li podmínku
(b  B)(a, a  A)(a f b & a f b = a = a ).
Při takovém zobrazení f každý prvek b  B má nanejvýš jeden
vzor, tedy prvek a  A takový, že b = f(a).
Zobrazení f : A  B se nazývá bijekce, nebo též vzájemně
jednoznačné zobrazení množiny A na množinu B, je-li f sou-
časně injekce i surjekce.
Nechť A, B jsou množiny a nechť f : A  B je bijekce. Pak
inverzní relace f-1
k relaci f je zase zobrazení. To ihned plyne
z předchozích podmínek, neboť požadavky, aby f byla surjekce a
injekce, přesně odpovídají podmínkám, které je třeba splnit, aby
f-1
bylo zobrazení. Máme tedy zobrazení f-1
: B  A, které
samo je rovněž bijekce, neboť zase požadavky nutné k tomu,
aby f bylo zobrazení, znamenají, že f-1
je surjekce a injekce.
Říkáme, že f-1
je inverzní zobrazení k zobrazení f.
Definujeme skládání zobrazení. Poněvadž zobrazení jsou
speciální typy relací, definujeme toto skládání stejným způso-
bem jako skládání relací. Je ale zřejmé, že jsou-li A, B, C mno-
žiny a jsou-li f : A  B a g : B  C zobrazení, pak je-
jich složením dostaneme relaci g  f, která je opět zobrazením
g  f : A  C. Přitom toto zobrazení je očividně dáno předpi-
sem
(a  A)((g  f)(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í idA : A  A
předpisem
(a  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í f : A  B
platí
f  idA = f = idB  f,
a je-li f navíc bijekce, pak platí také
f-1
 f = idA, f  f-1
= idB.
Důležitý je následující fakt.
Věta. Nechť A, B jsou množiny a nechť
f : A  B, g : B  A
jsou zobrazení. Pak f je bijekce s vlastností, že f-1
= g, právě
tehdy, když platí g  f = idA a f  g = idB.
Důkaz. Je-li f bijekce a je-li g = f-1
, pak samozřejmě
g  f = idA a f  g = idB.
Nechť naopak zobrazení f, g splňují gf = idA a f g = idB.
Ukážeme nejprve, že f je bijekce. Nechť b  B je libovolný prvek.
Položme a = g(b). Pak f(a) = f(g(b)) = idB(b) = b, takže
vidíme, že f je surjekce. Nechť dále a, a  A jsou takové prvky,
že f(a) = f(a ). Pak ovšem a = idA(a) = g(f(a)) = g(f(a )) =
idA(a ) = a , čili a = a , takže f je také injekce. Celkem f je
bijekce a existuje tedy inverzní zobrazení f-1
, které je rovněž
bijekce. Odtud pak dostáváme g = idA  g = f-1
 f  g =
f-1
 idB = f-1
, čili g = f-1
.
Jsou-li A, B množiny a je-li f : A  B zobrazení, pak mno-
žinu Im f značíme rovněž f(A) a nazýváme ji obraz při zobra-
zení f.
10