Ekvivalence a rozklady
Nechť A je množina a nechť n > 1 je přirozené číslo. Pak libovolnou podmnožinu g kartézské mocniny An nazýváme n-ární relací na množině A. Je-li n = 1, pak prostě g je podmnožinou množiny A a říkáme též, že g je unární relace na A. Je-li n = 2, tedy je-li g C A2, říkáme, že g je binární relace na A. Podobně je-li n = 3, tedy je-li g C A3, říkáme, že £> je ternární relace na A, atd. Významnou roli ovšem hrají binární relace. Proto řekneme-li pouze, že g je relace na A, budeme tím mít na mysli, že g je binární relace na A.
Pro libovolnou množinu A je identické zobrazení id a relací na množině A, v této souvislosti se značí též A^, takže máme Aa = {(a, a) | a G A}, a nazývá se diagonální relace na A.
Relace g na A se nazývá reflexivní, je-li splněno C g, tedy platí-li
(Va G A) (a g a).
Relace g na A se nazývá symetrická, je-li splněno g = £>_1, tedy platí-li
(\/a,b E A)(a gb ==ŕ b g a).
Relace g na A se nazývá asymetrická, je-li splněno ^fl^-1 = 0, tedy platí-li
(Va,6 G A)(agb ==r b$a).
Relace g na A se nazývá antisymetrická, je-li splněno g n g~l C A,4, tedy platí-li
(\/a,b E A)(a gb Sz bga  ==r  a = b).
Relace g na A se nazývá tranzitivní, je-li splněno g o g C g, tedy platí-li
(Va, b, c E A)(a g b Sz bgc ==ŕ  a g c).
1
Relace 9 na množině A, která je současně reflexivní, symetrická a tranzitivní, se nazývá ekvivalence na A. Jsou-li prvky a, b G A takové, že a 6 b, říkáme, že prvek a je ekvivalentní prvku b podle 9.
Příklad. Nechť A, B jsou množiny a nechť / : A —y B je zobrazení. Definujme relaci ker / na A předpisem:
(Va,6 G A)((a,b) G ker/ ^ f(a) = f(b)).
Pak ker / je ekvivalence na A a nazývá se jádro zobrazení /.
Pro libovolnou množinu A je diagonální relace nejmenší ekvivalence na A a univerzální relace A x A je nej větší ekvivalence na A.
Buď A množina. Připomeňme, že podmnožiny Q C V (A) chápeme jako soubory podmnožin množiny A a že pro každý takový soubor Q značíme krátce [j Q sjednocení souboru Q, to znamená sjednocení všech podmnožin X C A, které jsou prvky souboru Q.
Buď A množina a buď 1Z C V (Ä) libovolný soubor podmnožin množiny A splňující podmínky:
(VX,F ell){x ^ Y => xnľ = |), \jn = A.
Pak 1Z se nazývá rozklad množiny A. Množiny, jež jsou prvky TZ se nazývají třídy rozkladu 1Z. Názorně řečeno, rozklad 1Z reprezentuje rozdělení množiny A na soubor neprázdných vzájemně disjunktních tříd.
Příklad. Nechť A, B jsou množiny a nechť / : A —y B je zobrazení. Pro libovolný prvek b G f (A) definujme množinu
f-\b) = {aeA\b = f(a)}. 2
Pak soubor množin
{f-\b) | b e f (A)}
tvoří rozklad množiny A. Říkáme, že jde o rozklad množiny A indukovaný zobrazením /.
Pro libovolnou množinu A jsou soubory množin {{a} | a G A} a {A} rozklady množiny A.
Buď 0 ekvivalence na množině A. Pro každý prvek a E A definujeme množinu
[a]0 = {b E A \ a 9 b}.
Tato množina se nazývá třída ekvivalence 0 určená prvkem a.
Tvrzení. Buď 0 ekvivalence na množině A. Pak pro kterékoliv dva prvky a, b G A platí:
a G [a]0,
[a]en[b]e^(b <^ [a]e=[b]e <^ a eb.
Důkaz. Pokud jde o první řádek, poněvadž 0 je reflexivní, je a 0 a, takže a G [a]6. Dokážeme dále ekvivalenci tří podmínek uvedených na druhém řádku.
Nechť nejprve [a]0 n [b]6 ^ 0. Pak existuje c G [a]0 n [b]0, takže máme a0c a b0c. Ze symetrie 0 pak plyne také c0b a z tranzitivity 0 odtud plyne a 0 b.
Nechť dále a 0 b. Pak ze symetrie 0 plyne také b 0 a. Ukážeme, že odtud vyplývá inkluze [a]0 C [b]0. Nechť d E [a]0. Pak máme a 0 d a opět z tranzitivity # dostáváme b 0 d, takže d E [b]0. Analogicky se ověří inkluze [b]0 C [a]#, takže celkem platí rovnost [a]0 = [b]0.
Konečně je-li [a]0 = [b]0, pak ovšem [a]0 fl [b]0 ^ 0, neboť obě tyto třídy jsou neprázdné. Jsou tedy uvedené tři podmínky navzájem ekvivalentní.
3
Z právě dokázaného tvrzení je vidět, že soubor množin
A/9= {[a]9 \ a E A}
tvoří rozklad množiny A. Mluvíme o rozkladu podle ekvivalence 9, nebo též o faktorové množině ekvivalence 9 na A. Volně řečeno, pořídili jsme rozklad množiny A na třídy prvků vzájemně ekvivalentních podle 9.
Poznamenejme, že faktorová množina A/Aa je rovna rozkladu {{a}\ a E A} a faktorová množina A /AxA je rovna rozkladu {Á}.
Příklad. Nechť A, B jsou množiny a nechť / : A —y B je zobrazení. Pak faktorová množina A/ker / je právě výše popsaný rozklad množiny A indukovaný zobrazením /. Navíc pro obraz f(Á) při tomto zobrazení platí
f (A) = A/ker/.
Skutečně je vidět, že zobrazení
C : A/kevf ->• f (A)
dané pro každé a E A předpisem
C([a]ker/) =f(a)
je korektně definováno, neboť pro každá a, b E A platí
[a]ker/ = [6]ker/ ^ f(a) = f(b),
a z téhož důvodu je £ také bijekce uvedených dvou množin.
Buď nyní 1Z rozklad množiny A. Definujeme relaci =-ji na množině A předpisem
{\/a,bEA)(a =nb ^ {3X eK){a,beX)).
4
Pak z toho, že 1Z je rozklad množiny A, bezprostředně plyne, že =11 je ekvivalence na A. Názorně řečeno, tuto ekvivalenci jsme pořídili tak, že dva prvky a, b 6 A jsou ekvivalentní podle =-ji právě když leží ve stejné třídě rozkladu 1Z. Mluvíme o ekvivalenci na A příslušné rozkladu 1Z.
Ukážeme, že popsaná korespondence mezi ekvivalencemi na množině A a rozklady množiny A je vzájemně jednoznačná. Označme S (A) množinu všech ekvivalencí na A a II (A) množinu všech rozkladů množiny A.
Věta. Buď A množina. Pak zobrazení
<p : S (A) U{A)
dané pro každou ekvivalenci 6 na A předpisem
m = A/e
a zobrazení
V> : n (A) ->• £(A) dané pro každý rozklad 1Z množiny A předpisem
jsou vzájemně inverzní bijekce množin S(A) a II(A).
Důkaz. Podle první věty z kapitoly o zobrazeních stačí ověřit, že platí rovnosti
ý o ip = idS(A) a foip = idu{A).
K ověření těchto rovností se ovšem stačí přesvědčit, že pro libovolnou ekvivalenci 6 na A a pro libovolný rozklad 1Z množiny A platí
=A/e = 0 a A/=n = 1Z. Obojí jsou ale jednoduchá cvičení.
5
Konstrukce racionálních čísel
Ukážeme, jak s pomocí ekvivalencí a rozkladů lze z množiny
N = {1,2,3,...}
všech přirozených čísel a z množiny
Z = {...,-2,-l,0,l,2,...}
všech celých čísel sestrojit množinu Q všech racionálních čísel. Racionální čísla jsou zlomky tvaru |, kde p G Z a q G N. Přitom pro libovolná p, s£Zag,í GN platí:
p s
- = - <í=^ p-t = s-q, q t
kde p-t, s-q G 7L. To vede k myšlence definovat na množině Z x N relaci « následovně. Pro libovolná p, s£Zag,í GN klademe
(p,g) « (s,í) <í=^ p-í = s-q.
Snadno se lze přesvědčit, že pak « je ekvivalence na množině Z x N. Vzniká faktorová množina Z x N/~. Přitom z použité definice relace ~ plyne, že zobrazení
£ : Q    Z x N/w
dané pro každá p G Z a g G N předpisem
je korektně definováno a je to bijekce mezi množinami Q a ZxN/~. Nabízí se tedy možnost konstruovat množinu Q tak, že ji položíme přímo rovnu faktorové množině Z xN/~.
6