Zobrazení
Jan Paseka
Masarykova univerzita Brno
Zobrazení a relace ­ p.1/61

Abstrakt
V této kapitole připomeneme pojem zobrazení
množiny a pojmy s ním spjaté (prosté zobrazení,
surjektivní zobrazení, bijektivní zobrazení).
Pokračujeme pak pojmem relace mezi
množinami, skládání relací, inverzní relace.
Následně zavedeme pojem mohutnosti množin a
dokážeme Cantorovu větu.
Zobrazení a relace ­ p.2/61

Obsah přednášky
Ú vod
Zobrazení.
Injektivní, surjektivní a bijektivní zobrazení.
Skládání zobrazení.
Zobrazení a relace ­ p.3/61

Obsah přednášky
Ú vod
Zobrazení.
Injektivní, surjektivní a bijektivní zobrazení.
Skládání zobrazení.
Relace mezi množinami.
Skládání relací, inverzní relace.
Zobrazení a relace ­ p.3/61

Obsah přednášky
Ú vod
Zobrazení.
Injektivní, surjektivní a bijektivní zobrazení.
Skládání zobrazení.
Relace mezi množinami.
Skládání relací, inverzní relace.
Ekvivalence množin, mohutnost.
Cantorova věta, spočetné a nespočetné
množiny. Zobrazení a relace ­ p.3/61

Definice zobrazení
Necht' 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.
Zobrazení a relace ­ p.4/61

Definice zobrazení
Necht' 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.
Zobrazení a relace ­ p.4/61

Definice zobrazení
Necht' 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 nespecifikovaný pojem ,,předpis".
Přesnou definici si uvedeme v kapitole o
relacích.
Zobrazení a relace ­ p.4/61

Vlastnosti zobrazení I
Jestliže f : A  B je zobrazení, pak množina A
se nazývá definiční obor a množina B se
nazývá obor hodnot tohoto zobrazení.
Zobrazení a relace ­ p.5/61

Vlastnosti zobrazení I
Jestliže f : A  B je zobrazení, pak množina A
se nazývá definiční obor a množina B se
nazývá obor hodnot tohoto zobrazení.
Dvě zobrazení f : A  B , g : C  D se rovnají
(což budeme stručně vyjadřovat zápisem f = g ) ,
jestliže:
A = C  B = D  f(x) = g(x) pro každé x  A
Zobrazení a relace ­ p.5/61

Vlastnosti zobrazení I
Jestliže f : A  B je zobrazení, pak množina A
se nazývá definiční obor a množina B se
nazývá obor hodnot tohoto zobrazení.
Dvě zobrazení f : A  B , g : C  D se rovnají
(což budeme stručně vyjadřovat zápisem f = g ) ,
jestliže:
A = C  B = D  f(x) = g(x) pro každé x  A
tj. jestliže se rovnají jejich definiční obory, obory
hodnot a příslušné předpisy.
Zobrazení a relace ­ p.5/61

Vlastnosti zobrazení II
V opačném případě (tzn. není­ li splněna
alespoň jedna z předchozích tří podmínek) se
obě zobrazení nerovnají, což budeme stručně
zapisovat ve tvaru f = g.
Zobrazení a relace ­ p.6/61

Vlastnosti zobrazení II
V opačném případě (tzn. není­ li splněna
alespoň jedna z předchozích tří podmínek) se
obě zobrazení nerovnají, což budeme stručně
zapisovat ve tvaru f = g.
K zadání zobrazení je nutno zadat definiční obor,
obor hodnot a příslušný předpis. Přitom předpis
je možno zadat různými způsoby.
Zobrazení a relace ­ p.6/61

Příklady zobrazení I
Definujme zobrazení f : A - B takto:
A = {a, b, c, d} , B = {r, s, t, u, v} a položíme :
f(a) = u , f(b) = r , f(c) = v , f(d) = t.
Zobrazení a relace ­ p.7/61

Příklady zobrazení I
Definujme zobrazení f : A - B takto:
A = {a, b, c, d} , B = {r, s, t, u, v} a položíme :
f(a) = u , f(b) = r , f(c) = v , f(d) = t.
A = Z , B = N a položíme :
f(x) =
2
x + 1 pro x  0
-2x pro x < 0
Zobrazení a relace ­ p.7/61

Příklady zobrazení II
Definujme zobrazení f : A - B takto:
A = R , B = R a položíme : f(x) = sin x pro
každé x  R
Zobrazení a relace ­ p.8/61

Příklady zobrazení II
Definujme zobrazení f : A - B takto:
A = R , B = R a položíme : f(x) = sin x pro
každé x  R
A = R , B = [-1, 1 ] a položíme :
f(x) = sin x pro každé x  R .
Zobrazení a relace ­ p.8/61

Surjektivní a injektivní zobrazení
Necht' A, B jsou množiny. Zobrazení f : A  B
se nazývá surjekce, nebo též zobrazení na
množinu B, platí-li, že každý prvek b  B má
alespoň jeden vzor, tedy prvek a  A takový, že
b = f(a).
Zobrazení a relace ­ p.9/61

Surjektivní a injektivní zobrazení
Necht' A, B jsou množiny. Zobrazení f : A  B
se nazývá surjekce, nebo též zobrazení na
množinu B, platí-li, že 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
(a, a 
A)(f(a) = f(a )
= a = a )
.
Zobrazení a relace ­ p.9/61

