Cvičné príklady

written by shelll, shelll.host.sk

1

Mohutnost mnozin a konecne mnoziny.

1. Dokazte nasledovne tvrdenia (za tvrdenim je oznacenie podla prednasky; niektore boli dokazane uz
na prednaske).

a) Ak |A| ≤ |X|, |B| ≤ |Y |, potom |A| + |B| ≤ |X| + |Y | (2a)

b) Ak |A| ≤ |X|, |B| ≤ |Y |, potom |A|.|B| ≤ |X|.|Y | (2b)

c) Ak |A| ≤ |X|, |B| ≤ |Y |, potom |A||B| ≤ |X||Y | (2c)

d) |A| + |B| = |B| + |A| (3a)

e) |A| + (|B| + |C|) = (|A| + |B|) + |C| (3b)

f) |A|.|B| = |B|.|A| (3c)

g) |A|.(|B|.|C|) = (|A|.|B|).|C| (3d)

h) |A|.(|B| + |C|) = (|A|.|B|) + (|A|.|C|) (3e)

i) |A||B|+|C| = |A|B.|A|C (4a)

j) (|A|.|B|)|C| = |A||C|.|B||C| (4b)

k)

|A||B|

|C | = |A||B|.|C| (4c)

2. Ak ma mnozina n ∈ N prvkov, potom je konecna.

3. Dokazte, ze mnozina vsetkych prvocisel je nekonecna. Mozete pouzit tvrdenie, ze kazde prirodzene
cislo n ≥ 2 ma rozklad na prvocisla.

4. Oznacime An = {(k, l) ∈ N

2; max{k, l} = n}.

a)

Ukazte, ze An ∩ Am = ∅ pre n 6= m.

b)

Pre kazde n plati Nn × Nn =

n−1

[

p=0

Ap.

c)

Na zaklade a) a b) dokazte, ze

n

X

i=0

(2i + 1) = (n + 1)

2.

d)

celu uvahu vhodne graficky znazornite.

5. Uvahou podobnou, ako v ulohe 4 dokazte tieto rovnosti (pre lubovolne n ∈ N):

a)

n

X

i=0

(3i

2 + 3i + 1) = (n + 1)3

b)

n

X

i=0

i =

n2 − n

2

+ n =

1

2

n(n + 1)

6. Nech X je konecna mnozina. Potom plati:

a) ak f : X

1−1

−→ X, tak f je zobrazenie na mnozinu X;

b) ak f : X

−→

na X, tak f je proste zobrazenie.

Dokazte.

7. Nech X je mnozina pre ktoru plati: ak f : X

1−1

−→ X, tak f je zobrazenie na mnozinu X. Potom X

je konecna podla Dedekinda. Dokazte!

written by shelll, shelll.host.sk

2

Spocitatelne mnoziny.

1. Priamo podla definicie ukazte, ze |N| + |R| = |R|.

2. Ukazte, ze |Z × h0, 1)| = |R|. Odtial odvodte |R| · |N| = |R|.

3. Ak |N| ≤ |A|, potom |A| + |{a}| = |A|. Dokazte!

4. Ak |A| + |{a}| = |A|, a 6∈ A, potom |A| ≥ |N|. Dokazte!
(Navod: a 6∈ A a f : A ∪ {a}

1−1

−→ A; h(0) = f (a), h(n + 1) = f (h(n)), potom h : N

1−1

−→ A)

5. Ak |A| ≥ |{0, 1}|, |A| · |A| = |A|, potom |A| ≥ |N |. Dokazte!

6. Ak |A| · |A| = |A|, potom |An| = |Am| pre lubovolne n, m ∈ N,

n, m > 0. Dokazte!

7. Ak |N| ≤ |A|, potom |A| + |N| = |A|. Dokazte!

8. Ak A, B su disjunktne mnoziny, potom |P(A)| · |P(B)| = |P(A ∪ B)|. Dokazte!

9. Najdite ”vzorec”, ktory definuje proste zobrazenie z N

3 na N.

10. Vypocitajte

a)

(2

ℵ0 + ℵℵ0

0 ).ℵ0

b)

(2

2

ℵ0

.ℵ0

ℵ0

ℵ0

)

2

ℵ0

c)

(2

ℵ0 + ℵℵ0

0 )

n

11. Mnozina vsetkych otvorenych intervalov s racionalnymi koncami je spocitatelna. Dokazte!

12. Najdite mnozinu X ⊆ R

