IBOOO Úvod do informatiky — príklady na procvičení Sada 5 — Zadání
Téma
Vlastnosti relací — relace reflexivní, symetrická, antisynietrikcá, tranzitivní. Ekvivalence na množině a rozklad množiny.
Příklad 1.
Určete, které z následujících relací jsou reflexivní, symetrické, antisymetrické resp. tranzitivní. Určete, které z relací jsou ekvivalence.
a)  R ={(1,1), (1,2), (1,3), (2, 2), (2,3), (3,3)} C M x M, kde M = {1,2, 3}.
b)  R= {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3)} C {1,2,3} x {1,2,3}.
c)  R ={(1,1), (1,2), (1,3), (2, 2), (2,3), (3,3)} C M x M, kde M = {1,2,3,4}.
d)  R = {(a, a), (b, b), (c, c)}
e)  i? = 0
f)  R= {(n,n+l) \neN}
g)  i? = {(m,n)GNxN| 5|ma 7\n} h) R = {(n, n + k) \ n,k eN}
í) R= {(n,n + k) j n, k e Z} ']) R = {(m,n) E Z x Z \ m ^ n}
Příklad 2.
Pro každou z množin Mo = 0, Mi = {a} a M3 = {a, b, c} určete počet relací i?C M,x Mi, které jsou
a)  reflexivní
b)  symetrické
c)  tranzitivní
Příklad 3.
Nechť A, B jsou množiny, / : A —► B funkce.  Uvažujme relaci R <Z A x A definovanou předpisem
R={(x,y)eAxA\f(x) = f(y)}
Rozhodněte, zda je tato relace ekvivalencí a své tvrzení dokažte.
Příklad 4.
Nechť A, B jsou množiny, S (^ Ax B funkce. Uvažujme relaci R C B x B definovanou předpisem
R = {(x, y) E B x B \ 3 a E A : (a, x) E S A (a, y) E S}
Rozhodněte, zda je tato relace ekvivalencí a své tvrzení dokažte.
Příklad 5.
Nechť R, S C M x M jsou antisymetrické relace. Rozhodněte, zda platí, že S o R a R~ľ jsou antisymetrické relace a svá tvrzení dokažte.
Příklad 6.
Rozhodněte, které z následujících systémů podmnožin množiny M = {1,2,3, 4, 5, 6} jsou rozkladem množiny M. U rozkladů vypište výčtem prvků příslušné ekvivalence.
a)  {{1,2,3}, {3,4}, {4,5,6}}
b)  {{1,2,6}, {3,5}, {4}}
c)  {{2,4,6},{1,5}}
d)  {{1,4,5},{2,3,6}}
Příklad 7.
Nechť A je množina. Uvažme systém S podmnožin množiny 2 , S = {Ma \ a E A}, kde pro a E A je Ma = {M C A \ a E M}.
Určete, zda se jedná o rozklad množiny 2 , své tvrzení dokažte, a pokud ano, definujte příslušnou ekvivalenci.
Příklad 8.
Nechť A je množina.  Definujme relaci R C 2    x 2    následovně: pro každé X,Y E 2
platí (X, Y) E R právě tehdy, když existuje bijekce / : X —► y.
Dokažte, že R je ekvivalence a nalezněte třídy ekvivalence příslušného rozkladu.
Příklad 9.
Nechť A, B jsou množiny, / : A —► B funkce. Definice funkce / se rozšiřuje na množiny podle následujícího předpisu
/(M) = {f(x) \xeM}
(Přestože funkce označujeme stejně, jedná se vlastně o dvě různé funkce. Původní / : A —► B a nově definovanou /' : 2 —► 2B. Stejné označení není na závadu — typ funkce, kterou máme na mysli, je jednoznačně určen tím, na jaký argument ji aplikujeme.)
Nechť A je množina.   Definujme množiny
MM C Aa, kde M C A, a systém S C 2A
následovně:
Mm = {/ | f (A) = M} S = {Mm I 0 ^ M C A}
Dokažte, že S je rozklad na A a určete příslušnou relaci ekvivalence. Byla by to pravda i v případě, kdy bychom uvažovali obecné funkce / : A —► B?
Nápověda: Pečlivě si uvědomujte, se kterou strukturou v kterém okamžiku pracujete. Například S je množina množin funkcí z A do A.