Surjektivní a injektivní zobrazení
Necht' A, B jsou množiny. Zobrazení f : A  B
se nazývá surjekce, nebo též zobrazení na
množinu B, platí-li, že 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
(a, a 
A)(f(a) = f(a )
= 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í a relace ­ p.9/61

Příklady injektivního a surjektivního zobrazení I
Definujme zobrazení f : A - B takto:
A = {a, b, c, d} , B = {r, s, t, u, v} a položíme :
f(a) = u , f(b) = r , f(c) = v , f(d) = t.
Zobrazení a relace ­ p.10/61

Příklady injektivního a surjektivního zobrazení I
Definujme zobrazení f : A - B takto:
A = {a, b, c, d} , B = {r, s, t, u, v} a položíme :
f(a) = u , f(b) = r , f(c) = v , f(d) = t.
Zobrazení je injektivní a není surjektivní.
Zobrazení a relace ­ p.10/61

Příklady injektivního a surjektivního zobrazení II
Definujme zobrazení f : A - B takto:
A = Z , B = N a položíme :
f(x) =
2
x + 1 pro x  0
-2x pro x < 0
Zobrazení a relace ­ p.11/61

Příklady injektivního a surjektivního zobrazení II
Definujme zobrazení f : A - B takto:
A = Z , B = N a položíme :
f(x) =
2
x + 1 pro x  0
-2x pro x < 0
Zobrazení je injektivní a surjektivní.
Zobrazení a relace ­ p.11/61

Příklady injektivního a surjektivního zobrazení III
Definujme zobrazení f : A - B takto:
A = R , B = R a položíme : f(x) = sin x pro
každé x  R
Zobrazení a relace ­ p.12/61

Příklady injektivního a surjektivního zobrazení III
Definujme zobrazení f : A - B takto:
A = R , B = R a položíme : f(x) = sin x pro
každé x  R
Zobrazení není injektivní a není surjektivní.
Zobrazení a relace ­ p.12/61

Příklady injektivního a surjektivního zobrazení IV
Definujme zobrazení f : A - B takto:
A = R , B = [-1, 1 ] a položíme :
f(x) = sin x pro každé x  R
Zobrazení a relace ­ p.13/61

Příklady injektivního a surjektivního zobrazení IV
Definujme zobrazení f : A - B takto:
A = R , B = [-1, 1 ] a položíme :
f(x) = sin x pro každé x  R
Zobrazení není injektivní a je surjektivní.
Zobrazení a relace ­ p.13/61

Vzájemně jednoznačné zobrazení
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.
Zobrazení a relace ­ p.14/61

Vzájemně jednoznačné zobrazení
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.
Necht' A, B jsou množiny a necht' f : A  B je bijekce.
Položme
f-1
(b) = a  f(a) = b.
Zobrazení a relace ­ p.14/61

Vzájemně jednoznačné zobrazení
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.
Necht' A, B jsou množiny a necht' f : A  B je bijekce.
Položme
f-1
(b) = a  f(a) = b.
Máme tedy zobrazení f-1
: B  A, které samo je rovněž
bijekce, nebot' zase požadavky nutné k tomu, aby f bylo
zobrazení, znamenají, že f-1
je surjekce a injekce.
Zobrazení a relace ­ p.14/61

Vzájemně jednoznačné zobrazení
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.
Necht' A, B jsou množiny a necht' f : A  B je bijekce.
Položme
f-1
(b) = a  f(a) = b.
Máme tedy zobrazení f-1
: B  A, které samo je rovněž
bijekce, nebot' 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.
Zobrazení a relace ­ p.14/61

Příklad bijektivního zobrazení
Zobrazení f : Z - N z příkladu II je bijektivní.
Zobrazení a relace ­ p.15/61

Příklad bijektivního zobrazení
Zobrazení f : Z - N z příkladu II je bijektivní.
Existuje tedy k němu zobrazení inverzní
f-1
: N - Z .
Zobrazení a relace ­ p.15/61

Příklad bijektivního zobrazení
Zobrazení f : Z - N z příkladu II je bijektivní.
Existuje tedy k němu zobrazení inverzní
f-1
: N - Z .
Lehce se zjistí, že:
f-1
(x) =
x
-1
2 pro každé liché x  N
-x
2 pro každé sudé x  N.
Zobrazení a relace ­ p.15/61

Složené zobrazení I
Necht' f : A - B , g : B - C jsou zobrazení.
Potom zobrazení (g  f) : A - C definované
předpisem
(g  f)(x) = g ( f(x) ) pro každé x  A
se nazývá složené zobrazení (ze zobrazení f a
g, v tomto pořadí).
Zobrazení a relace ­ p.16/61

Složené zobrazení II
Složené zobrazení je možno definovat pouze
v případě, že obor hodnot prvního zobrazení je
roven definičnímu oboru druhého zobrazení.
Zobrazení a relace ­ p.17/61

Složené zobrazení II
Složené zobrazení je možno definovat pouze
v případě, že obor hodnot prvního zobrazení je
roven definičnímu oboru druhého zobrazení.
Poznamenejme ještě, že symbol g  f čteme
bud' "g kolečko f" nebo "g po f".
Zobrazení a relace ­ p.17/61

Složené zobrazení II
Složené zobrazení je možno definovat pouze
v případě, že obor hodnot prvního zobrazení je
roven definičnímu oboru druhého zobrazení.
Poznamenejme ještě, že symbol g  f čteme
bud' "g kolečko f" nebo "g po f".
U zápisu složeného zobrazení g  f si ještě
všimněme toho, že i když se nejprve provádí
zobrazení f a potom zobrazení g, je zaveden
zápis "v obráceném pořadí". Konvence, podle
které se argument x píše napravo od symbolu
zobrazení f.
Zobrazení a relace ­ p.17/61

Identické zobrazení - I
Definujme pro libovolnou množinu A zobrazení
idA : A  A předpisem
(a  A)(idA(a) = a).
Zobrazení a relace ­ p.18/61

Identické zobrazení - I
Definujme pro libovolnou množinu A zobrazení
idA : A  A předpisem
(a  A)(idA(a) = a).
Toto zobrazení se nazývá identita na A.
Zobrazení a relace ­ p.18/61

Identické zobrazení - I
Definujme pro libovolnou množinu A zobrazení
idA : A  A předpisem
(a  A)(idA(a) = a).
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  .,
Zobrazení a relace ­ p.18/61

Identické zobrazení - II
Je-li f navíc bijekce, pak platí také
f-1
 f = idA, f  f-1
= idB.
Zobrazení a relace ­ p.19/61

Identické zobrazení - II
Je-li f navíc bijekce, pak platí také
f-1
 f = idA, f  f-1
= idB.
Věta. Necht' A, B jsou množiny a necht'
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.
Zobrazení a relace ­ p.19/61

Identické zobrazení - III
Příklad. Necht' f : N - N , resp˙ g : N - N
jsou zobrazení, definovaná takto :
f(x) = x + 1 pro  x  N
resp. g(x) =
1
pro x = 1
x - 1 pro x  2
Zřejmě platí: g  f = idN (nebot' (g  f)(x) =
g(f(x)) = g(x + 1) = (x + 1) - 1 = x ) , f není
surjektivní (1 nemá při zobrazení f žádný vzor) a
g není injektivní (nebot' g(1) = g(2) ).
Zobrazení a relace ­ p.20/61

Základní tvrzení o zobrazeních
Věta Necht' f : A - B, g : B - C, h : C - D
jsou zobrazení. Pak platí:
h  ( g  f ) = ( h  g )  f .
Jsou-li navíc f, g injektivní (surjektivní) zobrazení,
je g  f injektivní (surjektivní) zobrazení. Obrá-
ceně, je-li g  f injektivní (surjektivní) zobrazení,
je f (g) injektivní (surjektivní) zobrazení.
Zobrazení a relace ­ p.21/61

Restrinkce zobrazení
Definice. Necht' f : A - B je zobrazení a necht'
M  A. Pak zobrazení
h : M - B definované : h(x) = f(x) , pro x  M
se nazývá zúžení zobrazení (restrinkce) f na
množinu M a obvykle se značí symbolem f|M
(což čteme: "f zúženo na M").
Zobrazení a relace ­ p.22/61

Restrinkce zobrazení
Definice. Necht' f : A - B je zobrazení a necht'
M  A. Pak zobrazení
h : M - B definované : h(x) = f(x) , pro x  M
se nazývá zúžení zobrazení (restrinkce) f na
množinu M a obvykle se značí symbolem f|M
(což čteme: "f zúženo na M").
Zúžením zobrazení se mohou podstatně změnit
některé jeho základní vlastnosti.
Zobrazení a relace ­ p.22/61

Restrinkce zobrazení - příklad
Mějme zobrazení
f : R - R, f(x) = x2
, pro každé x  R
a zkonstruujeme jeho zúžení na množinu R+
všech kladných reálných čísel,
Zobrazení a relace ­ p.23/61

Restrinkce zobrazení - příklad
Mějme zobrazení
f : R - R, f(x) = x2
, pro každé x  R
a zkonstruujeme jeho zúžení na množinu R+
všech kladných reálných čísel, tzn. máme
f|R+
: R+
- R, f|R+
(x) = x2
, pro x  R+
,
pak vidíme, že zobrazení f není injektivní,
zatímco zúžení zobrazení f|R+
je injektivní.
Zobrazení a relace ­ p.23/61

Obraz při zobrazení
Jsou-li A, B množiny a je-li f : A  B zobrazení,
pak množinu Im f = {y  B : y = f(x), x  A}
značíme rovněž f(A) a nazýváme ji obraz při
zobrazení f.
Zobrazení a relace ­ p.24/61

Obraz při zobrazení
Jsou-li A, B množiny a je-li f : A  B zobrazení,
pak množinu Im f = {y  B : y = f(x), x  A}
značíme rovněž f(A) a nazýváme ji obraz při
zobrazení f.
Pro libovolné dvě množiny A, B symbolem BA
značíme množinu všech zobrazení f : A  B.
Zobrazení a relace ­ p.24/61

Uspořádaná dvojice prvků - I
Intuitivní představa - ke každým dvěma prvkům
x, y lze přiřadit nový prvek (x, y), nazývaný
uspořádanou dvojicí tak, že dvě uspořádané
dvojice (x, y) a (r, s) jsou si rovny právě když
x = r a y = s .
Zobrazení a relace ­ p.25/61

Uspořádaná dvojice prvků - I
Intuitivní představa - ke každým dvěma prvkům
x, y lze přiřadit nový prvek (x, y), nazývaný
uspořádanou dvojicí tak, že dvě uspořádané
dvojice (x, y) a (r, s) jsou si rovny právě když
x = r a y = s .
V uspořádané dvojici (x, y) tedy záleží na po-
řadí prvků x, y, přičemž prvek x se nazývá první
složka a prvek y se nazývá druhá složka uspo-
řádané dvojice (x, y).
Zobrazení a relace ­ p.25/61

Uspořádaná dvojice prvků - II
Konkrétní realizace - uspořádanou dvojicí prvků
s první složkou a a druhou složkou b rozumíme
množinu
(a, b) = {{a}, {a, b}}.
Zobrazení a relace ­ p.26/61

Uspořádaná dvojice prvků - II
Konkrétní realizace - uspořádanou dvojicí prvků
s první složkou a a druhou složkou b rozumíme
množinu
(a, b) = {{a}, {a, b}}.
Je jasné, že pak pro libovolné prvky a, b, c, d platí
(a, b) = (c, d)  a = c & b = d.
Zobrazení a relace ­ p.26/61

Uspořádaná n ­ tice prvků
Analogickým způsobem lze pro libovolné n  2
zavést pojem uspořádaná n ­ tice prvků, kterou
označujeme symbolem (a1, a2, . . . an). Přitom
klademe s použitím indukce
(a1, . . . , an) = ((a1, . . . , an-1), an),
Zobrazení a relace ­ p.27/61

Uspořádaná n ­ tice prvků
Analogickým způsobem lze pro libovolné n  2
zavést pojem uspořádaná n ­ tice prvků, kterou
označujeme symbolem (a1, a2, . . . an). Přitom
klademe s použitím indukce
(a1, . . . , an) = ((a1, . . . , an-1), an),
Nutně pak se dvě uspořádané n ­ tice prvků
rovnají právě když se rovnají jejich odpovídající
si složky.
Zobrazení a relace ­ p.27/61

Kartézský součin dvou množin
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.
Zobrazení a relace ­ p.28/61

Kartézský součin dvou množin
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}.
Zobrazení a relace ­ p.28/61

Kartézský součin dvou množin
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 čtvercem množiny A a značíme ji
A2
.
Zobrazení a relace ­ p.28/61

Vlastnosti kartézského součinu
Množiny A × B a B × A jsou obecně různé.
Zobrazení a relace ­ p.29/61

Vlastnosti kartézského součinu
Množiny A × B a B × A jsou obecně různé.
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é.
Zobrazení a relace ­ p.29/61

Vlastnosti kartézského součinu
Množiny A × B a B × A jsou obecně různé.
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é.
Rozdíl mezi objekty ((a, b), c) a (a, (b, c)) se
přehlíží.
Zobrazení a relace ­ p.29/61

Kartézský součin konečně mnoha množin I
Pro každé n  2 a libovolné množiny A1, . . . , An
definujeme jejich kartézský součin
A1 ×    × An jako množinu
A1×  ×An = {(a1, . . . , an) | a1  A1 & . . . & an  A
Zobrazení a relace ­ p.30/61

Kartézský součin konečně mnoha množin I
Pro každé n  2 a libovolné množiny A1, . . . , An
definujeme jejich kartézský součin
A1 ×    × An jako množinu
A1×  ×An = {(a1, . . . , an) | a1  A1 & . . . & an  A
Kartézský součin A1 ×    × An je pak definován
jako součin (. . . (A1 × A2) × . . . ) × An, tedy s uzá-
vorkováním odleva.
Zobrazení a relace ­ p.30/61

Kartézský součin konečně mnoha množin II
Jestliže A1 =    = An = A, dostáváme tak
definici kartézské mocniny An
pro všechna
n  2.
Zobrazení a relace ­ p.31/61

Kartézský součin konečně mnoha množin II
Jestliže A1 =    = An = A, dostáváme tak
definici kartézské mocniny An
pro všechna
n  2.
Navíc klademe také A1
= A a definujeme ještě A0
jako mmnožinu {}.
Zobrazení a relace ­ p.31/61

Základní tvrzení o kartézském součinu
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).
Zobrazení a relace ­ p.32/61

Základní tvrzení o kartézském součinu
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).
Zobrazení a relace ­ p.32/61

Základní tvrzení o kart. součinu II
Tvrzení. Pro libovolnou množinu C, pro
libovolnou indexovou množinu I =  a pro
libovolný soubor množin Ai, kde i  I, platí:
Zobrazení a relace ­ p.33/61

Základní tvrzení o kart. součinu II
Tvrzení. Pro libovolnou množinu C, pro
libovolnou indexovou množinu I =  a pro
libovolný soubor množin Ai, kde i  I, platí:
i
I
Ai
×
C =
i
I
(Ai × C),
i
I
Ai
×
C =
i
I
(Ai × C).
Zobrazení a relace ­ p.33/61

Relace mezi množinami
Necht' 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.
Zobrazení a relace ­ p.34/61

Relace mezi množinami
Necht' 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.
Píšeme a b. Jestliže (a, b) / , píšeme obvykle
a /b.
Zobrazení a relace ­ p.34/61

Relace mezi množinami
Necht' 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.
Píšeme a b. Jestliže (a, b) / , píšeme obvykle
a /b.
Relace mezi množinami je opět množina.
K označení množiny obvykle používáme malé
řecké písmeno.
Zobrazení a relace ­ p.34/61

Příklady relací I
Definovat relaci mezi množinami A, B znamená
popsat jistou podmnožinu množiny A × B , tj.
jednoznačně určit všechny uspořádané dvojice
z A × B, které patří do .
Zobrazení a relace ­ p.35/61

Příklady relací I
Definovat relaci mezi množinami A, B znamená
popsat jistou podmnožinu množiny A × B , tj.
jednoznačně určit všechny uspořádané dvojice
z A × B, které patří do .
Příklad R 1. Necht'A = {a, b, c, d} , B = {x, y, z} .
Pak = {(a, y), (c, y), (c, z)} je relací mezi množi-
nami A, B.
Zobrazení a relace ­ p.35/61

Příklady relací II
Příklad R 2. Necht' A = N , B = N . Pak
= {(x, y)  N × N | y - x je kladné číslo} je
relací mezi množinami A, B.
Zobrazení a relace ­ p.36/61

Příklady relací II
Příklad R 2. Necht' A = N , B = N . Pak
= {(x, y)  N × N | y - x je kladné číslo} je
relací mezi množinami A, B.
Je zřejmé, že v tomto případě je číslo x v relacis
číslem y právě tehdy, když x je menší než y (při
běžném uspořádání čísel podle velikosti).
Zobrazení a relace ­ p.36/61

Příklady relací IIIa
Příklad R 3. Necht' A, B jsou libovolné množiny.
Uvedeme dva speciální případy relací mezi
množinami A, B:
Zobrazení a relace ­ p.37/61

Příklady relací IIIa
Příklad R 3. Necht' A, B jsou libovolné množiny.
Uvedeme dva speciální případy relací mezi
množinami A, B:
prázdná množina je zřejmě podmnožinou
A × B, a tedy =  je relací mezi množinami
A, B, kterou budeme nazývat prázdná
relace mezi A, B, tj. žádný prvek z A není
v relaci s žádným prvkem z B .
Zobrazení a relace ­ p.37/61

Příklady relací IIIb
Podmnožinou A × B je množina A × B samotná.
Zobrazení a relace ­ p.38/61

Příklady relací IIIb
Podmnožinou A × B je množina A × B samotná.
Tedy = A × B je relací mezi množinami
A, B, kterou budeme nazývat univerzální
relace mezi A, B, tj. každý prvek z množiny
A je v relaci s každým prvkem z množiny B .
Zobrazení a relace ­ p.38/61

Příklady relací IV
Příklad R 4. Bud' A množina a bud' P(A)
potenční množina množiny A. Prvky množiny
P(A) jsou podmnožiny X  A.
Zobrazení a relace ­ p.39/61

Příklady relací IV
Příklad R 4. Bud' A množina a bud' P(A)
potenční množina množiny A. Prvky množiny
P(A) jsou podmnožiny X  A.
Definujme podmnožinu  A × P(A) takto:
= {(a, X)  A × P(A) | a  X}.
Pak je relace mezi množinami A a P(A).
Zobrazení a relace ­ p.39/61

Příklady relací V
Příklad R 5. Bud' A množina a bud' P(A)
potenční množina množiny A. Prvky množiny
P(A) jsou podmnožiny X  A.
Zobrazení a relace ­ p.40/61

Příklady relací V
Příklad R 5. Bud' A množina a bud' P(A)
potenční množina množiny A. Prvky množiny
P(A) jsou podmnožiny X  A.
Definujme podmnožinu množiny P(A) × P(A)
takto:
R = {(X, Y )  P(A) × P(A) : X  Y }.
Pak R je relace na množině P(A).
Zobrazení a relace ­ p.40/61

Příklady relací VI
Příklad R 6. Bud' A množina. Množina
{(x, x) : x  A} je relace na A.
Zobrazení a relace ­ p.41/61

Příklady relací VI
Příklad R 6. Bud' A množina. Množina
{(x, x) : x  A} je relace na A.
Mluvíme o relaci rovnosti a označujeme symbo-
lem A nebo .
Zobrazení a relace ­ p.41/61

Zobrazení a relace
Pojem zobrazení je možné naprosto korektně
definovat pomocí relací takto:
Zobrazení a relace ­ p.42/61

Zobrazení a relace
Pojem zobrazení je možné naprosto korektně
definovat pomocí relací takto:
Necht' A, B jsou množiny a necht' f je relace
mezi množinami A, B, splňující podmínku: ke
každému x  A existuje jediné y  B tak, že
(x, y)  f .
Zobrazení a relace ­ p.42/61

Zobrazení a relace
Pojem zobrazení je možné naprosto korektně
definovat pomocí relací takto:
Necht' A, B jsou množiny a necht' f je relace
mezi množinami A, B, splňující podmínku: ke
každému x  A existuje jediné y  B tak, že
(x, y)  f .
Pak uspořádanou trojici (A, B, f) nazýváme
zobrazením množiny A do množiny B.
Zobrazení a relace ­ p.42/61

Definiční obor a obor hodnot relace
Necht'  A × B je libovolná relace mezi A a B.
Zobrazení a relace ­ p.43/61

Definiční obor a obor hodnot relace
Necht'  A × B je libovolná relace mezi A a B.
Definičním oborem Dom relace rozumíme
množinu
Dom = {a  A | (b  B)(a b)},
Zobrazení a relace ­ p.43/61

Definiční obor a obor hodnot relace
Necht'  A × B je libovolná relace mezi A a B.
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.
Zobrazení a relace ­ p.43/61

Definiční obor a obor hodnot relace
Necht'  A × B je libovolná relace mezi A a B.
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.
Oborem hodnot Im relace rozumíme
množinu
Im = {b  B | (a  A)(a b)}.
Zobrazení a relace ­ p.43/61

Prázdné zobrazení
Je-li A = , pak BA
je B
, a to je množina všech
zobrazení f :   B.
Zobrazení a relace ­ p.44/61

Prázdné zobrazení
Je-li A = , pak BA
je B
, a to je množina všech
zobrazení f :   B.
Pro taková zobrazení f ovšem máme f   × B,
ale  × B = , takže nutně f =  je prázdné
zobrazení.
Zobrazení a relace ­ p.44/61

Prázdné zobrazení
Je-li A = , pak BA
je B
, a to je množina všech
zobrazení f :   B.
Pro taková zobrazení f ovšem máme f   × B,
ale  × B = , takže nutně f =  je prázdné
zobrazení.
To znamená, že B
= {}.
Zobrazení a relace ­ p.44/61

Prázdné zobrazení
Je-li A = , pak BA
je B
, a to je množina všech
zobrazení f :   B.
Pro taková zobrazení f ovšem máme f   × B,
ale  × B = , takže nutně f =  je prázdné
zobrazení.
To znamená, že B
= {}.
Poněvadž při konstrukci nezáporných celých čí-
sel bylo 0 = , je to důvod, proč jsme definovali
množinu B0
jako {}.
Zobrazení a relace ­ p.44/61

Skládání relací
Necht' je relace mezi množinami A, B a necht' 
je relace mezi množinami B, C. Pak relace
Zobrazení a relace ­ p.45/61

Skládání relací
Necht' je relace mezi množinami A, B a necht' 
je relace mezi množinami B, C. Pak relace
  = {(x, y)  A × C |  b  B tak, že
(x, b)   (b, y)  }
Zobrazení a relace ­ p.45/61

Skládání relací
Necht' je relace mezi množinami A, B a necht' 
je relace mezi množinami B, C. Pak relace
  = {(x, y)  A × C |  b  B tak, že
(x, b)   (b, y)  }
se nazývá složená relace z relací a .
Zobrazení a relace ­ p.45/61

Skládání relací
Necht' je relace mezi množinami A, B a necht' 
je relace mezi množinami B, C. Pak relace
  = {(x, y)  A × C |  b  B tak, že
(x, b)   (b, y)  }
se nazývá složená relace z relací a .
Symbol   pro složenou relaci čteme bud' "
kolečko " nebo " po ".
Zobrazení a relace ­ p.45/61

Skládání relací - příklad I
Příklad R 7. Necht' A = {a, b, c, d} ,
B = {x, y, z} , C = {k, l, m, n} a necht' je dána
relace mezi množinami A, B a relace  mezi
množinami B, C takto:
= {(a, y), (c, y), (c, z)}
 = {(x, k), (x, l), (x, m), (x, n), (y, k), (y, n)} .
Zobrazení a relace ­ p.46/61

Skládání relací - příklad I
Příklad R 7. Necht' A = {a, b, c, d} ,
B = {x, y, z} , C = {k, l, m, n} a necht' je dána
relace mezi množinami A, B a relace  mezi
množinami B, C takto:
= {(a, y), (c, y), (c, z)}
 = {(x, k), (x, l), (x, m), (x, n), (y, k), (y, n)} .
Potom z definice složené relace ihned plyne, že
  = {(a, k), (a, n), (c, k), (c, n)} .
Zobrazení a relace ­ p.46/61

Graf relace
Poznámka. Relace si můžeme znázorňovat
graficky, zejména jsou ­ li množiny konečné.
.
Zobrazení a relace ­ p.47/61

Graf relace
Poznámka. Relace si můžeme znázorňovat
graficky, zejména jsou ­ li množiny konečné.
Je ­ li například relací mezi množinami A, B ,
pak si znázorníme prvky obou množin jako body
v rovině a bod r  A spojíme orientovanou
šipkou s bodem s  B právě tehdy, když
(r, s)  .
.
Zobrazení a relace ­ p.47/61

Graf relace
Poznámka. Relace si můžeme znázorňovat
graficky, zejména jsou ­ li množiny konečné.
Je ­ li například relací mezi množinami A, B ,
pak si znázorníme prvky obou množin jako body
v rovině a bod r  A spojíme orientovanou
šipkou s bodem s  B právě tehdy, když
(r, s)  .
Výsledný obrázek budeme nazývat graf relace .
Zobrazení a relace ­ p.47/61

Graf relace - příklad I
Pro relace ,  z předchozího příkladu R 7. tak
dostáváme následující grafy:
Pomocí grafů si můžeme schematicky znázornit i
další pojmy, jako například skládání relací.
Zobrazení a relace ­ p.48/61

Znázorňování relací na množině I
Znázorňování relací na množině můžeme
provést obrázkem, podobně jako u relací mezi
množinami.
Zobrazení a relace ­ p.49/61

Znázorňování relací na množině I
Znázorňování relací na množině můžeme
provést obrázkem, podobně jako u relací mezi
množinami.
Jestliže je tedy (A, ) množina s relací, pak prvky
množiny A znázorníme jako body v rovině a
z bodu x nakreslíme orientovanou šipku do bodu
y právě tehdy, když x y .
Zobrazení a relace ­ p.49/61

Znázorňování relací na množině I
Znázorňování relací na množině můžeme
provést obrázkem, podobně jako u relací mezi
množinami.
Jestliže je tedy (A, ) množina s relací, pak prvky
množiny A znázorníme jako body v rovině a
z bodu x nakreslíme orientovanou šipku do bodu
y právě tehdy, když x y .
Přitom je samozřejmě možné, že šipka začíná a
končí ve stejném bodu. Taková šipka se nazývá
smyčka. Vzniklý obrázek budeme nazývat
uzlový graf relace .
Zobrazení a relace ­ p.49/61

Znázorňování relací na množině II
Výhodné je rovněž vyjadřování relace na
(konečné) množině A pomocí tabulky, kterou se
strojíme následujícím způsobem: do záhlaví
řádků a sloupců vypíšeme prvky množiny A , a to
ve stejném pořadí.
Zobrazení a relace ­ p.50/61

Znázorňování relací na množině II
Výhodné je rovněž vyjadřování relace na
(konečné) množině A pomocí tabulky, kterou se
strojíme následujícím způsobem: do záhlaví
řádků a sloupců vypíšeme prvky množiny A , a to
ve stejném pořadí.
Do průsečíku řádku označeného x a sloupce
označeného y pak napíšeme jedničku, je ­ li
x y , resp. napíšeme nulu, je ­ li x y .
Necht' A = {a, b, c, d} a necht' například
= {(a, b), (b, a), (b, b), (b, c)} . Potom je relace
na množině A .
Zobrazení a relace ­ p.50/61

Skládání relací - příklad II
Příklad R.8. Bud' A množina.
Zobrazení a relace ­ p.51/61

Skládání relací - příklad II
Příklad R.8. Bud' A množina. Uvažme opět její
potenční množinu P(A). Prvky množiny P(A)
jsou všechny podmnožiny X  A.
Zobrazení a relace ­ p.51/61

Skládání relací - příklad II
Příklad R.8. Bud' A množina. Uvažme opět její
potenční množinu P(A). Prvky množiny P(A)
jsou všechny podmnožiny X  A.
Uvažme dále potenční množinu P(P(A)). Prvky
množiny P(P(A)) jsou libovolné podmnožiny
Q  P(A).
Zobrazení a relace ­ p.51/61

Skládání relací - příklad II
Příklad R.8. Bud' A množina. Uvažme opět její
potenční množinu P(A). Prvky množiny P(A)
jsou všechny podmnožiny X  A.
Uvažme dále potenční množinu P(P(A)). Prvky
množiny P(P(A)) jsou libovolné podmnožiny
Q  P(A).
Takové podmnožiny Q ale nejsou nic jiného než
soubory některých podmnožin X  A.
Zobrazení a relace ­ p.51/61

Skládání relací - příklad II
Pro každý takový soubor Q označme stručněQ
sjednocení souboru Q, to znamená
sjednocení všech těch podmnožin X  A, které
jsou prvky souboru Q.
Zobrazení a relace ­ p.52/61

Skládání relací - příklad II
Pro každý takový soubor Q označme stručněQ
sjednocení souboru Q, to znamená
sjednocení všech těch podmnožin X  A, které
jsou prvky souboru Q. V příkladu R.4 jsme
definovali relaci  A × P(A) předpisem:
= {(a, X)  A × P(A) | a  X}.
Zobrazení a relace ­ p.52/61

Skládání relací - příklad II
Pro každý takový soubor Q označme stručněQ
sjednocení souboru Q, to znamená
sjednocení všech těch podmnožin X  A, které
jsou prvky souboru Q. V příkladu R.4 jsme
definovali relaci  A × P(A) předpisem:
= {(a, X)  A × P(A) | a  X}.
Definujme podobně relaci   P(A) × P(P(A))
předpisem:
 = {(X, Q)  P(A) × P(P(A)) | X  Q}.
Zobrazení a relace ­ p.52/61

Skládání relací - příklad II
Pak složená relace    A × P(P(A)) má
podle předchozí definice tvar:
Zobrazení a relace ­ p.53/61

Skládání relací - příklad II
Pak složená relace    A × P(P(A)) má
podle předchozí definice tvar:
  = { (a, Q)  A × P(P(A))
(X  P(A))(a  X & X  Q)},
Zobrazení a relace ­ p.53/61

Skládání relací - příklad II
Pak složená relace    A × P(P(A)) má
podle předchozí definice tvar:
  = { (a, Q)  A × P(P(A))
(X  P(A))(a  X & X  Q)},
což podle definice sjednocení
Q
znamená, že
tato relace je dána předpisem:
  = {(a, Q)  A × P(P(A)) | a 
Q
}.
Zobrazení a relace ­ p.53/61

Vlastnosti skládání relací
Skládání relací je asociativní:
Zobrazení a relace ­ p.54/61

Vlastnosti skládání relací
Skládání relací je asociativní:
Tvrzení. Necht' A, B, C, D jsou množiny a necht'
 A × B,   B × C,   C × D jsou relace.
Pak platí:
(  )  =   (  ).
Zobrazení a relace ­ p.54/61

Inverzní relace I
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}.
Zobrazení a relace ­ p.55/61

