Ordinale Arithmetik - Ordinal arithmetic

Im mathematischen Bereich der Mengenlehre , Ordnungs Arithmetik beschreibt die drei üblichen Operationen auf Ordnungszahl : Addition , Multiplikation und Potenzierung . Jede kann im Wesentlichen auf zwei verschiedene Arten definiert werden: entweder durch Konstruieren einer expliziten wohlgeordneten Menge , die das Ergebnis der Operation darstellt, oder durch Verwendung der transfiniten Rekursion . Die Cantor-Normalform bietet eine standardisierte Schreibweise für Ordnungszahlen. Neben diesen üblichen Ordinaloperationen gibt es noch die "natürliche" Arithmetik der Ordinalzahlen und die Zahlenoperationen .

Zusatz

Die Vereinigung zweier disjunkter wohlgeordneter Mengen S und T kann wohlgeordnet sein. Der Ordnungstyp dieser Vereinigung ist die Ordinalzahl, die sich aus der Addition der Ordnungstypen von S und T ergibt . Wenn zwei wohlgeordnete Mengen nicht bereits disjunkt sind, können sie durch ordnungsisomorphe disjunkte Mengen ersetzt werden, zB ersetze S durch {0} × S und T durch {1} × T . Auf diese Weise, die gut geordneten Menge S geschrieben wird „links“ der wohlgeordneten Menge T , definiert man einen Auftrag zu Bedeutung S T , in dem jedes Element von S kleiner ist als jedes Element ist , T . Die Sets S und T selbst behalten die Reihenfolge bei, die sie bereits haben. Diese Addition der Ordnungstypen ist assoziativ und verallgemeinert die Addition natürlicher Zahlen . ${\displaystyle \cup}$

Die erste transfinite Ordinalzahl ist ω, die Menge aller natürlichen Zahlen. Zum Beispiel erhält man die Ordinalzahl ω + ω durch zwei in üblicher Weise geordnete Kopien der natürlichen Zahlen und die zweite Kopie ganz rechts von der ersten. Wenn man 0' < 1' < 2' < ... für die zweite Kopie schreibt, sieht ω + ω aus wie

0 < 1 < 2 < 3 < ... < 0' < 1' < 2' < ...

Dies unterscheidet sich von , da in ω nur 0 keinen direkten Vorgänger hat, während in ω + ω die beiden Elemente 0 und 0' keine direkten Vorgänger haben. Als weiteres Beispiel hier 3 + ω und ω + 3:

0 < 1 < 2 < 0' < 1' < 2' < ...

0 < 1 < 2 < ... < 0' < 1' < 2'

