Arytmetyka liczb porządkowych

Arytmetyka liczb porządkowych – dział teorii mnogości zajmujący się liczbami porządkowymi i działaniami na nich.

Arytmetyka liczb porządkowych znacznie różni się od arytmetyki liczb kardynalnych – zarówno rozważane działania mają inne własności, jak i stawiane pytania są inne. Podstawową różnicą jest jednak fakt, że większość stwierdzeń dotyczących działań na liczbach porządkowych jest dowodliwa na gruncie aksjomatyki Zermela-Fraenkla (zwykle aksjomat wyboru nie jest potrzebny, choć tutaj, zgodnie z tradycją przyjętą w matematyce, zakłada się ZFC). Ponadto bardzo rzadko spotyka się w niej wyniki niezależnościowe.

Arytmetyka liczb porządkowych kardynalnych różni się także od arytmetyki liczb rzeczywistych, choć można dostrzec między nimi pewne analogie.

Definicje

Na liczbach porządkowych rozważa się następujące działania dwuargumentowe: dodawanie, mnożenie i potęgowanie liczb porządkowych. Operacje dodawania i mnożenia można zdefiniować na dwa sposoby (dające ten sam wynik); poniżej przedstawiono oba podejścia.

Dodawanie i mnożenie: definicje konstrukcyjne

Operacje „+” i „·” na liczbach porządkowych można wprowadzić przez pewne konstrukcje zbiorów dobrze uporządkowanych.

Przypuśćmy, że $\mathbf {A} =(A,\leqslant _{A})$ oraz $\mathbf {B} =(B,\leqslant _{B})$ są dobrymi porządkami. Dla uproszczenia opisu załóżmy też, że zbiory $A$ i $B$ są rozłączne. Określamy:

• $\mathbf {A} +\mathbf {B} =(A\cup B,\sqsubseteq ^{+}),$ gdzie $\sqsubseteq ^{+}$ jest relacją binarną na $A\cup B$ zdefiniowaną przez

$x\sqsubseteq ^{+}y$ wtedy i tylko wtedy, gdy $(x,y\in A\cup B)$ oraz

$x,y\in A$ i $x\leqslant _{A}y\;{}$ lub

$x,y\in B$ i $x\leqslant _{B}y\;{}$ lub

$x\in A$ i $y\in B.$

• $\mathbf {A} \cdot {\mathbf {B} }=(A\times B,\sqsubseteq ^{\circ }),$ gdzie $\sqsubseteq ^{\circ }$ jest relacją binarną na produkcie $A\times B$ zdefiniowaną przez

$(a_{1},b_{1})\sqsubseteq ^{\circ }(a_{2},b_{2})$ wtedy i tylko wtedy, gdy ($a_{1},a_{2}\in A,$ $b_{1},b_{1}\in B$) oraz

$b_{1}<_{B}b_{2}\;{}$ lub

$b_{1}=b_{2}$ i $a_{1}\leqslant _{A}a_{2}.$

Można wykazać, że zarówno $\mathbf {A} +\mathbf {B} ,$ jak i $\mathbf {A} \cdot \mathbf {B}$ są dobrymi porządkami.

Liczba porządkowa $\omega \cdot \omega {:}$ każda kreska pionowa przedstawia liczbę porządkową poniżej $\omega \cdot \omega$ – kreski te odpowiadają liczbom postaci $\omega \cdot m+n$ gdzie $m$ i $n$ są liczbami naturalnymi.

Dla liczb porządkowych $\alpha ,\beta$ określamy

• sumę $\alpha +\beta$ jako (jedyną) liczbę porządkową izomorficzną ze zbiorem dobrze uporządkowanym $\mathbf {A} +\mathbf {B} ,$ gdzie $\mathbf {A} ,\mathbf {B}$ są rozłącznymi kopiami $\alpha$ i $\beta ,$ odpowiednio;
• iloczyn $\alpha \cdot \beta$ jako (jedyną) liczbę porządkową izomorficzną ze zbiorem dobrze uporządkowanym $\mathbf {A} \cdot \mathbf {B} ,$ gdzie $\mathbf {A} ,\mathbf {B}$ są kopiami $\alpha$ i $\beta ,$ odpowiednio.

Definicje indukcyjne

• Dodawanie: przez indukcję po liczbach porządkowych $\beta ,$ dla każdej liczby porządkowej $\alpha ,$ definiujemy $\alpha +\beta$ w sposób następujący:

$\alpha +0=\alpha ,$

$\alpha +1=\alpha \cup \{\alpha \}$ jest następnikiem porządkowym liczby $\alpha ,$

$\alpha +(\beta +1)=(\alpha +\beta )+1,$

jeśli $\beta$ jest liczbą graniczną, to

$\alpha +\beta =\lim \limits _{\gamma <\beta }(\alpha +\gamma ).$

• Mnożenie: przez indukcję po liczbach porządkowych $\beta ,$ dla każdej liczby porządkowej $\alpha ,$ definiujemy $\alpha \cdot \beta$ w sposób następujący:

