Cesko.wiki Ordinální aritmetika
Author
Albert FloresOrdiná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 \alpha \,\. a \beta \,\. +more 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í \isin 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 \,\. +more 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
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 .
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. +more 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 . +more 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 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} . +more \alpha \,\. # pro limitní ordinál \beta \,\. je \alpha^{\beta} = sup \{ \alpha^{\gamma} : 0 - sup v tomto výrazu znamená supremum dané množiny k uspořádání ordinálních čísel relací \isin.
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 \,\. +more 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. +more Pro \,\alpha tedy je \,\alpha>\beta_0, což umožňuje často používanou metodu dokazování - takzvanou indukci do epsilon nula.