n taku, ze

a)

X je spocitatelna

b)

∀ε > 0 a ∀a = (a1, . . . , an) ∈ R

n ∃x ∈ X, x = (x

1, . . . , xn) take, ze

n

X

i=1

|xi − ai| < ε

13. Ak X je mnozina navzajom disjunktnych otvorenych intervalov, tak X je spocitatelna. Dokazte!

14. Nech f je neklesajuca funkcia f : R → R. Dokazte, ze plati:

a)

∀a ∈ R ∃ lim

x→a+

f (x) a lim

x→a−

f (x);

b)

mnozina bodov nespojitosti funkcie f je nespocitatelna.

15. Nech f je funkcia f : R → R. Pripomenme, ze f ma totalne minimum v cisle a, ak existuje ε > 0
take, ze pre ∀x ∈ (a − ε, a + ε), x 6= a je f (x) > f (a). Podobne totalne maximum. Dokazte, ze mnozina
vsetkych bodov, v ktorych funkcia ma totalne minimum alebo totalne maximum, je spocitatelna.

16. Nech T k(X) je mnozina vsetkych postupnosti {an}

∞

n=0 prvkov mnozniny X takych, ze existuje m ∈ N

take, ze pre ∀n ≥ m je an = am. Aka je mohutnost mnozin T k({0}), T k({0, 1}), T k({N}), T k({Q}), T k({R})?

17. Nech P je podmnozina {0, 1}N . Dvaja hraci I a II hraju takuto nekonecnu hru. Hrac I vyberie
a0 ∈ {0, 1}, hrac II vyberie a1 ∈ {0, 1} atd., hrac I vybera a2n ∈ {0, 1}, hrac II vybera a2n+1 ∈ {0, 1}.
Hrac I vyhra, ak postupnost {an}

∞

n=0 je prvok mnoziny P . V opacnom pripade vyhra hrac I I . Ak P

je spocitatelna mnozina, tak mozno dat hracovi II taky navod na hru, aby vzdy vyhral. Najdite taky
sposob hry hraca II.

18. Z vysledku ulohy 17 odvodte, ze mnozina {0, 1}N nie je spocitatelna.

written by shelll, shelll.host.sk

3

19. Aka je mohutnost mnoziny vsetkych podgrup aditivnej grupy (Z, +, 0)?

Zapojenie - vypojenie.

1. Na univerzitnej katedre pracuje 30 pracovnikov, pricom kazdy z nich ovlada aspon jeden cudzi jazyk.
10 pracovnikov vie po anglicky, 7 nemecky, 6 francuzsky, 5 anglicky a nemecky, 4 anglicky a francuzsky,
3 nemecky a francuzsky.

a) Kolko pracovnikov ovlada vsetky tri jazyky?

b) Kolko pracovnikov ovlada prave dva jazyky?

c) Kolko pracovnikov ovlada len anglicky jazyk?

2.

a) Ukazte, ze pocet prirodzenych cisel, ktore su delitelne x a neprevysuju n je rovny

n
x

.

b) Najdite pocet prirodzenych cisel, neprevysujucich 1000, ktore nie su delitelne ziadnym z cisel 3, 5

a 7.

c) Najdite pocet prirodzenych cisel, neprevysujucich 1000 a nesudelitelnych s cislami 6, 10 a 15.

3. Ukazte, ze ak n = 30m, potom pocet prirodzenych cisel, neprevysujucich n a nedelitelnych ziadnym
z cisel 6, 10, 15 je rovny 22m.

4. Nech p1, p2, . . . , pr su vsetky prvocisla, neprevysujuce

√

n. Ukazte, ze pocet prvocisel p, takych, ze

√

n < p ≤ n je rovny n − 1 −

r

P

k=1

(−1)k+1Sk, kde Sk =

P

h

n

pi

1 ...pin

i

, kde sucet ide cez vsetky podmnoziny

{i1, . . . , ik} ⊆ {1, 2, . . . , r}.

5. Najdite pocet prvocisel neprevysujucich a) 25, b) 250, c) n.

6. Uloha o nepriatelskych dvojiciach. Kolkymi sposobmi mozeme za okruhly stol posadit n nepriatel-
skych dvojic tak, ze ziadni nepriatelia nesedia vedla seba? Stolicky su ocislovane.

7. Uloha o manzelskych dvojiciach. Kolkymi sposobmi mozeme posadit za okruhly stol n manzelskych
dvojic tak, aby sa striedali muzi so zenami a ziadna manzelska dvojica nesedela vedla seba? Stolicky su
ocislovane.

