Binární relace v množině M a jejich vlastnosti
Poznámka Všude v této části se budeme zabývat binárními relacemi
definovanými v množině M, resp. na množině M. První a druhé složky
všech uspořádaných dvojic všech uvažovaných relací budou tedy
prvky jedné a téže množiny M.
Definice Nechť R je binární relace v množině M. Pak řekneme, že tato
relace je reflexivní (ve zkratce R), jestliže platí
(x [x, x] R.
Poznámka V reflexivní relaci musí být každý prvek množiny M v
relaci sám se sebou, v uzlovém grafu relace tedy musí být kolem
každého uzlu smyčka. Kartézský graf reflexivní relace musí obsahovat
všechny prvky tzv. hlavní diagonály. Aby relace nebyla reflexivní (ve
zkratce 𝑅), musí platit negace definice, tedy (x [x, x] R).
Definice Nechť R je binární relace v množině M. Pak řekneme, že tato
relace je antireflexivní (ve zkratce AR), jestliže platí
(x [x, x] R).
Poznámka V antireflexivní relaci nesmí být žádný prvek množiny M
v relaci sám se sebou, v uzlovém grafu relace tedy nesmí být ani jedna
smyčka. Kartézský graf antireflexivní relace nesmí obsahovat ani
jeden prvek hlavní diagonály. Aby relace nebyla antireflexivní (ve
zkratce 𝐴𝑅), musí platit negace definice, tedy (x [x, x] R).
Poznámka Je zřejmé, že žádná relace nemůže být reflexivní a
antireflexivní současně. Nemusí však být ani reflexivní ani
antireflexivní (obsahuje-li uzlová graf alespoň jednu smyčku, ale ne
všechny). Tyto dvě vlastnosti tedy nejsou doplňkové.
Definice Nechť R je binární relace v množině M. Pak řekneme, že tato
relace je symetrická (ve zkratce S), jestliže platí
(x, y [x, y] R  [y, x] R.
Poznámka V uzlovém grafu symetrické relace musí být každé dva
různé prvky množiny M spojeny buďto oboustrannou šipkou
(orientovanou na obou koncích) nebo nejsou spojeny vůbec. Na počtu
smyček v grafu nezáleží. Kartézský graf symetrické relace musí být
souměrný podle hlavní diagonály. Aby relace nebyla symetrická (ve
zkratce 𝑆), musí platit negace definice, tedy
(x, y [x, y] R  [y, x] R.
V uzlovém grafu tedy stačí k vyloučení symetrie dané relace existence
jediné jednoduché šipky. Poznamenejme ještě užitečné tvrzení, že
relace R je symetrická, právě když platí R = R1
.
Definice Nechť R je binární relace v množině M. Pak řekneme, že tato
relace je antisymetrická (ve zkratce AS), jestliže platí
(x, y x  y [x, y] R)  [y, x] R.
Poznámka V uzlovém grafu antisymetrické relace musí být každé dva
různé prvky množiny M spojeny buďto jednoduchou šipkou
(orientovanou na jednom konci) nebo nejsou spojeny vůbec. Na počtu
smyček v grafu nezáleží. V kartézském grafu antisymetrické relace
nesmí být žádná dvojice bodů souměrná podle hlavní diagonály. Aby
relace nebyla antisymetrická (ve zkratce 𝐴𝑆), musí platit negace
definice, tedy musí platit
(x, y x  y [x, y] R  [y, x] R).
V uzlovém grafu tedy stačí k vyloučení antisymetrie dané relace
existence jediné oboustranné šipky).
Poznámka Z definic je opět zřejmé, že vlastnosti symetrie a
antisymetrie nejsou doplňkové. Existují tedy relace, které nejsou
symetrické ani antisymetrické (obsahuje-li jejich uzlový graf
jednoduché i oboustranné šipky). Existují však i relace, které mohou
být symetrické a antisymetrické současně. To nastane pouze v
případě, kdy ani jedna dvojice různých prvků množiny M není spojena
žádnou šipkou a uzlový graf obsahuje pouze smyčky. Např. na
množině M = {1, 2, 3} je relace R = {[1, 1], [2, 2]} současně
symetrická i antisymetrická.
Poznámka V literatuře bývá často vlastnost antisymetrie relace R
definována takto:
(x, y [x, y] R) [y, x] R)  x  y.
Snadno se lze přesvědčit pomocí výrokové logiky, že tato definice a
předchozí definice jsou ekvivalentní.
Definice Nechť R je binární relace v množině M. Pak řekneme, že tato
relace je tranzitivní (ve zkratce T), jestliže platí
(x, y, z [x, y] R [y, z] R)  [x, z] R.
Poznámka Tranzitivita binární relace je jedinou vlastností, pro kterou
nelze v uzlovém ani kartézském grafu vyslovit nějaký univerzální
předpis, Obecně platí, že tranzitivitu relace lze jednodušeji vyloučit
než ji prokázat. K tomu může sloužit negace vlastnosti T. Aby relace
nebyla tranzitivní (ve zkratce 𝑇), musí platit negace definice, tedy
musí platit
(x, y, z [x, y] R [y, z] R)  [x, z] R.
Nalezení trojice bodů s touto vlastností (tedy vyloučení tranzitivnosti
relace) se v uzlovém grafu často podaří. Jednou z variant např. je, že v
uzlovém grafu tranzitivní relace pro každou oboustrannou šipku musí
platit, že musí mít na obou koncích smyčky. Je-li relace R zadána
výčtem prvků, je velmi užitečné následující tvrzení: Relace R je
tranzitivní, právě když platí R o R  R.
Definice Nechť R je binární relace v množině M. Pak řekneme, že tato
relace je souvislá (ve zkratce SO), jestliže platí
(x, y x  y  ([x, y] R  [y, x] R).
Poznámka V uzlovém grafu souvislé relace musí být každé dva různé
prvky množiny M spojeny buďto jednoduchou šipkou nebo
obostrannou šipkou. Na počtu smyček v grafu nezáleží. Aby relace
nebyla souvislá (ve zkratce 𝑆𝑂), musí platit negace definice, tedy musí
platit (x, y x  y [x, y] R  [y, x] R). V uzlovém grafu
tedy stačí k vyloučení souvislosti dané relace existence jediné dvojice
prvků nespojených šipkou.
Příklady: Velmi názorný ilustrační příklad pochází z publikace L.
Skuly:
Nechť a) až i) jsou následující relace:
a) M = {a, b, c, d}, R = {[a, b], [a, c], [c, a], [b, c], [c, c]}.
b) M  , R = . Prázdná relace na M (žádný prvek není v relaci
s žádným).
c) M  , R = M  M. Univerzální relace (každý prvek je v relaci
s každým).
d) M  , R = {[x, x], x  M}. Relace rovnosti (každý prvek je v
relaci jen sám se sebou).
e) M je množina všech obyvatel města Brna, R = {[x, y], x  M,
y  M; osoby x, y jsou narozeny ve stejném měsíci}.
f) M je množina N všech přirozených čísel, R je relace dělitelnosti na
N (uspořádaná dvojice přirozených čísel [x, y]  R, právě když x y).
g) M je množina všech trojúhelníků v rovině, R je relace podobnosti ~
(dva trojúhelníky jsou v relaci, právě když jsou podobné).
h) M je množina všech trojúhelníků v rovině, R je relace shodnosti 
(dva trojúhelníky jsou v relaci, právě když jsou shodné).
i) Nechť X je neprázdná množina, nechť M = P (X). Pak M  , R je
relace inkluze  na množině M (uspořádaná dvojice množin
[A, B]  R, právě když A  B).
Vlastnosti relací a) až i) jsou uvedeny v následující tabulce. Symbol +
značí, že daná relace uvedenou vlastnost má a symbol  značí, že tuto
vlastnost nemá.
a b c d e f g h i
Reflexivita   + + + + + + +
Antireflexivita  +       
Symetrie  + + + +  + + 
Antisymetrie  +  1 +  +   +
Tranzitivita  + + + + + + + +
Souvislost   +  2      3
 1 Je-li M jednoprvková množina, pak univerzální relace na M je
