21
Obory přirozených, celých a racionálních čísel
V 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 nej základnějším pojmům y 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. Polookruh přirozených čísel
4.1. Definice. Libovolnou mnbžinťí ,V budeme nazývat množinou přivozených čísel a každý prvek z Jsf přirozeným číslem, jestliže ke každému prvku x G Af je přiřazen prvek x 6 N, který nazýváme následník prvku x tak, že platí:
i) Existuje alespoň jeden prvek množiny JV, který není následníkem žádného prvku z JV. (Jeden z těchto prvků označme symbolem 1 = ljy.)
ii) Pro libovolné x, y G JV, z x = y plyne x = y.
iii) Nechť M C JV má následující vlastnosti
a) 1 6 M,
b) iěW=>I€ M. Pak M = JV,
Vlastnost iii) se nazývá 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ě JV je vlastně zobrazení : M ~+ JV. Přesnější než o množině přirozených číslech by bylo hovořit o algebraické struktuře
11
Obory přirozených, celých a racionálních čísel
přirozených čísel, čímž bychom měli na mysli uspořádanou dvojici (JV,-). Z důvodů stručnosti a větší přehlednosti textu to však nebudeme dělat a budeme psát o množině JV, majíce na mysli, že přiřazení následníků v množině JV je pevně zvoleno.
b) V teorii množin se ukazuje, že taková množina JV 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 JV".
c) Z tvrzení 4.3 (c) plyne, že prvek množiny JV s vlastností i) je určen jednoznačně.
V dalším textu budeme předpokládat, že JV je množina přirozených čísel, tj. má vlastnosti i)-iii) z definice 4.1.
4.3. Tvrzení. Nechť x, y G JV. Paic platí; .   (a) x ŕ y      x i= y,
(b) x ^ ä,i
(ej\ x ŕ 1 ==* 3 u S JV : a: = u.
Důkaz. Cást (a) plyne ihned z vlastnosti ii) definice 4.1.
Položme M - {z G JV | z £ ž}. Výrok (b) je ekvivalentní s M = JV=Podle i) v definici 4.1 platí 1 G M. Buď nyní m é.'M takové, iax^M. Tedy x; = fa podle ii) v definici 4.1 platí x = x, což je spor s x G M. Proto x g M S Q M a z axiomu úplné indukce plyne M = JV.
Položme M = {z 6 JV j 3 v G N, v = z} U {1}. Je-li x G M, pak zřejmě x 6 M a z axiomu úplné indukce tedy plyne M = JV, tudíž (c).
4.4. Věta. Na množině JV existuje právě jedna operace + taková, že pro každé x,y G JV piati:
(a) x + 1 = x,
(b) x + y = x + y.
Pro tuto operaci + a pro každé x, y e. M pak platí:
(c) 1 + x — x,_
(d.) x + y = x + y.
Důkaz. Nejdříve ukažme existenci takové operace +. Nechť M je množina všech x G N, ke kterým existuje zobrazení /, množiny JV do sebe takové, že platí:
/■(1)= X,   f*(v) - 7x(y} pro každé j/ e JV. (*)
Poznamenejme, že fx bude vlastně přičtení x zleva.
Položíme-li fi{y) - y pro y G JV, pak fa je takové zobrazení pro x = 1. Tudíž 1 G M.
Buď x & M a fx nechť je zobrazení splňující (*) pro toto x. Zkonstruujeme nyní fw. Pro y G JV položíme h{y) = f,{y). Pak j%(l) = /„(I) = x a pro y G M máme _ . _
fw(V) = /.<J0 =-U(y) = Mv)-
Tudíž /x splňuje (*), a proto x G M. Z axiomu úplné indukce plyne M = JV.
I
Kap. 4. Polookřuh přiložených čísel
23
Předpokládejme, že pro některé x £ Af existují dvě zobrazení vlastností (*), Označme je fx, gx a položme M =* {ý 6hl \ fx(v) — ďa;(í/)}■ Zřejmě l £ M. Pokud z € Á4, pak
/sO) = /■(*) - g*(*) = Sís(2),
tudíž ž £ M a a axiomu úplné indukce dostáváme M = Af. Tedy fx~9x& pro každé x existuje právě jedno zobrazení vlastností (*).
Nyní můžeme operaci + pro x,y € Af definovat vztahem x + y — fx(y). Tato operace, vzhledem k (*), splňuje podmínky (a) a (b).
Z uvedeného vztahu x + y = dostáváme 1 + x — fi(x) — x a x + y =
= Mv) = /s (y) = äT+17. 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 £ Af 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é a; 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 + 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 6 Af. Položme M = {z 6 Af |' (x '+ y) + z — x + (y + z)},. Jelikož
(x + y) + 1 - x + y,   x + (y + l) = x + y = x+y, je 1 e M. Je-li z 6 AA, pak
(x + y) + z = (x + y) + z = x + (y + z),
x + (y + z) = x + y + z = x + (y + z).
Tudíž z~ £ M a z axiomu úplné indukce plyne M — Af. Operace + je tedy asociativní.
Nechť x £ Af a nechť M = {y £ Af \ x + y = y + x}. Podle 4.4 (a), (c) je 1 6 M. Pokud z £ M, pak
x + z — x + z = z + x — J + x podle 4.4 (b), (d), tudíž z 6 M. Odtud plyne M — Af a operace + je komutativní. 4.7. Věta. V grupoídu (Aí, + ) platí zákon o odečítání, tj. platí: X, V, Z € AI,■ 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ť.j/, z £ Af, y ^ z jsou pevně zvoleny. Položme M = {x e Af \ x + y ^ x + z}. Jelikož l + y — y ^íž = l+z, platí 1 £ M. Jestliže u £ Ad, pak u + y ^ u + z, odkud plyne u + y — u + y u + z = u + z, tudíž u £ M. Z axiomu úplné indukce dostáváme M = Af.
4.8. Tvrzení. Pro x, y £ Af platí x ^ x + y.
Důkaz. Jestliže x — x + y, pak x+l = x + y + íaze zákona o odečítání plyne 1 = y + 1 = y, což je spor s i) v definici 4.1.
4.9. Tvrzení. NecM 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 e Af a nechť A4X je množina všech y 6 Af takových, že pro x, y nastano některý z případů (a), (b), (c). Tvrzení bude dokázáno, pokud pro každé x S hl 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 e 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 + il — — z + v = z + v = ž + v. Pro prvky x,ž pak nastane případ (b). Zbývá nám třetí případ, kdy existuje v € hl, z ~ m + v. Pak z = x + v = x + v, tudíž pro prvky x,l nastane případ (c). Odtud plyne ž £ Mx. Z axiomu úplné indukce dostávame 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šírn prv-. kem 1.
Důkaz. Reflexivita a tranzitivita relace < je zřejmá. Antisymetrie a úplnost plyne z 4.9.
Nechť x £ Af. Je-li x = 1, pak 1 < x. Jestliže x ^ 1, pak existuje u e Af tak, že u — x, tudíž x = u + 1, odkud plyne 1 < x. Tím jsme ukázali, že 1 jc nejrnenší prvek uspořádané množiny (Af, < ).
Kap. 4. Pohokruh přirozených čísel ^5
Lineární uspořádání < na množině Aí je spojeno s operací + následujícími
vztahy.
4.12. Věta. Nechť x,y,z,r,s £ Aí. Pak plutí:
(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 £ Aí tak, že a; + 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 £ Aí tak, že x + 2 + u = y 4- 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 4- r, r +y < s + y a z tranzitivity plyne x + r < 1/ + s. Podobně ae ukáží ostatní části výroku (c). Výrok (d) pak snadno plyne z (c).
Nechť x < y, pak existuje u G Af tak, že x + u = y. Jestliže u = 1, pak x = y. Jestliže u jíl; pak existuje ľ G A/" tak, že u = v, tudíž y = x + tJ-x + v = x + u, odkud plyne x < y. Platí tedy ž = 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 8,5? 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á nejmenší 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 M. Ukážeme, že má nejmenší prvek. Položme M* = {x £ Aí | V m £ M : x < m}. Protože je množina M neprázdná, můžeme zvolit prvek r £ A4. Protože ř = r + .1 > r, nepatří r do množiny M*. Jelikož 1 £ M*, plyne z axiomu úplné indukce existence prvku s £ M* takového, že š i M*. Ukážeme, že s je nejmenší prvek množiny M.
Poněvadž s £ M* platí s < m pro každý prvek M. Jestliže s g M, pak s < m pro každý prvek m e M a podle 4.12 (e) je š < m pro každý prvek m £ M, což je spor s předpokladem š £ M*. Tudíž s e M a, věta je dokázána.
4.10. Tvrzení. Nechť 0 ^ M Q Aí je shora ohraničená množina, tj. existuje zčAÍ tak, že pro každý prvek m € M platí m < z. Pak M má největší prvek.
Důkaz. Položme M* = {i £ JV|V m € M : x > m). Jelikož M* # 0, existuje nejmenší prvek s množiny M*. Ukážeme-li, že s e A4, pak s bude největší prvek množiny Ai.
Je-li s = 1, pak nutně M = {!}• Nechť s # 1. Pak existuje v £ // tak, že P = s.
26 Obory přirozených, celých a racionáiiu'cii čísei
Protože s je nejmenší prvek M*, platí u £ X*,, 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 £ A4.
4.17. Příklad. Ukážeme si, že existuje injekce A/" -> JV", která není surjekce. Buď i 6 TV" libovolné a definujme /& : /V -*• jV takto
^ . . _ I x,    jestliže x < b, 1 x,    jestliže x > b.
Ověřte sami rozepsáním, že pro libovolné x,y £ Aí z x < y plyne /(,(x) < /&(y), a tedy /& je injektivní. Na druhou stranu pro žádné m £ M neplatí fb{x) = b, a proto /& není surjekce.
4.18. Věta. Nechť7« e A/". Označme A(m) = {s G | s < m}. Pak neexistuje injekce f : M -> A(m).
Důkaz. Označme = {m e A/" | neexistuje injekce / : Af ~> A(m)}. Snadno se vidí, že / : H -4 {1} není injekce, a tedy 1 e M.
Buď m e M a předpokládejme, že m g A4, tj. existuje injekce f : Af -> A(m). Pripomeňme, že z 4.12 (e) plyne A(m) = A(m)U{řří}. Rozlišme dva prípady podle toho, zda existuje b G A/" s vlastností /(&) = řň. Pokud neexistuje, můžeme uvážit injektivní zobrazení g : H -t určené.předpisem y(x) = /(x), což je však
spor s m G jM> Pokud takové b existuje, pak je jediné, neboť / je injekce. Položme Q — f 0 f b, kde f t je definováno v předchozím příkladu. Pak g : N -> /l(řřt) je injekce a neexistuje x e M s vlastností y(x) = m, což je opět podle předchozího spor.
Pro M jsme tedy ukázali m £ M m € M. Proto M = AT 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 -* 5;
- existuje injekce / : M -J> jlí, která není surjekcí;
- existuje injekce / : M -4 M.
Z věty 4.18 plyne, že shora ohraničené podmnožiny množiny A^ jsou konečné.
Zavedeme nyní další operaci na Af.
4.20. Věta. Na množině Aí existuje právě jedna operace ■ taková, že pro každé x, y £ A/" piat/;
(a) x ■ 1 = x,
(b) x ■ y = x • y -f- x.
Pro tuto operaci a pro každé x,y £ Af pak platí:
(c) 1 • x = x,
(d) x ■ y = x ■ y + y.
Kap. 4. Polookruh 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 £ A/, ke kterým existuje zobrazení fx množiny U do sebe 3 vlastnostmi:
fx(l) = x,   fx{y) = fx{y) + x pro každé y e A/V (*)
Položíme-li fi(y) - y pro každé y e M, pak /i je takové zobrazení pro x = 1. Tudíž 1 6 X. Buď /„ uvedené zobrazení pro a; 6 M. Pro y e M položíme Mv) = + y. Pak =7,(l)+l=* + l = sa iWW = + ¥* = /.M + * + y + 1 = Mí/) + x pro y SAÍ. Tudíž ieMaJW=^.
Předpokládejme, že pro některé x 6 jV existují dvě zobrazení vlastností (*). Označme je /„ gx a položme M = {y e M \ fx(y) = Zřejmě 1 6 M.
Pokud z £ M, pak /„(ž) =       + x = fo(J),tudíž ^ &MaM=M.
Tedy fx=gx& pro každé a- existuje právě jedno zobrazení vlastností (*).
Nyní můžeme operaci • definovat vztahem x-y — fx{y). Tato operace, vzhledem k (*), splňuje podmínky (a) a (b).
Ze vztahu x ■ y = fx{y) pak dostáváme l ■ x = fi{x) - x a x ■ y = fx(y) m
= L (v) + 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ě N dvě operace + a • a uspořádání <. Často budeme množinu A/ uvažovat jako čtveřici (A/, + ,-,<)• 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 o • 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 A/ je komutativní a asociativní a s operací + je svázána tzv. distributivním zákonem:
x, y, z € Af =ŕ- x ■ {y + z) — x ■ y + x ■ z.
Důkaz. Nechť x € M. Položme M = {y 6 M \ x-y = yx}. Z 4.20 (a), (c) plyne 1 e M. Pro y e M podle 4.20 (b), (d) dostávame y■ x = y-x + x = x-y + x = x-y, tudíž y € M. Tedy M — M, což dokazuje komutativitu násobení.
Buď x,y e M. Položme M = {z 6 M \ x ■ {y + z) m x ■ y + x ■ z}. Platí x . (y + 1) = x ■ y = x ■ y + x. - x ■ y + x ■ 1, tudíž 1€M, Nechť z € M, pak
x ■ (y + z) = x- (y + z) = x-(y + z) + x = x-y + x-z + x = x- y + x-z,
tedy ž e M. Opět z axiomu úplné indukce dostáváme M = N- Odtud plyne distributivní zákon.
28 Obory přirozených, celých a racionálních čísel
Nechť a:,y S M. Položme M = {z € M \ (x -y) ■ z = x ■ (y ■ z)}. Zrejme 1 € M. Je-liž 6 M, pak (s5-J/)-Z = (x-y)-z+x-y = x-(y-z)+xy = x-{y-z+y) = x-(y-ž), tedy z e M. Tedy M = A/", což dokazuje asociativitu násobení.
Z distributivního zákona ihned obdržíme:
4.23. Tvrzení. Pro x,y,u,v e H platí:
(x + y) • (u + v) = x • u + x • v + y ■ u + y ■ v. Z 4.20 (a), (c) plyne:
4.24. Tvrzení. V grupoidu (A/-, •) je i jednoticový prvek.
4.25. Věta. Nechť x, y, z, r, s € M. Pak platí:
(a) x < y <S=» x ■ z < y ■ z,
(b) x ■ z - y ■ z      x = y,
(c) x < y       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ť % < y. Pak existuje u 6 M tak, že y = x + u. Odtud plyne y ■ z = x ■ z + u • z, tudíž x ■ z < y ■ z.
Je-li x ■ z < y • z a y < 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 ,4 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 e G platí obě implikace
x-y - x ■ z       y - z,
y ■ x — z ■ x x=$f y šs z,
říkáme, že v (G, •) platí zákon o krácení. Věta 4.25 (b) tedy tvrdí, že v grupoidu (A/\ •) platí zákon o krácení. V případě, kdy užívame 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 : j\ľ x M —}• M a m je libovolný prvek z M.
Pak ebcistuje právě jedno zobrazení P i M -+ M takové, že platí:
i) P(l) = m,
ii) pro x e M platí ip(x, P(x)) — P(x).
Kap. 4, Polookruh přirozených čísel
29
30
Obory přirozených, celých a racionálních čísel
Důkaz. Pro x £ Af položme A{x) = {t € M \ t < x}. Zřejmě 1 e A(x). Množinu A(x) nazveme úsekem určeným prvkem x. Zobrazení.p : A(x) —> M nazveme přípustné, jestliže platí
(a) p(l) == m,
(b) s 6 A(x),s G A(x)      cp(s, p(s)) - p(s).
Ukážeme, že každý úsek má nejvýše jediio přípustné zobrazení. Nechť p, q jsou různá pří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 í € 4(a:) tak, že í = u. Podle (b) je p(u)1 = = V(ř, g(í)) = 9(w). což Je spor.
Označme nyní M množinu všech x G N takových, že úsek A(x) má přípustné zobrazení. Zřejmě 1 6 M. Pro x £ M platí též x G M, protože A(x) = A(x)U{x}; je-li totiž p prípustné zobrazení úseku A(x), pak zobrazení 7 : A (x) -> M, které je určené předpisem q(t) = p(í) pro t £ A(x) a q{x) = <p(x, p(x)), je přípustné zobrazení úseku A(x). Tudíž M = A/".
Snadno se vidí, že zúžení přípustného zobrazení úseku A(x) na úsek A(y) pro x, y G A/", y < x, je opět přípustné zobrazení.
Pro x G AT položme P(x) = p(x), kde p je přípustné zobrazení úseku A(x). Pak p(l) = m. Nechť x- e .V a nechť p je přípustné zobrazení úseku A(x) a g přípustné zobrazení úseku A(x). Potom
P(x) = q(x) = <p(x, q{x)) =       p(x)) = <ŕ>(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í (<p, 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 6 A/ máme definovat nějaký pojem P(x). Označíme M množinu pojmů, které přicházejí v úvahu. Pojem P{x) £ M je definován pro každé x G Kí, jestliže
i) je definován pojem F(l),
ii) pokud je definován pojem P(s) pro s 6JV, definujeme pak pojem P(s). Tímto způsobem je podle 4.27 jednoznačně určen pojem P{x) pro každé x G Kí.
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. Necht! Kí, Kí* jsou množiny přirozených čísel, p. 6 Kí*. Pak existuje přivě jedno zobrazení f : M -> Kí* tak, že platí:
i) /(l) - /*, " _
ii) pro x Z M je /(x) = f(x).
Toto zobrazení f je injekce a f{KÍ) = {v G Kí* \ p. < v).
Důkaz. Použijeme větu 4.27, ve které položíme M = Kí*, m = fi a pro x £ A'' položíme y>(x, í) = í pro každé t e A/"*. Podle 4.27 existuje právě jedno zobrazení / : yV -> Kí* tak, že /(l) = ^ a pro a; 6 Kí je /(x) = /(x).
Ukážeme, že pro libovolná x, y G Kí, x < y platí /(x-) < /(y). Označme za tím účelem M = {x e Kí \ 3 y e Kí, x < y, f (y) < f (x)}. Předpokládejme, že existuje tt G M. Pro toto u uvažme množimu Ou = {y e A/- | u < y, f (y) < f {u)}. Množina Ou je dle předpokladu u € M neprázdna, tudíž existuje její nejmenší prvek; označme jej v. Protože v £ 1, existuje-w G Kí tak, že w = v. Z 4.12 (e) plyne u < w. Protože v je nejmenší prvek Qu, musí platit w £ Ou, ten. buď u = iu nebo /(«) < /(uj). V obou případech tedy
/(u) < f m < /w = f m = /(«).
což je spor s w g Ou. Tzn. Al = 0, a tedy pro každé x. y g A/",s < j/ platí /í21) < /(y)- Odtud plyne, že / je injekce a /(A/) C {v € JV* [ /1 < ľ}.
Nechť A je nejmenší prvek množiny všech prvků z A/"*, které nemají vzor při zobrazení / a jsou větší než /i. Zřejmě A ■ a proto musí existovat k g Ar*
takové, že K — A. Prvek k má vzor při zobrazení /, který označme m. Potom /("») = f {m) = k - A, což je spor. Tudíž /(JV) = {v g Kí* | p < v) a lemma je dokázáno.
Z lemmatu ihned dostáváme:
4.30. Věta (o jednoznačnosti přirozených čísel). Nechť A/, A/* jsou množiny přirozených číseJ. Pa/r existuje právě jedna bijekce f : jV -> A/"* taková, že pro každé x g A/" piatí: /(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 +, ■ 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 I (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 V= 1 + x, tudíž trojice (N, + , •) není okruh. Nicméně z dokázaných vlastností plyne, že (N, + , •) je polookruh, přičemž polookruh je definován následujícím způsobem.