Ordinální aritmetika

Ordinální aritmetika je jednou z disciplín klasické teorie množin. Zabývá se rozšířením základních aritmetických operací (sčítání, násobení, mocnění) z přirozených čísel na všechna ordinální čísla (včetně nekonečných). Toto rozšíření probíhá tak, aby byly dobře zachyceny vlastnosti takzvaných dobrých uspořádání.

Na ordinálech lze zavést součin a součet, které ale nejsou komutativní, např. platí $1+\omega =\omega \not =\omega +1$ . Symbol 1 zde představuje jednoprvkovou množinu, symbol $\omega$ pak množinu přirozených čísel (včetně nuly) s obvyklým uspořádáním.

Rovnost $1+\omega =\omega$ vyjadřuje, že částečně uspořádaná množina „jednoprvková množina a za ní přirozená čísla“ je izomorfní s přirozenými čísly. Pro názornost lze tuto jednoprvkovou množinu chápat jako $\{-1\}$ a pak $f(x)=x+1$ je izomorfismus mezi touto výslednou množinou a $\omega$ .
Nerovnost $\omega \not =\omega +1$ vyjadřuje, že je-li za přirozená čísla přidán další prvek, vznikne dobře uspořádaná množina, která není izomorfní s $\omega$ (např. má největší prvek). To ilustruje, že na nekonečné spočetné množině mohou existovat různé typy dobrého uspořádání.

Podobně se supremum (tj. sjednocení) množiny $\{\omega +1,\omega +2,\omega +3,\ldots \}$ značí $\omega +\omega$ nebo též $\omega \times 2$ a platí

$2\times \omega =\omega$ : na dvou kopiích přirozených čísel („modré“ a „červené“ kopii) lze zavést dobré uspořádání tak, že po modré nule následuje červená nula, dále modrá jednička, červená jednička, modrá dvojka atd. Toto uspořádání je však izomorfní s $\omega$ .
$\omega \times 2>\omega$ : Tutéž množinu lze uspořádat i tak, že každé modré číslo předchází každému červenému (tj. napřed všechna modrá, v obvyklém pořadí, po nich červená nula, červená jednička atd.) Taková množina ale není izomorfní s $\omega$ , například má prvek (červenou nulu), který není ani nejmenším prvkem množiny, ani přímým následníkem jiného prvku; tuto vlastnost by izomorfismus zachoval.

V celém článku jsou písmena ze začátku řecké alfabety používána pro označení ordinálů.

Vztah ke kardinální aritmetice

Jinou možností je pokus o zachycení vlastností velikosti množin – tím se zabývá kardinální aritmetika. Např. kardinální součet $\omega +\omega$ je roven $\omega$ , protože obě množiny mají stejnou mohutnost (kardinalitu). Pokud však stejný symbol, plus, označuje ordinální součet, rovnost neplatí, protože $\omega +\omega$ definuje jinak uspořádanou množinu, než $\omega$ (ač mají stejnou mohutnost, a to spočetnou), a tato uspořádání nejsou izomorfní. V ordinální aritmetice tedy platí $\omega <\omega +1<\omega +\omega =\omega \times 2<\omega \times \omega$ , zatímco v kardinální aritmetice jsou všechny tyto výrazy rovny $\omega$ neboli $\aleph _{0}$ .

Ordinální čísla a jejich vlastnosti

Základní definice a vlastnosti ordinálních čísel najdete v článku Ordinální číslo.

Definice ordinálního součtu a součinu

Jsou-li $\alpha \,\!$ a $\beta \,\!$ dvě ordinální čísla, pak:

jako $\alpha +\beta \,\!$ označíme ordinální číslo, které je typem množiny $(\{0\}\times \alpha )\cup (\{1\}\times \beta )$ v lexikografickém uspořádání
jako $\alpha .\beta \,\!$ označíme ordinální číslo, které je typem množiny $\beta \times \alpha$ v lexikografickém uspořádání.

