Základy matematiky — podzim 2005 — 2. opravný termín — 25.1.2006
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 Mezi množinami R a N existuje bijekce.
(b) ano — ne Pro libovolné množiny A, B, C a zobrazení f : A → B, g : B → C platí:
g ◦ f je bijektivní =⇒ f, g jsou bijektivní.
(c) ano — ne Relace ρ na množině A je antisymetrická právě tehdy, když ρ ∩ ρ−1
= ∅.
(d) ano — ne Má-li uspořádaná množina (A, ≤) nejmenší prvek, pak (A, ≥) má také nejmenší
prvek.
(e) ano — ne Množina všech izotonních zobrazení uspořádané množiny (A, ≤) do sebe spolu
s operací skládání zobrazení tvoří grupu.
(f) ano — ne (Z, −) je monoid.
(g) ano — ne Ke každému prvku grupy existuje nejvýše jeden prvek inverzí.
2. (7 bodů) Definujte pojem rozkladu množiny A. Definujte pojem relace ekvivalence na množině A
a rozklad příslušného této relaci (tzv. faktorová množina). Definujte pojem jádra zobrazení.
3. (3krát 2 body) Určete počet všech slov délky 6, která jsou sestavena z písmen a, b, c, d takových, že
(a) některá skupina bezprostředně po sobě jdoucích písmen je abcd;
(b) se nezmění, pokud jsou čtena odzadu;
(c) všechna písmena jsou použita.
4. (5krát 2 body) Udejte příklad
(a) množin X a Y takových, že |P(X) ∪ P(Y )| = 5;
(b) pětiprvkové uspořádané množiny, která má právě jeden maximální, právě jeden minimální,
právě jeden největší a právě jeden nejmenší prvek;
(c) surjektivního zobrazení f : N → Z;
(d) relace na množině Z, která je antisymetrická i symetrická, ale není reflexivní;
(e) binární operace na P(N), která má neutrální prvek (uveďte ho).
5. (10 bodů) Na množině Z definujeme binární operaci ◦ vztahem
a ◦ b = a + b − ab, pro a, b ∈ Z.
Rozhodněte, zda je operace ◦ asociativní. Rozhodněte, zda je operace ◦ komutativní. Je (Z, ◦)
grupa? Odpovědi zdůvodněte.
6. (10 bodů) Nechť M je konečná n-prvková množina. Určete počet všech binárních operací na množině
M, pro které existuje neutrální prvek. Kolik z nich je komutativních?
7. (10 bodů) Na množině R je definována binární relace ρ vztahem
xρy ⇐⇒ (x = y ∨ xy > 0) pro x, y ∈ R.
Dokažte, že ρ je relace ekvivalence na množině R. Popište rozklad R\ρ. Určete kolik má tento
rozklad tříd a kolik prvků mají jednotlivé třídy.
8. (10 bodů) Uvažujme množinu M = {X ⊆ N | X konečná , 1 ∈ X} uspořádanou inkluzí ⊆. Nalezněte
všechny minimální a maximální prvky uspořádané množiny (M, ⊆). Nalezněte nejmenší a
největší prvek uspořádané množiny (M, ⊆). Je (M, ⊆) úplný svaz? Je (M, ⊆) svaz? Rozhodněte,
zda zobrazení g : M → N, definované předpisem g({r1, r2, . . . , rk}) = r1 + r2 + · · · + rk, je izotonní
zobrazení z uspořádané množiny (M, ⊆) do uspořádané množiny (N, ≤). Odpovědi zdůvodněte.
(Pozn: ≤ je uspořádání přirozených čísel podle velikosti.)
9. (10 bodů) Na množině S = {f : N → N | f surjektivní } (všech surjektivních zobrazení z množiny
N do sebe ) definujeme uspořádání takto:
f g ⇐⇒ (∀n ∈ N)(f(n) ≤ g(n)), pro f, g ∈ S.
Dále definujme zobrazení ϕ : S → S vztahem ϕ(f) = f ◦ f.
Dokažte, že skládání zobrazení je operací na množině S, tj. f, g ∈ S =⇒ g◦f ∈ S. Rohodněte, zda
je zobrazení ϕ injektivní. Rohodněte, zda je zobrazení ϕ surjektivní. Rohodněte, zda ϕ je izotonní
zobrazení z uspořádané množiny (S, ) do sebe.
Odpovědi zdůvodněte. (Pozn: ≤ je uspořádání přirozených čísel podle velikosti.)