Priklady roznych typov.

1. Kolko je permutacii n > 1 prvkov a1, a2, . . . , an, v ktorych pre ziadne i ∈ {1, 2, . . . , n − 1} nie je prvok
ai+1 bezprostredne za prvkom ai?

2. Kolko existuje k−prvkovych variacii s opakovanim z n prvkov takych, ze kazda obsahuje vsetkych n
prvkov?

3. Mame 2k + 1 listkov ocislovanych prirodzenymi cislami 1, 2, . . . , 2k + 1. Aky najvacsi pocet listkov
mozno vybrat tak, aby sa ziadne vybrate cislo nerovnalo suctu dvoch vybratych cisel?

4. Nech A = (aij) je matica typu n × n, aij = {−1, 0, 1}. Kolko mozno vytvorit matic tak, aby sucty
prvkov v riadkoch, stlpcoch, na diagonalach boli navzajom rozne? (Teda napr. sucet v riadku musi byt
rozny od inych suctov v riadku, od vsetkych suctov v stlpci a na diagonalach)

5. Ak je v miestnosti pritomnych n osob, potom aspon dvaja z pritomnych maju rovnaky pocet znamych
spomedzi pritomnych. Dokazte. (Vztah ”a je znamy b” pokladame za vzajomny, t.j. ak a je znamy b,
potom b je znamy a.)

written by shelll, shelll.host.sk

4

6. Nech An je pocet Spernerovych systemov pre mnoziny z n prvkov. Dokazte, ze

2

Tn < A

n < C

Tn

2Tn ,

Tn = C

[ n

2 ]

n

7. Je danych n dvojic, z ktorych kazda sa sklada z dvoch rovnakych pismen, pricom dve rozne dvojice
obsahuju vzdy rozne pismena. Vsetkych 2n pismen usporiadavame tak, ze ziadne dve rovnake pismena
nenasleduju za sebou. Kolko je takych usporiadani?

8. Mame r roznych veci, ktore rozdelujeme medzi n + p ludi a to tak, aby kazdy z n vopred danych
ludi dostal aspon jednu vec. Dokazte, ze toto rozdelenie mozeme previest Sr sposobmi, kde

Sr = (n + p)

r − n(n + p − 1)r +

n

2

(n + p − 2)

r − · · · + (−1)npr

9. Dokazte, ze plati

(n + r − 1)!

r!

−

n

1

(n + r − 3)!

(r − 2)!

+

n(n − 1)

1.2

(n + r − 5)!

(r − 4)!

− · · · =

n!(n − 1)!

r!(n − r)!

10. Skupina skladajuca sa zo 41 studentov uspesne zlozila semestralne skusky z 3 predmetov. Mozne
znamky boli 1, 2, 3. Dokazte, ze aspon pat studentov zlozilo semestralne skusky s rovnakymi znamkami!

11. Komisia zasadala 40−krat. Kazdy raz sa na zasadanuti zucastnilo 10 osob, pricom ziadny dvaja
clenovia sa na zasadanuti nezucastnili spolu viac ako jedenkrat. Dokazte, ze pocet clenov komisie je viac
ako 60.

12. V niektorej institucii pracuje 25 pracovnikov. Dokazte, ze z nich nie je mozne vytvorit viac ako 30
komisii po 5 osob v kazdej tak, aby ziadne dve komisie nemali spolocneho viac ako jedneho clena

13. Kolkymi sposobmi mozeme posadit v kine n manzelskych dvojic do posledneho radu, kde je 2n miest
tak, aby ziadny manzelsky par nesedel vedla seba?

14.

Kolko je vsetkych permutacii 2n prvkov m1, m2, . . . , m2n, v ktorych pre ziadne neparne i ∈

{1, 2, . . . , 2n} nie je prvok mi na i−tom mieste?

15. Kolko je vsetkych permutacii k prvkov m1, m2, . . . , mk, v ktorych pre ziadne i ∈ {1, 2, . . . , k} nie je
prvok mi na i−tom miest, a pritom prvky m1 a m2 su vedla seba?

16. Uloha o hareme.
Nech M = {S1, S2, . . . , Sm} je system konecnych neprazdnych mnozin. Pozadujeme, aby kazda mnozina
mala viacej ako jedneho reprezentanta, nadalej vsak pozadujeme, aby reprezentanti boli rozni. Najdite
nutnu a postacujucu podmienku riesenia tejto ulohy.