Nach der Umbenennung sieht ersteres nur wie ω selbst aus, dh 3 + ω = ω, während letzteres nicht: ω + 3 ist ungleich ω, da ω + 3 ein größtes Element (nämlich 2') hat und ω nicht (auch wenn ω und ω + 3 sind gleich stark , sie sind nicht isomorph). Daher ist diese Addition nicht kommutativ . Tatsächlich ist es ziemlich selten, dass α + β gleich β + α ist : Dies passiert genau dann, wenn α = γm , β = γn für eine Ordnungszahl γ und natürliche Zahlen m und n ist . Daraus folgt, dass " α kommutiert mit β " eine Äquivalenzrelation auf der Klasse der von Null verschiedenen Ordinalzahlen ist und alle Äquivalenzklassen abzählbar unendlich sind.

Die Addition ist jedoch immer noch assoziativ; man sieht zum Beispiel, dass (ω + 4) + ω = ω + (4 + ω) = ω + ω.

Die Definition der Addition kann auch induktiv angegeben werden (die folgende Induktion erfolgt auf β ):

• α + 0 = α ,
• α + ( β + 1) = ( α + β ) + 1 (hier bezeichnet "+1" den Nachfolger einer Ordinalzahl),
• und wenn β eine Grenzordinalzahl ist, dann ist α + β der Grenzwert von α + δ für alle δ < β .

Mit dieser Definition kann ω + 3 als Nachfolger-Ordinalzahl angesehen werden (es ist der Nachfolger von ω + 2), während 3 + ω eine Grenzordinal ist , nämlich der Grenzwert von 3 + 0 = 3, 3 + 1 = 4, 3 + 2 = 5 usw., was nur ω ist.

Null ist eine additive Identität α + 0 = 0 + α = α .

Zusätzlich ist assoziativ ( α + β ) + γ = α + ( β + γ ).

Die Addition ist im richtigen Argument streng ansteigend und stetig:

${\displaystyle \alpha <\beta \Rightarrow \gamma +\alpha <\gamma +\beta}$

aber die analoge Beziehung gilt nicht für das linke Argument; stattdessen haben wir nur:

${\displaystyle \alpha <\beta \Rightarrow \alpha +\gamma \leq \beta +\gamma}$

Ordinale Addition ist linksaufhebend : wenn α + β = α + γ , dann β = γ . Darüber hinaus kann man definieren linke Subtraktion für ordinals β ≤ α : ein einzigartiges γ , so dass α = β + γ . Auf der anderen Seite funktioniert das Widerrufsrecht nicht:

${\displaystyle 3+\omega =0+\omega =\omega}$ aber ${\displaystyle 3\neq 0}$

Auch nicht rechte Subtraktion, selbst dann , wenn & bgr; ≤ & agr; : Es gibt beispielsweise keines existiert γ , so dass γ + 42 = ω.

Wenn die Ordinalzahlen kleiner als α unter Addition abgeschlossen sind und 0 enthalten, wird α gelegentlich als γ-Zahl bezeichnet (siehe additiv unzerlegbare Ordinalzahlen ). Dies sind genau die Ordinalzahlen der Form ω ^β .

Multiplikation

Das kartesische Produkt , S × T von zwei wohlgeordnete Mengen S und T wird durch eine Variante der gut geordneten lexikographischer Reihenfolge Das setzt die niedrigstwertige Position zuerst. Effektiv wird jedes Element von T durch eine disjunkte Kopie von S ersetzt . Der Ordnungstyp des kartesischen Produkts ist die Ordinalzahl, die sich aus der Multiplikation der Ordnungstypen von S und T ergibt . Auch diese Operation ist assoziativ und verallgemeinert die Multiplikation natürlicher Zahlen.

Hier ist ω·2:

0 ₀ < 1 ₀ < 2 ₀ < 3 ₀ < ... < 0 ₁ < 1 ₁ < 2 ₁ < 3 ₁ < ...,

die den gleichen Auftragstyp wie ω + ω hat. Im Gegensatz dazu sieht 2·ω so aus:

0 ₀ < 1 ₀ < 0 ₁ < 1 ₁ < 0 ₂ < 1 ₂ < 0 ₃ < 1 ₃ < ...

und nach dem Umetikettieren sieht das genauso aus wie ω. Somit ist ω·2 = ω+ω ≠ ω = 2·ω, was zeigt, dass die Multiplikation von Ordinalzahlen nicht kommutativ ist. Allgemeiner gesagt, eine natürliche Zahl größer als 1 kommutiert niemals mit einer unendlichen Ordinalzahl, und zwei unendliche Ordinalzahlen α , β kommutieren genau dann, wenn α ^m = β ⁿ für einige positive natürliche Zahlen m und n ist . Die Relation " α kommutiert mit β " ist eine Äquivalenzrelation auf den Ordinalzahlen größer 1, und alle Äquivalenzklassen sind abzählbar unendlich.

Für die Ordinalarithmetik gilt teilweise die Distributivität : α ( β + γ ) = αβ + αγ . Das andere Distributivgesetz ( β + γ ) α = βα + γα gilt jedoch nicht allgemein: (1+1)·ω = 2·ω = ω während 1·ω+1·ω = ω+ω, was unterschiedlich ist . Daher bilden die Ordnungszahlen links in der Nähe von -Halbring , aber nicht eine Form Ring .

Die Definition der Multiplikation kann auch induktiv gegeben werden (die folgende Induktion erfolgt auf β ):

• α ·0 = 0,
• α ·( β +1) = ( α · β )+ α ,
• und wenn β ist ein Limesordinalzahl dann α · β ist die Grenze des α · δ für δ < β .

Die Haupteigenschaften des Produkts sind:

• α · 0 = 0 · α = 0.
• Eins (1) ist eine multiplikative Identität α ·1 = 1· α = α .
• Multiplikation assoziativ ( α · β ) · γ = α · ( β · γ ).
• Die Multiplikation ist streng steigend und im richtigen Argument stetig: ( α < β und γ > 0) γ · α < γ · β${\displaystyle \Rightarrow}$
• Die Multiplikation ist im linken Argument nicht streng steigend, zB 1 < 2, aber 1·ω = 2·ω = ω. Sie ist jedoch (nicht streng) steigend, dh α ≤ β α · γ ≤ β · γ .${\displaystyle \Rightarrow}$
• Es gibt ein linkes Aufhebungsgesetz : Wenn α > 0 und α · β = α · γ , dann gilt β = γ .
• Rechte Aufhebung funktioniert nicht, zB 1·ω = 2·ω = ω, aber 1 und 2 sind unterschiedlich.
• α · β = 0 α = 0 oder β = 0.${\displaystyle \Rightarrow}$
• Distributivgesetz links: α ·( β + γ ) = α · β + α · γ
• Rechts kein Verteilungsgesetz: zB (ω+1)·2 = ω+1+ω+1 = ω+ω+1 = ω·2+1, was nicht ω·2+2 ist.
• Left Division mit Rest : für alle α und β , wenn β > 0, dann ist es eindeutig sind γ und ö , so dass α = β · γ + δ und δ < β . (Dies bedeutet jedoch nicht, dass die Ordinalzahlen eine euklidische Domäne sind , da sie nicht einmal ein Ring sind und die euklidische "Norm" einen Ordinalwert hat.)
• Rechts Teilung nicht funktioniert: Es gibt keine α , so dass α · & le; ω ω ^ω & le; ( α + 1) · ω.

Eine δ-Zahl (siehe Multiplikativ unzerlegbar ) ist eine Ordinalzahl größer als 1, so dass αβ = β gilt, wenn 0< α < β . Diese bestehen aus der Ordnungszahl 2 und den Ordnungszahlen der Form ω ^{ω β} .

Potenzierung

Die Definition der ordinalen Exponentiation für endliche Exponenten ist einfach. Wenn der Exponent eine endliche Zahl ist, ist die Potenz das Ergebnis einer iterierten Multiplikation. Zum Beispiel ist ² = ω·ω unter Verwendung der Operation der ordinalen Multiplikation. Beachten Sie, dass ω·ω mit der Menge von Funktionen von 2 = {0,1} bis ω = {0,1,2,...} definiert werden kann, lexikographisch geordnet mit der niederwertigsten Stelle zuerst:

(0,0) < (1,0) < (2,0) < (3,0) < ... < (0,1) < (1,1) < (2,1) < (3,1 ) < ... < (0,2) < (1,2) < (2,2) < ...

Hier haben wir der Kürze halber die Funktion {(0, k ), (1, m )} durch das geordnete Paar ( k , m ) ersetzt.

In ähnlicher Weise für jedes finite Exponent n , kann aus der Verwendung der Satz von Funktionen definiert werden , n (der Domäne) zu den natürlichen Zahlen (die codomain). Diese Funktionen können als n- Tupel natürlicher Zahlen abgekürzt werden. ${\displaystyle \omega^{n}}$

Aber für unendliche Exponenten ist die Definition möglicherweise nicht offensichtlich. Eine Grenzordinalzahl wie ω ^ω ist das Supremum aller kleineren Ordinalzahlen. Es mag natürlich erscheinen, ω ^{ω unter} Verwendung der Menge aller unendlichen Folgen natürlicher Zahlen zu definieren. Wir stellen jedoch fest, dass jede absolut definierte Ordnung in diesem Set nicht wohlgeordnet ist. Um dieses Problem zu lösen, können wir wieder die Variante lexikographische Ordnung verwenden. Wir beschränken die Menge auf Folgen, die nur für eine endliche Anzahl von Argumenten von Null verschieden sind. Dies ist natürlich als Grenze der endlichen Potenzen der Basis motiviert (ähnlich dem Konzept des Koprodukts in der Algebra). Dies kann man sich auch als die unendliche Vereinigung vorstellen . ${\displaystyle \bigcup_{n<\omega}\omega^{n}}$

Jede dieser Sequenzen entspricht einer Ordnungszahl kleiner als solche und ist die höchste aller dieser kleineren Ordnungszahlen . ${\displaystyle \omega ^{\omega}}$${\displaystyle \omega^{n_{1}}c_{1}+\omega^{n_{2}}c_{2}+\cdots +\omega^{n_{k}}c_{k}}$${\displaystyle \omega ^{\omega}}$

Die lexikographische Ordnung in diesem Satz ist eine wohlgeordnete Ordnung, die der Ordnung von natürlichen Zahlen in Dezimalschreibweise ähnelt, außer mit umgekehrten Ziffernpositionen und mit willkürlichen natürlichen Zahlen anstelle nur der Ziffern 0–9:

(0,0,0,...) < (1,0,0,0,...) < (2,0,0,0,...) < ... <

(0,1,0,0,0,...) < (1,1,0,0,0,...) < (2,1,0,0,0,...) < .. . <

(0,2,0,0,0,...) < (1,2,0,0,0,...) < (2,2,0,0,0,...)

< ... <

(0,0,1,0,0,0,...) < (1,0,1,0,0,0,...) < (2,0,1,0,0,0,. ..)

< ...

Im Allgemeinen kann jede Ordinalzahl α auf die gleiche Weise mit einer anderen Ordinalzahl β potenziert werden, um α ^{β zu erhalten} .

Dies lässt sich am einfachsten mit der von Neumannschen Definition einer Ordinalzahl als Menge aller kleineren Ordinalzahlen erklären . Um dann eine Menge des Ordnungstyps α ^β zu konstruieren , betrachten wir alle Funktionen von β bis α, so dass nur eine endliche Anzahl von Elementen des Gebietes β auf ein von Null verschiedenes Element von α abbildet (im Wesentlichen betrachten wir die Funktionen mit endlicher Unterstützung ). Die Reihenfolge ist lexikografisch mit der niedrigstwertigen Position zuerst. Wir finden

• 1 ^ω = 1,
• 2 ^ω = ω,
• 2 ^ω+1 = ·2 = ω+ω.

Die Definition der Exponentiation kann auch induktiv gegeben werden (die folgende Induktion erfolgt auf β , dem Exponenten):

• α ⁰ = 1,
• α ^{β +1} = ( α ^β )· α , und
• wenn β eine Grenzordinalzahl ist, dann ist α ^β der Grenzwert von α ^δ für alle δ < β .

Eigenschaften der ordinalen Exponentiation:

• α ⁰ = 1.
• Wenn 0 < α , dann 0 ^α = 0.
• 1 ^α = 1.
• α ¹ = α .
• α ^β · α ^γ = α ^{β + γ} .
• ( & Agr; ^{& bgr;} ) ^γ = & agr; ^{& bgr; · γ} .
• Es gibt α , β und γ , für die ( α · β ) ^γ & ne; α ^γ · β ^γ . Zum Beispiel (ω·2) ² = ·2·ω·2 = ² ·2 ≠ ² ·4.
• Ordinale Exponentiation ist im richtigen Argument streng steigend und stetig: Wenn γ > 1 und α < β , dann ist γ ^α < γ ^β .
• Wenn α < β , dann ist α ^γ ≤ β ^γ . Beachten Sie zum Beispiel, dass 2 < 3 und dennoch 2 ^ω = 3 ^ω = ω ist.
• Wenn α > 1 und α ^β = α ^{γ ist} , dann ist β = γ . Bei α = 1 oder α = 0 ist dies nicht der Fall.
• Für alle α und β , wenn β > 1 und α > 0 , dann gibt es einzigartige γ , δ und ρ , so dass α = β ^γ · δ + ρ , so daß 0 < δ < β und ρ < β ^γ .

Während für ordinale Exponentiation und kardinale Exponentiation dieselbe Notation verwendet wird , unterscheidet sich die ordinale Exponentiation stark von der kardinalen Exponentiation. Zum Beispiel mit ordinaler Exponentiation , aber für ( Aleph nichts , die Kardinalität von ), . Hier ist die Kardinalität der Menge aller Funktionen von der Menge aller natürlichen Zahlen bis zu einer Menge mit zwei Elementen. (Dies ist die Kardinalität der Potenzmenge der Menge aller natürlichen Zahlen und ist gleich , der Kardinalität des Kontinuums .) Um eine Verwechslung von ordinaler Exponentiation mit kardinaler Exponentiation zu vermeiden, kann man Ordinalzeichen (zB ω) in ersterem verwenden und Symbole für Kardinäle (zB ) in letzterem. ${\displaystyle 2^{\omega}=\omega}$${\displaystyle \aleph _{0}}$${\displaystyle\omega}$${\displaystyle 2^{\aleph _{0}}>\aleph _{0}}$${\displaystyle 2^{\aleph _{0}}}$${\displaystyle {\mathfrak{c}}}$${\displaystyle \aleph _{0}}$

Jacobsthal zeigte, dass die einzigen Lösungen von α ^β  =  β ^α mit α  ≤  β gegeben sind durch α  =  β , oder α  = 2 und β  = 4, oder α ist eine beliebige Grenzordinal und β  =  εα wobei ε eine ε-Zahl größer ist als α .

Kantor Normalform

Jede Ordnungszahl α kann eindeutig als geschrieben werden , wobei k eine natürliche Zahl ist, positive ganze Zahlen sind und Ordnungszahlen sind. Der entartete Fall α = 0 tritt auf, wenn k = 0 ist und es weder β s noch c s gibt. Diese Zerlegung von α wird als Cantor-Normalform von α bezeichnet und kann als das Basis-ω- Positionszahlensystem angesehen werden . Der höchste Exponent wird als Grad von bezeichnet und erfüllt . Die Gleichheit gilt genau dann, wenn . In diesem Fall drückt die Cantor-Normalform die Ordinalform nicht durch kleinere aus; Dies kann wie unten beschrieben passieren. ${\displaystyle \omega^{\beta_{1}}c_{1}+\omega^{\beta_{2}}c_{2}+\cdots +\omega^{\beta_{k}}c_ {k}}$${\displaystyle c_{1},c_{2},\ldots ,c_{k}}$${\displaystyle \beta_{1}>\beta_{2}>\ldots >\beta_{k}\geq 0}$${\displaystyle \beta_{1}}$${\displaystyle\alpha}$${\displaystyle \beta_{1}\leq \alpha}$${\displaystyle \beta_{1}=\alpha}$${\displaystyle \alpha =\omega^{\alpha}}$

Eine kleinere Variante der Cantor-Normalform, die normalerweise etwas einfacher zu handhaben ist, besteht darin, alle Zahlen c _i gleich 1 zu setzen und die Exponenten gleich zu lassen. Mit anderen Worten, jede Ordnungszahl α kann eindeutig als geschrieben werden , wobei k eine natürliche Zahl ist und Ordnungszahlen sind. ${\displaystyle \omega^{\beta_{1}}+\omega^{\beta_{2}}+\cdots +\omega^{\beta_{k}}}$${\displaystyle \beta_{1}\geq \beta_{2}\geq \ldots \geq \beta_{k}\geq 0}$

Eine andere Variation der Cantor-Normalform ist die "Basis- δ- Entwicklung", wobei ω durch eine beliebige Ordinalzahl δ > 1 ersetzt wird und die Zahlen c _i positive Ordinalzahlen kleiner als δ sind .

Die Cantor-Normalform ermöglicht es uns, die Ordinalzahlen α , die aus den natürlichen Zahlen durch eine endliche Anzahl von arithmetischen Operationen der Addition, Multiplikation und Exponentiation zur Basis gebildet werden , eindeutig auszudrücken – und zu ordnen : mit anderen Worten, in der Cantor-Normalform wir können die Exponenten auch in Cantor-Normalform ausdrücken und rekursiv die gleiche Annahme wie für α usw. machen, erhalten wir ein Notationssystem für diese Ordinalzahlen (zum Beispiel ${\displaystyle\omega}$${\displaystyle \beta_{1}<\alpha}$${\displaystyle \beta_{i}}$${\displaystyle \beta_{i}}$

${\displaystyle \omega ^{\left(\omega ^{\left(\omega ^{7}\cdot 6+\omega +42\right)}\cdot 1729+\omega ^{9}+88\right) }\cdot 3+\omega^{\left(\omega^{\omega}\right)}\cdot 5+65537}$

bezeichnet eine Ordnungszahl).

Die Ordinalzahl ₀ ( Epsilon null ) ist die Menge von Ordinalwerten α der arithmetischen Ausdrücke endlicher Länge der Cantor-Normalform, die erblich nicht trivial sind, wobei nicht trivial β ₁ < α bedeutet, wenn 0 < α . Es ist die kleinste Ordinalzahl, die keinen endlichen arithmetischen Ausdruck in Bezug auf hat, und die kleinste Ordinalzahl so, dass , dh in der Cantor-Normalform, der Exponent nicht kleiner als die Ordinalzahl selbst ist. Es ist die Grenze der Folge ${\displaystyle \varepsilon_{0}=\omega ^{\varepsilon_{0}}}$

${\displaystyle 0,\,1=\omega^{0},\,\omega =\omega^{1},\,\omega^{\omega},\,\omega^{\omega^{\omega }},\,\ldots\,.}$

Die Ordinalzahl ε ₀ ist aus verschiedenen Gründen in der Arithmetik wichtig (im Wesentlichen, weil sie die beweistheoretische Stärke der Peano-Arithmetik erster Ordnung misst : Das heißt, Peanos Axiome können bis zu jeder Ordinalzahl kleiner als ε _0, aber nicht bis ε ₀ selbst).

Die Cantor-Normalform erlaubt uns auch, Summen und Produkte von Ordinalzahlen zu berechnen: Um die Summe zu berechnen, muss man beispielsweise nur wissen (siehe die in § Addition und § Multiplikation aufgeführten Eigenschaften ), dass

${\displaystyle \omega^{\beta}c+\omega^{\beta'}c'=\omega^{\beta'}c'\,,}$

if (wenn man das Distributivgesetz auf der linken Seite anwenden und dies in umschreiben kann , und wenn der Ausdruck bereits in Cantor-Normalform vorliegt); und um Produkte zu berechnen, sind die wesentlichen Tatsachen, dass wenn in Cantor-Normalform und , dann ${\displaystyle \beta '>\beta }$${\displaystyle \beta '=\beta}$${\displaystyle \omega^{\beta}(c+c')}$${\displaystyle \beta '<\beta }$${\displaystyle 0<\alpha =\omega^{\beta_{1}}c_{1}+\cdots +\omega^{\beta_{k}}c_{k}}$${\displaystyle 0<\beta '}$

${\displaystyle \alpha\omega^{\beta'}=\omega^{\beta_{1}+\beta'}\,}$

und

${\displaystyle \alpha n=\omega^{\beta_{1}}c_{1}n+\omega^{\beta_{2}}c_{2}+\cdots +\omega^{\beta_{ k}}c_{k}\,,}$

wenn n eine natürliche Zahl ungleich Null ist.

Um zwei Ordinalzahlen in Cantor-Normalform zu vergleichen , vergleichen Sie zuerst , dann , dann , dann usw. Beim ersten Unterschied ist die Ordinalzahl mit der größeren Komponente die größere. Wenn sie gleich sind, bis einer vor dem anderen endet, dann ist derjenige kleiner, der zuerst endet. ${\displaystyle \beta_{1}}$${\displaystyle c_{1}}$${\displaystyle \beta_{2}}$${\displaystyle c_{2}}$

Faktorisierung in Primzahlen

Ernst Jacobsthal zeigte, dass die Ordinalzahlen eine Form des eindeutigen Faktorisierungssatzes erfüllen: Jede von Null verschiedene Ordinalzahl kann als Produkt einer endlichen Anzahl von Primzahlen geschrieben werden. Diese Zerlegung in Primzahlen ist im Allgemeinen nicht eindeutig, aber es gibt eine „minimale“ Zerlegung in Primzahlen, die bis hin zur Änderung der Ordnung endlicher Primfaktoren eindeutig ist ( Sierpiński 1958 ).

Eine Primzahl ist eine Ordnungszahl größer als 1, die nicht als Produkt zweier kleinerer Ordnungszahlen geschrieben werden kann. Einige der ersten Primzahlen sind 2, 3, 5, ... , , ω+1, ω ² +1, ω ³ +1, ..., ω ^ω , ω ^ω +1, ω ^ω+1 +1 , ... Es gibt drei Arten von Primzahlen:

• Die endlichen Primzahlen 2, 3, 5, ...
• Die Ordinalzahlen der Form ω ^{ω α} für jede Ordinalzahl α . Dies sind die Prim-Ordinalzahlen, die Grenzwerte sind, und sind die Delta-Zahlen .
• Die Ordinalzahlen der Form ω ^α +1 für jede Ordinalzahl α >0. Dies sind die unendlichen Nachfolgerprimzahlen und die Nachfolger der Gammazahlen , der additiv unzerlegbaren Ordinalzahlen.

Die Faktorisierung in Primzahlen ist nicht eindeutig: zum Beispiel 2×3=3×2, 2×ω=ω, (ω+1)×ω=ω×ω und ω×ω ^ω = ω ^ω . Es gibt jedoch eine eindeutige Faktorisierung in Primzahlen, die die folgenden zusätzlichen Bedingungen erfüllt:

• Jede Grenz-Primzahl tritt vor jeder Nachfolge-Primzahl auf
• Wenn zwei aufeinanderfolgende Primzahlen der Primfaktorzerlegung beide Grenzen oder beide endlich sind, dann ist die zweite höchstens die erste.

Diese Primfaktorzerlegung lässt sich mit der Cantor-Normalform leicht wie folgt ablesen:

• Schreiben Sie zunächst die Ordinalzahl als Produkt αβ, wobei α die kleinste Potenz von ω in der Cantor-Normalform ist und β ein Nachfolger ist.
• Wenn α =ω ^γ, dann ergibt die Schreibweise von γ in Cantor-Normalform eine Entwicklung von α als Produkt von Grenzprimzahlen.
• Betrachten Sie nun die Cantor-Normalform von β . Wenn β = ω ^λ m + ω ^μ n + kleinere Terme, dann ist β = (ω ^μ n + kleinere Terme)(ω ^{λ − μ} + 1) m ein Produkt einer kleineren Ordinalzahl und einer Primzahl und einer ganzen Zahl m . Wiederholt man dies und zerlegt die ganzen Zahlen in Primzahlen, erhält man die Primfaktorzerlegung von β .

Also die Faktorisierung der Cantor-Normalform-Ordinalzahl

${\displaystyle \omega^{\alpha_{1}}n_{1}+\cdots +\omega^{\alpha_{k}}n_{k}}$(mit )${\displaystyle \alpha_{1}>\cdots>\alpha_{k}}$

in ein minimales Produkt von unendlichen Primzahlen und ganzen Zahlen ist

${\displaystyle \omega^{\omega^{\beta_{1}}}\cdots\omega^{\omega^{\beta_{m}}}n_{k}(\omega^{\alpha_{ k-1}-\alpha_{k}}+1)n_{k-1}\cdots n_{2}(\omega^{\alpha_{1}-\alpha_{2}}+1)n_ {1}}$

wobei jedes n _i durch seine Zerlegung in eine nicht wachsende Folge endlicher Primzahlen ersetzt werden sollte und

${\displaystyle \alpha_{k}=\omega^{\beta_{1}}+\cdots+\omega^{\beta_{m}}}$mit .${\displaystyle \beta_{1}\geq \cdots \geq \beta_{m}}$

Große zählbare Ordnungszahlen

Wie oben diskutiert, kann die Cantor-Normalform von Ordinalzahlen unten in einem Alphabet ausgedrückt werden, das nur die Funktionssymbole für Addition, Multiplikation und Exponentiation sowie konstante Symbole für jede natürliche Zahl und für enthält . Wir können die unendlich vielen Ziffern beseitigen, indem wir nur das Konstantensymbol 0 und die Nachfolgeoperation verwenden (zum Beispiel kann die ganze Zahl 4 als ausgedrückt werden ). Dies beschreibt eine Ordinalnotation : ein System zum Benennen von Ordinalzahlen über einem endlichen Alphabet. Dieses spezielle System der Ordinalnotation wird als Sammlung arithmetischer Ordinalausdrücke bezeichnet und kann alle folgenden Ordinalzahlen ausdrücken , aber nicht ausdrücken . Es gibt andere Ordinalnotationen, die Ordinalzahlen weit nach erfassen können , aber da es nur abzählbar viele Strings über einem endlichen Alphabet gibt, gibt es für jede gegebene Ordinalnotation Ordinalzahlen darunter (die erste unzählbare Ordinalzahl ), die nicht ausdrückbar sind. Solche Ordnungszahlen werden als große abzählbare Ordnungszahlen bezeichnet . ${\displaystyle \varepsilon _{0}}$${\displaystyle\omega}$${\displaystyle S}$${\displaystyle S(S(S(S(0))))}$${\displaystyle \varepsilon _{0}}$${\displaystyle \varepsilon _{0}}$${\displaystyle \varepsilon _{0}}$${\displaystyle \omega_{1}}$

Die Operationen Addition, Multiplikation und Exponentiation sind alle Beispiele für primitive rekursive Ordinalfunktionen , und allgemeinere primitive rekursive Ordinalfunktionen können verwendet werden, um größere Ordinalzahlen zu beschreiben.

Natürliche Operationen

Die Natursummen- und Naturprodukt- Operationen auf Ordinalzahlen wurden 1906 von Gerhard Hessenberg definiert und werden manchmal als Hessenberg-Summe (oder Produkt) bezeichnet ( Sierpinski 1958 ) . Dies sind die gleichen wie die Addition und Multiplikation (beschränkt auf ordinals) von John Conway ‚s Feld von surrealen Zahlen . Sie haben den Vorteil, dass sie assoziativ und kommutativ sind und sich Naturprodukt über Natursumme verteilt. Der Preis, diese Operationen kommutativ zu machen, besteht darin, dass sie die Stetigkeit im richtigen Argument verlieren, die eine Eigenschaft der gewöhnlichen Summe und des Produkts ist. Die natürliche Summe von α und β wird oft mit α ⊕ β oder α # β bezeichnet und der Naturstoff mit α ⊗ β oder α ⨳ β . harv error: no target: CITEREFSierpinski1958 ( Hilfe )

Die natürlichen Operationen kommen in der Theorie der Brunnenteilordnungen vor ; gegeben zwei gut partielle Ordnungen S und T , der Typen (maximale Linearisierungen ) o ( S ) und o ( T ), der Typ der disjunkten Vereinigung ist o ( S )⊕ o ( T ), während der Typ des direkten Produkts ist o ( S )⊗ o ( T ). Man kann diese Beziehung als Definition der natürlichen Operationen nehmen, indem man S und T als Ordinalzahlen α und β wählt ; also ist α ⊕ β der maximale Ordnungstyp einer Gesamtordnung, die die disjunkte Vereinigung (als Teilordnung) von α und β erweitert ; während α ⊗ β der maximale Ordnungstyp einer Gesamtordnung ist, die das direkte Produkt (als Teilordnung) von α und β erweitert . Eine nützliche Anwendung davon ist, wenn α und β beide Teilmengen einer größeren Gesamtordnung sind; dann hat ihre Vereinigung höchstens den Ordnungstyp α ⊕ β . Wenn sie beide Teilmengen einer geordneten abelschen Gruppe sind , dann hat ihre Summe höchstens den Ordnungstyp α ⊗ β .

Wir können die natürliche Summe von α und β auch induktiv (durch gleichzeitige Induktion über α und β ) als kleinste Ordinalzahl größer als die natürliche Summe von α und γ für alle γ < β und von γ und β für alle γ < α definieren . Es gibt auch eine induktive Definition des Naturprodukts (durch gegenseitige Induktion), aber es ist etwas mühsam aufzuschreiben und wir werden dies nicht tun (siehe den Artikel über surreale Zahlen für die Definition in diesem Zusammenhang, die jedoch surreal verwendet Subtraktion, etwas, das offensichtlich nicht auf Ordnungszahlen definiert werden kann).

Die natürliche Summe ist assoziativ und kommutativ. Sie ist immer größer oder gleich der üblichen Summe, kann aber auch strikt größer sein. Zum Beispiel ist die natürliche Summe von ω und 1 ω+1 (die übliche Summe), aber dies ist auch die natürliche Summe von 1 und ω. Das Naturprodukt ist assoziativ und kommutativ und verteilt sich über die Natursumme. Das Naturprodukt ist immer größer oder gleich dem üblichen Produkt, kann aber auch unbedingt größer sein. Zum Beispiel ist das Naturprodukt von ω und 2 ω·2 (das übliche Produkt), aber dies ist auch das Naturprodukt von 2 und ω.

Eine weitere Möglichkeit, die natürliche Summe und das Produkt zweier Ordinalzahlen α und β zu definieren, besteht darin, die Cantor-Normalform zu verwenden: Man kann eine Folge von Ordinalzahlen γ ₁ > … > γ _n und zwei Folgen ( k ₁ , …, k _n ) finden. und ( j ₁ , …, j _n ) von natürlichen Zahlen (einschließlich Null, aber k _i + j _i > 0 für alle i erfüllend ), so dass

${\displaystyle \alpha =\omega^{\gamma_{1}}\cdot k_{1}+\cdots +\omega^{\gamma_{n}}\cdot k_{n}}$

${\displaystyle \beta =\omega^{\gamma_{1}}\cdot j_{1}+\cdots +\omega^{\gamma_{n}}\cdot j_{n}}$

und definieren

${\displaystyle \alpha\#\beta =\omega^{\gamma_{1}}\cdot (k_{1}+j_{1})+\cdots+\omega^{\gamma_{n}}\ cdot (k_{n}+j_{n}).}$

Unter natürlicher Addition lassen sich die Ordinalzahlen mit den Elementen des durch die Gammazahlen ω ^α erzeugten freien kommutativen Monoids identifizieren . Unter natürlicher Addition und Multiplikation lassen sich die Ordinalzahlen mit den Elementen des durch die Deltazahlen ω ^{ω α} erzeugten freien kommutativen Halbrings identifizieren . Die Ordinalzahlen haben unter dem Naturprodukt keine eindeutige Faktorisierung in Primzahlen. Während der vollständige Polynomring eine eindeutige Faktorisierung hat, hat die Teilmenge der Polynome mit nicht-negativen Koeffizienten dies nicht: Wenn beispielsweise x eine beliebige Delta-Zahl ist, dann

${\displaystyle x^{5}+x^{4}+x^{3}+x^{2}+x+1=(x+1)(x^{4}+x^{2}+1 )=(x^{2}+x+1)(x^{3}+1)}$

hat zwei inkompatible Ausdrücke als Naturprodukt von Polynomen mit nicht-negativen Koeffizienten, die nicht weiter zerlegt werden können.

Nimber-Arithmetik

Es gibt arithmetische Operationen auf Ordnungszahlen aufgrund der Eins-zu-eins-Entsprechung zwischen Ordnungszahlen und Zahlen . Drei übliche Operationen an Zahlen sind Zahlenaddition, Zahlenmultiplikation und minimaler Ausschluss (mex) . Die Nimber-Addition ist eine Verallgemeinerung der bitweisen Exklusiv-Oder- Operation auf natürliche Zahlen. Die mex einer Menge von Ordnungszahlen ist die kleinste Ordnungszahl, die nicht in der Menge vorhanden ist.

Anmerkungen

Verweise

• Thomas Jech (21. März 2006). Set Theory: The Third Millennium Edition, überarbeitet und erweitert . Springer Wissenschaft & Wirtschaftsmedien. ISBN 978-3-540-44085-7.
• Kunen, Kenneth , 1980. Mengentheorie: Eine Einführung in die Unabhängigkeitsbeweise . Sonst. ISBN  0-444-86839-9 .
• Sierpiński, Wacław (1958), Kardinal- und Ordnungszahlen , Polska Akademia Nauk Monografie Matematyczne, 34 , Warschau: Państwowe Wydawnictwo Naukowe, MR  0095787

Externe Links

• ordCalc Ordnungsrechner