1   První cvičení
1.1 Indukce
Příklad 1.1 Dokažte, že pro každou konečnou množinu A platí
|2A| = 2'AI
kde 2A = {C|C C A} a |X| žnačí počet prvkU konečne množiny X. Příklad 1.2 Dokažte, že pro všechny konečne množiny A, B platí
|BA| = |B|A
kde BA = {/|/ : A — B} je množina všečh žobražení ž A do B a |X| žnačí počet prvkU konečne množiny X.
Příklad 1.3 Definujme induktivne množinu X C N0.
• Položíme 2 G X a 3 G X.
• Dále pro každe x, y G X platí x • y G X.
To štejne formílneji: X = [jj£N Xj, kde Xi = {2, 3} a Xj+1 = Xj U {x • y | x, y G Xj}.
Dokažte, že pro každy prvek x G X platí
bud'   2 | x   nebo   3 | x
kde c | x je relače delitelnosti, tedy pro c G N a x G N0 platí c | x pokud existuje b G N0 takove, že c • b = x.
1.2 Relace
Příklad 1.4 Dejte príklad množiny A a relače R na množine A t.ž.
a) R je reflexivní, symetrička a není transitivní
b) R je reflexivní, transitivní a není symetričkí č) R je symetričkí, transitivní a není reflexivní
Příklad 1.5 Nečht' A je množina a R, S jsou relače ekvivalenče na množine A. Které ž nasledujíčíčh jsou take relače ekvivalenče?
a) R n S
b) R U S
č) R \ S d) R o S
Příklad 1.6 Kolik je ekvivalenčí na množine 0?
1
1.3 Funkce
Příklad 1.7 Necht' A,B jsou neprázdné množiny a f : A — B je funkce. Dokažte, že
a) f je injektivní, prave když existuje g : B — A t.ž. g o f = idA
b) f je surjektivní, práve když existuje g : B — A t.ž. f o g = idB kde idX (a) = a pro každe a G X.
1.4 Uspořádané množiny
Definice 1.8 Necht' (A, C) a (B, ^) jsou usporádane množiny. Řekneme, že tyto usporadane množiny jsou izomorfní, pokud existuje bijekce f : A — B, t.ž. pro všechna x, y G A platí x E y       f (x) ^ f (y).
Příklad 1.9 Necht' C = {9,        #}. Naležnete
a) dve räžna ižomorfní uspoMdaní na C a
b) dve navžájem neižomorfní usporadaní na C. Příklad 1.10 Naležnete
a) dve navžíjem neisomorfní usporadíní na N0
b) nekonecne mnoho navžíjem neisomorfních ^poradím na N0
c) nespocetne mnoho navžíjem neisomorfních usporadaní na N0
(tip: množina vsech nekonecnych posloupností priroženích císel je nespocetna)
a dokažte, že nejsou isomorfní. Příklad 1.11 Naležnete
a) dve navžíjem neisomorfní linearní usporadíní na N0
b) nekonecne mnoho navžíjem neisomorfních lineírních usporadíní na N0
c) nespocetne mnoho navžajem neisomorfních lineírních usporadíní na N0 a dokažte, že nejsou isomorfní.
Příklad 1.12 Necht' (A, C) je konecna usporadana množina. Dokažte, že existuje linearní usporadaní ^ na A, t.ž. CC<
2