17. Zistite, ci mozu hodiny: matematiky, fyziky, zemepisu a biologie bezat subezne, ak mame k dis-
pozicii: matematika, fyzika, M+Z, B+Z, B+Z. Vyuku mame zabezpecit 4 vyucujucimi.

18. Ukazte, ze ak kazda mnozina ma r prvkov r ≥ 1 a kazdy prvok sa vyskytuje v r mnozinach, tak
potom existuje system roznych reprezentantov pre mnoziny {S1, ..., Sm}.

Fibonacciho cisla.

Postupnost F ibonacciho cisel je postupnost definovana rekurentnym predpisom:

F0

=

0

F1

=

1

Fn+2

=

Fn+1 + Fn,

n ≥ 0

1. Dokazte, ze

Fn =

1

√

5

"

1 +

√

5

2

!n

−

1 −

√

5

2

!n #

written by shelll, shelll.host.sk

5

2. Dokazte, ze

dn/2e

X

k=0

n − k + 1

k

= Fn+2

3. Dokazte, ze

n

X

k=0

F2k+1 = F2n+2

4. Dokazte, ze

n

X

k=0

F2k = F2n+1 − 1

5. Dokazte, ze

(a) Fn+m = Fn−1Fm + FnFm+1,

n ≥ 1, m ≥ 0

(b) ak m deli n, tak Fm deli Fn

(c) NSD(Fn, Fn+1) = 1

(d) F 2

n + F

2

n+1 = F2n+1

(e) F 3

n+1 + F

3

n − F

3

n−1 = F3n

(f) (FnFn+3)

2 + (2Fn+1Fn+2)2 = (F2n+3)2

6. Kolko je retazcov zo symbolov 0 a 1 dlzky n takych, ze v nich nenasleduju dve jednotky za sebou?

7. Kazde prirodzene cislo r > 1 mozno jednoznacne zapisat v tvare takeho suctu Fibonacciho cisel, ze
kazde Fibonacciho cislo sa v nom vyskytuje najviac raz a ziadne dve susedne Fibonacciho cisla sa v nom
nevyskytuju sucasne. Dokazte.

8. Nech

G0

=

1

G1

=

2

Gn+2

=

Gn+1 + Gn − 1,

n ≥ 0

Najdite vyjadrenie postupnosti Gn pomocou Fibonacciho cisel.

9.∗ Nech

G0

=

0

G1

=

2

Gn+2

=

Gn+1 + Gn + 1 − n,

n ≥ 0

Najdite vyjadrenie postupnosti Gn pomocou Fibonacciho cisel.

Dirichletov princip.

1. Dokazte, ze z lubovolnych 52 cisel mozno vybrat dve tak, ze ich sucet alebo rozdiel je delitelny
100−mi.

2. V stvorci je danych 9 bodov, z ktorych ziadne tri nelezia na jednej priamke. Dokazte, ze tri z tychto
bodov su vrcholmi trojuholnika, ktoreho obsah neprevysuje 1/8 obsahu stvorca.

3. Dokazte, ze v lubovolnom konvexnom 11−uholniku sa najdu dve uhlopriecky s vlastnostou, ze uhol
priamok, na ktorych lezia je mensi ako 5 stupnov.

written by shelll, shelll.host.sk

6

4. V miestnosti je lubovolne rozmiestnenych 30 stoliciek. 30 ludi, sediacich na tychto stolickach, hra
nasledovnu hru: na povel vsetci vstanu a snazia sa dostat na najblizsiu susednu stolicku. Dokazte, ze o
ziadnu stolicku nie je viac ako 6 zaujemcov.

5. V rovine je dana mnozina M 90−tich bodov, z ktorych ziadne tri nelezia na jednej priamke. Kazdy
z nich je spojeny useckou s aspon 10−timi dalsimi z nich. Dokazte, ze ku kazdemu bodu mnoziny M
mozno vybrat tri dalsie body mnoziny M tak, ze vo vzniknutej stvorici je kazdy bod spojeny aspon s
dvomi dalsimi.

Dirichletov princip.

1. Hadzeme dvoma kockami. Kolko krat treba hodit, aby sme mali zarucene, ze dvakrat padol rovnaky
sucet bodov na kockach?

2. Kolkokrat treba hodit troma kockami, aby bolo zaistene, ze aspon styrikrat padol rovnaky sucet
bodov na kockach?