$\alpha \cdot 0=0,$

$\alpha \cdot (\beta +1)=\alpha \cdot \beta +\alpha ,$

jeśli $\beta$ jest liczbą graniczną, to

$\alpha \cdot \beta =\lim \limits _{\gamma <\beta }(\alpha \cdot \gamma ).$

• Potęgowanie: przez indukcję po liczbach porządkowych $\beta ,$ dla każdej liczby porządkowej $\alpha ,$ definiujemy $\alpha ^{\beta }$ w sposób następujący:

$\alpha ^{0}=1,$

$\alpha ^{\beta +1}=\alpha ^{\beta }\cdot \alpha ,$

jeśli $\beta$ jest liczbą graniczną, to

$\alpha ^{\beta }=\lim \limits _{\gamma <\beta }\alpha ^{\gamma }.$

Podstawowe własności

Pewne własności „zwykłych” działań na liczbach rzeczywistych są prawdziwe dla działań na liczbach porządkowych, ale wiele nie. Dla dowolnych liczb porządkowych $\alpha ,\beta ,\gamma$ prawdziwe są następujące równości:

• $(\alpha +\beta )+\gamma =\alpha +(\beta +\gamma )$ oraz $(\alpha \cdot \beta )\cdot \gamma =\alpha \cdot (\beta \cdot \gamma ),$
• $\alpha +0=0+\alpha =\alpha ,$ $\alpha \cdot 0=0\cdot \alpha =0$ oraz $\alpha \cdot 1=1\cdot \alpha =\alpha ,$
• $\alpha \cdot (\beta +\gamma )=(\alpha \cdot \beta )+(\alpha \cdot \gamma ),$
• $\gamma ^{\alpha +\beta }=\gamma ^{\alpha }\cdot \gamma ^{\beta }$ oraz $(\beta ^{\alpha })^{\gamma }=\beta ^{\alpha \cdot \gamma },$
• $\alpha ^{0}=1$ oraz $\alpha \neq 0\implies 0^{\alpha }=0,$
• $\alpha ^{1}=\alpha$ oraz $1^{\alpha }=1.$

Przykłady

Przypomnijmy, że $\omega =\{0,1,2,3,\dots \}$ jest pierwszą nieskończoną liczbą porządkową.

• Ani dodawanie, ani mnożenie liczb porządkowych nie są przemienne, gdyż na przykład:

$888+\omega =\omega <\omega +888$ oraz $888\cdot \omega =\omega <\omega \cdot 888$

• Prawostronna rozdzielność mnożenia względem dodawania na ogół nie zachodzi:

$(\omega +888)\cdot 2=(\omega +888)+(\omega +888)=\omega +\omega +888,$ ale $\omega \cdot 2+888\cdot 2=\omega +\omega +1776\neq \omega +\omega +888,$

• $(\omega +\omega )\cdot \omega =\omega \cdot \omega ,$
• $(\omega \cdot 2)^{2}=(\omega +\omega )\cdot (\omega +\omega )=\omega \cdot \omega +\omega \cdot \omega <\omega \cdot \omega +\omega \cdot \omega +\omega \cdot \omega +\omega \cdot \omega =\omega \cdot \omega \cdot 4=\omega ^{2}\cdot 2^{2},$
• $2^{\omega }=\lim \limits _{n<\omega }2^{n}=\omega ,$

Więcej własności

• Niech $\alpha ,\beta$ będą liczbami porządkowymi, $\alpha >0.$ Wówczas liczba $\beta$ ma jednoznaczne przedstawienie postaci

$\beta =\alpha \cdot \gamma +\delta$ gdzie $\gamma ,\delta$ są liczbami porządkowymi i $0\leqslant \delta <\alpha .$

• Twierdzenie Cantora o postaci normalnej: Każda niezerowa liczba porządkowa $\alpha >0$ może być przedstawiona jednoznacznie w postaci

$\alpha =\omega ^{\beta _{1}}\cdot m_{1}+\omega ^{\beta _{2}}\cdot m_{2}+\ldots +\omega ^{\beta _{n}}\cdot m_{n}$

dla pewnych liczb naturalnych $n\geqslant 1$ oraz $m_{1},\dots ,m_{n}>0$ oraz liczb porządkowych $\beta _{1},\dots ,\beta _{n}$ spełniających warunek $\beta _{n}<\beta _{n-1}<\ldots <\beta _{1}\leqslant \alpha .$

• Liczby porządkowe α dla których zachodzi równość $\omega ^{\alpha }=\alpha$ były nazwane przez Cantora liczbami epsilonowymi; tworzą one klasę właściwą. Najmniejszą liczbą epsilonową jest

$\varepsilon _{0}=\sup\{\omega ^{\omega },\omega ^{\omega ^{\omega }},\omega ^{\omega ^{\omega ^{\omega }}},\dots \}.$

• Jeśli $\varepsilon$ jest liczbą epsilonową, to

