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.

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^[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 $\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ł^[2], ż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ł^[3], ż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^[4]).

Przypisy

↑ Hessenberg G.: Grundbegriffe der Mengenlehre, Göttingen: Vandenhoeck & Ruprecht, 1906.
↑ Toulmin G.H., Shuffling ordinals and transfinite dimension, Proc. London Math. Soc., 4 (1954), s. 177–195.
↑ Brookfield G., The Length of Noetherian Polynomial Rings. Communications in Algebra, 1532-4125, (31), Issue 11, 2003, s. 5591–5607. [1].
↑ Gulliksen T.H., A Theory of Length for Noetherian Modules, J. of Pure and Appl., Algebra 1973, 3, s. 159–170.

Bibliografia

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

[1] Hessenberg G.: Grundbegriffe der Mengenlehre, Göttingen: Vandenhoeck & Ruprecht, 1906.

[2] Toulmin G.H., Shuffling ordinals and transfinite dimension, Proc. London Math. Soc., 4 (1954), s. 177–195.

[3] Brookfield G., The Length of Noetherian Polynomial Rings. Communications in Algebra, 1532-4125, (31), Issue 11, 2003, s. 5591–5607. [1].

[4] Gulliksen T.H., A Theory of Length for Noetherian Modules, J. of Pure and Appl., Algebra 1973, 3, s. 159–170.

[1]

[2]

[3]

[4]

logika matematyczna	algebraiczna mereologia rachunek zdań teoria dowodu teoria modeli teoria rekursji teoria typów
metamatematyka	metalogika
teoria mnogości	opisowa algebra zbiorów arytmetyka liczb kardynalnych arytmetyka liczb porządkowych teoria PCF
teoria obliczeń	teoria obliczalności teoria złożoności
inne	teoria kategorii filozofia matematyki

główne	elementarna teoretyczna lub wyższa, in. teoria liczb algebraiczna algorytmiczna analityczna elementarna geometryczna teoria sit
dyscypliny z arytmetyką w nazwie	arytmetyka liczb kardynalnych arytmetyka liczb porządkowych arytmetyka modularna geometria arytmetyczna

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Eisspeedway

Arytmetyka liczb porządkowych

Definicje

Dodawanie i mnożenie: definicje konstrukcyjne

Definicje indukcyjne

Podstawowe własności

Przykłady

Więcej własności

Zastosowania

Operacje naturalne

Przykład zastosowania

Przypisy

Bibliografia