3. Kolkokrat treba hodit dvoma kockami, aby trikrat padla ta ista dvojica cisel? (Ulohu rieste pre
rozlisene aj pre nerozlisene kocky).

4. Dokazte zovseobecnenia Dirichletovho principu:

(a) Ak je danych n realnych cisel, ktorych sucet je vacsi alebo sa rovna cislu b , tak aspon jedno z nich

je vacsie alebo sa rovna

b

n .

(b) Ak je danych n realnych cisel, ktorych sucet je vacsi nez cislo b , tak aspon jedno z nich je vacsie

ako

b

n .

(c) Ak je danych n realnych cisel, ktorych sucet je mensi alebo sa rovna cislu b , tak aspon jedno z

nich je mensie alebo sa rovna

b

n .

(d) Ak je danych n realnych cisel, ktorych sucet je mensi nez b , tak aspon jedno z nich je mensie nez

b

n .

5. Dany je konvexny 14−sten s 9 vrcholmi. Dokazte, ze na nom existuje vrchol, z ktoreho vychadza
aspon 5 hran. 1

6. Dany je konvexny 7−sten so 6 vrcholmi. Dokazte, ze prave 1 stena tohto 7−stena je 4−uholnik.

7. V zahrade o rozmeroch 80 m × 90 m rastie 365 stromov. Da sa najst cast zahrady tvaru obdlznika o
rozmeroch 5 m × 8 m na ktorej rastu aspon 3 stromy?

8. Na obslzniku rozmerov 27 m × 36 m je umiestnenych 1945 bodov. Dokazte, ze aspon 7 z nich mozno
naraz pokryt trojuholnikom plosneho obsahu 3 m2.

9. Poldavia ma rozlohu 268138 km2. Je v nej rozmiestnenych 13 televiznych vysielacov. Nejake miesto
splna normu kvality prijmu, ak nie je vzdialene od najblizsieho vysielaca viac ako 80 km. Dokazte, ze v
Poldavii existuje miesto s nekvalitnym televiznym prijmom.

10. V sade tvaru obdlznika o rozmeroch 100 m × 300 m musi byt menej nez 2576 stromov, ak vzdialenost
lubovolnych dvoch ma byt vacsia ako 4 m. Dokazte.

11. Dokazte, ze v obdlzniku o rozmeroch 197 × 94 sa neda umiestnit 24000 bodov tak, aby kazde dva
mali vzdialenost nie mensiu nez 1.

12. Dokazte, ze v obdlzniku o rozmeroch a, b sa neda umiestnit viac nez

4(a+ε)(b+ε)

πε2

bodov tak, aby

vzdialensot lubovolnych dvoch bola vacsia nez ε.

1Eulerova veta : Ak s je pocet stien, v pocet vrcholov a h pocet hran konvexneho mnohostena, tak s + v = h + 2

written by shelll, shelll.host.sk

7

13. Ak je v stvorci o strane 1 umiestnenych lubovolne 51 bodov, tak niektore tri spomedzi nich mozno
pokryt kruhom o polomere

1
7 .

14. Je danych 82 prirodzenych cisel. Dokazte, ze sa medzi nimi daju najst take dve, ze ich rozdiel je
delitelny cislom 81.

15. Ku kazdemu prirodzenemu cislu n existuje cislo zapisane v desiatkovej sustave v tvare 11...100...0,
ktore je delitelne cislom n. Dokazte.

16. Ku kazdemu prvocislu cislu p 6= 2, 5 existuje cislo zapisane v desiatkovej sustave v tvare 111...1,
ktore je delitelne cislom p. Dokazte.

17. Spomedzi n cisel mozno vybrat niekolko tak, ze ich sucet je delitelny cislom n. Dokazte.

18. Ignac sa pripravuje na prijimacie skusky. Po dobu troch mesiacov riesi aspon jednu ulohu denne.
Pritom za kalendarny tyzden neriesi viac ako 13 uloh. Dokazte, ze sa da najst niekolko po sebe iducich
dni v uvedenom obdobi, za ktore vyriesi prave 33 uloh.

19. Dokazte, ze dekadicky zapis niektorej mocniny cisla 37 konci skupinou cifier 00001.

20. Nech p je cislo nesudelitelne s cislom 10. Dokazte, ze pre kazde cilso n existuje take k 6= 0, ze pk ma
desiatkovy zapis konciaci skupinou n nul a cifrou 1.

