Základy matematiky — podzim 2005 — 1. termín — 5.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 P(P(N)) a P(N) existuje bijekce.
(b) ano — ne Pro libovolné množiny A, B, C a zobrazení f : A → B, g : B → C platí:
f, g jsou surjektivní =⇒ g ◦ f je surjektivní.
(c) ano — ne Každá lineárně uspořádaná množina má největší prvek.
(d) ano — ne Relace ρ na množině A je symetrická právě tehdy, když ρ ⊆ ρ−1
.
(e) ano — ne Je-li uspořádaná množina (A, ≤) úplný svaz, pak (A, ≥) je také úplný svaz.
(f) ano — ne (P(A), ∩) je monoid.
(g) ano — ne (Z, +, ·) je těleso.
2. (7 bodů) Definujte pojem uspořádání na množině A. Definujte pojem infima a suprema podmnožiny
množiny A. Definujte všechny užité pojmy. Určete, co je infimem prázdné podmnožiny.
3. (3krát 2 body) Určete počet všech slov, která lze vytvořit z písmen slova BEROUNKA (každé
písmeno se použije právě jednou) takových, že
(a) některá skupina bezprostředně po sobě jdoucích písmen tvoří slovo BERAN;
(b) žádné dvě samohlásky nestojí vedle sebe;
(c) samohlásky jsou seřazeny podle abecedy.
4. (5krát 2 body) Udejte příklad
(a) množin X a Y takových, že P(X) ∪ Y = P(Y ) − Y ;
(b) uspořádané množiny, která má právě 6 automorfismů (tj. izomorfismů do sebe);
(c) zobrazení z množiny N do sebe, které není surjektivní a je injektivní;
(d) relace na množině N, která je antisymetrická i symetrická;
(e) binární operace na Z, která je komutativní, ale nemá neutrální prvek.
5. (10 bodů) Na množině M = Q × Q definujeme binární operaci ◦ vztahem
(a, b) ◦ (a′
, b′
) = (aa′
+ 2bb′
, ab′
+ a′
b), pro a, b, a′
, b′
∈ Q.
Rozhodněte, zda je operace ◦ asociativní. Rozhodněte, zda je operace ◦ komutativní. Je (M, ◦)
grupa? Odpovědi zdůvodněte.
6. (10 bodů) Nechť M je konečná n-prvková množina. Určete počet všech dvojic množin (A, B),
takových, že A ⊆ B ⊆ M. Kolik z nich je takových, že A = B?
7. (10 bodů) Na množině Z je definována binární relace ρ vztahem
xρy ⇐⇒
x
3
=
y
3
pro x, y ∈ Z.
Dokažte, že ρ je relace ekvivalence na množině Z. Popište rozklad Z\ρ. Určete kolik má tento
rozklad tříd a kolik prvků mají jednotlivé třídy. (Pozn: ⌊a⌋ značí celou část čísla a, tj. největší celé
číslo nepřevyšující číslo a.)
8. (10 bodů) Na množině M = {(a, b) | a, b ∈ N, a ≤ b} definujeme binární relaci takto:
(a, b) (a′
, b′
) ⇐⇒ (a′
≤ a ∧ b ≤ b′
), pro a, b, a′
, b′
∈ N.
Dokažte, že je uspořádání. Nalezněte všechny minimální a maximální prvky uspořádané množiny
(M, ). Je (M, ) úplný svaz? Je (M, ) svaz? Určete sup{(a, b), (a′
, b′
)} Odpovědi zdůvodněte.
(Pozn: ≤ je uspořádání přirozených čísel podle velikosti.)
9. (10 bodů) Na množině I = {f : N → N | (∀n, m ∈ N)(n ≤ m =⇒ f(n) ≤ f(m))} (všech
izotonních zobrazení z množiny N do sebe ) definujeme uspořádání takto:
f g ⇐⇒ (∀n ∈ N)(f(n) ≤ g(n)), pro f, g ∈ I.
Dále definujme zobrazení ϕ : I → I vztahem ϕ(f) = f ◦ f.
Dokažte, že skládání zobrazení je operací na množině I, tj. f, g ∈ I =⇒ g ◦ f ∈ I. Rohodněte, zda
je zobrazení ϕ injektivní. Rohodněte, zda je zobrazení ϕ surjektivní. Rohodněte, zda ϕ je izotonní
zobrazení z uspořádané množiny (I, ) do sebe.
Odpovědi zdůvodněte. (Pozn: ≤ je uspořádání přirozených čísel podle velikosti.)