Inverzní relace I
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).
Zobrazení a relace ­ p.55/61

Inverzní relace I
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).
Tedy Dom -1
= Im , Im -1
= Dom a
( -1
)-1
= .
Zobrazení a relace ­ p.55/61

Inverzní relace II
Mezi skládáním relací a inverzními relacemi
existuje následující souvislost:
Zobrazení a relace ­ p.56/61

Inverzní relace II
Mezi skládáním relací a inverzními relacemi
existuje následující souvislost:
Tvrzení. Necht' A, B, C jsou množiny a necht'
 A × B,   B × C jsou relace. Pak platí:
(  )-1
= -1
 -1
.
Zobrazení a relace ­ p.56/61

Mohutnost množin
Ř ekneme, že dvě množiny A, B jsou
ekvivalentní, anebo též že mají stejnou
mohutnost, jestliže existuje bijekce f : A  B.
Pak píšeme A = B.
Zobrazení a relace ­ p.57/61

Mohutnost množin
Ř ekneme, že dvě množiny A, B jsou
ekvivalentní, anebo též že mají stejnou
mohutnost, jestliže existuje bijekce f : A  B.
Pak píšeme A = B.
Tvrzení. Pro libovolné množiny A, B, C platí:
(A × B)C = AC
× BC
,
(AB
)C = AB×C
.
Zobrazení a relace ­ p.57/61