21. Konferencie sa zucastnilo 70 delegatov, ktori hovoria 11 roznymi jazykmi (kazdy prave jednym).
Jednym jazykom hovori najviac 15 delegatov. Organizacny vybor rozhodol, ze za oficialny bude pova-
zovat taky jazyk, ktorym hovori najmenej 5 delegatov. Dokazte, ze na konferencii boli aspon 3 oficialne
jazyky.

22. Dane su dve cifry. Kolko sa da najst trojcifernych cisel zostavenych iba z tychto cifier takych, aby
sa lisili aspon na dvoch miestach?

23. Dokazte, ze nemozno najst viac ako 2n−1 n−cifernych cisel zostavenych z dvoch cifier tak, aby sa
lubovolne dve z nich lisili aspon na dvoch miestach. Dajte navod na zostrojenie 2n−1 n−cifernych cisel
s touto vlastnostou.

24. Dokazte, ze nemozno najst viac nez

j

2

n

n+1

k

n−cifernych cisel zostavenych z dvoch cifier tak, aby sa

kazde dve z nich lisili aspon na 3 miestach.

25. Dokazte, ze nemozno najst viac nez 2n−4 n−cifernych cisel zostavenych z dvoch cifier tak, aby sa
kazde dve z nich lisili aspon na 4 miestach.

26. Dokazte, ze nemozno najst viac ako kn−1 n−cifernych cisel zostavenych z dvoch cifier tak , aby sa
lubovolne dve z nich lisili aspon na dvoch miestach. Dajte navod na zostrojenie kn−1 n−cifernych cisel
s touto vlastnostou.

27. Dokazte, ze pomocou k cifier nemozno zostrojit viac nez

j

k

n

(nk+1−n)

k

n−cifernych cisel, z ktorych

kazde dve sa lisia aspon na 3 miestach.

28. Dokazte, ze pomocou k cifier nemozno zostrojit viac nez

k

n

P

m
j=0 (

n

j )(k−1)

j

n−cifernych cisel, z kto-

rych kazde dve sa lisia aspon na 2m + 1 miestach.

V nasledujucich ulohach rozumieme pod k−farebnym n−grafom uplny graf s n vrcholmi, ktoreho kazda
hrana je zafarbena jednou z k farieb.

29. V kazdom (a) dvojfarebnom 6−grafe (b) trojfarebnom 17−grafe (c) stvorfarebnom 66−grafe (d)
patfarebnom 327−grafe existuje jednofarebny trojuholnik. Dokazte.

30. Dokazte, ze v dvojfarebnom 6−grafe existuju aspon 2 jednofarebne trojuholniky. Zostrojte dvoj-
farebny 6−graf, v ktorom neexistuju 3 jednofarebne trojuholniky.

written by shelll, shelll.host.sk

8

31. Dokazte, ze v dvojfarebnom (a) 7−grafe (b) 8−grafe (c) 9−grafe (d) 10−grafe (e) 11−grafe existuje
apson (a) 4 (b) 7 (c) 11 (d) 16 (e) 22 jednofarebnych trojuholnikov.

32. Dokazte, ze pre n ≥ 10 existuje v dvojfarebnom n−grafe aspon

1
2 n

2 − 19

2 n + 61 jednofarebnych

trojuholnikov.

33. Dokazte, ze v kazdom dvojfarebnom 24−grafe existuju aspon dva jednofarebne 4−grafy.

34. Dokazte, ze v kazdom dvojfarebnom 192−grafe existuje aspon jeden jednofarebny 5−graf.

35. Kazda postupnost n2 + 1 roznych prirodzenych cisel obsahuje alebo rastucu alebo klesajucu pod-
postupnost n + 1 prvkov.

Teoria mnozin.

To, ze medzi mnozinami A, B existuje bijektivne zobrazenie, budeme symbolicky oznacovat A ∼ B alebo
A ≡ B. Vtedy hovorime, ze mnoziny A, B su ekvivalentne. Hovorime tiez, ze take mnoziny A, B maju
rovnaku mohutnost.

Oznacme n mohutnost mnoziny Nn = {0, 1, . . . , n − 1}, kde n ∈ N. Kazdu mnozinu, pre ktoru

plati, ze A ∼ Nn nazyvame konecnou, pricom n nazyvame poctom jej prvkov. Mnozina, ktora nie je
konecna, sa nazyva nekonecna. Kazdu mnozinu A, ekvivalentnu s mnozinou N = {0, 1, . . . }, nazyvame
spocitatelnou a jej mohutnost oznacujeme ℵ0.

