21
Obory přirozených, celých a racionálních čísel
Y této kapitole ukážeme, jak lze vybudovat teorii přirozených čísel, celých čísel a racionálních čísel. Budeme předpokládat, že známe jen intuitivní teorii množin, s kterou byl čtenář seznámen v dřívějších učebních textech. Na základě této teorie zavedeme pojem „přirozené číslo" jako pojem, který vyhovuje speciálnímu axiomatickému systému. Tento axiomatický systém byl zaveden na konci 19. století italským matematikem G. Peanem, který jím úspěšně charakterizoval přirozená čísla. Z těchto axiomů odvodíme některé základní vlastnosti přirozených čísel, které jsou čtenáři dobře známy ze střední školy. Celá čísla pak dostaneme jako „rozdílovou grupu" aditivní pologrupy přirozených čísel a čísla racionální definujeme pomocí „podílového tělesa" okruhu celých čísel.
Pojem přirozeného čísla patří k nejzákladnějším pojmům v matematice, který člověk používal od pradávných dob a který je jedním z prvních matematických pojmů, s kterými se seznamuje dítě. V těchto dobách však jsou znalosti o přirozených číslech získávány jen intuitivní cestou. Podobně je tomu s pojmem celého čísla, k jehož poznání dochází velmi brzo po přirozeném čísle, a s pojmem racionálního čísla.
Náš způsob výkladu je proveden abstraktní cestou, uvedené pojmy jsou definovány jako abstraktní objekty splňující jisté vlastnosti.
4. Polo okruh přirozených čísel
4.1. Definice. Libovolnou množinu Af budeme nazývat množinou přirozených čísel a každý prvek z Af přirozeným číslem, jestliže ke každému prvku x £ Af je přiřazen prvek x £ Af, který nazýváme následník prvku x tak, že platí:
i) Existuje alespoň jeden prvek množiny Af, který není následníkem žádného prvku z Af. (Jeden z těchto prvků označme symbolem 1 = ljy-.)
ii) Pro libovolné x, y £ Af, z x = y plyne x = y.
iii) Nechť M C Af má následující vlastnosti
a) 1 £ M,
b) x £ M      x G. M. Pak M = Af.
Vlastnost iii) se nazýva axiom úplné indukce. Vlastnosti i)-iii) jsou ekvivalentní s tzv. Peanovými axiomy.
4.2. Poznámky.
a) Přiřazení následníků v množině je vlastně zobrazení : Af -> Af. Přesnější než o množině přirozených číslech by bylo hovořit o algebraické struktuře
22
Obory přirozených, celých a racionálních čísni
přirozených čísel, čímž bychom měli na mysli uspořádanou dvojici {Af,~). Z důvodů stručnosti a větší přehlednosti textu to však nebudeme dělat a budeme psát 3 množině Af, majíce na mysli, že přiřazení následníků v množině Af je pevně zvoleno.
b) V teorii množin se ukazuje, že taková množina Af existuje. Je to množina kardinálních čísel konečných neprázdných množin. Závěrem tohoto odstavce (věta 4.30) ukážeme jednoznačnost množiny Af.
c) Z tvrzení 4.3 (c) plyne, že prvek množiny Af s vlastností i) je určen jednoznačně.
V dalším textu budeme předpokládat, že je množina přirozených čísel, tj. má vlastnosti i)-iii) z definice 4.1.
4.3. Tvrzení. Nechť x,y £ Af. Pak platí:
(a) x^y=^x^ y,
(b) x ^ x, i
(c) x £ 1 =» 3 « 6 Af : * =
Důkaz. Část (a) plyne ihned z vlastnosti ii) definice 4.1.
Položme M = {z £ Af \ z f ž}. Výrok (b) je ekvivalentní s M = A/VPodle i) v definici 4.1 platí 1 £ M. Buď nyní x £ M takové, že x g M. Tedy x = x a podle ii) v definici 4.1 platí x = x, což je spor s x £ M. Proto x6 M .===* S £ M a z axiomu úplné indukce plyne M = Af.
Položme M = {z e Af \ 3v e Af,v = z}U{l}. Je-li x £ M, pak zřejmě x £ M a z axiomu úplné indukce tedy plyne M — Af, tudíž (c).
4.4. Věta. Na množine Af existuje právě jedna operace + taková, že pro každé x, y £ Af platí:
(a) x + 1 — x,
(b) x + y = x + y.
Pro tuto operaci + a pro každé x,y £ Af pak platí:
(c) 1 + x — x, {ď)x + y = x + y.
Důkaz. Nejdříve ukažme existenci takové operace +. Nechť AA je množina všech x £ Af, ke kterým existuje zobrazení fx množiny Af do sebe takové, že platí:
= x,   U {V) = f x {y) Pro každé y € Af. {*)
Poznamenejme, že fx bude vlastně přičtení x zleva.
Položíme-li fi{y) = y pro y € Af, pak /i je takové zobrazení pro x = 1. Tudíž 1 e M.
Buď x £ M a fx nechť je zobrazení splňující (*) pro toto x. Zkonstruujeme nyní fx. Pro y £ Af položíme h{y) = fa(y). Pak h{l) = /„(l) = x a pro y e Af máme _ -,. _
h(v) = MV) -f*{y) = k{y)-
Tudíž f x splňuje (*), a proto x £ M. Z axiomu úplné indukce plyne M = Af.
Kap. 4. Polookruh přirozených čísel
23
Předpokládejme, že pro některé x G Af existují dvě zobrazení vlastností (*). Označme je fx, gx a položme M = {y £ Af \ fx{y) = gx{y)}- Zřejmě 1 £ M. Pokud z 6 A4, pak
fx(ž) = - 9x(z) = 9x(ž),
tudíž I £ a z axiomu úplné indukce dostáváme AA — Af. Tedy /a = gx a pro každé x existuje právě jedno zobrazení vlastností (*).
Nyní můžeme operaci + pro x,y G Af definovat vztahem x + y — fx(y)- Tato operace, vzhledem k (*), splňuje podmínky (a) a (b).
Z uvedeného vztahu x + y = fx(y) dostáváme 1 -f x = fi(x) = x a x + y = = = fx{y) = í + y- Platí tudíž i (c) a (d).
Jednoznačnost uvedené operace + plyne z přechozího, neboť každá operace + splňující (a), (b) indukuje pro libovolné x £ M zobrazení fx, definované vztahem fx(y) — x + y, které splňuje vlastnosti (*). Pokud by existovaly dvě různé operace splňující (a), (b), pak by pro nějaké x musela existovat dvě různá zobrazení vlastností (*), což dle předchozího není možné.
Věta je tím dokázána.
4.5. Definice. V dalším pro operaci na množině Af uvažovanou ve větě 4.4 vyhradíme symbol 4- a budeme ji nazývat sčítání. Dvojice (Af, + ) je pak grupoid.
Odvodíme si nyní některá tvrzení o této operaci +.
4.6. Věta. Operace + na množině přirozených čísel Af je asociativní a komutativní.
Důkaz. Nechť x,y £ Af. Položme M = {z £ Af \ (af+ y) + z = x + (y + z)};. Jelikož
(x + y) + 1 = x + y,   x + (y + 1) = x + y = x + y, je 1 e M. Je-li z £ M, pak
-----.............•-   , - .........^^^^^^^^
(x + y) + z = (a; + y) + z = x + (y + z),
x + (y + z) = x + y + z = x + (y + z).
Tudíž ž € M a z axiomu úplné indukce plyne M = J\í. Operace + je tedy asociativní.
Nechť x 6 Áí a nechť M = {y G N \ x + y = y + x}. Podle 4.4 (a), (c) je 1 e M. Pokud z e M, pak
x + z = x-\-z'i= z + x~ z + x
podle 4.4 (b), (d), tudíž ž G M. Odtud plyne M = hf a operace + je komutativní. 4.7. Věta. V grupoidu (Af, + ) platí zákon o odečítání, tj. platí: x, y,z G N,  x + y — x + z =¥■ y = z.
24
Obory přirozených, celých a racionálních čísel
Důkaz. Tvrzení dokážeme nepřímo. Nechť ,y, z £ Af,y ^ z jsou pevně zvoleny. Položme M — {x G ÄÍ \ x + y ^ x + z}. Jelikož 1+y — y^ž= 1 + z, platí 1 G M. Jestliže u G Á4, pak u + y ^ u + z, odkud plyne u + y = u + y^u + z—u + z, tudíž u G M. Z axiomu úplné indukce dostáváme M = Af.
4.8. Tvrzení. Pro x, y G Af platí x ^ x + y.
Důkaz. Jestliže x = x + y, pak x + l = x + y + laze zákona o odečítání plyne 1 = y + 1 = y, což je spor s i) v definici 4.1.
4.9. Tvrzení. Necht! x,y £ Af. Pak nastane právě jeden z následujících tří případů:
(a) x-y,
(b) existuje u £ Af tak, že x — y + u,
(c) existuje v £ Af tak, že y = x + v.
Důkaz. Podle 4.8 nemohou nastat současně případy (a), (b) a (a), (c). Kdyby nastaly současně případy (b), (c), pak x = y + u — x + (v + u), což není možné podle 4.8.
Buď x £ Af a nechť Mx je množina všech y £ Af takových, že pro x, y nastane některý z případů (a), (b), (c). Tvrzení bude dokázáno, pokud pro každé x £ Af ukážeme, že Mx — Af.
Jestliže x = 1, pak pro každé y £ Af, y ^ 1 existuje v £ Af tak, že y = v = 1 + v, tudíž Mi = Af.
Jestliže x    1, pak existuje u £ Af tak, že x = u = 1 + u, tudíž 1 G Mx.
Nechť z £ Mx. Rozlišme nyní, který z případů (a), (b), (c) nastal pro dvojici x, z. Jestliže nastal první případ, tj. z = x, potom ž — x + 1, tudíž pro dvojici x,ž nastane případ (c). Jestliže nastal druhý případ, tj. existuje u £ Af tak, že x — z + u, pak pro u = 1 máme x = z + 1 = ž, a tudíž'pro prvky x,ž nastane případ (a). Je-li u ^ 1, pak existuje v £ Af tak, že u = v, a pak x = z + u — = z + v = z + v = J + v. Pro prvky x, ž pak nastane případ (b). Zbývá nám třetí případ, kdy existuje v G Af, z — x + v. Pak ž = x + v = x + v, tudíž pro prvky x,ž nastane případ (c). Odtud plyne ž G Mx- Z axiomu úplné indukce dostáváme Mx =Af.
Důkaz je dokončen.
4.10. Definice. Pro x,y £ Af položme x < y, jestliže x = y, nebo existuje u £ Af tak, že y = x + u. Jestliže x < y a x ^ y, klademe x < y. Neboli x < y právě tehdy, když existuje u £ Af tak, že y = x + u.
4.11. Věta. Relace < na množině Af je lineární uspořádání s nejmenším prv-. kem 1.
Důkaz. Reflexivita a tranzitivita relace < je zřejmá. Antisymetrie a úplnost plyne z 4.9.
Nechť x £ Af. Je-li .-c — 1, pak 1 < x. Jestliže x ^ 1, pak existuje u £ Af tak, že u = x, tudíž x = u + 1, odkud plyne 1 < x. Tím jsme ukázali, že 1 je nejmenší prvek uspořádané množiny (Af, < ).
Kap. 4. Polookruh přirozených čísel
25
26
Obory přirozených, celých a racionálních čísel
Lineární uspořádání < na množině Af je spojeno s operací + následujícími
vztahy.
4.12. Věta. Nechť x, y, z, r, s G //. Pak platí:
(a) x < y       x + z < y + z,
(b) x < y       x + z < y + z,
(c) pokud x <y,r < s nebo x <y,r < s nebo x < y,r < s, pakx+r < y + s,
(d) x < y, r < s => x + r < y + s,
(e) x < y => x < y. .
Důkaz. Jestliže x < y, pak existuje u e Af tak, že x + u = y, odkud y + z = = (x + z) + u, z čehož dostáváme x + z < y + z.
Jestliže x + z < y + z, pak existuje u G Af tak, že x + z + u = y + z. Ze zákona o odečítání pak plyne x + u = y, tedy x < y. Platí (a), odkud se snadno odvodí platnost výroku (b).
Nechť x < y, r < s. Pak podle (a) x + r < y + r, r +y < s + y a z tranzitivity plyne x + r < y + s. Podobně se ukáží ostatní části výroku (c). Výrok (d) pak snadno plyne z (c).
Nechť x <y, pak existuje u G U tak, že x + u = y. Jestliže u = 1, pak x - y. Jestliže u ž í, pak existuje v € H tak, že u - v, tudíž y - x + v = x + v = x + v, odkud plyne x < y. Platí tedy x = y nebo x < y, což je tvrzení (e).
Věta je dokázána.
4.13. Poznámka. Výrok (e) můžeme interpretovat tak, že mezi prvky x, x neexistuje žádný jiný prvek. Poznamenejme ještě, že vždy platí x < x.
4.14. Definice. Nechť P je neprázdná množina a ■< lineární uspořádání na P. Relace < se nazývá dobré uspořádání, jestliže každá neprázdná podmnožina množiny P má nej menší prvek: Říkáme též, že (P, <) je dobře uspořádaná množina.
4.15. Věta. Množina. (Aí, <) je dobře uspořádaná množina.
Důkaz. Nechť M je libovolná neprázdná podmnožina Af. Ukážeme, že má nejmenší prvek. Položme M* = {xeAf\VmeM : x < m}. Protože je množina M neprázdná, můžeme zvolit prvek r € M. Protože ř = r + 1 > r, nepatří f do množiny M*. Jelikož 1 G M*, plyne z axiomu úplné indukce existence prvku s e M* takového, že I £ M*. Ukážeme, že s je nejmenší prvek množiny M.
Poněvadž s E M* platí s < m pro každý prvek M. Jestliže s £ M, pak s < m pro každý prvek m e M a, podle 4.12 (e) je š < m pro každý prvek m G M, což je spor s předpokladem š g M*. Tudíž s G M a věta je dokázána.
4.16. Tvrzení. Nechť 0 ^ M C V je siiora ohraničená množina, tj. existuje z <e j\f tak, že pro každý prvek m G M platí m<z. Pak M má největší prvek.
Důkaz. Položme M* a'{í 6 ATjV m 6 M ■ x > m}. Jelikož M*ý 0, existuje nejmenší prvek s množiny M*. Ukážeme-li, že s G M, pak s bude největší prvek množiny M..
Je-li s = l, pak nutně M = {1}. Nechť s ^ 1. Pak existuje v £ M tak, že v = s.
Protože s je nejmenší prvek M*, platí v g M*f a tedy existuje m e M takové, že v < m. Zároveň však m < s = v, a tedy podle 4.12 (e) je s = m G M.
4.17. Příklad. Ukážeme si, že existuje injekce M -> tV, která není surjekce. Buď b € N libovolné a definujme fi,:Aŕ-tAf takto
yr / % _ I ®i    jestliže a; < 6, 1 x,    jestliže x > 6.
Ověřte sami rozepsáním, že pro libovolné x,y G Áf z sc < y plyne /6(i) < fb(y), a tedy /fc je injektivní. Na druhou stranu pro žádné x € Aí neplatí fb(x) = b, a proto    není surjekce.
4.18. Věta. Nechť m G Äf. Označme A{m) = {s G N \ s < m}. Pak neexistuje injekce f t M -» yl(m).
Důkaz. Označme yVť = {rn G A/" | neexistuje injekce / : jV -> Ä(m)}. Snadno se vidí, že f : Af -i {1} není injekce, a tedy 1 e M.
Buď mGMa předpokládejme, že m ^ A^, tj. existuje injekce / : Af -4 A (m). Pripomeňme, že z 4.12 (e) plyne A(m) = A(m) U {m}. Rozlišme dva případy podle toho, zda existuje b G Af s vlastností /(&) = m. Pokud neexistuje, můžeme uvážit injektivní zobrazení g : Af -» A(?/j) určené předpisem #(a;) == /(»), což je však spor s m G M. Pokud takové b existuje, pak je jediné, neboť / je injekce. Položme 9 — / ° /&, kde je definováno v předchozím příkladu. Pak g : tV -> A (m) je injekce a neexistuje x e N s vlastností p(cu) = m, což je opět podle předchozího spor.
Pro M jsme tedy ukázali m G M ==*■ m G M. Proto //( = yV a věta je dokázána.
4.19. Poznámka. V teorii množin lze definovat nekonečnou množinu jako takovou množinu M, která splňuje některou z následujících navzájem ekvivalentních podmínek:
- existuje vlastní podmnožina S C M a bijekce / : M -* S]
- existuje injekce / : M -¥ M, která není surjekcí;
- existuje injekce / : Af -+ M.
Z věty 4.18 plyne, že shora ohraničené podmnožiny množiny Af jsou konečné.
Zavedeme nyní další operaci na Af.
4.20. Věta. Na množině Af existuje právě jedna operace ■ taková, že pro každé x,y G Af platí:
(a) x ■ 1 = x,
(b) x ■ y = x ■ y + x.
Pro tuto operaci a pro každé x, y G Af pak platí:
(c) 1 • x = x,
(d) x-y = x-y + y.
Kap. 4. Polookiuh přirozených čísel 27 Důkaz. Provádí se analogicky jako důkaz věty 4.4.
Ukážeme nejdříve existenci takové operace. Nechť M je množina všech x £Af, ke kterým existuje zobrazení fx množiny Af do sebe s vlastnostmi:
fx(l) = x,   fx(y) = fx(y) + x pro každé y G /V. (*)
Položíme-li fi(y) — y pro každé y G Af, pak /i je takové zobrazení pro x — \. Tudíž 1 G M. Buď /z uvedené zobrazení pro x e M. Pro y G TV položíme My) = /*(y) + V- Pak Ml) =        + l = * + l = * a = fx(y) + f =
= My) + x + y +1 - My) + ^ Pro v e x&m&m=aí.
Předpokládejme, že pro některé x G Af existují dvě zobrazení vlastností (*). Označme je fx, gx a položme M = {y € Af \ fx(y) = gx(y)}. Zřejmě 1 G M. Pokud z e M, pak fx(ž) ~ fx(z) + x = gx{z) + x = gx(ž), tudíž ž 6 M a M = Af. Tedy fx = gx& pro každé x existuje právě jedno zobrazení vlastností (*).
Nyní můžeme operaci • definovat vztahem x-y — Mí/)- Tato operace, vzhledem k (*), splňuje podmínky (a) a (b).
Ze vztahu x ■ y = fx(y) pak dostáváme 1 • x = fi(x) = ar a x • y = Mí/) = = fx(y) + y = x ■ y + y. Platí tudíž (c) i (d).
Jednoznačnost uvedené operace plyne z přechozího. Stačí si uvědomit, že každá operace • splňující (a) a (b) indukuje zobrazení splňující (*) (předpisem fx{y) = = x-y).
Věta je tím dokázána.
4.21. Definice. Operaci uvedenou ve větě 4.20 nazýváme násobení a vyhradíme pro ni symbol •. Máme tudíž na množině Af dvě operace + a • a uspořádání <. Často budeme množinu M uvažovat jako čtveřici (JV, + ,-,<)• Jestliže v zápisu nepoužijeme závorky, dáváme přednost jako v okruhu operaci • před operací +. Tedy a ■ b + c značí (a •b) + c a nikoliv a ■ (b + c). Při zápisu operace násobení často vynecháváme označení operace •, tudíž místo a • b píšeme ab.
Odvodíme nyní některé vlastnosti operace násobení.
4.22. Věta. Operace násobení ■ na množině přirozených čísel Af je komutativní a asociativní a s operací + je svázána tzv. distributivním zákonem:
x, y,z € TV =4» x ■ (y + z) = x ■ y + x ■ z.
Důkaz. Nechť x € M. Položme M = {y G Af | x-y = yx}. Z 4.20 (a), (c) plyne 1 G M. Pro y e M podle 4.20 (b), (d) dostáváme y ■ x = y-x + x = x-y + x = x-y, tudíž y € M. Tedy M = Af, což dokazuje komutativitu násobení.
Buď x,y € Af. Položme M = {z G Af | x • (y + z) = x ■ y + x ■ z}. Platí x -(y + 1) = a; • y — x ■ y -f x.— x ■ y + x • 1, tudíž 1 G M. Nechť z G M, pak
x . (y + z) = x- • (y + z) = x-(y + 2:) + 3; = a;-y + 3;-z + a; = x- í/ + x'-2,
tedy z e M. Opět z axiomu úplné indukce dostáváme M - Af. Odtud plyne distributivní zákon.
28 Obory přirozených, celých a racionálních čísel
Nechť x,y € Af. Položme M = {z G Af | (x -.y) • z = a; • (y • z)}. Zrejme 1 € M. Je-li z G A4, pak (a?-j/)-ž = (x-y)-z+x-y = x-(y-z)+x-y = x-(y-z+y) — x-{y-~ž), tedy ž e M. Tedy M = Af, což dokazuje asociativitu násobení.
Z distributivního zákona ihned obdržíme:
4.23. Tvrzení. Pro x, y, u, v G A/ platí:
(x + y)-(u + v) = x- u + x- v + y- u + y-v. Z 4.20 (a), (c) plyne:
4.24. Tvrzení. V grupoidu (Af, ■) je 1 jednotkový prvek.
4.25. Věta. Nechť x, y, z, r, s G TV". PaJc platí: (&) x <y «í=^ i • z < y • z,
(b) x ■ z = y ■ z      x = y,
(c) a; < y 4=3* x ■ z < y ■ z,
(d) jestliže x < y,r < s nebo x <y,r < s nebo x < y,r < s, pak x -r < y ■ s,
(e) x < y, r < s => x ■ r < y ■ s.
Důkaz. Nechť x < y. Pak existuje u e Af tak, že y = x + u. Odtud plyne y «z = x • z + u • z, tudíž x • z < y • z.
Je-li x-z<y-zay<x, pak podle předešlého y ■ z < x ■ z, což je spor. Platí tudíž část (a).
Nechť x • z = y • z. Jestliže x ^ y, pak můžeme předpokládat x < y a z (a) dostaneme spor. Platí tedy (b). Výrok (c) je obměnou (a).
Nechť x < y, r < s. Pak podle (a) x ■ r < y ■ r, y ■ r < y ■ s, tudíž x • r < y ■ s. Podobně se dokáží ostatní části výroku (d) a výrok (e).
4.26. Poznámka. Jestliže v nějakém grupoidu (G, ■) pro libovolné x, y, z G G platí obě implikace
x y z=x, z      y == z,
y • x — z ■ x      y — z,
říkáme, že v (G, ■) platí zákon o krácení. Věta 4.25 (b) tedy tvrdí, že v grupoidu (Af, ■) platí zákon o krácení. V případě, kdy užíváme aditivní terminologie, zákonu o krácení se říká zákon o odečítání (srovnej s větou 4.7).
Závěrem tohoto odstavce si uvedeme metodu rekurentní definice.
4.27. Věta. Nechť M je libovolná neprázdná množina, ip : Af x M -> M a m je libovolný prvek z M.
Pak existuje právě jedno zobrazení P : Af -> M takové, že platí: 0   P(l) = m,
ii) pro x £ Af platí (p(x, P(x)) == P(x).
Kap. 4. Polookruh přirozených čísel
29
Důkaz. Pro a; G AT položme A(x) = {ŕ G TV \ t < x}. Zřejmě 1 G A{x). Množinu A(x) nazveme úsekem určeným prvkem x. Zobrazení.p : A(x) -> M nazveme přípustié, jestliže platí
(a) p(l) - m,
(b) s G A(x),š G A(x) =» <p(s, p(s)) =p(ä).
Ukážeme, že každý úsek má nejvýše jedno přípustné zobrazení. Nechť p, q jsou různá prípustná zobrazení úseku A{x) a nechť u G A(x) je nejmenší přirozené číslo z úseku A(x) takové, že platí p(u) ^ q(u); existenci takového u zaručuje 4.15. Protože p'(l) = m = g(l), je u ^ 1, a existuje tedy t e A{x) tak, že í = u. Podle
(b) je p(u) = ¥>(í, p(í)) =       ?•(*)) =        což J.e sP°r-
Označme nyní .M množinu všech x- € TV takových, že úsek A(x) má přípustné zobrazení. Zřejmě 1 e M.Prox e M platí též S G M, protože A(x) = A(x)U{W}; je-li totiž p přípustné zobrazení úseku A(x), pak zobrazení q : A(x) -t M, které je určené předpisem q(t) = p(t) pro t G A(x) a q(x) = y(x, p(x)), je přípustné zobrazení úseku A(x). Tudíž M = Af.
Snadno se vidí, že zúžení přípustného zobrazení úseku A(x) na úsek A(y) pro x, J/ G TV,y < x, je opět přípustné zobrazení.
Pro x G TV položme P(x) = p(x), kde p je přípustné zobrazení úseku A(x). Pak P(l) - m. Nechť o; G TV a nechť p je přípustné zobrazení úseku A(x) a q přípustné zobrazení úseku A (x). Potom
P (x) = g(š) = p(s,        = v(x, p(x)) = v(xy P(x)).
Jednoznačnost zobrazení P plyne z jednoznačnosti přípustného zobrazení, neboť libovolné P splňující vlastnosti i), ii) indukuje přípustná zobrazení pro všechna A(x).
4.28. Definice. Jestliže jsou splněny předpoklady věty 4.27, řekneme, že jsme dvojicí (</?, m) rekurentně definovali zobrazení P.
Uvedený druh definice se nazývá rekurentní definice. Rekurentní definici můžeme také interpretovat následujícím způsobem: Pro,každé přirozené číslo x G TV máme definovat nějaký pojem P(x). Označíme M množinu pojmů, které přicházejí v úvahu. Pojem P(x) G M je definován pro každé x G N, jestliže
i) je definován pojem P(l),
ii) pokud je definován pojem P(s) pro s G TV, definujeme pak pojem P(š). Tímto způsobem je podle 4.27 jednoznačně určen pojem P(x) pro každé x G TV.
Na základě rekurentní definice si odvodíme následující větu o jednoznačnosti množiny přirozených čísel (4.30). Nejdříve uvedeme pomocné tvrzení.
4.29. Lemma. Nechť TV,TV* jsou množiny přirozených čísel, p G TV*. Pak existuje právě jedno zobrazení f : TV -> TV* tak, že platí:
i) /(l) = M, " _
ii) pro x G TV je /(x) = /(x).
Toto zobrazení f je injekce a /(TV) = {v G TV* | p < ľ}.
30
Obory přirozených, celých a racionálních čísel
Důkaz. Použijeme větu 4.27, ve které položíme M = TV*, m = \i a pro x G TV položíme <p(x, t) = t pro každé ř G ./V*. Podle' 4.27 existuje právě jedno zobrazení / : TV -> TV* tak, že /(l) = p a pro x G M je /(x) = f (x).
Ukážeme, že pro libovolná x, y G TV, x < y platí /(x) < f (y). Označme za tím účelem X = {xGTV|32/GtV,x< y, f (y) < f (x)}. Předpokládejme, že existuje u G M. Pro toto u uvažme množimu Ou — {y G TV | u < y, f (y) < f {u)}. Množina Ou je dle předpokladu u G M neprázdná, tudíž existuje její nejmenší prvek; označme jej v. Protože u # 1, existuje u; G M tak, iew = v.Z 4.12 (e) plyne u <w. Protože v je nejmenší prvek Ou, musí platit w £ Ou, tzn. buď u - w nebo f (u) < f(u>). V obou případech tedy
f (u) < /(«,) < /(«;) = f(w) = f (v),
což je spor s w G Ou. Tzn. = 0, a tedy pro každé x, y G TV, x < y platí /(x) < /(y)- Odtud plyne, že / je injekce a /(TV) C {v e TV* | /j, < u}.
Nechť A je nejmenší prvek množiny všech prvků z TV*, které nemají vzor při zobrazení / a jsou větší než p. Zřejmě A ^ l/v*, a proto musí existovat k G TV* takové, že k, — A. Prvek k má vzor při zobrazení /, který označme m. Potom f(m) - /.{»») = k = A, což je spor. Tudíž /(TV) = G TV* | p < ^} a lemma je dokázáno.
Z lemmatu ihned dostáváme:
4.30. Věta (o jednoznačnosti přirozených čísel). Nechť TV, TV* jsou množiny přirozených čísei. Pak existuje právě jedna bijekce f : U -4 TV* taková, že pro každé x G TV piati: /(x) = /(x).
4.31. Poznámky.
a) Cílem předchozí věty je ukázat, že ačkoliv je různých množin přirozených čísel nepřeberné množství, všechny jsou v jistém smyslu stejné. Tyto množiny mohou mít samozřejmě zcela libovolné prvky, věta 4.30 však zaručuje, že prvky libovolných dvou takových množin lze ztotožnit (pomocí bijekce /) tak, že v obou množinách je pak přiřazení následníků stejné. A protože operace 4-, • i uspořádání < byly definovány pouze pomocí následníků, všechny množiny přirozených čísel mají stejné algebraické vlastnosti. Jednu z těchto množin nyní pevně zvolíme a v dalším textu ji budeme značit N. Budeme-li tedy v budoucích kapitolách hovořit o přirozených číslech, budeme mít na mysli prvky této množiny N. Číslem 1 budeme značit nejmenší prvek množiny N, tj. ten, který není následovníkem žádného přirozeného čísla. Číslo T (následovník 1) budeme značit symbolem 2, následovník 2 symbolem 3, atd..
b) Jelikož např. 1 < 1 + x pro každé x G N, neexistuje přirozené číslo x tak, aby platilo L = 1 + x, tudíž trojice (N, + , •) není okruh. Nicméně z dokázaných vlastností plyne, že (N, + ,-) jé polookruh, přičemž polookruh je definován následujícím způsobem.