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í / : A —► B, g : B —► C platí: / 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. (V(A x -S), C), 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 o 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 p C N x Z a neprázdné relace uCZxQ takových, že složená relace a o p 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 (Zg, •) označme Zg množinu všech prvků, ke kterým existuje inverzní prvek. Určete, kolik má množina Zg prvků, a vypište je.
Určete nějaké k E Z tak, že p : Z6 —► Zg dané předpisem ^([ajö) = [k]g je homomorfismus z grupy (Z6, +) do grupy (Zg, •) (tj. pro toto k ukažte, že předpis korektně definuje zobrazení p a že p je homomorfismus).
Určete nějaké k E Z tak, že p : Z6 —► Zg dané předpisem ^([ajö) = [k]g je izomorfismus z grupy (Z6,+) do grupy (Zg>).
Odpovědi zdůvodněte.
6.   (10 bodů) Nechť n E 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ínii 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 p vztahem
XpY -<=>- minX = minY.
Dokažte, že p je relace ekvivalence na množině M.
Popište rozklad M\p.
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 U {_L, T} definujeme binární relaci ^ takto:
P ľi Q -<=>-  ( P = -L  V q = T  V  (p, q E Q A p < q A \j)\ = [q\) )     pro p, q E 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, X) 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,  |_pj značí celou část čísla p.)
9.   (10 bodů) Na množině M = {(a,X) G N x V (N) \ a E X} definujeme binární relaci ^ takto:
(a,X)l(b,Y)  ^^  (a<bAX CY). Označme dále M1- = M U {J-}, kde uspořádání ^ pro prvek _L dodefinujeme takto:
(VieM^l^i).
Je (M, X) svaz?
Je (M±, X) svaz?
Je (M-1, ^) úplný svaz?
Popište, jak se počítají konečná suprema v (M, ^).
Popište, jak se počítají libovolná infima v (M-1, ^).
Odpovědi zdůvodněte.