Kazdu mnozinu A, ekvivalentnu s mnozinou vsetkych realnych cisel R, nazyvame kontinualnou a jej

mohutnost oznacujeme c.

Mohutnosti lubovolnych mnozin sa nazyvaju kardinalnymi cislami. Kardinalne cisla konecnych

mnozin sa nazyvaju konecne a kardinalne cisla nekonecnych mnozin nekonecne. Kardinalne cislo c sa
nazyva mohutnost kontinua.

Budeme hovorit, ze |A| ≤ |B|, ak A je ekvivalentna niektorej podmnozine mnoziny B. Budeme

hovorit, ze |A| < |B|, ak |A| ≤ |B|, ale A a B nie su ekvivalentne.

1. Dokazte, ze

(a) A ∼ A (reflexivnost)

(b) ak A ∼ B, tak B ∼ A (symetrickost)

(c) ak A ∼ B a B ∼ C, tak A ∼ C (tranzitivnost)

2. Dokazte, ze

(a) A ∼ B ⇐⇒ |A| = |B|

(b) ak |A1| = |A2|, |B1| = |B2| a |A1| ≤ |B1|, tak |A2| ≤ |B2|

(c) ak existuje surjektivne zobrazenie z A → B, tak |B| ≤ |A|

3.∗ Nech A ⊇ A1 ⊇ A2 a A ∼ A2. Dokazte, ze A ∼ A1.

4. Dokazte, ze ak |A| ≤ |B| a |B| ≤ |A|, tak |A| = |B| (Cantor-Bersteinova veta).

5. Dokazte, ze

(a) kazda podmnozina konecnej mnoziny je konecna;

(b) zjednotenie konecneho poctu konecnych mnozin je konecna mnozina;

(c) karteziansky sucin konecneho poctu konecnych mnozin je konecna mnozina.

6. Dokazte, ze

(a) konecna mnozina nie je ekvivalentna ziadnej svojej vlastnej podmnozine a ziadnej svojej nadm-

nozine.

written by shelll, shelll.host.sk

9

(b) dve konecne mnoziny su ekvivalentne prave vtedy, ked obsahuju rovnaky pocet prvkov.

(c) kardinalnych cisel je nekonecne vela.

7. Dokazte, ze z kazdej nekonecnej mnoziny mozeme vydelit spocitatelnu podmnozinu.

8. Dokazte, ze mnozina je nekonecna vtedy a len vtedy, ked je ekvivalentna niektorej svojej podmnozine.

9. Dokazte, ze kazda podmnozina spocitatelnej mnoziny je spocitatelna alebo konecna.

10.

(a) Nech obor definicie funkcie je spocitatelna mnozina. Dokazte, ze obor hodnot tejto funkcie je

konecna alebo spocitatelna mnozina.

(b) Dokazte, ze neprazdna mnozina A je spocitatelna alebo konecna prave vtedy, ked je mnozinou

hodnot niektorej funkcie z N → A.

11. Dokazte, ze ak zo spocitatelnej mnoziny vynechame konecnu podmnozinu, tak zostavajuca mnozina
je nekonecna.

12. Dokazte, ze

(a) ak A a B su spocitatelne mnoziny, tak A ∪ B je tiez spocitatelna;

(b) ak vsetky Ai su konecne, neprazdne a po dvoch disjunktne mnoziny, tak

