Základy matematiky -- podzim 2008 -- 2. opravný termín -- 3.2.2009
Jméno:. . . . . . . . . . . . . . . . . . . . . . . . . .
test
Hodnocení
cel.suma zn.
UČO: . . . . . . . . . . . . . . . . . . . . . . . . . .
1 2 3 4 5 6 7 8 9
1. (7krát 1 bod (správně 1 bod, chybně -1, bez odpovědi 0 -- při záporném součtu se do celkového hodnocení
započítá 0))
Odpovězte (škrtnutím nehodícího se ano nebo ne na patřičném řádku), zda jsou pravdivá následující
tvrzení (čtěte velmi pozorně!):
(a) ano -- ne Existuje bijekce z množiny Q do množiny N.
(b) ano -- ne Je-li g : A  B surjektivní zobrazení a f : B  C je také surjektivní zobrazení,
pak f  g : A  C je opět surjektivní zobrazení.
(c) ano -- ne Uspořádané množiny (Q, ) a (R, ) jsou izomorfní.
(d) ano -- ne Každý svaz má nejmenší prvek.
(e) ano -- ne Každá konečná uspořádaná množina má alespoň jeden minimální prvek.
(f) ano -- ne Pokud je binární relace R na množině A tranzitivní, pak R-1
je také tranzitivní.
(g) ano -- ne V monoidu (Z5, ) má každý prvek inverzi.
2. (7 bodů) Definujte pojem grupa, komutativní grupa a izomorfismus grup. Definujte všechny užité
pojmy.
3. (3krát 2 body) Každá z pěti politických stran nominovala 4 zástupce na společnou kandidátku.
Určete, kolika způsoby lze na kandidátce z těchto 20 osob vybrat 3 tak, že
(a) -- (bez omezení);
(b) jsou všichni z jedné strany;
(c) jsou aspoň ze dvou stran.
Odpověď: a) b) c)
4. (5krát 2 body) Udejte příklad
(a) monoidu, který není grupa a jeho podmnožiny, která tvoří grupu (se stejnou operací);
(b) konečné množiny A takové, že A je nekonečná množina;
(c) relace ekvivalence  na množině N tak, aby rozklad N\ měl nekonečně mnoho tříd;
(d) izotonního zobrazení f : (N, )  (N, ), které není injektivní (zde  je uspořádaní podle
velikosti);
(e) uspořádané množiny, která má jeden maximální prvek a nemá minimální prvek.
5. (10 bodů) Na množině Z definujeme binární operaci  vztahem
x  y = x + y + 7, pro x, y  Z.
Dokažte, že  je asociativní operace.
Dokažte, že pro operaci  existuje neutrální prvek.
Dokažte, že (Z, ) je grupa.
Nalezněte zobrazení  : Z  Z tak, že  je izomorfismus z grupy (Z, ) do grupy (Z, +).
Odpovědi zdůvodněte.
6. (10 bodů) Pro libovolné n  N označujeme Xn = {1, 2, . . . , n}.
Určete, kolik je zobrazení z P(X2) do P(Xn).
Určete, kolik je izotonních zobrazení z (P(X2), ) do (P(Xn), ).
Postup výpočtu komentujte.
7. (10 bodů) Buď na množině Z × Z definována relace  takto:
(a, b)  (c, d)  a2
- c2
= b2
- d2
= 0, pro a, b, c, d  Z.
Dokažte, že  je relace ekvivalence na množině Z × Z.
Popište rozklad Z × Z\.
Určete, kolik má tento rozklad tříd a kolik prvků mají jednotlivé třídy.
8. (10 bodů) Na množině M = P(N) - {} definujeme binární relaci takto:
X Y  (X = Y  min(X) < min(Y )), pro X, Y  M.
Dokažte, že je uspořádání množiny M.
Nalezněte všechny minimální, maximální, nejmenší a největší prvky uspořádané množiny (M, ).
Je (M, ) svaz?
Je (M, ) úplný svaz?
Uvažujme zobrazení id : M  M dané předpisem id(X) = X.
Rozhodněte, zda id : (M, )  (M, ) je izotonní zobrazení.
Odpovědi zdůvodněte. (Pro X  M, tj. X neprázdnou podmnožinu množiny A, značí min(X) nejmenší
přirozené číslo v X  A vzhledem k velikosti.)
9. (10 bodů) Buď A libovolná množina a R relace na této množině. Pro i  N definujeme induktivně
Ri
takto: R1
= R a Rk+1
= Rk
 R pro k  N. Ekvivalentně: pro a, b  A platí (a, b)  Ri
tehdy a
jen tehdy, když existují prvky a0, a1, . . . , ai  A takové, že a = a0, b = ai a platí (ak-1, ak)  R pro
libovolné k  {1, . . . , i}. Položme nyní R
= iN Ri
.
Rozhodněte zda platí následující implikace:
R reflexivní = R
reflexivní;
R
reflexivní = R reflexivní;
R symetrická = R
symetrická;
R
symetrická = R symetrická;
R tranzitivní = R
tranzitivní;
R
tranzitivní = R tranzitivní.
Odpovědi zdůvodněte.