antisymetrická; pro víceprvkové množiny M nikoliv.
 2 Je-li M jednoprvková množina, pak relace rovnosti na M je
souvislá; pro víceprvkové množiny M nikoliv.
 3 Relace inkluze je na množině M = 2X
souvislá, právě když
množina X je jednoprvková.
Ekvivalence a uspořádání
Relace ekvivalence a rozklad množiny
Poznámka Nyní se budeme zabývat speciálními relacemi
definovanými na množině M, a to relacemi ekvivalence a uspořádání.
Definice Nechť M je neprázdná množina, nechť R je relace na
množině M, která je reflexivní, symetrická a tranzitivní. Pak tato
relace se nazývá relace ekvivalence. Nechť platí [x, y]  R. Pak
řekneme, že prvky x, y jsou ekvivalentní a píšeme x  y.
Příklad Nechť M = {a, b, c, d}. Pak následující relace jsou relace
ekvivalence na M:
a) E1 = {[a, a], [b, b], [c, c], [d, d], [a, c], [c, a], [b, d], [d, b]}
b) E2 = {[a, a], [b, b], [c, c], [d, d], [a, b], [b, a]}
c) E3 = {[a, a], [b, b], [c, c], [d, d], [b, c], [c, b], [b, d], [d, b], [c, d], [d, c]}
d) E4 = {[a, a], [b, b], [c, c], [d, d]}
e) E5 = M  M
Poznámka Z uzlových grafů všech pěti ekvivalencí z předchozího
příkladu (náčrt si proveďte sami) je patrné, že tyto uzlové grafy nejsou
souvislé (kromě relace E5), ale že jistým způsobem “rozdělují” prvky
množiny M do skupin. To nás vede k následující definici.
Definice Nechť M je neprázdná množina. Pak systém
T = {A1, A2, A3, … , An} podmnožin množiny M nazveme rozklad
množiny M, právě když platí:
(i) Ai   pro každý index i {1, 2, 3, … , n},
(ii) A1  A2 A3  …  An = M,
(iii) Ai  Aj = pro každou dvojici indexů i, j {1, 2, 3, … , n}.
Poznámka Všechny tři podmínky předchozí definice lze slovně
formulovat takto:
Rozklad množiny M je systém neprázdných podmnožin množiny M s
vlastností, že každý prvek množiny M patří právě do jedné z těchto
podmnožin.
Zvýrazněná slova vyjadřují tři podmínky předchozí definice.
Příklad Nechť M = {a, b, c, d}. Pak následující systémy jsou rozklady
množiny M:
a) T1 = {{a, c}, {b, d}}
b) T2 = {{a, b}, {c}, {d}}
c) T3 = {{a}, {b, c, d}}
d) T4 = {{a}, {b}, {c}, {d}}
e) T5 = {{a, b, c, d}}
Poznámka Prohlédnete-li si znovu uzlové grafy ekvivalencí z
předchozího příkladu, uvidíte, že bloky (třídy rozkladu), na které jsou
tyto uzlové grafy rozloženy, odpovídají rozkladům množiny M
uvedeným v předchozím příkladu. To vede k následující větě.
Věta Nechť M je neprázdná množina, nechť E je relace ekvivalence
na množině M. Pro každé x  M označme Ax množinu všech prvků
množiny M, které jsou ekvivalentní s prvkem x, tedy
Ax = {y ∈ M; [x, y] } = {y ; x ~ y}. Potom system
T = {Ax; x  M} je rozklad množiny M. Prvky systému T se nazývají
třídy rozkladu množiny M.
Definice Rozklad T množiny M z předchozí věty se nazývá rozklad
množiny M příslušný ekvivalenci E. Někdy užíváme též názvu
rozklad indukovaný ekvivalencí E nebo rozklad generovaný
ekvivalencí E.
Poznámka Tvrzení věty říká, že každá ekvivalence E na množině M
jednoznačně generuje rozklad této množiny. Toto tvrzení platí i
naopak, tzn. každý rozklad množiny M jednoznačně generuje
ekvivalenci E na množině M. To je obsahem následující věty.
Věta Nechť T je rozklad neprázdné množiny M. Potom binární relace
definovaná následujícím způsobem
E ={[x, y]  M; ∃ X  T: x  X ∧ y  X} je relace ekvivalence
na množině M.
Definice Ekvivalence E na množině M z předchozí věty se nazývá
ekvivalence na množině M generovaná (nebo též indukovaná)
rozkladem T této množiny.
Relace uspořádání a uspořádané množiny
Definice Nechtˇ M je neprázdná množina. Nechť R je relace v
množině M, která je antisymetrická a tranzitivní. Pak se tato relace
nazývá uspořádání (v množině M). Je-li navíc relace R souvislá,
nazývá se lineární uspořádání. Je-li relace R reflexivní, nazývá se toto
uspořádání neostré, v případě antireflexivnosti relace R je toto
uspořádání ostré.
Poznámka 2. 65 Z předchozí definice plyne, že kombinací
„přívlastků“ lineární, ostré a neostré lze definovat celkem šest typů
relací uspořádání v množině M. Přehledně je nyní uvedeme s využitím
zavedených zkratek pro jednotlivé vlastnosti relací:
Nelineární ostré uspořádání v M má vlastnosti AS, T, 𝑆𝑂, AR;
Nelineární neostré uspořádání v M má vlastnosti AS, T, 𝑆𝑂, R;
Nelineární uspořádání v M, které není ostré ani neostré, má vlastnosti
AS, T, 𝑆𝑂, 𝑅, 𝐴𝑅;
Ostré lineární uspořádání v M má vlastnosti AS, T, SO, AR;
Neostré lineární uspořádání v M má vlastnosti AS, T, SO, R;
Lineární uspořádání v M, které není ostré ani neostré, má vlastnosti
AS, T, SO, 𝑅, 𝐴𝑅.
Místo nelineární uspořádání se někdy říká též částečné uspořádání.
Poznámka Relace uspořádání se někdy označuje některým z běžně
užívaných symbolů , , , . V tom případě se např. místo zápisu
[x, y]užívá zápis x y. Tento zápis pak chápeme ve smyslu, že
prvek x předchází v relaci uspořádání před prvkem y.
Příklad a) Nechť M = {a, b, c, d}. Pak následující relace jsou relace
uspořádání na M:
a) U1 = {[a, a], [b, b], [c, c], [d, d], [a, c], [b, d]} je neostré nelineární
uspořádání;
b) U2 = {[a, b]} je ostré nelineární uspořádání;
c) U3 = {[a, a], [b, c], [b, d], [c, d]} je nelineární uspořádání, které
není ostré ani neostré;
d) U4 = {[a, a], [b, b], [c, c], [d, d]} je neostré nelineární uspořádání.
Toto uspořádání na množině M je jediné, které je současně
ekvivalencí na množině M;
e) U5 = {[a, a], [b, b], [c, c], [d, d], [b, c], [c, d], [b, d], [b, a], [c, a], [d,
a]} je neostré lineární uspořádání;
f) U6 = {[c, d], [c, a], [c, b], [d, a], [d, b], [a, b]} je ostré lineární
uspořádání;
g) U7 = {[d, d], [a, d], [c, c], [a, b], [d, c], [d, b], [c, b]} je lineární
uspořádání, které není ostré ani neostré.
Příklad Nechť N je množina všech přirozených čísel, nechť relace
na množiněN označuje přirozené uspořádání všech přirozených
čísel podle velikosti. Pak je ostré lineární uspořádání.
Poznámka Obsahem předmětu matematika na 1. stupni základní
školy je zejména množina přirozených čísel, jejich vlastnosti a
operace s nimi. Proto podle předchozí poznámky je nejdůležitějším
typem uspořádání, kterým se nadále budeme zabývat, ostré lineární
uspořádání.
Definice Nechť M je neprázdná množina, nechť U je relace
uspořádání v množině M. Pak uspořádaná dvojice (M, U) se nazývá
uspořádaná množina. Množina M je pole uspořádané množiny.
Uspořádaná množina se též označuje [M]. Názvy uspořádaných
množin lze upřesnit podle typů uspořádání, např. nelineárně
uspořádaná množina, ostře lineárně uspořádaná množina apod.
Poznámka Charakterizaci konečných, ostře lineárně uspořádaných
množin, lze vyslovit takto: V konečné, ostře lineárně uspořádané
množině, má každý její prvek jednoznačně stanovené pořadí.
Poznámka Nyní zavedeme jednodušší, zkrácený zápis pro konečné,
ostře lineárně uspořádané množiny. Nechť např. (K, U) je ostře
lineárně uspořádaná množina definovaná takto:
(K, U) = ({a, b, c, d}, {[c, d], [c, a], [c, b], [d, a], [d, b], [a, b]}).
Tento zápis však je nepřehledný a neposkytuje přehlednou informaci o
pořadí jejích prvků. Využijeme toho, že místo zápisu
[x,y] užíváme zápis x y. Proto lze psát [K] = {c, d, a, b}v
tomto zápise vypíšeme do složených závorek prvky pole uspořádané
množiny v tom pořadí, které je definováno relací ostrého lineárního
uspořádání na dané množině. V dalších úvahách se ukáže výhodnost
tohoto zkráceného zápisu.
Definice Nechť [K] je ostře lineárně uspořádaná konečná množina.
Prvek a [K] se nazývá první prvekmnožiny[K], jestliže platí:
x [K]) x  a  a  x. Ve slovním vyjádření má první prvek ostře
lineárně uspořádané množiny tu vlastnost, že předchází před všemi
ostatními prvky této množiny.
Definice Nechť [K] je ostře lineárně uspořádaná konečná množina.
Prvek b [K] se nazývá poslední prvekmnožiny[K], jestliže platí:
x [K]) x  b  x  b. Ve slovním vyjádření má poslední prvek
ostře lineárně uspořádané množiny tu vlastnost, že jej předchází
všechny ostatní prvky této množiny.
Poznámka Vidíme, že označení první a poslední prvek má stejný
význam, jaký známe z běžného života. Představíme-li si konečnou
ostře lineárně uspořádanou množinu jako frontu osob např. v
supermarketu u pokladny, pak první je ten, který stojí před všemi
ostatními, zatímco poslední je ten, před kterým stojí všichni ostatní. S
pojmem první prvek souvisí poslední definice této části.
Definice Nechť [M] je ostře lineárně uspořádaná množina (konečná
nebo nekonečná). Pak řekneme, že tato množina je dobře uspořádaná a
uspořádání na této množině nazveme dobré uspořádání, jestliže každá
neprázdná podmnožina množiny [M] má první prvek.
Věta Nechť [M] je konečná, ostře uspořádaná množina. Pak platí:
Množina [M] je lineárně uspořádaná  množina [M] je dobře
uspořádaná. Každá konečná ostře lineárně uspořádaná množina je tedy
dobře uspořádaná a naopak, každá konečná dobře uspořádaná množina
je ostře lineárně uspořádaná. Tuto větu oceníme později.
ZOBRAZENÍ
Pojem zobrazení je jedním z nejdůležitějších pojmů současné
matematiky s aplikacemi už v učivu matematiky 1. stupně ZŠ.
Definuje se na střední škole jako speciální typ binární relace.
Definice Nechť A, B jsou množiny. Binární relace f  A  B
z množiny A do množiny B se nazývá zobrazení z množiny A do
množiny B, jestliže ke každému prvku x  A existuje nejvýše jeden
prvek y  B takový, že [x, y] ∈ R.
Poznámka Zobrazení z množiny A do množiny B lze chápat jako
jistý předpis, který každému prvku z množiny A přiřadí nejvýše jeden
prvek z množiny B (tzn. jeden nebo žádný).
Je-li f zobrazení z množiny A do množiny B, budeme často používat
zápis f : A  B a místo zápisu [x, y] ∈ f budeme psát f (x) = y.
V tomto případě prvek x se nazývá vzor prvku y a prvek y se nazývá
obraz prvku x. Množina A se nazývá definiční obor zobrazení
f : A  B a označuje se D(f). Množina všech obrazů všech prvků
množiny A, tj. množina {y  B; ∃x  A: f (x) = y} se nazývá obor
hodnot zobrazení f : A  B a označuje se H(f). Je-li v definici
zobrazení A = B, pak hovoříme o zobrazení v množině A.
Příklad Nechť A = {a, b, c} a B = {u, v}. Nechť f, g jsou binární
relace z množiny A do množiny B definované takto: f = {[a, v], [b, v],
[c, u]}, g = {[a, u], [b, v], [b, u], [c, v]}.
Vidíme, že ke každému prvku x  A existuje právě jedno y  B s
vlastností [x, y]  f . To znamená, že binární relace f je zobrazení
z množiny A do množiny B. U relace g si povšimněte, že prvek b  A
se zobrazí na prvek u  B a současně na prvek v  B. Proto binární
relace g není zobrazením z množiny A do množiny B.
Poznámka Protože zobrazení je speciální případ binární relace, je
možno využít všechny způsoby zadání i znázornění binárních relací.
Zobrazení lze tedy zadat výčtem uspořádaných dvojic nebo pomocí
výrokové formy o dvou proměnných (tedy předpisem, podle kterého
přiřadíme každému vzoru jeho obraz). Např. nechť f je zobrazení
z množiny Z všech celých čísel do množiny N0 všech přirozených
čísel předpisem f(x) =  x , které každému celému číslu přiřadí jeho
absolutní hodnotu.
U grafického znázornění zobrazení lze využít kartézské i uzlové
grafy, analogicky jako u binárních relací.
Poznámka Definiční obor zobrazení f z množiny A do množiny B
může být roven množině A nebo může být její vlastní podmnožinou,
stejně tak obor hodnot tohoto zobrazení může být roven množině B
nebo může být vlastní podmnožinou této množiny (připomeňme
analogické možnosti u prvního a druhého oboru binární relace). Podle
toho, který případ nastane, rozlišujeme čtyři možné typy zobrazení.
Definice Nechť f je zobrazení z množiny A do množiny B.
1. Nechť D(f)  A, D(f)  A, H(f)  B, H(f)  B. Pak f se nazývá
zobrazení z množiny A do množiny B.
2. Nechť D(f) = A, H(f)  B, H(f)  B. Pak f se nazývá zobrazení
množiny A do množiny B.
3. Nechť D(f)  A, D(f)  A, H(f) = B. Pak f se nazývá zobrazení
z množiny A na množinu B.
4. Nechť D(f) = A, H(f) = B. Pak f se nazývá zobrazení množiny A na
množinu B.
Poznámka V případě 1. předchozí definice je název zobrazení totožný
s obecným názvem zobrazení podle definice 3. 1. Zde však předložky
„z“ a „do“ mají význam, který určuje typ tohoto zobrazení. V případě
2. a 4. se někdy užívá názvu zobrazení celé množiny A do množiny B
(na množinu B). Doporučujeme používat tento delší název, neboť
vypuštění předložky „z“ z definice podstatně mění informaci o typu
zobrazení. Poznamenejme ještě, že v řadě publikací se zobrazení z
množiny A (případ 1. a 3.) vůbec nedefinuje a každé zobrazení se
rozumí jako zobrazení celé množiny A. My však budeme v dalším
studiu důsledně oba typy rozlišovat (zobrazení množiny A i zobrazení
z množiny A).
Příklad Nechť A = {a, b, c} a B = {u, v}. Nechť f, g, h, k jsou binární
relace z množiny A do množiny B definované takto:
f = {[a, v], [b, v], [c, u]},
g = {[a, u], [b, v]},
h = {[a, v], [b, v], [c, v]},
k = {[a, u], [b, u]}.
Pak f je zobrazení celé množiny A na množinu B, g je zobrazení
z množiny A na množinu B, h je zobrazení celé množiny A do
množiny B a k je zobrazení z množiny A do množiny B.
Definice Nechť f je zobrazení z množiny A do množiny B. Nechť
každým dvěma různým prvkům množiny A jsou přiřazeny dva různé
prvky množiny B. Pak zobrazení f je prosté zobrazení z množiny A do
množiny B. Někdy se též užívá zkrácené formulace, podle níž
v prostém zobrazení každé dva různé vzory mají různé obrazy.
Poznámka Formálně lze definice prostého zobrazení vyjádřit takto:
( x, y  A) x  y  f(x)  f(y), nebo též v obměněném tvaru
( x, y  A) f(x) = f(y)  x = y.
Definice Nechť f je zobrazení z množiny A do množiny B. Nechť f1
je inverzní relace k relaci f z množiny B do množiny A (ve smyslu
inverzní relace definované v předchozím textu). Je-li tato relace f1
zobrazením, pak se nazývá inverzní zobrazení k zobrazení f.
Definice Nechť f je zobrazení z množiny A do množiny B. Pak
zobrazení f je prosté zobrazení, právě když inverzní relace f1
je
zobrazení z množiny B do množiny A.
Příklad Nechť f, g, h, k jsou zobrazení definovaná dříve. Pak inverzní
relace k těmto zobrazením jsou následující:
f1
= {[v, a], [v, b], [u, c]},
g1
= {[u, a], [v, b]},
h1
= {[v, a], [v, b], [v, c]},
k1
= {[u, a], [u, b]}.
Je ihned vidět, že relace f1
, h1
, k1
nejsou zobrazení, zatímco g1
je
zobrazení množiny B do množiny A. Zobrazení g tedy je prosté
zobrazení, zatímco zobrazení f, h, k prostá nejsou.
Poznámka Místo názvu prosté zobrazení se často užívá názvu
injektivní zobrazení. Jsou-li množiny A, B konečné, pak existence
injektivního zobrazení z množiny A do množiny B vynucuje, že počet
prvků množiny B musí být větší nebo roven počtu prvků množiny A.
Poznámka Pro zobrazení na množinu B (typy 3. a 4. definice) se
často užívá názvu surjektivní zobrazení (čti „syrjektivní“). Jsou-li
množiny A, B konečné, pak existence surjektivního zobrazení
z množiny A na množinu B vynucuje, že počet prvků množiny B musí
být menší nebo roven počtu prvků množiny A.
Definice Nechť f je zobrazení celé množiny A na množinu B, které je
prosté. Pak f se nazývá vzájemně jednoznačné zobrazení množiny A
na množinu B. Množiny A, B jsou v tomto případě ekvivalentní,
píšeme A ~ B. Je-li navíc A = B, pak se prosté zobrazení celé množiny
A na množinu A nazývá permutace množiny A.
Poznámka Místo českého názvu vzájemně jednoznačné zobrazení
množiny A na množinu B se užívá též názvu bijektivní zobrazení
množiny A na množinu B. Jsou-li množiny A, B konečné, pak
existence bijektivního zobrazení množiny A na množinu B vynucuje,
že počet prvků množiny B musí roven počtu prvků množiny A. Dvě
ekvivalentní konečné množiny tedy mají stejný počet prvků.
Poznámka Pro nekonečné množiny je situace složitější (pojem počet
prvků nekonečné množiny nemá smysl). Uvedeme příklad: Nechť N
je množina všech přirozených čísel, nechť S je množina všech
nenulových sudých čísel. Platí tedy N = {1, 2, 3, …}, S = {2, 4, 6, …}.
Nechť f je zobrazení množiny N na množinu S definované takto:
(x  N) f(x) = 2x. Pak zřejmě zobrazení f je vzájemně jednoznačné
zobrazení celé množiny N na množinu S. Platí tedy N ~ S, přestože S
je vlastní podmnožina množiny N (S  N, S  N).
Poznámka Tuto vlastnost nekonečných množin (nekonečná množina
může být ekvivalentní se svou vlastní podmnožinou), uvedenou
v předchozí poznámce, lze užít k definici konečné a nekonečné
množiny. Povšimněme si důležitý fakt, že následující definice definují
konečnou a nekonečnou množinu bez použití obratu „počet prvků“.
Tento aspekt oceníme později při konstrukci oboru všech přirozených
čísel.
Definice Množina je nekonečná, je-li ekvivalentní s nějakou svou
vlastní podmnožinou. Množina je konečná, není-li ekvivalentní
s žádnou svojí vlastní podmnožinou.
Poznámka Definovali jsme permutaci množiny A jako prosté
zobrazení množiny A na množinu A. Nyní se budeme podrobněji
věnovat permutacím konečných množin. Nejprve zavedeme vhodné
označení:
Poznámka Nechť A je konečná množina, nechť p je permutace
množiny A, tzn. prosté zobrazení množiny A na množinu A. Nechť
A = {a1, a2, …, an}, nechť permutace p je dána výčtem prvků takto:
p = {[a1, p(a1)], [a2, p(a2)], …, [an, p(an)]}. Pak tuto permutaci budeme
zapisovat ve formě dvouřádkové tabulky (tzv. matice) takto:
p = (
𝑎1 ⋯ 𝑎 𝑛
𝑝( 𝑎1) … 𝑝( 𝑎 𝑛)) .
Do horního řádku tabulky zapíšeme všechny prvky množiny A
(vzory), do spodního řádku zapíšeme jejich obrazy v permutaci p.
Věta Nechť množina A je konečná a má n prvků. Pak existuje n!
různých permutací množiny A.
Příklad Nechť A = {1, 2, 3}. Pak na množině A existuje 6 permutací:
a = (
1 2 3
2 1 3
), b = (
1 2 3
1 3 2
), c = (
1 2 3
3 2 1
)
d = (
1 2 3
2 3 1
), e = (
1 2 3
1 2 3
), f = (
1 2 3
3 1 2
).
Definice Nechť f je zobrazení z množiny A do množiny B a g nechť je
zobrazení z množiny B do množiny C. Potom binární relace f o g
z množiny A do množiny C definovaná vztahem
f o g = {[x, y]  A  C; z  B : [x, z]  f ∧ [z, y] g}
je také zobrazení. Toto zobrazení nazýváme složené zobrazení ze
zobrazení f a g (v tomto pořadí).
Poznámka Protože zobrazení je speciální typ binární relace, je
skládání zobrazení definováno stejně jako skládání relací. Při skládání
zobrazení f o g nejprve aplikujeme zobrazení f a potom zobrazení g.
Z definice složeného zobrazení vyplývá, že složené zobrazení ze
zobrazení f a g je možné definovat pouze tehdy, když obor hodnot
zobrazení f je podmnožinou definičního oboru zobrazení g.
Příklad Nechť A = {a, b, c, d}, B = {x, y, z}, C = {u, v}. Nechť
zobrazení f : A  B, g : B  C jsou zadána takto:
f = {[a, z], [b, z], [c, y], [d, x]}, g = {[x, u], [y, u], [z, v]}. Pak složené
zobrazení f o g je následující: f o g = {[a, v], [b, v], [c, u], [d, u]},
zatímco složené zobrazení g o f není definováno.
Poznámka Skládání zobrazení není obecně komutativní, a to ani
tehdy, jsou-li obě zobrazení f o g, g o f definována. Např. pro
permutace a, b na množině A = {1, 2, 3} z příkladu platí
a o b = (
1 2 3
3 1 2
) = f, b o a = (
1 2 3
2 3 1
) = d. Platí ale užitečné
tvrzení, které uvedeme bez důkazu.
Věta Nechť f, g, h jsou tři zobrazení taková, že všechna zapsaná
složená zobrazení jsou definována. Pak platí:
1. (f o g) o h = f o (g o h), tzn. skládání zobrazení je asociativní.
2. Jsou-li f, g prostá zobrazení, pak f o g je prosté zobrazení.
3. Jsou-li f, g zobrazení bijektivní, pak f o g je rovněž bijektivní.
4. Jsou-li f, g permutace množiny M, pak f o g je rovněž permutace
množiny M.
Poznámka Již jsme definovali 6 permutací množiny A = {1, 2, 3}.
Podle předchozí věty má smysl určit složené permutace pro každou
dvojici permutací a, b, c, d, e, f. Tyto složené permutace zapíšeme do
tabulky (v předchozím příkladu byla již jedna dvojice permutací
složena). S touto tabulkou budeme pracovat později.
o a b c d e f
a
b
c
d
e
f
e f d c a b
d e f a b c
f d e b c a
b c a f d e
a b c d e f
c a b e f d
Příklad Nechť Z je množina všech celých čísel. Nechť jsou dána dvě
zobrazení f, g v množině Z: f(x) =  x, g(x) = x + 1 pro každé x  Z.
Pak složená zobrazení jsou následující:
f o g (x) =  x + 1, g o f (x) = (x + 1) pro každé x  Z.