(a) $\beta +\varepsilon =\varepsilon$ dla każdej liczby $\beta <\varepsilon ,$

(b) $\beta \cdot \varepsilon =\varepsilon$ dla każdej liczby $1\leqslant \beta <\varepsilon ,$

(c) $\beta ^{\varepsilon }=\varepsilon$ dla każdej liczby $2\leqslant \beta <\varepsilon .$

Zastosowania

• Dowód twierdzenia Goodsteina używa cantorowskiej postaci normalnej dla liczb porządkowych mniejszych niż $\varepsilon _{0}.$

Operacje naturalne

W 1906 roku niemiecki matematyk Gerhard Hessenberg wprowadził dwie dodatkowe operacje na liczbach porządkowych: naturalną sumę i naturalny produkt. Czasami operacje te są nazywane sumą Hessenberga i produktem Hessenberga, odpowiednio. Są one zdefiniowane w taki sposób, że przedstawiamy dane liczby porządkowe w postaci normalnej Cantora i działania wykonujemy, traktując te rozwinięcia jak formalne wielomiany zmiennej $\omega .$

Niech $\alpha$ i $\beta$ będą liczbami porządkowymi. Na mocy twierdzenia Cantora o postaci normalnej możemy znaleźć liczby naturalne $n\geqslant 1$ oraz $m_{1},\dots ,m_{n},k_{1},\dots ,k_{n}$ oraz liczby porządkowe $\xi _{n}<\xi _{n-1}<\ldots <\xi _{1}$ takie, że

$\alpha =\omega ^{\xi _{1}}\cdot m_{1}+\omega ^{\xi _{2}}\cdot m_{2}+\ldots +\omega ^{\xi _{n}}\cdot m_{n}$ oraz $\beta =\omega ^{\xi _{1}}\cdot k_{1}+\omega ^{\xi _{2}}\cdot k_{2}+\ldots +\omega ^{\xi _{n}}\cdot k_{n}.$

Określamy teraz sumę naturalną $\alpha (+)\beta$ przez

$\alpha \oplus \beta =\omega ^{\xi _{1}}\cdot (k_{1}+m_{1})+\omega ^{\xi _{2}}\cdot (k_{2}+m_{2})+\ldots +\omega ^{\xi _{n}}\cdot (k_{n}+m_{n}).$

Definicja produktu naturalnego $\alpha \odot \beta$ jest trochę bardziej skomplikowana: traktujemy wyrażenia $\omega ^{\xi _{1}}\cdot m_{1}+\omega ^{\xi _{2}}\cdot m_{2}+\ldots +\omega ^{\xi _{n}}\cdot m_{n}$ i $\omega ^{\xi _{1}}\cdot k_{1}+\omega ^{\xi _{2}}\cdot k_{2}+\ldots +\omega ^{\xi _{n}}\cdot k_{n}$ jakby przedstawiały wielomiany zmiennej ω. Dla każdej pary liczb naturalnych $1\leqslant i,j\leqslant n$ rozważamy liczbę $\omega ^{\xi _{i}\oplus \xi _{j}}\cdot m_{i}\cdot k_{j}$ (zwróćmy uwagę, że w wykładniku potęgi mamy operację sumy naturalnej). Produkt naturalny $\alpha \odot \beta$ jest zdefiniowany jako suma (w sensie +) wszystkich wyrażeń postaci $\omega ^{\xi _{i}\oplus \xi _{j}}\cdot m_{i}\cdot k_{j}$ uporządkowanych tak, że wykładniki maleją.

Obie operacje, $\oplus$ i $\odot ,$ są przemienne i łączne. Zauważmy, że

$(\omega +1)+(\omega +1)=\omega \cdot 2+1,$ ale $(\omega +1)\oplus (\omega +1)=\omega \cdot 2+2,$ oraz

$(\omega +1)\cdot (\omega +1)=\omega ^{2}+\omega +1,$ ale $(\omega +1)\odot (\omega +1)=\omega ^{2}+\omega \cdot 2+1.$

Przykład zastosowania

W roku 1954 G.H. Toulmin udowodnił, że jeżeli $X$ i $Y$ są przestrzeniami regularnymi, to

$\operatorname {ind} X\times Y\leqslant (\operatorname {ind} X\oplus \operatorname {ind} Y)+n,$

gdzie ind oznacza mały wymiar induktywny oraz $n$ jest liczbą naturalną zależną od wymiarów przestrzeni $X$ i $Y.$ Gary Brookfield udowodnił, że jeżeli $R$ jest pierścieniem noetherowskim, to

$\operatorname {len} R[x]=\omega \odot \operatorname {len} R,$

gdzie len jest liczbą porządkową mierzącą długość ideałową pierścienia $R,$ w pewnym sensie dokładniej niż wymiar Krulla (pojęcie to wprowadził Gulliksen).

Bibliografia

• Wacław Sierpiński: Cardinal and ordinal numbers. Wydanie 2. Monografie Matematyczne, tom 34. Państwowe Wydawnictwo Naukowe, Warszawa 1965.