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 G Af je přiřazen prvek x G 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 = ljv-.) ii)   Pro libovolné x,y G Af, z x = y plyne x = y. iii) Nechť M C Af má následující vlastnosti
a)  1 E M,
b)  x e M ==*• 16 M. Pak M =Af.
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ě Af. 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 čísel
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 Af je množina přirozených čísel, tj. má vlastnosti i)-iii) z definice 4.1.
4.3.  Tvrzení. Nechť x, y G Af. Pak platí:
(a)  x ŕ y ==* x ^ y,
(b)  x^x,,
(c)  x # 1 =*■ 3 u 6 Af :.x - u.
Důkaz. Cást (a) plyne ihned z vlastnosti ii) definice 4.1.
Položme M = {z G Af \ z f z\. Výrok (b) je ekvivalentní s M - Af .Poc\\e i) v definici 4.1 platí 1 € M. Buď nyní x £ M takové, že x g M. Tedy x-1 a podle ii) v definici 4.1 platí x - x, což je spor s a: G M. Proto x € M .=*• S & M a z axiomu úplné indukce plyne M = Af.
Položme M = {z€Af\3veAf,v = *}U{1}. Je-li x G M, pak zřejmě x G 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 G Af platí:
(a)  x + 1 = x,
(b)  x + y = x + y.
Pro tuto operaci + a pro každé x,y G Af pak platí:
(c)  1 + x — x,
(d)  x + y = x + y.
Důkaz. Nejdříve ukažme existenci takové operace +. Nechť A4 je množina všech x G Af, ke kterým existuje zobrazení fx množiny Af do sebe takové, že platí:
/.(lj=*,    /*(!/)= 7^3/) pro každé y G A/\    (*)
Poznamenejme, že fx bude vlastně přičtení x zleva.
Položíme-li fi{y) - y pro y G Af, pak /i je takové zobrazení pro as = 1- Tudíž
lEM.
Buď x G M a fx nechť je zobrazení splňující (*) pro toto x. Zkonstruujeme nyní h- Pro y G Af položíme fw{y) = /.(»). Pak /»(l) = /,(1) = x a pro y e Af máme                                           _____     -..           _____
My) = fx{y) =4fx{y) = kiv)-
Tudíž fs splňuje (*), a proto x G M. Z axiomu úplné indukce plyne M = Af.
Kap. 4. Polooktuh prirazených čísel                                                                        23

Předpokládejme, že pro některé x £ Aí existují dvě zobrazení vlastností (*). Označme je /«, gx a položme M = {y £ Aí \ }x{y) = gx{y)}. Zřejmě 1 £ M. |ft              Pokud zeX, pak
jf:                                            fx(ž) = /,(*) = &.(*) = $,(»),
tudíž ž£Maz axiomu úplné indukce dostáváme M — Aí. Tedy fx = gx a pro každé a; existuje právě jedno zobrazení vlastností (*).
Nyní můžeme operaci + pro x,y 6 Aí 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 + x = fi(x) — x a x + y = = h(y) ~ íx(y) - x + y. Platí tudíž i (c) a (d).
Jednoznačnost uvedené operace + plyne z přechozího, neboť každá operace 4-splňující (a), (b) indukuje pro libovolné x £ Aí 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é. i|f'r;'                        Věta je tím dokázána.
4.5. Definice. V dalším pro operaci na množině Aí uvažovanou ve větě 4.4 *              vyhradíme symbol + a budeme ji nazývat sčítání. Dvojice (Aí, + ) je pak grupoid.
íj'1                       Odvodíme si nyní některá tvrzení o této operaci +.
1 ,                      4.6. Věta. Operace + na množině přirozených čísei Aí je asociativní a komu-
í!                    fcafcivní.
:;'|                      Důkaz. Nechť x,y £ Aí. Položme M = {z € Aí \(x + y) + z = x + (y + z)}:.
Jelikož
(x + y) + l = x + y,    x + (y + l)=x + y = x + y,
■ '
■   ■;:'■:      , iCv-í.-::-.'

I
je 1 e M. Je-li z € M, pak
ffte                             ■              . (x+ y) + z = (x+ y) + z = x +(y + z),
x + (y + z) = x + y + z = x + (y + z). Tudíž ž e M az axiomu úplné indukce plyne M = Aí. Operace + je tedy asocia-
&r.-.           tivni.
Nechť x e Aí a nechť M = {y £ Aí \ x + y = y + x}. Podle 4.4 (a), (c) je
ř\               1 e M. Pokud z € M, pak
x + z = x + z == z 4- x — z + x podle 4.4 (b), (d), tudíž ž e M. Odtud plyne M = Aí a operace + je komutativní. 4.7. Věta. V grupoidu (Aí, + ) platí zákon o odečítání, tj. platí: x, y, z e Aí,   x + y — x + z =*• y = z.
24                                                         Oborj přirozených, celých a racíanáijiícA čiše/
Důkaz. Tvrzení dokážeme nepřímo. Nechť .y, z £ Aí, y ^ z jsou pevně zvoleny. Položme M — {x € Aí \ x + y ^ x + z}. Jelikož 1 + y — y^ž — 1 + z, platí 1 £ M. Jestliže u G A4, pak u + y ^ u + z, odkud plyne u + y — u + y^u + z — ü + z, tudíž v, e M ■ Z axiomu úplné indukce dostáváme M — Aí.
4.8.  Tvrzení. Pro x,y E Aí 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 £ Aí. Pak nastane právě jeden z následujících tří případů:
(a)  x = y,
(b)  existuje u S Aí tak, že x — y + u,
(c)   existuje v £ Aí 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 £ Aí a nechť Mx je množina všech y £ Aí 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 £ Aí ukážeme, že Mx = Aí.
Jestliže x s= 1, pak pro každé y £ Aí, y jé 1 existuje v £ Aí tak, že y — v = 1 + v, tudíž Mi = Aí.
Jestliže x ^ 1, pak existuje u £ Aí tak, že x = ü = 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, z nastane případ (c). Jestliže nastal druhý případ, tj. existuje u £ Aí tak, že x = z + u, pak pro tí = 1 máme x — z + 1 = ~ž, a tudíž pro prvky x, J nastane případ (a). Je-li u/ 1, pak existuje v £ Aí tak, že u = v, a pak x — i + tí = = z + v = z + v — z + v. Pro prvky x,ž pak nastane případ (b). Zbývá nám třetí případ, kdy existuje v £ Aí, z — x + v. Pak ž = x + v — x + v, tudíž pro prvky x, J nastane případ (c). Odtud plyne ž £ Mx. Z axiomu úplné indukce dostáváme MX=AÍ.
Důkaz je dokončen.
4.10.  Definice. Pro x,y £ Aí položme x < y, jestliže x = y, nebo existuje u £ Aí tak, že y = x + u. Jestliže x < y a x ^ y, klademe x < y. Neboli x < y právě tehdy, když existuje u £ Aí tak, ie y = x + u.
4.11.  Věta. Relace < na množině Aí je lineární uspořádání s nejmenším prv-. kern 1.
Důkaz. Reflexivita a tranzitivita relace < je zřejmá. Antisymetrie a úplnost plyne z 4.9.
Nechť x £ Aí. Je-li x = 1, pak 1 < x. Jestliže x jí 1, pak existuje u £ Aj' tak, že ü — x, tudíž x — u + 1, odkud plyne 1 < x. Tím jsme ukázali, že 1 je nejmenší prvek uspořádané množiny (Aí, < ).
Kap. 4. Polookruh přirozených čísel
25
Lineární uspořádání < na množině M je spojeno s operací + následujícími
vztahy.
4.12. Věta. Nechť x, y, z, r, s £ A/'. 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, paic K+r < y + s,
(d)  x < y,r < s ==> x + r < y + s,
Důkaz. Jestliže x < y, pak existuje u £ M tak, že a: + u ~ y, odkud y + z — = (a; + z) + u, z čehož dostáváme x + z < y + z.
Jestliže x + z < y + z, pak existuje u £ M tak, že x + z + u = y ■+ z. Ze zákona o odečítání pak plyne x + u — y, tedy a; < 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 + yaz 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 A/ tak, že x + u = y. Jestliže u = 1, pak x — y. Jestliže u ^ 1, pak existuje v £ Aľ 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á nejmenší prvek; Říkáme též, že (P, ■<) je dobře uspořádaná množina.
4.15.  Věta. Množina (JV, <) je dobře uspořádaná množina.
Důkaz. Nechť A4 je libovolná neprázdná podmnožina M. Ukážeme, že má nejmenší prvek. Položme AI* = {a; G A/* | V m 6 A4 : x < m}. Protože je množina M neprázdna, můžeme zvolit prvek r G A4. Protože ř = r + 1 > r, nepatří f do množiny A4*. Jelikož 1 G A4*, plyne z axiomu úplné indukce existence prvku s G A4* takového, že š ^ A4*. Ukážeme, že s je nejmenší prvek množiny A4.
Poněvadž s G A4* platí s <m pro každý prvek A4. Jestliže s $ A4, pak s < ro uro každý prvek ro G A4 a podle 4.12 (e) je š < m pro každý prvek m G A4, což je spor s předpokladem š 0 A4*. Tudíž s G A4 a věta je dokázána.
4.16. Tvrzení. Nechť 0 ^ M C A/ je sJiora ohraničená množina, tj. existuje z £ N tak, že pro každý prvek m £ M platí m < z. Pak A4 má největší prveic.
Důkaz. Položme A4* = {x G A/ | V tti G A4 : a: > m}. Jelikož A4"* # (3, existuje nejmenší prvek s množiny A4*. Ukážeme-li, že s G A4, pak s bude největší
prvek množiny A4.
Je-li s = 1, pak nutně A4 = {1}. Nechť s ^ 1. Pak existuje v £ M tak, že TJ = s.
2G
Obory přirozených, celých a racionálních čísej
Protože s je nejmenší prvek A4*, platí v ^ A4*,, a tedy existuje m G A4 takové, že v < m. Zároveň však m < s = v,a tedy podle 4.12 (e) je s — m G A4.
4.17.  Příklad. Ukážeme si, že existuje injekce N —> M, která není surjekce. Buď b £ N libovolné a definujme /& : A/" ->■ N takto
...       I x,     jestliže x < b, fb{x) = < _
I x,     jestliže x > b.
Ověřte sami rozepsáním, že pro libovolné x,y £ N z x < y plyne f b (x) < fb(y), a tedy /& je injektivní. Na druhou stranu pro žádné x £ M neplatí f b (x) = b, a proto fb není surjekce.
4.18. Věta. Nechť m G A/. Označme A(m) = {s £ A/ | s < m). Pak neexistuje injekce / : A/ -> A(m).
Důkaz. Označme M = {m £ Aí \ neexistuje injekce / : A/ -> Ä(m}}. Snadno se vidí, že / : A/ -4 {1} není injekce, a tedy 1 G A4.
Buď m G A4 a předpokládejme, že m ^ A4, tj. existuje injekce / : A/ -4 A(m). Připomeňme, že z 4.12 (e) plyne A(m) — A(m)U{m}. Rozlišme dva případy podle toho, zda existuje b £ M s vlastností f (b) = m. Pokud neexistuje, můžeme uvážit injektivní zobrazení g : M -> A(m) určené předpisem y (x) = /(x), což je však spor s m G A4. Pokud takové b existuje, pak je jediné, neboť / je injekce. Položme g = / o f b, kde f b je definováno v předchozím příkladu. Pak g : A/ '-> A (m) je injekce a neexistuje x £ M s vlastností y (x) = m, což je opět podle předchozího spor.
Pro M jsme tedy ukázali m G A4 =^ m G A4. Proto A4 = A/'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 f : M -* M, která není surjekcí;
-    existuje injekce / : A/ -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 A/.
4.20.  Věta. JVa množině N existuje právě jedna operace • taková, že pro každé x, y G A/ piati:
(a)  x • 1 = x,
(b)  x • y — x ■ y + x.
Pro tuto operaci a pro každé x, y £ N 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ť A4 je množina všech x 6 Aí, ke kterým existuje zobrazení fx množiny Aí do sebe s 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 € Aí, pak /i je takové zobrazení pro x = 1. Tudíž 1 G A4. Buď /z uvedené zobrazení pro a; € A4. Pro y € A/" položíme My) = /*(y) + y. Pak h{l) = /a(l) + 1 = x + 1 = x a JV(y) = /,(y) + y = = /z(y) + íc + y + 1 = fx(y) + ? pro i/ € A/". Tudíž a; e A4 a M = A/".
Předpokládejme, že pro některé x e Aí existují dvě zobrazení vlastností (*). Označme je fx, gx a položme A4 ■= {y € Aí | fx{y) = 9x{y)}- Zřejmě 1 € A4. Pokud z e M, pak fx(ž) = fx{z) + x = ^(z) + x = 9x(ž), tudíž ž 6 A4 a M = Aí. Tedy f® = |a a pro každé a; existuje právě jedno zobrazení vlastností (*).
Nyní můžeme operaci • definovat vztahem x -y = /a, (y). Tato operace, vzhledem k (*), splňuje podmínky (a) a (b).
Ze vztahu x ■ y = fx(y) pak dostáváme 1 ■ x = /i (x) = a; a x ■ y = fx(y) = = 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ě Aí 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 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 Aí je komutativní a asociativní a s operací + je svázána tzv. distributivním zákonem:
x,y,z 6 Aí =*• x ■ (y + z) — x ■ y -\-x ■ z.
Důkaz. Nechť x € Aí. Položme M = {y e Aí \ x-y = y-x). Z 4.20 (a), (c) plyne 1 e A4. Pro y e M podle 4.20 (b), (d) dostáváme y ■ x = y-x + x - x-y + x = x-y, tudíž y € A4. Tedy A4 = A/", což dokazuje komutativitu násobení. .
Buď x,y € Aí. Položme A4 - {z € Aí \ x ■ {y 4- z) - x ■ y + x ■ z}. Platí x ■ (y + 1) = x-y~x-y + x~x-y + x-l, tudíž 1 6 M. Nechť z € M, pak
x ■ (y + ž) = x • (y + z) — x • (y -M) + x = x • y -f x • z -f x = a;. • y + x ■ J,
tedy ž £ M. Opět z axiomu úplné indukce dostáváme A4 — A/". Odtud plyne distributivní zákon.
28                                                                 Obory přirozených, celých a racionálních čísel
Nechť x, y e Aí. Položme A4 = {z £ Aí \ (x -_j/) -z - x-(y-z)}. Zrejme 1 6 A4. Je-li2 G A4, pak (x-y)-ž = {x-y)-z+x-y ~x-{y-z) + x-y ~ x-{y-z+y) = x-(yz), tedy ž e A4. 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 (Aí, ■) je 1 jednotJíový prvek.
4.25.  Věta. Nechť x,y,z,r,s € Aí. Pak platí:
(a)  X < y <=> x ■ z < y ■ z,
(b)  x ■ z = y ■ z => x = y,
(c)  x < y 4=^ x ■ z < y ■ z,
(d) jestliže x <y,r < s nebo x <y,r < s nebo x <y,r < s, pak x-r <ys,
(e)  x <y,r < s => x ■ r < y ■ s.
Důkaz. Nechť x < y. Pak existuje u 6 Aí tak, že y = x + u. Odtud plyne y ■ z = x ■ z + XJ, ■ z, tudíž x ■ z < y • z.
Je-li x- z <y ■ z a y < x, pak podle předešlého y ■ z < a: ■ 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 e G platí obě implikace
x • y = x • z =*■ y = z,
y ■ x = z ■ x => y = z,
říkáme, že v (G, •) platí zá/zon o krácení. Věta 4.25 (b) tedy tvrdí, že v grupoidu (A/", •) platí zákon o krácení. V prípade, 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 : Aí x M -+ M am je libovolný prvek z M.
Pak existuje právě jedno zobrazení P : Aí ~> M takové, že platí: i)    P(l) = m, ii)   pro x 6 Aí platí <p(x, P(x)) = P(x).
Kap. 4. Polookruh přirozených čísel
29
Důkaz. Pro x € AÍ položme A{x) — {t 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řípustné, jestliže platí
(a)  p(l) = m,
(b)  s e 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á 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 — q(ľ), je u ^ 1, a existuje tedy í G A{x) tak, že í = u. Podle (b) je p(u) = tp(t, p(í)) = ¥>(i, 9(í)) = q(u), což je spor.
Označme nyní A4 množinu všech x E ŕ/ takových, že úsek A(x) má přípustné zobrazení. Zřejmě 1 € M. Pro x £ M platí též x € M, protože A(x) = A(x)U{x}; je-li totiž p přípustné zobrazení úseku A(x), pak zobrazení q : A(x) -i M, které je určené předpisem q(ť) = p(í) pro í € A(x) a <jr(x) = tp(x, p(x)), je přípustné zobrazení úseku A(x). Tudíž A4 = TV.
Snadno se vidí, že zúžení přípustného zobrazení úseku A(x) na úsek A(y) pro x,:y e Aí,ý < x, je opět přípustné zobrazení.
Pro x G A/" položme P(x) == p(x), kde p je přípustné zobrazení úseku A(x). Pak P(l) = m. Nechť x £ N a. nechť p je přípustné zobrazení úseku A(x) a g přípustné zobrazení úseku A (x). Potom
P(x) - q{x) = iŕ(a;, g(x)) = v(i, p(aO) = <p(a:y 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 Af, 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 Aí.
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ť AÍ,AÍ* jsou množiny přirozených čísel, p, G Aí*. Pak existuje právě jedno zobrazení f : Aí —► Aí* tak, že piatí:
i)    /(l) - ß,       ____
ii)  pro x e Aí je /(x) = f(x). Toto zobrazení f je injekce a f(AÍ) = \y G TV* | p < u).
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 Aí položíme <p(x, i) =t pro každé t G TV*. Podle' 4.27 existuje právě jedno zobrazení / : TV -4 TV* tak, že /(l) = p a pro x G TV je /(x) = /(x).
Ukážeme, že pro libovolná x,y G TV, x < y platí /(x) < /(y). Označme za tím účelem A/í = {xGTV|3j/GTV, x< y, f (y) < /(x)}. Předpokládejme, že existuje u G M. Pro toto u uvažme množimu Ou = {y £ Aí \ u < y, f (y) < f (u)}. Množina Ou je dle předpokladu u € M neprázdná, tudíž existuje její nejmenší prvek; označme jej v. Protože v ^ 1, existuje'u; G Aí tak, že w = v. Z 4.12 (e) plyne u < w. Protože v je nejmenší prvek öu, musí platit w £ Ou, tzn. buď u = w nebo /(u) < /(io). V obou případech tedy
/(«) < /(«O < 7w » /(«j) « /(v),
což je spor s u G öu. Tzn. Al = 0, a tedy pro každé x, y G TV, x < y platí /(x) < /(y). Odtud plyne, že / je injekce a /(TV) C {^ G TV* | /i < y}.
Nechť A je nejmenší prvek množiny všech prvků z A/"*, které nemají vzor při zobrazení / a jsou větší než p. Zřejmě A ^ Ijy*, a proto musí existovat k G TV* takové, že k, — X. Prvek k má vzor při zobrazení /, který označme m. Potom /(m) = f(m) — k — A, což je spor. Tudíž /(TV) = {ľ G TV* | p < i/} 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Í,jV* jsou množiny přirozených čísel. Pak existuje právě jedna bijekce f : TV -)■ TV* taJcová, že pro každé x E Aí platí: f(x) = f{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 1 (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 1/= 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.