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 editovat

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 editovat

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 editovat

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 editovat

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 editovat

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 editovat

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 editovat

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 editovat

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.