Typem dobře uspořádané množiny se rozumí ordinální číslo, které je při uspořádání relací $\in$ izomorfní s touto množinou – jedním z poměrně jednoduchých výsledků teorie ordinálních čísel je, že každá dobře uspořádaná množina je izomorfní s právě jedním ordinálem.

Příklady součtu dvou ordinálních čísel

Součet 3 + 2:
$(\{0\}\times 3)\cup (\{1\}\times 2)=$
$(\{0\}\times \{0,1,2\})\cup (\{1\}\times \{0,1\})=$
$\{[0,0],[0,1],[0,2]\}\cup \{[1,0],[1,1]\}=$
$\{[0,0],[0,1],[0,2],[1,0],[1,1]\}\,\!$
Typem této množiny v lexikografickém uspořádání (tj. napřed podle prvního a pak podle druhého prvku uspořádané dvojice) je ordinál 5, takže 2 + 3 = 5, což vypadá docela povědomě.

Součet $1+\omega _{0}\,\!$ (jako $\omega _{0}\,\!$ se značí množina všech přirozených čísel)
$(\{0\}\times 1)\cup (\{1\}\times \omega _{0})=$
$(\{0\}\times \{0\})\cup (\{1\}\times \{0,1,2,3,...\})=$
$\{[0,0]\}\cup \{[1,0],[1,1],[1,2],[1,3],...\}=$
$\{[0,0],[1,0],[1,1],[1,2],[1,3],...\}\,\!$
Typem této množiny v lexikografickém uspořádání je $\omega _{0}\,\!$ , takže $1+\omega _{0}=\omega _{0}\,\!$ . Tady už je to s tou povědomostí horší – když něco zleva přičtu k množině všech přirozených čísel, dostanu opět množinu přirozených čísel.

Doporučuji každému, aby si zkusil podle definice rozepsat $\omega _{0}+1\,\!$ . Dojde k překvapivému zjištění:
$1+\omega _{0}=\omega _{0}<\omega _{0}+1\,\!$

Příklady součinu dvou ordinálních čísel

Součin 3.2:
$2\times 3=\{0,1\}\times \{0,1,2\}=$
$\{[0,0],[0,1],[0,2],[1,0],[1,1],[1,2]\}\,\!$
Typem této množiny s lexikografickým uspořádáním je číslo 6.

Součin $2.\omega _{0}\,\!$
: $\omega _{0}\times 2=\{0,1,2,...\}\times \{0,1\}=\,\!$
$\{[0,0],[0,1],[1,0],[1,1],[2,0],...\}\,\!$
Typem této množiny s lexikografickým uspořádáním je $\omega _{0}\,\!$ .

Obrátím-li poslední příklad na $\omega _{0}.2\,\!$ , dostávám množinu
$\{[0,0],[0,1],[0,2],...,[1,0],[1,1],[1,2],...\}\,\!$ ,
jejímž typem již není $\omega _{0}\,\!$ , ale větší ordinální číslo $\omega _{0}+\omega _{0}=\omega _{0}.2\,\!$

Rozhodně opět $2.\omega _{0}<\omega _{0}.2\,\!$ .

Vlastnosti ordinálního součtu a součinu

Ordinální součet a součin je definován tak, aby na přirozených číslech (tj. v našem případě na konečných ordinálech) dával stejné výsledky jako běžný aritmetický součet a součin v Peanově aritmetice. Dá se dokonce ukázat, že ordinální aritmetika na konečných ordinálech je modelem Peanovy aritmetiky.

Zajímavější začíná být situace na nekonečných ordinálech, kde se již toto chování liší – součet ani součin nejsou komutativní a ordinální součin je distributivní pouze zleva:
$(\forall \alpha ,\beta ,\gamma )(\alpha .(\beta +\gamma )=\alpha .\beta +\alpha .\gamma )$
Opačně to ale neplatí, protože například: $(1+1).\omega _{0}=2.\omega _{0}\neq 1.\omega _{0}+1.\omega _{0}=\omega _{0}.2$ – viz předchozí příklady.

