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.

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.

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

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

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

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

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

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

${\displaystyle x\in A}$ i ${\displaystyle y\in B.}$

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

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

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

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

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

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

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

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

${\displaystyle \alpha +0=\alpha ,}$

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

${\displaystyle \alpha +(\beta +1)=(\alpha +\beta )+1,}$

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

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

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

${\displaystyle \alpha \cdot 0=0,}$

${\displaystyle \alpha \cdot (\beta +1)=\alpha \cdot \beta +\alpha ,}$

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

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

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

${\displaystyle \alpha ^{0}=1,}$

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

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

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

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 ${\displaystyle \alpha ,\beta ,\gamma }$ prawdziwe są następujące równości:

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

Przypomnijmy, że ${\displaystyle \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:

${\displaystyle 888+\omega =\omega <\omega +888}$ oraz ${\displaystyle 888\cdot \omega =\omega <\omega \cdot 888}$

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

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

• ${\displaystyle (\omega +\omega )\cdot \omega =\omega \cdot \omega ,}$
• ${\displaystyle (\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},}$
• ${\displaystyle 2^{\omega }=\lim \limits _{n<\omega }2^{n}=\omega ,}$

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

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

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

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

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

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

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

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

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

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

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

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

W 1906 roku niemiecki matematyk Gerhard Hessenberg^[1] 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 ${\displaystyle \omega .}$

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

${\displaystyle \alpha =\omega ^{\xi _{1}}\cdot m_{1}+\omega ^{\xi _{2}}\cdot m_{2}+\ldots +\omega ^{\xi _{n}}\cdot m_{n}}$ oraz ${\displaystyle \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ą ${\displaystyle \alpha (+)\beta }$ przez

${\displaystyle \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 ${\displaystyle \alpha \odot \beta }$ jest trochę bardziej skomplikowana: traktujemy wyrażenia ${\displaystyle \omega ^{\xi _{1}}\cdot m_{1}+\omega ^{\xi _{2}}\cdot m_{2}+\ldots +\omega ^{\xi _{n}}\cdot m_{n}}$ i ${\displaystyle \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 ${\displaystyle 1\leqslant i,j\leqslant n}$ rozważamy liczbę ${\displaystyle \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 ${\displaystyle \alpha \odot \beta }$ jest zdefiniowany jako suma (w sensie +) wszystkich wyrażeń postaci ${\displaystyle \omega ^{\xi _{i}\oplus \xi _{j}}\cdot m_{i}\cdot k_{j}}$ uporządkowanych tak, że wykładniki maleją.

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

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

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

W roku 1954 G.H. Toulmin udowodnił^[2], że jeżeli ${\displaystyle X}$ i ${\displaystyle Y}$ są przestrzeniami regularnymi, to

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

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

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

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

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