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 ( { 0 } × α ) ∪ ( { 1 } × β ) {\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:
( { 0 } × 3 ) ∪ ( { 1 } × 2 ) = {\displaystyle (\{0\}\times 3)\cup (\{1\}\times 2)=}
( { 0 } × { 0 , 1 , 2 } ) ∪ ( { 1 } × { 0 , 1 } ) = {\displaystyle (\{0\}\times \{0,1,2\})\cup (\{1\}\times \{0,1\})=}
{ [ 0 , 0 ] , [ 0 , 1 ] , [ 0 , 2 ] } ∪ { [ 1 , 0 ] , [ 1 , 1 ] } = {\displaystyle \{[0,0],[0,1],[0,2]\}\cup \{[1,0],[1,1]\}=}
{ [ 0 , 0 ] , [ 0 , 1 ] , [ 0 , 2 ] , [ 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 1 + ω 0 {\displaystyle 1+\omega _{0}\,\!} (jako ω 0 {\displaystyle \omega _{0}\,\!} se značí množina všech přirozených čísel)
( { 0 } × 1 ) ∪ ( { 1 } × ω 0 ) = {\displaystyle (\{0\}\times 1)\cup (\{1\}\times \omega _{0})=}
( { 0 } × { 0 } ) ∪ ( { 1 } × { 0 , 1 , 2 , 3 , . . . } ) = {\displaystyle (\{0\}\times \{0\})\cup (\{1\}\times \{0,1,2,3,...\})=}
{ [ 0 , 0 ] } ∪ { [ 1 , 0 ] , [ 1 , 1 ] , [ 1 , 2 ] , [ 1 , 3 ] , . . . } = {\displaystyle \{[0,0]\}\cup \{[1,0],[1,1],[1,2],[1,3],...\}=}
{ [ 0 , 0 ] , [ 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 ω 0 {\displaystyle \omega _{0}\,\!} , takže 1 + ω 0 = ω 0 {\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 ω 0 + 1 {\displaystyle \omega _{0}+1\,\!} . Dojde k překvapivému zjištění:
1 + ω 0 = ω 0 < ω 0 + 1 {\displaystyle 1+\omega _{0}=\omega _{0}<\omega _{0}+1\,\!}

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

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

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

Rozhodně opět 2. ω 0 < ω 0 .2 {\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: ( 1 + 1 ) . ω 0 = 2. ω 0 ≠ 1. ω 0 + 1. ω 0 = ω 0 .2 {\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):

  • α + 0 = 0 + α = α {\displaystyle \alpha +0=0+\alpha =\alpha \,\!}
  • α .0 = 0. α = 0 {\displaystyle \alpha .0=0.\alpha =0\,\!}
  • α .1 = 1. α = α {\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 α , β , β > 0 {\displaystyle \alpha ,\beta ,\beta >0\,\!} existují γ 1 ≤ α , γ 2 < β {\displaystyle \gamma _{1}\leq \alpha ,\gamma _{2}<\beta \,\!} takové, že
α = β . γ 1 + γ 2 {\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. α 0 = 1 {\displaystyle \alpha ^{0}=1\,\!}
  2. α β + 1 = α β . α {\displaystyle \alpha ^{\beta +1}=\alpha ^{\beta }.\alpha \,\!}
  3. pro limitní ordinál β {\displaystyle \beta \,\!} je α β = s u p { α γ : 0 < γ < β } {\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:

  • 0 0 = 1 {\displaystyle 0^{0}=1\,\!}
  • 0 α = 0 {\displaystyle 0^{\alpha }=0\,\!} pro α > 0 {\displaystyle \alpha >0\,\!}
  • 1 α = 1 {\displaystyle 1^{\alpha }=1\,\!}
  • α 1 = α {\displaystyle \alpha ^{1}=\alpha \,\!}
  • α 2 = α . α {\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 ω 0 {\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 ω = ω 0 {\displaystyle \omega =\omega _{0}\,\!} množina přirozených čísel a α {\displaystyle \alpha \,\!} libovolný ordinál, pak existují jednoznačně daná přirozená čísla k , m 0 , m 1 , . . . , m k {\displaystyle k,m_{0},m_{1},...,m_{k}\,\!} a ordinály β 0 > β 1 > β 2 > . . . > β k {\displaystyle \beta _{0}>\beta _{1}>\beta _{2}>...>\beta _{k}\,\!} takové, že platí:
α = ω β 0 . m 0 + ω β 1 . m 1 + . . . + ω β k . m k {\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í α ≥ β 0 {\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á ε 0 {\displaystyle \varepsilon _{0}} . Pro α < ε 0 {\displaystyle \,\alpha <\varepsilon _{0}} tedy je α > β 0 {\displaystyle \,\alpha >\beta _{0}} , což umožňuje často používanou metodu dokazování – takzvanou indukci do epsilon nula.

Související články