Charakteristické zobrazení
Připomeňme, že 2 = {0, 1}. Pro libovolnou
množinu A a pro libovolnou podmnožinu Y  A
definujme charakteristické zobrazení
Y : A  2 podmnožiny Y následovně.
Zobrazení a relace ­ p.58/61

Charakteristické zobrazení
Připomeňme, že 2 = {0, 1}. Pro libovolnou
množinu A a pro libovolnou podmnožinu Y  A
definujme charakteristické zobrazení
Y : A  2 podmnožiny Y následovně.
Pro libovolné a  A klademe
Y (a) =
1
pokud a  Y,
0 pokud a / Y.
Zobrazení a relace ­ p.58/61

Charakteristické zobrazení
Připomeňme, že 2 = {0, 1}. Pro libovolnou
množinu A a pro libovolnou podmnožinu Y  A
definujme charakteristické zobrazení
Y : A  2 podmnožiny Y následovně.
Pro libovolné a  A klademe
Y (a) =
1
pokud a  Y,
0 pokud a / Y.
Tvrzení. Pro libovolnou množinu A je
P(A) = 2A
.
Zobrazení a relace ­ p.58/61

Cantorova věta
Zásadní význam má následující Cantorova věta.
Zobrazení a relace ­ p.59/61

Cantorova věta
Zásadní význam má následující Cantorova věta.
Věta. Pro každou množinu A platí A = P(A).
Zobrazení a relace ­ p.59/61

