Základy matematiky — podzim 2006 — 2. termín — 12.1.2007
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 Pro libovolné množiny A, B, C a zobrazení f : A → B, g : B → C platí:
f je injektivní a g je surjektivní =⇒ g ◦ f je bijekce.
(b) ano — ne Pro každé uspořádání R množiny N existuje minimální nebo maximální prvek v
uspořádané množině (N, R).
(c) ano — ne Pro libovolné množiny A a B tvoří množina všech relací mezi množinami A a B
s uspořádáním inkluzí, tj. (P(A × B), ⊆), svaz.
(d) ano — ne Okruh (Z4, +, ·) zbytkových tříd modulo 4 je těleso.
(e) ano — ne Pro libovolnou relaci R na množině A je R ◦ R tranzitivní relace.
(f) ano — ne Množina všech injektivních zobrazení množiny N do sebe tvoří spolu s operací
skládání zobrazení grupu.
(g) ano — ne Množina všech konečných podmnožin množiny N je spočetná.
2. (7 bodů) Definujte pojem uspořádání na množině A. Definujte pojmy binární relace a relace ekvivalence
na množině A. Definujte všechny užité pojmy. Které relace jsou zároveň relace ekvivalence
a uspořádání?
3. (3krát 2 body) Kolik přirozených čísel mezi 1 a 300 je
(a) dělitelných 2, 3, ale není dělitelných 5;
(b) s ciferným součtem 18;
(c) zapsaných pouze pomocí sudých číslic.
4. (5krát 2 body) Udejte příklad
(a) svazu, který není úplný svaz;
(b) nekonečné, nespočetné grupy;
(c) 3-prvkového okruhu;
(d) neprázdné relace ρ ⊆ N × Z a neprázdné relace σ ⊆ Z × Q takových, že složená relace σ ◦ ρ je
prázdnou relací.
(e) uspořádané množiny, kde každý maximální prvek je zároveň minimální a existuje prvek, který
je minimální, ale není maximální.
5. (10 bodů) V monoidu (Z9, ·) označme Z∗
9 množinu všech prvků, ke kterým existuje inverzní prvek.
Určete, kolik má množina Z∗
9 prvků, a vypište je.
Určete nějaké k ∈ Z tak, že ϕ : Z6 → Z9 dané předpisem ϕ([a]6) = [k]a
9 je homomorfismus z grupy
(Z6, +) do grupy (Z∗
9, ·) (tj. pro toto k ukažte, že předpis korektně definuje zobrazení ϕ a že ϕ je
homomorfismus).
Určete nějaké k ∈ Z tak, že ϕ : Z6 → Z9 dané předpisem ϕ([a]6) = [k]a
9 je izomorfismus z grupy
(Z6, +) do grupy (Z∗
9, ·).
Odpovědi zdůvodněte.
6. (10 bodů) Nechť n ∈ N, A = {1, 2, . . ., n + 2} a B = {1, 2, . . ., n}. Určete počet všech surjektivních
zobrazení z množiny A do množiny B.
Kolik z nich je navíc izotonními zobrazeními z (A, ≤) do (B, ≤), kde ≤ je uspořádání přirozených
čísel podle velikosti.
Výpočty komentujte.
7. (10 bodů) Nechť n ∈ N. Označme A = {1, 2, . . ., n} a dále nechť M je množina všech neprázdných
podmnožin množiny A. Na množině M je definována binární relace ρ vztahem
XρY ⇐⇒ minX = minY.
Dokažte, že ρ je relace ekvivalence na množině M.
Popište rozklad M\ρ.
Určete, kolik má tento rozklad tříd a kolik prvků mají jednotlivé třídy.
Pro n = 6 vypište explicitně některou třídu rozkladu obsahující nějakou dvouprvkovou podmnožinu
množiny A.
(Pozn: minX značí minimální prvek množiny X (uspořádané podle velikosti). )
8. (10 bodů) Na množině M = Q ∪ {⊥, ⊤} definujeme binární relaci takto:
p q ⇐⇒ ( p = ⊥ ∨ q = ⊤ ∨ (p, q ∈ Q ∧ p ≤ q ∧ ⌊p⌋ = ⌊q⌋) ) pro p, q ∈ M.
Dokažte, že je uspořádání.
Nalezněte všechny minimální a maximální prvky uspořádané množiny (M, ).
Je (M, ) svaz?
Popište, čemu se rovná sup{p, q}.
Je (M, ) úplný svaz?
Odpovědi zdůvodněte. (Pozn: ≤ je uspořádání racionálních čísel podle velikosti, ⌊p⌋ značí celou
část čísla p.)
9. (10 bodů) Na množině M = {(a, X) ∈ N × P(N) | a ∈ X} definujeme binární relaci takto:
(a, X) (b, Y ) ⇐⇒ (a ≤ b ∧ X ⊆ Y ).
Označme dále M⊥
= M ∪ {⊥}, kde uspořádání pro prvek ⊥ dodefinujeme takto:
(∀x ∈ M⊥
)(⊥ x).
Je (M, ) svaz?
Je (M⊥
, ) svaz?
Je (M⊥
, ) úplný svaz?
Popište, jak se počítají konečná suprema v (M, ).
Popište, jak se počítají libovolná infima v (M⊥
, ).
Odpovědi zdůvodněte.