[

i∈N

Ai

je spocitatelna mnozina.

13. Dokazte, ze

(a) ak A je nekonecna mnozina a B je konecna alebo spocitatelna mnozina, tak A ∪ B ∼ A;

(b) ak A je nekonecna a nespocitatelna mnozina a B je konecna alebo spocitatelna mnozina, tak

A \ B ∼ A.

14. Dokazte, ze ak A1, . . . , An (n ≥ 1) su spocitatelne mnoziny, tak aj A1 × · · · × An je spocitatelna
mnoznina.

15. Dokazte, ze

(a) mnozina celych cisel je spocitatelna;

(b) mnozina racionalnych cisel je spocitatelna;

(c) mnozina racionalnych cisel intervalu ha, bi je spocitatelna pre a < b;

(d) mnozina dvojic (x, y), kde x a y su racionalne cisla, je spocitatelna.

16. Dokazte, ze mnozina vsetkych konecnych postupnosti, vytvorenych z prvkov niektorej spocitatelnej
mnoziny je spocitatelna.

17. Dokazte, ze mnozina vsetkych konecnych podmnozin spocitatelnej mnoziny je spocitatelna.

18. Dokazte, ze mnozina mnohoclenov jednej premennej s celociselnymi koeficientami je spocitatelna.

19. Dokazte, ze mnozina algebraickych cisel, t.j. cisel, ktore su korenmi mnohoclenov jednej premennej
s celociselnymi koeficientami, je spocitatelna.

20. Dokazte, ze lubovolna mnozina po dvoch disjunktnych otvorenych intervalov na realnej priamke nie
je vacsia nez spocitatelna.

written by shelll, shelll.host.sk

10

21.∗ Dokazte, ze mohutnost lubovolnej mnoziny po dvoch disjunktnych pismen T v rovine nie je vacsia
ako spocitatelna.

22. Dokazte, ze ak A ⊆ R a existuje δ > 0 take, ze pre vsetky rozne prvky x, y ∈ A take, ze plati
|x − y| ≥ δ, tak A je konecna alebo spocitatelna.

23. Dokazte, ze mnozina bodov nespojitosti rydzomonotonnej funkcie na realnej osi nie je viac ako
spocitatelna.

24. Dokazte, ze

(a) (0, 1) ∼ h0, 1i ∼ h0, 1) ∼ (0, 1i;

(b) ha, bi ∼ hc, di, kde a < b a c < d;

(c) ha, bi ∼ R

25. Dokazte, ze mnoziny bodov stvorca a usecky su ekvivalentne.

26. Dokazte, ze mnoziny bodov dvoch kruznic su ekvivalentne.

27. Dokazte, za R

n ∼ Rm (n, m ≥ 1).

28. Zostrojte bijektivne zobrazenie medzi bodmi stvorca a roviny.

29.∗ Dokazte, ze mnozina bodov intervalu h0, 1i nie je spocitatelna.

30. Aka je mohutnost mnoziny vsetkych iracionalnych cisel?

31. Dokazte existenciu transcendentnych (t.j. nealgebraickych) cisel.

32. Dokazte, ze zjednotenie konecneho alebo spocitatelneho poctu mnozin mohutnosti c ma mohutnost
c.

33.∗ Dokazte, ze mnozina vsetkych spocitatelnych postupnosti prirodzenych cisel ma mohutnost c.

34. Dokazte, ze

(a) mnozina vsetkych spocitatelnych postupnosti zlozenych z 0 a 1 ma mohutnost c;

(b) |P(N)| = c.

35. Dokazte, ze

(a) ak vsetky Ai su kontinualne, tak |A1 × · · · × An| = c;

(b) ak pre vsetky i plati |Ai| = i a |I| = ℵ0, tak

Y

i∈I

Ai

= c

36. Aka je mohutnost mnoziny

(a) vsetkych spocitatelnych postupnosti realnych cisel;

(b) vsetkych spojitych funkcii na realnej priamke;

(c) rydzomonotonnych funkcii na realnej priamke?

37.

Nech A je spocitatelna mnozina bodov na realnej priamke.

Mozno potom vybrat a tak, aby

{x + a|x ∈ A} ∩ A = ∅?

38.∗ Dokazte, ze mnozina realnych funkcii definovanych na intervale h0, 1i ma mohutnost vacsiu ako c.

written by shelll, shelll.host.sk

11

39.

Dokazte, ze mohutnost mnoziny vsetkych funkcii definovanych na intervale ha, bi pre a < b a

nespojitych aspon v jednom bode je vacsia ako c.

40.∗ Dokazte, ze mnozina vsetkych podmnozin P(A) mnoziny A ma mohutnost vacsiu ako A.

41. Nech S je system mnozin taky, ze pre kazdu mnozinu A z S existuje mnozina B z S taka, ze nie
je ekvivalentna ziadnej podmnozine mnoziny A. Dokazte, ze zjednotenie vsetkych mnozin z S nie je
ekvivalentne ziadnej podmnozine mnoziny z S.

42. Dokazte, ze neexistuje mnozina, ktora obsahuje vsetky mnoziny.

43. Budeme hovorit, ze postupnost kladnych celych cisel b1, b2, . . . rastie rychlejsie ako postupnost
a1, a2, . . . , ak

lim

n→∞

an

bn

= 0

Dokazte, ze pre kazdu postupnost kladnych celych cisel existuje postupnost, rastuca rychlejsie.