Cantorova věta
Zásadní význam má následující Cantorova věta.
Věta. Pro každou množinu A platí A = P(A).
Nástin důkazu. Připust'me, že existuje bijekce
f : A  P(A).
Zobrazení a relace ­ p.59/61

Cantorova věta
Zásadní význam má následující Cantorova věta.
Věta. Pro každou množinu A platí A = P(A).
Nástin důkazu. Připust'me, že existuje bijekce
f : A  P(A).
Zvolíme množinu Y = {a  A | a / f(a)}  P(A).
Zobrazení a relace ­ p.59/61

Cantorova věta
Zásadní význam má následující Cantorova věta.
Věta. Pro každou množinu A platí A = P(A).
Nástin důkazu. Připust'me, že existuje bijekce
f : A  P(A).
Zvolíme množinu Y = {a  A | a / f(a)}  P(A).
Y = f(y) pro jediné y  A.
Zobrazení a relace ­ p.59/61

Cantorova věta
Zásadní význam má následující Cantorova věta.
Věta. Pro každou množinu A platí A = P(A).
Nástin důkazu. Připust'me, že existuje bijekce
f : A  P(A).
Zvolíme množinu Y = {a  A | a / f(a)}  P(A).
Y = f(y) pro jediné y  A.
y  Y implikuje y / f(y) = Y
a y / Y implikuje y  f(y) = Y ­ SPOR!
Zobrazení a relace ­ p.59/61

