IBOOO Úvod do informatiky -- príklady na procvičení
Sada 6 -- Řešení
Upozornění
Vzorová řešení dostáváte k dispozici, abyste mohli zkontrolovat správnost svých řešení.
Můžete je použít i jako návody k řešení jednotlivých příkladů tak, že je budete číst po
částech a budete se snažit další krok provést vždy sami. Příklady ztratí veškerý svůj
smysl, pokud se je budete učit jako básničku. Snažte se nad nimi přemýšlet a vyřešit je
sami, než se podíváte do vzorových řešení.
Téma
Vlastnosti relací. Ekvivalence, rozklad množiny, třídy ekvivalence. Uspořádání, předuspořádání.
Minimální, maximální, nejmenší a největší prvky uspořádaných množin. Horní
a dolní závora, suprémum a infimum. Relace pokrytí na uspořádané množině. Hasseovské
diagramy.
Příklad 1.
a) Dokažte, že každé uspořádání je předuspořádání, ale obrácené tvrzení neplatí.
b) Dokažte, že každá ekvivalence je předuspořádání, ale obrácené tvrzení neplatí.
Řešení
a) Nechť M je libovolná množina a nechť i? C M x M je libovolné uspořádání na M.
Potom R je reflexivní, antisymetrická a tranzitivní relace. Protože je relace R reflexivní
a tranzitivní, je to předuspořádání.
Abychom dokázali, že obrácené tvrzení neplatí, nalezneme předuspořádání, které
není uspořádáním. Nechť M = {a, b} a R = M x M. Důkaz, že R je hledaná relace, tedy
že i? je reflexivní a tranzitivní, ale není antisymetrická, ponecháváme čtenáři.
b) Nechť M je libovolná množina a nechť i? C M x M je libovolná ekvivalence na M.
Potom R je zejména reflexivní a tranzitivní, je to tedy předuspořádání.
Abychom ukázali, že obecné tvrzení neplatí, nalezneme předuspořádání, které není
ekvivalencí. Nechť M = {a,b,c} & R = ÍCIM U {(a, b), (a, c), (b, c), (c, &)}.
Příklad 2.
Rozhodněte, které z následujících relací jsou předuspořádání, uspořádání, resp. úplná
uspořádání. Svá tvrzení dokažte. Pokud je to nutné, tak v definicích předpokládáme, že
(A, <A) a
(-S) < B ) Js o u
uspořádné množiny.
a) R= {(a,b),(b,c),(a,c)} C M x M, kde M = {a,b,c}
b) R = {(a, a), (b, b), (b, c), (c, c)} C M x M, kde M = {a, b, c}
c) R = {(X, Y) | X C Y} C 2A
x 2A
d)R={(f,g)\f(A)Cg(A)}CBA
xBA
e) R = {((a, b), (c, d)) | a <A c a d <A b} C (A x A) x (A x A)
f) R = {{a, b) | 3 c G M : a = b + c} C M x M, kde M = {m e N0 | m < n} pro n e N
g) R = {(0, 0)} U {(a, b) | a ˇ b > 0 V a < b} C Z x Z
h) R = {((a, b), (a^)) \_b <B c} C (A x B) x (A x B)
j) R = {(X, Y) | X C Y} C 2A
x 2A
1
Řešení
a) Relace i? je sice tranzitivní a antisymetrická, není však reflexivní. Například (a, a,) ^
^ R. Proto se nejedná ani o předuspořádání, ani o uspořádání.
b) Relace R je reflexivní, tranzitivní i antisymetrická. Jedná se proto o uspořádání.
Toto uspořádání není úplné, protože (a, b) ^ R a (6, a) ^ R (prvky a a b jsou nesrovnatelné)
.
c) Relace R je reflexivní, protože X C X platí pro každou množinu X. Relace je
tranzitivní, protože pro libovolné tři množiny X,Y, Z, pro které platí X C Y a. Y C Z,
platí také X C Z. (Detailně to dokažte!) Relace je antisymetrická. Nechť X, Y jsou dvě
libovolné množiny. Nechť platí I C ľ a ľ C I . Potom X = Y.
Uspořádání to není úplné. Nechť A = {a, b}. Potom množiny {a} G 2 a {6} G 2
jsou nesrovnatelné.
d) Připomeňme, že definici funkce / : A --ˇ B rozšiřujeme na množiny M, M C A
předpisem f (M) = {f (a) \ a G M}.
Relace R je reflexivní, protože f (A) = f (A). Tranzitivita R plyne z tranzitivity
inkluze množin. (Dokažte tranzitivitu i detailně!) Relace i? je tedy jistě předuspořádání.
Relace R není uspořádání, protože není antisymetrická. Uvažme totiž A = B = {a,b}
a funkce / = {(a, a), (b, b)} a g = {(a, 6), (6, a)}. Potom f (A) = g(A), tedy (f,g) G R,
a zároveň g(A) = f (A), tedy (g, f) G R. Přitom / ^ g.
e) Uvědomte si, že <A a <B jsou uspořádání. Můžeme tedy využít toho, že jako relace
mají příslušné vlastnosti.
Relace R je reflexivní. Nechť a, b G A jsou libovolné. Potom ((a, 6), (a, 6)) G R,
protože a <A a a b <A b.
Relace R je tranzitivní. Nechť (ai, 6i), (2,62), (3, 63) G A x A jsou libovolné. Nechť
platí ((ai,6i), (02,62)) G i? a ((02,62), (03,63)) G R. Potom ai <A a2 <A 3, tedy
cil <A a
3- Zároveň 63 <A 62 <A 61, tedy 63 <A b\. Celkem ((a\, 61), (as, 63)) G i?.
Relace R je antisymetrická. Nechť (a,b),(c,d) E A x A jsou libovolné a platí
((a, 6), (c, d)), ((c, d), (a, 6)) G R. Potom a <A C a zároveň c < ^ a, tedy a = c. Současně
d <A 6 a zároveň 6 < ^ d, tedy b = d. Celkem dostáváme (a, 6) = (c, <i).
Relace R není úplné uspořádání. V podstatě se totiž jedná o uspořádání po složkách
součinu uspořádaných množin (A, <A) a (A,>A), kde >A = <A_ 1
- Lze tedy použít
analogický protipříklad. (Napište jej!) Právě jsme použili tvrzení: pokud R C M x M
je uspořádání, potom R~ľ
je také uspořádání. Dokažte toto tvrzení! Rozmyslete si, zda
analogické tvrzení platí pro předuspořádání, resp. úplné uspořádání.
f) Relace R je reflexivní, protože 0 G M a a + 0 = a pro každé a G No- Relace R
je tranzitivní. Nechť a,b,c G M, (a, b), (b, c) G R. Potom existují di,d2  M tak, že
a = b + di a 6 = c + cfôˇ Celkem dostáváme a = c + d\+d2- Zbývá ukázat, že d\ + d2 G M.
To ovšem platí, protože a, c, di i d2 jsou nezáporná, takže musí platit 0 < d\ + d2 <
< a < n. Symbol < zde reprezentuje standardní uspořádání přirozených čísel. Relace
R je antisymetrická. Nechť pro a, b G M platí (a, 6) G i?, (6, a) G i?. Potom existují
ci,c2 E M taková, ž e a = 6 + ci a 6 = a + C2. Odtud dostáváme a = a + c\ + c2. Protože
c\ i c2 je nezáporné, musí platit 0 = c\ = c2, odkud a = b.
Uspořádání je úplné. Nechť a, 6 G M. Bez újmy na obecnosti předpokládejme, že
a < b. Potom existuje c G No, 0 < c < 6 < n takové, že 6 = a+c. Vzhledem k podmínkám
kladeným na c musí platit c G M a tedy (6, a) G R.
g) Relace R je reflexivní. Nechť a E Z. Je-li a < 0 nebo a > 0, potom a ˇ a > 0, tedy
(a, a) G i?. Je-li a = 0, potom (0, 0) G i? přímo z definice.
2
Relace je tranzitivní. Nechť a, b, c E Z, (a, b), (b, c) E Z. Rozlišíme tři případy podle
hodnoty b. Pokud 6 = 0, potom a < 0 < c, odkud (a, 6) E R. (Tyto kroky nejsou tak
zřejmé. Dobře si je promyslete!) Pokud 6 < 0, potom a < 0. Rozlišíme dva podpřípady
podle c. Pokud c < 0, potom a ˇ c > 0 a (a, c) E R. Pokud 0 < c, potom a < c a také
(a,c) E R. Pokud 0 < 6, je důkaz analogický jako v předchozím případě. Detailně jej
proveďte sami
Tedy relace R je jistě předuspořádání. Relace není uspořádání, protože není antisymetrická.
Například (1, 2), (2,1) E R, ale 1 ^ 2.
h) Relace R je reflexivní, tranzitivní i antisymetrická, což plyne z toho, že <B je uspořádání.
(Proveďte důkaz detailně!) Relace R obecně nemusí být úplné uspořádání a to
ani tehdy, pokud <B je úplné. Stačí, aby \A\ > 1 a \B\ > 0.
i) Tento příklad je zcela analogický příkladu (c). Relace je uspořádání, které není
úplné. Protipříklad úplnosti lze použít stejný jako v příkladě (c).
Příklad 3.
Nechť ň C M x M j e předuspořádání na M. Nechť ~ je jádro R. Dokažte, že uspořádaná
množina (M/L,<) indukovaná předuspořádáním i? je dobře definovaná. Tj. dokažte, že
~ C M x M je skutečně ekvivalence a < C M/L x M/L je skutečně uspořádání.
Řešení
Nechť i? C M x M je předuspořádání na M. Jádrem předuspořádání R rozumíme
relaci ~ C M x M takovou, že pro x,y E M platí x ~ y právě tehdy, když (x, y) E R a
současně (y, x) E R. Ukážeme, že ~ je ekvivalence.
Relace ~ je reflexivní, protože R je reflexivní. (Opravdu chápete, proč to platí?)
Relace ~ je symetrická přímo z definice. (Rozmyslete si to! Je snadné k tomuto závěru
dojít na základě špatných úvah. Relace R není symetrická.) Abychom dokázali tranzitivitu,
uvažme a,b,c E M takové, že a ~ 6 a 6 ~ c. Z definice relace R plyne
(a, 6), (6, a), (6,c), (c, 6) E R. Protože i? je tranzitivní, musí platit (a,c), (c,a) E R, odkud
a ~ c.
Protože ~ je ekvivalence, má smysl hovořit o rozkladu M/L. Předuspořádání R
indukuje na M/L relaci < C M/L x M/L definovanou pomocí reprezentantů. Pro libovolné
x,y E M platí [x] < [y] právě tehdy, když (x,y) E R.
Kdybychom chtěli být důslední, museli bychom na tomto místě ověřit, že definice
pomocí reprezentantů je korektní. Museli bychom dokázat: je-li (xo, yo) E R pro nějaká
xo, yo  M, potom pro všechna x E [xo] a pro všechna y E [yo] platí (x, y) E R. Dokažte
to! (Využijete především tranzitivitu R.)
Dokážeme, že < je uspořádání. Relace < je reflexivní, protože R je reflexivní.
(Promyslete si to!) Relace < je tranzitivní, protože R je tranzitivní. Pro antisymetrii
uvažme [x], [y] E M/L tak, že platí [x] < [y] a [y] < [x]. Z definice relace < potom platí
(x,y),(y,x) E R a tedy x ~ y. Proto [x] = [y], což jsme měli dokázat.
Příklad 4.
Nechť i? C M x M je ekvivalence (je to tedy i předuspořádání).
a) Jak vypadá jádro R?
b) Jak vypadá uspořádání indukované relací R na příslušném rozkladu?
3
Řešení
a) Nechť x, y G M a značme ~ jádro R. Potom z definice x ~ y právě tehdy, když
(x,y), (y,x) G i?. Protože R je ekvivalence, je symetrická, a tedy (x,y), (y,x) G i?
nastane právě tehdy, když (x, y) G i?. Proto ~ = R. (Zároveň jsme provedli oba směry
důkazu rovnosti množin R a ~.) Relace R je tedy svým vlastním jádrem.
b) Nechť x,y G M. Předpokládejme, že [x] < [y], kde [x], [y] G M/L. Potom z definice <
platí (x,y) G i?. Protože i? je symetrická, platí i (y,x) G R, odkud [y] < [x]. Protože <
je uspořádání, tedy relace antisymetrická, musí platit [x] = [y\. Ukázali jsme, že pokud
jsou dvě třídy ekvivalence v relaci <, potom jsou stejné. A protože relace < je reflexivní
(je to uspořádání), můžeme shrnout, že < = idjy^.
Příklad 5.
Nakreslete grafy relací a Hasseovské diagramy následujících uspořádaných množin.
a ) (2{a
>6
>c
},C)
b) ( { Í Í G N O |  < 10}, |)
c) (jneNo I n< 3},<)
d) ({ne No j n< 3},id)
Řešení
b) V tomto případě graf ponecháváme čtenáři kvůli prostorové náročnosti přehledného
zobrazení.
4
c)
3
2
1
O
d)
O 1 2 3
Příklad 6.
Pro uspořádané množiny zadané Hasseovskými diagramy
Ü3 Ü4 04
62
e3
nakreslete Hasseovské diagramy (nejen) následujících uspořádaných množin.
a) (B x A,<), kde < je uspořádání po složkách
b) (B x A,^<), kde ^ je lexikografické uspořádání
c) (D x >,<), kde < je lexikografické uspořádání
d) (C x E,^<), kde ^ je uspořádání po složkách
Řešení
a)
(62,03) (62,04)
(62,02) (61,03)
(62,01) (61,02)
(61,01)
(61,04)
5
b)
c)
d)
(c2,e4)
(62,03) (62,04)
(62,^2)
(62,^1)
(61, a3) (61, a4)
(61, a2)
(61, i)
(^4,62)
(<Í4,6l)
{<hM) (4,62)
(d2,6i) (4,6i)
(di, h)
(di,61)
(C3,e4)
(c2,ei) (c2,e2) (ci,e4) (c3,ei) (c3,e2) (c2,e3) (C3,e3)
(ci,ei) (ci,e2) (ci,e3)
Příklad 7.
Nakreslete Hasseovský diagram množiny funkcí {/i, /2, Í3, Í4, /s, f6, h} s uspořádáním
po bodech, kde pro i = 1, 2, 3, 4, 5, 6, 7 jsou funkce /i : N --ˇ N definovány následovně
fi(n) = 1
Í2(n) = n+ 1
h(n) = n2
h(n) = n + n
h(n) = n3
fein) = n2
+ 6
h(n) = 2 n
6
Řešení
77 76 h
jXj72 73
A
Příklad 8.
Určete jádro předuspořádání i?, příslušný rozklad a uspořádání indukované na tomto
rozkladu v případě, že
a) R = {(f, g) I f (A) C g(Ä)} C S"4
x BA
, kde A & B jsou libovolné množiny
b) i? = {(0,0)} U {(a, 6) | a ˇ 6 > 0 V a < 6} C Z x Z
c) i? = {(a, b) | 3 k,l,m,n G N0 : a = 5m + k Ab = bn + l Ak < 1} C N0 x N0
d) i? = {(a, b) | pro každé prvočíslo p platí: p | a = ^ p | 6 } C N x N
Řešení
a ) ~ = {(/,0)|/(A) = 0 ( A ) } C 2 ^ x 2 ^
M/,, = {{# G S A
| /(A) = 0(A)} | / G SA
}
< = {([/], M) I /(^) C y(A)} C MA x M/L
Protože jsme konstrukci provedli přesně podle definice a vět o vztahu rozkladu a
příslušné ekvivalence, není potřeba nic dalšího dokazovat.
b) ~ = {(0, 0)} U {(a, b) | a ˇ b > 0} C Z x Z
M/L = {{a G Z | a < 0}, {0}, {a G Z | a > 0}}
< = {([a], [6]) | a < 6} C M/L x M/L
Abyste nemuseli dokazovat korektnost těchto konstrukcí, stačí, když vyjdete z definic
a známých tvrzení a z nich získané vztahy upravit do uvedené podoby. Zejména u definice
< není zcela zřejmé, proč nezávisí na reprezentantech. Kolik prvků má <? Zapište
relaci < i výčtem jejích prvků.
c) Relace R v tomto případě není předuspořádání. Proč? Změňte podmínku k < l
v definici relace tak, aby R bylo předuspořádání a vyhovovalo následujícím výsledkům.
~ = {(a, b) | a = b mod 5} C N0 x N0
M/L = {{a G No | a = i mod 5} | i G No, i < 5}
< = {([5m + fc],[5n + /]) | k,l,m,n G N0 A k < l < 5} C M/~ x M/~
d) ~ = {(a, b) | pro každé prvočíslo p platí: p | a <í=^ p | 6} C N x N
Nechť A je konečná množina prvočísel. Položme
^A = { G N I rozklad a na prvočísla obsahuje právě prvočísla z množiny A}
M/L = {NA I A je konečná množina prvočísel}
< = {(NA,NB)\ACB}C M/L x M/L
Příklad 9.
Určete všechny minimální, maximální, nejmenší a největší prvky uspořádané množiny
a) (2M
, C), kde M je libovolná množina
b)(No,|)
c) ({n G No | n < 10}, |)
d) (Z,idz)
e) (Ax, <), kde < je uspořádání po složkách a uspořádané množiny (A, <A) a (E, <E)
jsou zadané následujícími Hasseovskými diagramy.
7
ß3 0"i
\ / C4
T a 2
A
* ˇ ˇ ˇ
ai ei e2 e3
(A < A ) (E, <E)
Řešení
a) Protože pro každou množinu X C M platí | C I a I C M, je 0 jediný nejmenší a
M jediný největší prvek množiny (2 , C). Proto je 0 také prvek minimální a M je prvek
maximální.
b) Protože pro každé n E No platí 1 | n a n | 0, je 1 nejmenší a 0 největší prvek
množiny (No, |). Proto je 1 také prvek minimální a 0 prvek maximální. Jak by se
výsledky změnily, kdybychom uvažovali přirozená čísla bez nuly?
c) Jedná se o konečnou verzi předchozího případu, výsledky jsou proto stejné. Jak by
se změnily, pokud bychom vynechali nulu? (Dopadne to jinak než v předchozím případě!)
d) Nechť a,b E Z, a ^ b. Potom a a b jsou nesrovnatelné. Proto každé a G Z je
minimální i maximální prvek a neexistuje žádný nejmenší ani největší prvek.
e) Minimální prvky množiny A x E v uspořádání po složkách jsou (a\,ei), (1,62) a
(0,1,03). Maximální prvky jsou (03,64), (04,64), (03,63) a (04,63). Množina nemá žádný
nejmenší ani největší prvek.
Příklad 10.
a) Dokažte, že každá uspořádaná množina má nejvýše jeden nejmenší prvek.
b) Dokažte, že každá uspořádaná množina má nejvýše jeden největší prvek.
Řešení
a) Sporem předpokládejme, že nějaká uspořádaná množina (M, <) má dva nejmenší
prvky, značme je a a b. Protože a je nejmenší, pro každé x E M platí a < x, zejména
a < b. Protože b je nejmenší, analogicky dostáváme b < a. Protože < je uspořádání, je
to antisymetrická relace a musí platit a = b.
b) Důkaz je podobný jako v předchozím případě, ponecháváme jej proto čtenáři.
Příklad 11.
Pro danou uspořádanou množinu (M, <) a její prvek x určete všechny prvky y, které
prvek x pokrývá, a všechny prvky z, které pokrývají prvek x.
a) (M, <) = (2{a
>6
>c
Ae}; c ) , x = {a, c, d}
b) (M,<) = (No,|),x = 924
c) (M, <) = (A x B, ^ ) , x = (a2, fe), kde ^ je lexikografické uspořádání a (A, <X) =
= ({0,1,0,2,0,3}, idA U {(0,1,0,2)}) a (B, <B) = ({bi, b2, 63},ids U{(6i, 62), (&2,&3), (&i,&3)})
Řešení
a) Prvek x pokrývá prvky {a,c}, {c,d} a {a,d}.
Prvek x pokrývají prvky {a, b, c, d} a {a, c, d, e}.
8
b) Rozložme prvek x na prvočísla: 924 = 22
* 3 ˇ 7 ˇ 11.
Prvek x pokrývá prvky 2 ˇ 3 ˇ 7 ˇ 11 = 462, 22
* 7 ˇ 11 = 308, 22
* 3 ˇ 11 = 132 a
22
* 3 ˇ 7 = 84.
Prvek x pokrývají prvky 22
* 3 ˇ 7 ˇ 11 ˇ p, kde p je libovolné prvočíslo.
c) Prvkem x je pokryt prvek (02, bi). Prvek x je pokryt prvkem (02, 63).
Příklad 12.
Najděte takovou uspořádanou množinu, v níž každý prvek kromě minimálních a maximálních
prvků bude pokrývat dva prvky a bude pokrýván třemi prvky, a uspořádaná
množina bude obsahovat alespoň tři takové prvky.
Řešení
Řešením je například uspořádaná množina zadaná následujícím Hasseovským diagramem.
Kromě tří prvků vyžadovaných v zadání jsou všechny ostatní prvky minimální
nebo maximální.
Zkuste najít menší (s ohledem na počet prvků) řešení. Kolik prvků má nejmenší
řešení?
Příklad 13.
Pro danou podmnožinu X uspořádané množiny (M, <) určete její dolní závory, horní
závory, infimum a supremum.
a) (M, <) = (2A
, C), kde A je množina a pro n G N je X = {Y C A \ \Y\ = n}
b) (M, <) = (2{°.6
.cAe}> c ) , X = {{b, c}, {c, d}}
c) (M, <) = (2{°.6
.cAe}> c ) , X = {{c}, {a, c, d}}
d) (M, <) = ( N , < ) , I = { n G N | n < n0} pro nějaké n 0 e N
e) (M, <) = (Z, <), X = {3k - 2 | k e Z}
f) (M, <) = (No, |), X C N, |X| = n pro nějaké n G N
g) (M,<) = (No,\),X = {2n
\neN}
Řešení
a) Nejprve si uvědomme, že pokud A je konečná a platí \A\ < n, potom X = 0 a je
to totéž, jako by bylo n = 0. Je-li A nekonečná, potom pro každé n G N platí n < \A\.
Proto se stačí omezit na taková n, která splňují 0 < n < \A\.
Pokud n = 0, potom X = {0} a 0 je jedinou horní závorou i jedinou dolní závorou
množiny X. Tedy je to i supremum i infimum množiny X.
Pokud A je konečná a n = \A\, potom X = {A} a A je jedinou horní závorou i
jedinou dolní závorou množiny X. Tedy je to i supremum i infimum množiny X.
Nechť 0 < n < \A\ a H C A je horní závora množiny X. Ukážeme, že H = A. K
tomu stačí ukázat ACH, protože opačná inkluze plyne přímo z předpokladů. Nechť
9
a E A. Potom jistě existuje Y C A taková, že \Y\ = n a a E Y. (Intuitivně je to zřejmé,
ale uměli byste to dokázat?) Protože |y| = n, platí Y E X a tudíž a E H (jinak by H
nebylo větší než Y). Tedy A je horní závora množiny X. Protože je to jediná horní
závora, je to zároveň i supremum.
Nechť 0 < n < \A\ a nechť D C A je dolní závora množiny X. Ukážeme, že D = 0.
Sporem tedy předpokládejme, že existuje a E D. Jistě existuje Y C A \ {a}, \Y\ = n,
takže Y E X. Protože a ^ Y, neplatí D C Y a D tak nemůže být dolní závorou X.
Proto D = 0. Protože je to jediná dolní závora, je to i infimum.
Proč jsme řešili případy n = 0 a n = \A\ zvlášť? Kde jsme ve zbylé části využili
0<n< \A\?
b) Dolní závory množiny X jsou {c} a 0, infimum je {c}.
Horní závory množiny X jsou {b,c,d}, {a,b,c,d}, {b,c,d,e} a {a,b,c,d,e}, supremum
je {b, c,d}.
c) Dolní závory množiny X jsou {c} a 0, infimum je {c}.
Horní závory množiny X jsou {a,c,d}, {a,b,c,d}, {a,c,d,e} a {a,b,c,d,e}, supremum
je {a, c, d}.
d) Jedinou dolní závorou množiny X je číslo 1, je to tedy zároveň i infimum.
Horními závorami množiny X jsou všechna čísla m E N, no < m. Suprémem je no.
e) Žádná dolní závora množiny X neexistuje. Sporem předpokládejme, že m G Z je
dolní závora množiny X. Pro nějaká k E Z, r E No, 0 < r < 3 platí m = 3k + r. Potom
m --r -- 2 E X, ale m -- r -- 2<m, takže m nemůže být dolní závora množiny X. Protože
neexistuje žádná dolní závora X, neexistuje ani infimum X.
Zcela analogicky je možné dokázat, že neexistuje žádná horní závora množiny X, a
proto neexistuje ani supremum X.
f) Dolní závorou množiny X je každý společný dělitel prvků X. Infimem je největší (ve
standardním uspořádání přirozených čísel) společný dělitel prvků X.
Horní závorou množiny X je každý společný násobek prvků X, tj. každé takové
přirozené číslo, které je dělitelné každým prvkem X. Supremum je nejmenší (ve standardním
uspořádání přirozených čísel) společný násobek prvků X.
Důkazy ponecháváme čtenáři. Dávejte pozor, kdy operujete s kterým uspořádáním.
g) Dolními závorami množiny X jsou 1 a 2, infimem je číslo 2. Jedinou horní závorou
a tedy suprémem je číslo 0. Důkaz, že jiná horní závora neexistuje, by používal stejnou
techniku, jako byl použit v případě (e).
10