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é fc-tice prvků tak, že každým k prvkům a\,..., ak přiřadíme nový objekt (ai,..., ak), jejich uspořádanou fc-tici, s vyznačeným pořadím těchto prvků. Chceme-li tyto nové objekty vytvářet jen s použitím množin, můžeme použít následující definici. 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.
Dále s použitím indukce můžeme definovat uspořádanou fc-tici prvků se složkami ai,..., například následovně. Pro k = 2 jsme tak již učinili, a je-li k > 3, klademe
(a1,...,ak) = ((ai,... ,ak-i),ak),
kde používáme indukční předpoklad, tedy fakt, že pro k — 1 jsme tento objekt již zavedli, a dále použijeme ještě jednou předchozí konstrukci uspořádané dvojice. Opět pro libovolné prvky ai,...,afc, A platí
(ai,..., ak) = (h,..., bk)   <í=^   ai = &i & ... & ak = bk.
Nyní 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ě
1
všechny uspořádané dvojice (a, b), kde a G A, b G B. To znamená, že klademe
A x 5 = {(a, 6) | a G A & 6 G 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
(A x B) x C = {((a, b),c)\aeA k beB k ceC}, Ax(BxC) = {(a, (b,c))\aeA k beB k ceC}
jsou formálně různé. Nicméně rozdíl mezi objekty ((a, b),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 k b e B k c e C}.
Podobně pro každé k > 2 a libovolné množiny A\,..., Ak definujeme jejich kartézský součin A\ x • • • x A^ jako množinu
A1 x ■ ■ ■ x Ak = {(ai, ...,ak)\a1eA1k ... k ak G Ak}.
Vezmeme-li v úvahu předchozí induktivní konstrukci uspořádaných fc-tic, znamená to vlastně, že jsme kartézský součin A\ x • • • x Ak definovali jako součin (... (A\ x A2) x ...) x Ak, tedy s uzávorkováním odleva. Jestliže A\ = ■ ■ ■ = Ak = A, dostáváme tak definici kartézské mocniny Ak pro všechna k > 2. Navíc klademe také A1 = A a z důvodů, které budou vysvětleny později, definujeme ještě A° jako mmnožinu {0}. Platí řada jednoduchých rovností:
Tvrzení. Pro libovolné množiny A, B, C platí:
{A U B) x C = {A x C) U {B x C), {A n B) x C = {A x C) n {B x C), (A - B) x C = (A x C) - (B x C).
2
Analogické rovnosti platí i pro C x (A U B), C x (A n B) a C x (A - B).
Důkaz všech rovností je snadný.
Tvrzení. Pro libovolnou množinu C, pro libovolnou indexovou množinu / ^ 0 a pro libovolný soubor množin Ai, kde i E I, platí:
(U^) xC = \J(AixC),
i€l i€l
(f|4) xC = f](AixC).
i€l i€l
Důkaz je analogický jako pro systém dvou množin.
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 E A, b E B takové prvky, že (a, b) E 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.
Příklad. Buď A množina a buď V(A) potenční množina množiny A. Prvky množiny V(A) jsou podmnožiny X C A. Definujme podmnožinu g C A x V(A) takto:
g={(a,X) EAx V{Á) \ a E X}.
Pak g je relace mezi množinami A a V (A).
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
Bom g = {a E A \ (3b E B)(agb)},
3
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 £ B \ (3a £ A)(agb)},
tedy množinu všech těch prvků z B, s nimiž je v relaci g alespoň jeden prvek z A.
Definujeme skládání relací. Nechť A,B,C jsou množiny a nechť gCAxBarjCBxC jsou relace. V této situaci definujeme relaci r\ o g C A x C vzniklou složením relací g a r\ následujícím způsobem:
77 o g = {(a, c) £ A x C I (3b £ B)(agb k br]c)}.
Zápis ry o £> čteme „ry po g".
Příklad. Buď A množina. Uvažme opět její potenční množinu V(A). Prvky množiny V(A) jsou všechny podmnožiny X C A. Uvažme dále potenční množinu V (V (A)). Prvky množiny V(V(A)) jsou libovolné podmnožiny Q C V(A). Takové podmnožiny Q ale nejsou nic jiného než soubory některých podmnožin X C A. Pro každý takový soubor Q označme stručně U Q sjednocení souboru Q, to znamená sjednocení všech těch podmnožin X C A, které jsou prvky souboru Q.
V minulém příkladu jsme definovali relaci g C A x V (A) předpisem:
g={(a,X) £ A x V(Ä) \ a £ X}.
Definujme podobně relaci r\ C V (A) x V (V (A)) předpisem:
■n = {(X, Q) £ V (A) x V (V (A)) I X £ Q}.
Pak složená relace r\ o g C A x V(V(A)) má podle předchozí definice tvar:
^og = {(a, Q) £ AxV(V(A)) \ (3X£ V(A))(a £XkX £ Q)},
4
což podle definice sjednocení [j Q znamená, že tato relace je dána předpisem:
V o g = {(a, Q) E A x V (V (A)) \ a E (J Q}-
Skládání relací je asociativní:
Tvrzení. Nechť A, B, C, D jsou množiny a nechť g C Ax B, t]CBxC,iiCCxD jsou relace. Pak platí:
(j/o 77) o g = /i o (770 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 £> C /i o (77 o £>). Nechť tedy a E A, d E D jsou takové prvky, že (a, d) E (n°ri)og. Pak podle definice skládání relací existuje prvek b E B takový, že (a, b) E g & (b,d) E /jot). Opět podle téže definice existuje prvek c E C takový, že (b, c) E 77 a (c, d) E [i. Pak ovšem (a, c) G 77 o £>, takže (a, d) G /i o (77 o g). Opačná inkluze /i o (77 o g) C (/i o 77) o £> se dokáže analogicky.
Ke každé relaci g mezi množinami A a B definujeme inverzní relaci g-1 mezi množinami B a A následovně:
g'1 = {(b, a) E B x A \ agb}.
To znamená, že platí
(VaEA)(VbEB)(agb <^ b g'1 a).
Odtud okamžitě plyne, že Dom p"1 = Im^, Im^-1 = Dom g. Dále je jasné, že platí
(Q'1)'1 = Q-
Navíc mezi skládáním relací a inverzními relacemi existuje následující souvislost:
5
Tvrzení. Nechť A, B, C jsou množiny a nechť g C A x B, r] C B x C jsou relace. Pak platí:
(r] o g)'1 = g'1 o r]'1.
Důkaz. Na obou stranách této rovnosti jsou relace mezi množinami C a A. Dokážeme inkluzi (rj o (o)_1 C g~l o ri~l. Nechť a E A, c E C jsou takové prvky, že (c, a) E (r] o g)-1. Pak (a, c) E r\ o g. To znamená, že existuje prvek b E B takový, že (a, b) E g a (6, c) G ry. Odtud plyne, že (6, a) G £>-1 a (c, 6) G ry-1, takže pak (c, a) G £>_1 o ry-1. Opačná inkluze g-1 o ry-1 C ry o (o)~1 se dokáže obdobně obráceným postupem.
6