1. Dokážte, že následující zobrazení jsou bijektivní:
(a) f : N x N — N, f (x, y) = 2f-1(2y - 1),
(b) f :(a,b) - R+,f (x) = f-f.
Udejte predpis inverzních zobrazení.
2. Pro disjunktní mnoziny A a B dokazte, ze zobrazení f : P (A U B) — P (A) x P (B) definovane předpisem f (X) = (X n A, X n B) je bijekce. Naleznete zobrazení inverzní.
Relace
• (Binární) relaci mezi mnozinami A a B definujeme jako podmnozinu R C A x B.
• Obecne R C Ai x A2 x • • • x An
• Zobrazení f : A — B odpovídí relaci R f C A x B s vlastností, ze pro libovolne a G A existuje prave jedno b G B, tak ze (a, b) G Rf.
• Skládání relací R C A x B a S C B x C se definuje predpisem
S o R = {(a, c) G A x C; 3 b G B; (a, b) G R, (b, c) G S} S o R C A x C.
• S o R C A x C, T C C x D, pak platí T o (S o R) = (T o S) o R.
• idB o R = R = R o idA
• Inverzní relace R-1 k realci R C A x B se definuje jako R-1 = {(b, a); (a, b) G R}.
Platí R-1 C B x A. Zrejme Rf-i = R-1.
Vlastnosti relací:
Pokud R C A x A, pak ríkame, ze R je relace na mnoZine A. Relace na mnozine A se nazyívía:
(a) reflexivní, pokud idA C R, tedy pokud pro Va G A platí (a, a) G R;
(b) symetrická, pokud R-1 = R, tedy pokud Va, b G A; (a, b) G R, pak (b, a) G R;
(c) tranzitivní, pokud R o R C R, tedy pokud Va, b G A; (a, b) G R a (b, c) G R, pak
(a, c) G R;
(d) antisymetrickía, pokud R n R-1 C idA, tedy pokud Va, b G A; (a, b) G R, (b, a) G R, pak a = b.
Relace R na mnozine A se nazýva ekvivalence, pokud je soucasne reflexivní, symetricka a tranzitivní.
Relace R na mnozine A se nazyví uspořadaní, pokud je soucasne reflexivní, antisymetricka a tranzitivní.
3. Na mnozine {0,1} naleznete vsechny relace, které jsou:
(a) reflexivní;
(b) symetrickíe;
(c) tranzitivní;
(d) relace ekvivalence;
1
(e) symetrické a tranzitivní;
(f) symetrické a antisymetrické.
TotéZ v prípade jednoprvkové a prázdné mnoZiny.
4. Na mnoZiné {1, 2, 3} naleznete všechny relace ekvivalence.
5. Je dána relace p na mnoZiné N. Rozhodnete zda p je reflexivní, resp. symetricka, resp. antisy-metrická, resp. tranzitivní relace, je-li pro x, y G N:
(a) xpy ^ x • y je liché císlo;
(b) xpy ^ x, y jsou nesoudélna;
(c) xpy ^ y = x V y = 2x V y = 3x;
(d) xpy ^ |x — y| =3 V x = y.
6. Je dana relace p na mnoziné P (A), kde A je neprázdní konecna mnozina. Rozhodnete zda p je reflexivní, resp. symetricka, resp. antisymetrickí, resp. tranzitivní relace, je-li pro X, Y G P (A):
(a) XpY    X U Y = A;
(b) XpY    X = 0V X = A;
(c) XpY    X n Y = 0;
(d) YpY ^ mnoziny X, Y mají stejní pocet prvku.
7. Na mnoziné M je definovana relace p. Rozhodnete, zda p je relací ekvivalence na M, je-li:
(a) M = Z; p = {(x, y) G Z x Z; y = x nebo y = x + 1};
(b) M = R; p = {(x, y) G R x R; x — y G Z};
(c) M = R; p = {(x, y) G R x R; |x — y| < 1};
(d) M = P (N); p = {(A, B) G P (N) x P (N); (A — B) je konecní mnozina};
(e) M = P (N); p = {(A, B) G P (N) x P (N); (A -ŕ- B) je konecní mnozina};
2