Spočetné množiny
Připomeňme, že dvě konečné množiny mají
stejnou mohutnost, právě když mají stejný počet
prvků.
Zobrazení a relace ­ p.60/61

Spočetné množiny
Připomeňme, že dvě konečné množiny mají
stejnou mohutnost, právě když mají stejný počet
prvků.
Ř ekneme, že daná množina je spočetná, jestliže
má stejnou mohutnost jako množina  všech
nezáporných celých čísel.
Zobrazení a relace ­ p.60/61

Spočetné množiny
Připomeňme, že dvě konečné množiny mají
stejnou mohutnost, právě když mají stejný počet
prvků.
Ř ekneme, že daná množina je spočetná, jestliže
má stejnou mohutnost jako množina  všech
nezáporných celých čísel.
Každá podmnožina spočetné množiny je
konečná nebo spočetná.
Zobrazení a relace ­ p.60/61

Spočetné množiny
Připomeňme, že dvě konečné množiny mají
stejnou mohutnost, právě když mají stejný počet
prvků.
Ř ekneme, že daná množina je spočetná, jestliže
má stejnou mohutnost jako množina  všech
nezáporných celých čísel.
Každá podmnožina spočetné množiny je
konečná nebo spočetná.
Množiny N, Z, Q všech přirozených, celých a
racionálních čísel jsou všechny spočetné.
Zobrazení a relace ­ p.60/61

Nespočetné množiny
Nekonečná množina, která není spočetná, se
nazývá nespočetná.
Zobrazení a relace ­ p.61/61

Nespočetné množiny
Nekonečná množina, která není spočetná, se
nazývá nespočetná.
Z Cantorovy věty plyne, že například množina 2
je nespočetná.
Zobrazení a relace ­ p.61/61

Nespočetné množiny
Nekonečná množina, která není spočetná, se
nazývá nespočetná.
Z Cantorovy věty plyne, že například množina 2
je nespočetná.
Lze ukázat, že množina R všech reálných čísel je
nespočetná. Přesněji je možné ukázat, že
množiny R a 2
mají stejnou mohutnost.
Zobrazení a relace ­ p.61/61

Nespočetné množiny
Nekonečná množina, která není spočetná, se
nazývá nespočetná.
Z Cantorovy věty plyne, že například množina 2
je nespočetná.
Lze ukázat, že množina R všech reálných čísel je
nespočetná. Přesněji je možné ukázat, že
množiny R a 2
mají stejnou mohutnost.
O množinách, které mají stejnou mohutnost jako
R, říkáme, že mají mohutnost kontinua.
Zobrazení a relace ­ p.61/61