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 =\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 =\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,\dots \}$ 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 ${\mathrm{\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

Šablona:Upravit 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

$(\mathrm{\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\ne 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$
• Pro každé dva ordinály $\alpha ,\beta ,\beta >0$ existují ${\gamma }_1\le \alpha ,{\gamma }_2<\beta$ takové, že $\alpha =\beta .{\gamma }_1+{\gamma }_2$(obdoba zbytku po dělení na přirozených číslech:)

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. ${\alpha }^0=1$
2. ${\alpha }^{\beta +1}={\alpha }^{\beta }.\alpha$
3. 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 \ge {\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á ${\epsilon }_0$. Pro $\alpha <{\epsilon }_0$ tedy je $\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