Uveďme některé další vlastnosti ordinálního součtu a součinu (všechny lze snadno odvodit přímo z definice stejně, jako v předchozích příkladech):

$\alpha +0=0+\alpha =\alpha \,\!$
$\alpha .0=0.\alpha =0\,\!$
$\alpha .1=1.\alpha =\alpha \,\!$
$\alpha +(\beta +\gamma )=(\alpha +\beta )+\gamma \,\!$
$\alpha .(\beta .\gamma )=(\alpha .\beta ).\gamma \,\!$

A na závěr ještě něco, co vypadá trochu jako zbytek po dělení na přirozených číslech:
Pro každé dva ordinály $\alpha ,\beta ,\beta >0\,\!$ existují $\gamma _{1}\leq \alpha ,\gamma _{2}<\beta \,\!$ takové, že
$\alpha =\beta .\gamma _{1}+\gamma _{2}\,\!$

Definice ordinální mocniny

Ordinální mocnina mocnina je opět rozšířením své jmenovkyně známé z přirozených čísel, definuje se rekurzivně následujícím způsobem:

$\alpha ^{0}=1\,\!$
$\alpha ^{\beta +1}=\alpha ^{\beta }.\alpha \,\!$
pro limitní ordinál $\beta \,\!$ je $\alpha ^{\beta }=sup\{\alpha ^{\gamma }:0<\gamma <\beta \}\,\!$ – sup v tomto výrazu znamená supremum dané množiny k uspořádání ordinálních čísel relací $\in$

Vlastnosti ordinální mocniny

Ordinální mocnina má opět řadu vlastností, které bychom od aritmetické operace toho jména čekali:

$0^{0}=1\,\!$
$0^{\alpha }=0\,\!$ pro $\alpha >0\,\!$
$1^{\alpha }=1\,\!$
$\alpha ^{1}=\alpha \,\!$
$\alpha ^{2}=\alpha .\alpha \,\!$

A především:

$\alpha ^{\beta +\gamma }=\alpha ^{\beta }.\alpha ^{\gamma }\,\!$
$(\alpha ^{\beta })^{\gamma }=\alpha ^{\beta .\gamma }\,\!$

Mocninný rozvoj ordinálního čísla

Na závěr ještě uveďme větu o mocninném rozvoji ordinálních čísel (konkrétně pro základ $\omega _{0}\,\!$ – opět lze srovnávat s mocninným rozvojem na přirozených číslech například ze základu 2:

Je-li $\omega =\omega _{0}\,\!$ množina přirozených čísel a $\alpha \,\!$ libovolný ordinál, pak existují jednoznačně daná přirozená čísla $k,m_{0},m_{1},...,m_{k}\,\!$ a ordinály $\beta _{0}>\beta _{1}>\beta _{2}>...>\beta _{k}\,\!$ takové, že platí:
$\alpha =\omega ^{\beta _{0}}.m_{0}+\omega ^{\beta _{1}}.m_{1}+...+\omega ^{\beta _{k}}.m_{k}\,\!$

Tento zápis nazýváme Cantorův normální tvar ordinálního čísla.

Pro vyjádření čísla $\,\alpha$ v Cantorově normálním tvaru platí $\alpha \geq \beta _{0}$ , přičemž rovnost nastává právě tehdy, když $\,\alpha =\omega ^{\alpha }$ . Takových $\,\alpha$ existuje dokonce vlastní třída, nejmenší z nich se nazývá $\varepsilon _{0}$ . Pro $\,\alpha <\varepsilon _{0}$ tedy je $\,\alpha >\beta _{0}$ , což umožňuje často používanou metodu dokazování – takzvanou indukci do epsilon nula.

Související články