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í. Jinou možností je pokus o zachycení vlastností velikosti množin – tím se zabývá kardinální aritmetika.

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

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 ${\displaystyle \alpha \,\!}$ a ${\displaystyle \beta \,\!}$ dvě ordinální čísla, pak:

• jako ${\displaystyle \alpha +\beta \,\!}$ označíme ordinální číslo, které je typem množiny ${\displaystyle (\{0\}\times \alpha )\cup (\{1\}\times \beta )}$ v lexikografickém uspořádání
• jako ${\displaystyle \alpha .\beta \,\!}$ označíme ordinální číslo, které je typem množiny ${\displaystyle \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í ${\displaystyle \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:
${\displaystyle (\{0\}\times 3)\cup (\{1\}\times 2)=}$
${\displaystyle (\{0\}\times \{0,1,2\})\cup (\{1\}\times \{0,1\})=}$
${\displaystyle \{[0,0],[0,1],[0,2]\}\cup \{[1,0],[1,1]\}=}$
${\displaystyle \{[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 ${\displaystyle 1+\omega _{0}\,\!}$ (jako ${\displaystyle \omega _{0}\,\!}$ se značí množina všech přirozených čísel)
${\displaystyle (\{0\}\times 1)\cup (\{1\}\times \omega _{0})=}$
${\displaystyle (\{0\}\times \{0\})\cup (\{1\}\times \{0,1,2,3,...\})=}$
${\displaystyle \{[0,0]\}\cup \{[1,0],[1,1],[1,2],[1,3],...\}=}$
${\displaystyle \{[0,0],[1,0],[1,1],[1,2],[1,3],...\}\,\!}$
Typem této množiny v lexikografickém uspořádání je ${\displaystyle \omega _{0}\,\!}$, takže ${\displaystyle 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 ${\displaystyle \omega _{0}+1\,\!}$. Dojde k překvapivému zjištění:
${\displaystyle 1+\omega _{0}=\omega _{0}<\omega _{0}+1\,\!}$

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

Součin 3.2:
${\displaystyle 2\times 3=\{0,1\}\times \{0,1,2\}=}$
${\displaystyle \{[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 ${\displaystyle 2.\omega _{0}\,\!}$
: ${\displaystyle \omega _{0}\times 2=\{0,1,2,...\}\times \{0,1\}=\,\!}$
${\displaystyle \{[0,0],[0,1],[1,0],[1,1],[2,0],...\}\,\!}$
Typem této množiny s lexikografickým uspořádáním je ${\displaystyle \omega _{0}\,\!}$.

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

Rozhodně opět ${\displaystyle 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:
${\displaystyle (\forall \alpha ,\beta ,\gamma )(\alpha .(\beta +\gamma )=\alpha .\beta +\alpha .\gamma )}$
Opačně to ale neplatí, protože například: ${\displaystyle (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):

• ${\displaystyle \alpha +0=0+\alpha =\alpha \,\!}$
• ${\displaystyle \alpha .0=0.\alpha =0\,\!}$
• ${\displaystyle \alpha .1=1.\alpha =\alpha \,\!}$
• ${\displaystyle \alpha +(\beta +\gamma )=(\alpha +\beta )+\gamma \,\!}$
• ${\displaystyle \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 ${\displaystyle \alpha ,\beta ,\beta >0\,\!}$ existují ${\displaystyle \gamma _{1}\leq \alpha ,\gamma _{2}<\beta \,\!}$ takové, že
${\displaystyle \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:

1. ${\displaystyle \alpha ^{0}=1\,\!}$
2. ${\displaystyle \alpha ^{\beta +1}=\alpha ^{\beta }.\alpha \,\!}$
3. pro limitní ordinál ${\displaystyle \beta \,\!}$ je ${\displaystyle \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í ${\displaystyle \in }$

Vlastnosti ordinální mocniny

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

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

A především:

• ${\displaystyle \alpha ^{\beta +\gamma }=\alpha ^{\beta }.\alpha ^{\gamma }\,\!}$
• ${\displaystyle (\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 ${\displaystyle \omega _{0}\,\!}$ – opět lze srovnávat s mocninným rozvojem na přirozených číslech například ze základu 2:

Je-li ${\displaystyle \omega =\omega _{0}\,\!}$ množina přirozených čísel a ${\displaystyle \alpha \,\!}$ libovolný ordinál, pak existují jednoznačně daná přirozená čísla ${\displaystyle k,m_{0},m_{1},...,m_{k}\,\!}$ a ordinály ${\displaystyle \beta _{0}>\beta _{1}>\beta _{2}>...>\beta _{k}\,\!}$ takové, že platí:
${\displaystyle \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 ${\displaystyle \,\alpha }$ v Cantorově normálním tvaru platí ${\displaystyle \alpha \geq \beta _{0}}$, přičemž rovnost nastává právě tehdy, když ${\displaystyle \,\alpha =\omega ^{\alpha }}$. Takových ${\displaystyle \,\alpha }$ existuje dokonce vlastní třída, nejmenší z nich se nazývá ${\displaystyle \varepsilon _{0}}$. Pro ${\displaystyle \,\alpha <\varepsilon _{0}}$ tedy je ${\displaystyle \,\alpha >\beta _{0}}$, což umožňuje často používanou metodu dokazování – takzvanou indukci do epsilon nula.

Související články

• Ordinální číslo
• Kardinální číslo
• Kardinální aritmetika
• Goodsteinova posloupnost
• Transfinitní indukce
• Transfinitní rekurze