Arytmetyka liczb porządkowych

Z Wikipedii

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 w ZF (zwykle aksjomat wyboru nie jest potrzebny, choć my zgodnie z tradycją przyjętą w matematyce zakładamy ZFC). Ponadto bardzo rzadko spotyka się tu 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.

Spis treści

1 Definicje
- 1.1 Dodawanie i mnożenie: definicje konstrukcyjne
- 1.2 Definicje indukcyjne
2 Podstawowe własności
3 Przykłady
4 Więcej własności
5 Zastosowania
6 Operacje naturalne
7 Dalsza lektura
8 Bibliografia
9 Zobacz też

[edytuj] 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 przedstawimy oba podejścia.

[edytuj] 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 ${\bold A}=(A,\leq_A)$ oraz ${\bold B}=(B,\leq_B)$ są dobrymi porządkami. Dla uproszczenia opisu załóżmy też, że zbiory A i B są rozłączne. Określamy:

${\bold A}+{\bold 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\leq_A y$ , lub

$x,y\in B$ i $x\leq_B y$ , lub

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

${\bold A}\cdot{\bold 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\leq_A a_2$ .

Łatwo można sprawdzić, że zarówno ${\bold A}+{\bold B}$ jak i ${\bold A}\cdot{\bold B}$ są dobrymi porządkami.

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

Dla liczb porządkowych $α,β$ określamy

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

[edytuj] Definicje indukcyjne

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

α + 0 = α

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

α

α + (β + 1) = (α + β) + 1

jeśli

β

jest liczbą graniczną, to $\alpha+\beta=\lim\limits_{\gamma<\beta}(\alpha+\gamma)$ .

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

$\alpha\cdot 0=0$ ,

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

jeśli

β

jest liczbą graniczną, to $\alpha\cdot\beta=\lim\limits_{\gamma<\beta}(\alpha\cdot\gamma)$ .

Potęgowanie: przez indukcję po liczbach porządkowych $β$ , dla każdej liczby porządkowej $α$ , definiujemy $α β$ w sposób następujący:

α 0 = 1

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

jeśli

β

jest liczbą graniczną, to $\alpha^\beta=\lim\limits_{\gamma<\beta}\alpha^\gamma$ .

[edytuj] 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 $α,β,γ$ prawdziwe są następujące równości:

$(α + β) + γ = α + (β + γ)$ oraz $(\alpha \cdot \beta) \cdot \gamma = \alpha \cdot (\beta \cdot \gamma)$ ,
$α + 0 = 0 + α = α$ , $\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}$ ,
$α 0 = 1$ oraz $\alpha \not = 0 \implies 0^\alpha = 0$ ,
$α 1 = α$ oraz $1 α = 1$ .

[edytuj] Przykłady

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

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

(czyli ani dodawanie ani mnożenie liczb porządkowych nie są przemienne),

$(\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$

(czyli prawostronna rozdzielność mnożenia względem dodawania nie jest spełniona dla działań na liczbach porządkowych),

$(\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$ ,

[edytuj] Więcej własności

Niech α,β będą liczbami porządkowymi, $α > 0$ . Wówczas liczba β ma jednoznaczne przedstawienie postaci

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

Twierdzenie Cantora o postaci normalnej: Każda niezerowa liczba porządkowa $α > 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\geq 1$ oraz $m_1,\ldots,m_n>0$ oraz liczb porządkowych $\beta_1,\ldots,\beta_n$ spełniających warunek $\beta_n<\beta_{n-1}<\ldots<\beta_1\leq\alpha$ .

Liczby porządkowe α dla których zachodzi równość $ω α = α$ były nazwane przez Cantora epsilon-liczbami. Pierwszą epsilon-liczbą jest $\varepsilon_0=\lim\limits_{n<\omega}\alpha_n$ , gdzie $α 1 = ω,α 2 = ω ω$ i $\alpha_{n+1}=\omega^{\alpha_n}$ . Epsilon-liczby tworzą klasę właściwą.
Jeśli α jest epsilon-liczbą, to

(a)

β + α = α

dla każdej liczby

β < α

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

(c)

β α = α

dla każdej liczby $2\leq\beta<\alpha$ .

[edytuj] Zastosowania

Dowód twierdzenia Goodsteina używa Cantorowskiej postaci normalnej dla liczb porządkowych mniejszych niż ε₀.

[edytuj] Operacje naturalne

W 1906, 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 jakby były formalnymi wielomianami zmiennej ω.

Niech α i β będą liczbami porządkowymi. Na mocy twierdzenia Cantora o postaci normalnej możemy znaleźć liczby naturalne $n\geq 1$ oraz $m_1,\ldots,m_n,k_1,\ldots,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ą $α( + )β$ przez

$\alpha(+)\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(\cdot)\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\leq i,j\leq n$ rozważamy liczbę $\omega^{\xi_i(+)\xi_j}\cdot m_i\cdot k_j$ (zwróćmy uwagę że w wykładniku potęgi mamy operację sumy naturalnej). Produkt naturalny $\alpha(\cdot)\beta$ jest zdefiniowany jako suma (w sensie +) wszystkich wyrażeń postaci $\omega^{\xi_i(+)\xi_j}\cdot m_i\cdot k_j$ uporządkowanych tak, że wykładniki maleją.