Uspořádané množiny, přirozená čísla
Doc. Dr. Vladimír Homola, Ph.D.
Definice: Nechť je na množině A dána areflexivní a tranzitivní relace (tedy ostré uspořádání). Taková množina se nazývá uspořádaná. Je-li na množině A dáno více ostrých uspořádání, např. F a G, pak mluvíme o množině A uspořádané v uspořádání F, v uspořádání G apod.
Je zřejmé, že každá podmnožina M uspořádané množiny A je uspořádaná (dokonce v tolika uspořádáních, kolik jich je dáno na A).
Označení: Je-li dáno jen jedno ostré uspořádání nebo není-li pochyb, o které z více uspořádání jde, značí se relace tohoto ostrého uspořádání symbolem "<".
Definice: Platí-li pro a Î A, b Î A (přičemž na A je dáno ostré uspořádání <) vztah a < b, pak se a nazývá předchůdce b nebo také že a předchází b, b se nazývá následník a nebo také že b následuje a, to vše v uspořádání <.
Definice: Platí-li pro a Î A, b Î A (přičemž na A je dáno ostré uspořádání <) vztah a < b a přitom pro žádné c Î A neplatí, že a < c a současně c < b, pak se a nazývá bezprostřední předchůdce b nebo také že a bezprostředně předchází b, b se nazývá bezprostřední následník a nebo také že b bezprostředně následuje a, to vše v uspořádání <.
Označení: Bezprostředního následníka prvku a budeme označovat a+, bezprostředního předchůdce symbolem -a.
Příklad: V množině desetinných čísel - uspořádané zatím intuitivně "podle velikosti" - mají všechny prvky předchůdce (následníka), ale žádný nemá bezprostředního předchůdce (bezprostředního následníka).
Definice: Nemá-li prvek a Î A v uspořádání < předchůdce, nazývá se a prvním prvkem v uspořádání <. Nemá-li prvek z Î A v uspořádání < následníka, nazývá se z posledním prvkem v uspořádání <.
Věta: Každá uspořádaná množina má nejvýše jeden první prvek a nejvýše jeden poslední prvek.
Důkaz plyne z vlastnosti relace ostrého uspořádání. Naopak uspořádaná množina nemusí mít poslední prvek (např. množina {1, 2, 3, ... } uspořádaná - zatím intuitivně - "podle velikosti"), nemusí mít první prvek (např. množina {..., -3, -2, -1}) a nemusí mít ani první, ani poslední prvek (např. množina {..., -3, -2, -1, 0, 1, 2, 3, ...}).
Věta: Každou množinu lze uspořádat.
Jinak řečeno, na každé množině A lze definovat alespoň jednu relaci R, která je areflexivní a tranzitivní. Idea důkazu může být např. následující:
Vezměme libovolný prvek a Î A a vytvořme množinu R1 = {[a,x]} pro všechny x Î A-{a}. Dále vezměme libovolný prvek b z množiny A-{a} a vytvořme množinu R2 = {[b,y]} pro všechny y Î A-{a,b} atd. Množina R = R1Č R2 Č ... je zřejmě podmnožinou AxA (je tedy relací) a snadno se ověří, že je areflexivní i tranzitivní. Prvním prvkem je prvek a, jeho bezprostředním následníkem prvek b atd.
Definice: Nechť jsou dány množina A s
uspořádáním R a množina D. Existuje-li prosté zobrazení F (celé)
množiny A na (celou) množinu D a existuje-li takové uspořádání
S na množině D, že platí:
a R b ® F(a) S F(b)
pro všechna a, b Î A
pak se množiny A, D nazývají podobně uspořádané
nebo někdy také jen podobné.
Poznámka: Podobné množiny jsou tedy ekvivalentní již podle podle definice.
Definice: Množina všech předchůdců prvku a Î A se nazývá úsek uspořádané množiny A tvořený prvkem a, a značí se A|a.
Prvek a sám do úseku A|a nepatří. Z toho plyne, že úsek tvořený prvním prvkem je prázdná množina. Protože každý úsek A je podmnožinou A, je sám uspořádanou množinou.
Věta: Ze dvou různých úseků téže uspořádané množiny je vždy jeden podmnožinou druhého.
Při některých úvahách je zapotřebí pracovat s takovou množinou, do které patří nejen všichni předchůdci prvku a, ale také prvek a samotný. Zavádí se proto pojem:
Definice: Množinu A|a Č {a}nazvěme vlastním úsekem uspořádané množiny A tvořený prvkem a, a označujme se A||a.
Definice: Má-li každá neprázdná část uspořádané množiny A první prvek, nazývá se množina A dobře uspořádaná množina.
Příklad (pod uspořádáním chápeme - zatím intuitivní - uspořádání "podle velikosti"): Je zřejmé, že množina přirozených čísel {1, 2, 3, ...} je dobře uspořádaná. Naopak množina všech desetinných čísel není "podle velikosti" dobře uspořádaná: např. její část tvořená desetinnými čísly většími než 1 nemá první prvek (prvek 1 tam nepatří a žádné desetinné číslo není "těsně vpravo vedle" 1).
Věta: Nechť A je neprázdná dobře uspořádaná množina. Pak platí: každý prvek A kromě posledního má bezprostředního následníka.
Poznámka: Zdaleka však neplatí, že každý prvek kromě prvního má bezprostředního předchůdce. Např. množina {1, 3, 5, 7, 9, ...., 2, 4, 6, 8, ....} je jistě dobře uspořádaná v uspořádání daném pořadím ve výčtu jejich prvků. Každý prvek má svého bezprostředního následníka (pro prvek X je to X+2). Naopak prvek 2 nemá bezprostředního předchůdce.
Věta: Každý úsek dobře uspořádané množiny je dobře uspořádaná množina.
Označení: Označujme v dalším symbolem Q nějakou dobře uspořádanou množinu, jejíž každý prvek kromě prvního má předchůdce (jejíž každý prvek kromě prvního je následníkem nějakého jiného prvku). Označujme dále symbolem P jakoukoliv množinu s vlastnostmi Q, která navíc nemá poslední prvek.
Důležitá poznámka: Na tomto místě by měl logicky stát důkaz toho, že alespoň jedna množina P s uvedenými vlastnostmi existuje. Její existence se však dokázat nedá, předpoklad její existence je jedním ze základních axiomů matematiky.
Věta: Každý neprázdný úsek množiny Q má poslední prvek.
Definice: Množina A je spočetná, je-li ekvivalentní s množinou Q nebo některým jejím neprázdným úsekem. Není-li množina A spočetná, je nespočetná.
Věta: Množina A je spočetná, lze-li ji uspořádat tak, aby každý její prvek kromě prvního byl následníkem nějakého jiného jejího prvku.
Věta plyne z vlastnosti podobnosti množin a vztahu ekvivalence. Dále platí:
Věta: Množina A je spočetná tehdy a jen tehdy, lze-li ji uspořádat tak, aby každý její neprázdný úsek měl poslední prvek.
Věta: Nechť je dána množina Q a dále množina B, která rovněž je dobře uspořádaná a každý její prvek kromě prvního má předchůdce (jejíž každý prvek kromě prvního je následníkem nějakého jiného prvku). Nemá-li množina B poslední prvek, je podobná množině Q. Má-li množina B poslední prvek, je podobná některému úseku množiny Q.
Definice: Množina A se nazývá konečná, je-li ekvivalentní s nějakým úsekem množiny P. Množina, která není konečná, se nazývá nekonečná.
Je zřejmé, že každá konečná množina je spočetná. Nekonečná množina však může být spočetná i nespočetná. Je-li nekonečná množina ekvivalentní s množinou P, je spočetná, jinak je nespočetná.
Protože vztah podobnosti dvou uspořádaných množin je ekvivalence, definuje tato ekvivalence rozklad množiny uspořádaných množin na třídy. Každá třída pak obsahuje množiny, které jsou si podobné.
Poznámka: Je zapotřebí zdůraznit, že tento rozklad na třídy podstatně závisí na uspořádání, které je na té které množině právě dáno. Při jednom uspořádání množiny A může být tato množina v jedné třídě, při jiném v jiné třídě.
Definice: Přiřaďme každé třídě popsané shora jakýkoliv symbol, který tuto třídu jednoznačně identifikuje (bude tedy zapotřebí použít tolika různých symbolů, kolik je tříd). Ordinální číslo dobře uspořádané množiny A je symbol přiřazený třídě, které je množina A prvkem. Označujme v dalším ordinální číslo množiny A jako O(A).
Všimněme si, že ordinální číslo se definuje pouze pro dobře uspořádané množiny. Je zřejmé, že dvě množiny mají stejné ordinální číslo, jsou-li si podobné. Vztah rovnosti ordinálních čísel je tedy vztahem ekvivalence.
Označme symbolem W nějakou množinu ordinálních čísel (množina symbolů označujících třídy rozkladu). Definujme na W vztah "býti menším" takto:
Definice: Je-li dobře uspořádaná množina A ze třídy s ordinálním číslem O(A)ÎW podobná nějakému úseku nějaké dobře uspořádané množiny B ze třídy s ordinálním číslem O(B)ÎW, pak definujeme že O(A) předchází O(B) nebo že O(A) je menší než O(B). Zapisujeme O(A) < O(B).
Věta: Vztah "Býti menším" podle předchozí definice je areflexivní (žádná dobře uspořádaná množina není podobná nějakému svému úseku) a tranzitivní. Tento vztah definuje tedy uspořádání množiny ordinálních čísel.
Věta: Ke každému ordinálnímu číslu každé množiny W ordinálních čísel existuje jeho bezprostřední následovník, a to jediný. Každá množina W ordinálních čísel má (jediný) první prvek.
Definice: Tento jediný první prvek se nazývá nejmenší (ordinální) číslo množiny W.
Shora byla zavedena jakási množina P, která je nekonečná a dobře uspořádaná. Její každý prvek s výjimkou prvního je následníkem nějakého jiného jejího prvku. Nemá poslední prvek. Dále byla definována konečná množina jako množina ekvivalentní s nějakým neprázdným úsekem P. Dále bylo ukázáno, že každou konečnou množinu lze dobře uspořádat a že nehledě na uspořádání dostaneme vždy množinu, která je ekvivalentní s týmž úsekem P. Proto můžeme na každou konečnou množinu nahlížet jako na dobře uspořádanou množinu, která má tedy určité ordinální číslo, a toto ordinální číslo není závislé na způsobu, kterým je daná množina uspořádána (proto je např. nerozhodující, o jakou konkrétní množinu P jde).
Definice: Ordinální čísla konečných (a tedy dobře uspořadatelných) množin se nazývají přirozená čísla.
Protože je každé přirozené číslo definováno jako ordinální číslo neprázdného úseku P, odpovídá každému prvku pÎP právě jedno přirozené číslo P|p a naopak. Toto "odpovídání" je ekvivalencí a množina přirozených čísel je tedy podobná množině P. Proto při úvahách o vlastnostech přirozených číslech můžeme množinu přirozených čísel ztotožnit s množinou P.
Název "přirozená" dostala přirozená čísla zřejmě proto, že se k množině P, ordinálním číslům a podobnosti množin přirozeně dopracovali už lovci mamutů. A to v okamžiku, když si uvědomili, že mamuta, uloveného předevčírem, mohou označit symbolem první, mamuta uloveného včera symbolem druhý, mamuta uloveného dnes symbolem třetí (a zavedli symboly - ordinální čísla). Mamut ulovený předevčírem je předchůdcem mamuta uloveného dnes, ale není to jeho bezprostřední předchůdce - tím je mamut ulovený včera (a zavedli uspořádání). Když ukazovali sousedovi v jeskyni, kolikže ulovili mamutů předevčírem, ukázali prst. Když mu chtěli ukázat, kolik jich mají dnes, ukázali tři prsty (a zavedli podobnost množin). Navíc: když už mamuti leželi před jeskyní a lovci mamutů se přesvědčovali, jestli jim někdo jednoho neukradl, přiřazovali mamuty prstům a pokud neukradl, dospěli vždy ke stejnému výsledku - bez ohledu na to, jestli je přiřazovali zleva doprava nebo zprava doleva (a došli k nezávislosti ordinálních čísel na uspořádání).
Definice: Nechť pÎP je první prvek množiny P v nějakém uspořádání. Jako ordinální číslo O(p) zavedeme symbol 1 a budeme číst jedna nebo také číslo jedna.
Podle definic podaných shora není číslo jedna následníkem žádného přirozeného čísla. Dále: ke každému přirozenému číslu a existuje jediné přirozené číslo, které je bezprostředním následníkem a a naopak: každé přirozené číslo různé od čísla jedna je bezprostředním následníkem jiného přirozeného čísla. Konečně různá přirozená čísla mají různé bezprostřední následníky.
Věta: Pro každou dvojici přirozených čísel a, b existuje právě jedno přirozené číslo c = c(a,b) takové, že platí:
c(a,1) = a+
c(a,b+)=c(a,b)+
Definice: Číslo c(a,b) z předchozí věty se nazývá b-tý následník čísla a. Tohoto následníka budeme v dalším označovat a+b.
Věta: a+b = b+a pro libovolná dvě přirozená čísla a, b.
Věta: (a+b)+c = a+(b+c) pro libovolná tři přirozená čísla.
Věta: Je-li a ą b, je také a+c ą b+c, kde a, b a c jsou přirozená čísla.
Věta: a+b je různé od a pro všechna přirozená čísla a, b.
Věta: Jsou-li a, b dvě přirozená čísla, pak nastane vždy jeden z případů:
1. a = b
2. existuje přirozené číslo i tak, že a+i = b
3. existuje přirozené číslo j tak, že a = b+j
Z definice přirozených čísel a z předchozích vět plyne, že množina přirozených čísel je jednak spočetná množina, jednak nekonečná množina. Na základě bezprostředně předcházející věty lze vyslovit definici:
Definice: Nastane-li případ 2, říkáme, že číslo a je menší než číslo b a značíme a<b. Nastane-li případ 3, říkáme, že číslo a je větší než číslo b a značíme a>b. Nastane-li případ 1 nebo 2, říkáme, že číslo a je menší nebo rovno číslu b a značíme aŁb. Nastane-li případ 1 nebo 3, říkáme, že číslo a je větší nebo rovno číslu b a značíme ałb.
Lze jednoduše dokázat, že vztah < definuje na množině přirozených čísel uspořádání, dokonce dobré uspořádání. Toto uspořádání se nazývá přirozené uspořádání. Proto platí následující věty:
Věta: V každé neprázdné množině přirozeně uspořádaných přirozených čísel existuje první prvek (číslo).
Definice: Prvnímu číslu z předchozí věty říkejme nejmenší číslo množiny.
Věta: V každé neprázdné konečné množině přirozeně uspořádaných přirozených čísel existuje poslední prvek (číslo).
Definice: Poslednímu číslu z předchozí věty říkejme největší číslo konečné množiny.
Konečně závěrečná, nejdůležitější definice této kapitoly:
Definice: Je-li konečná množina A ekvivalentní s vlastním úsekem P||n (kde P je množina přirozených čísel v přirozeném uspořádání), nazývá se přirozené číslo n počtem prvků množiny A.
Poznámka: Prvky množiny přirozených čísel bývá zvykem označovat zvláštními znaky: první prvek už zmíněným znakem 1, jeho bezprostředního následníka (tj. prvek 1+) znakem 2, prvek 2+ znakem 3 atd. Pozor však: v tomto pojetí je např. 10 jedním jediným nedělitelným symbolem, který označuje prvek 9+ (!!).
Rev. 10 - 2002