Der Satz von Goodstein

Satz von Goodstein

Jede Goodstein-Folge mit beliebigem Anfangswert aus den natürlichen Zahlen erreicht in endlich vielen Schritten den Wert null.

Dieser Satz wurde 1944 vom englischen Logiker Reuben Louis Goodstein (1912-1985) bewiesen. Dieser Satz ist innerhalb der Mathematik vor allem deswegen interessant, weil er sich nicht mit den Peano-Axiomen herleiten lässt. Stattdessen verwendet der Beweis Mittel der Mengenlehre, speziell die Theorie der Ordinalzahlen.
 
 

Beweis des Satzes von Goodstein

Der Satz von Kirby und Paris besagt, dass der Satz von Goodstein nicht mit Mitteln der Peano-Arithmetik beweisbar ist. Man benötigt also ein mächtigeres Werkzeug: die Ordinalzahlen.
Die Theorie der Ordinalzahlen erweitert die natürlichen Zahlen um Größen, die größer als alle natürlichen Zahlen sind. Die kleinste unendliche Ordinalzahl wird ω\omega genannt. Ordinalzahlen kann man addieren, multiplizieren und potenzieren, jedoch gelten einige Rechenregeln der natürlichen Zahlen nicht für Ordinalzahlen (z. B. ist ω\omega+1 ≠\neq 1+ω\omega = ω\omega). Ordinalzahlen sind der Größe nach geordnet (sie haben eine totale Ordnung), die drei genannten Rechenarten sind monoton in allen Argumenten, und die Ordinalzahlen sind wohlgeordnet, d. h., es gibt keine streng monoton fallende unendliche Folge von Ordinalzahlen.
Wir ordnen nun jeder natürlichen Zahl nn eine Ordinalzahl zu, indem wir nn zur Basis bb iteriert darstellen und dann jedes bb durch ω\omega ersetzen. Die so entstehenden Ordinalzahlen lassen sich durch eine endliche Folge von Additionen, Multiplikationen und Potenzierungen aus ω\omega und natürlichen Zahlen gewinnen; die Menge der so darstellbaren Ordinalzahlen heißt ϵ0\epsilon_0 (diese Menge ist die kleinste Ordinalzahl, die nicht auf diese Weise darstellbar ist). Wir haben also eine Abbildung
Ab(n):N→ϵ0A_b(n): \mathbb{N} \to \epsilon_0
(auch hier gibt es in der Literatur unterschiedliche Schreibweisen).
Es ist z. B.
A2(19)=A2(222+2+1)=ωωω+ω+1A_2(19) = A_2(2^{2^2} + 2 + 1) = \omega^{\omega^\omega} + \omega + 1
A3(g2(19))=A3(333+3)=ωωω+ωA_3(g_2(19)) = A_3(3^{3^3} + 3) = \omega^{\omega^\omega} + \omega
Ist nn kleiner als bb, dann ist Ab(n)A_b(n) eine endliche Ordinalzahl, z. B. ist
A5(3)=3A_5(3) = 3
Das Aufblähen hat keine Auswirkung auf die Ordinalzahl, denn es spielt keine Rolle, ob man in der iterierten Darstellung gleich jedes bb durch ω\omega ersetzt, oder erst jedes bb durch (b+1)(b+1) und dann jedes (b+1)(b+1) durch ω\omega, es gilt also
Ab+1(ab(n))=Ab(n)A_{b+1}(a_b(n)) = A_b(n)
Die Subtraktion von 1 hat jedoch Auswirkungen auf die Ordinalzahl: Diese wird reduziert.
Beispielsweise gilt
A5(a4(44+4))=A5(55+5)=ωω+ωA_5(a_4(4^4+4)) = A_5(5^5 + 5) = \omega^\omega + \omega
A5(a4(44+4)−1)=A5(55+4)=ωω+4A_5(a_4(4^4+4)-1) = A_5(5^5 + 4) = \omega^\omega + 4
Der Goodstein-Folge (gb(n))b∈N(g_b(n))_{b \in \mathbb{N}} ordnen wir nun eine Folge von Ordinalzahlen (Gb(n))b∈N(G_b(n))_{b \in \mathbb{N}} so zu:
Gb(n):=Ab+1(gb(n))G_b(n) := A_{b+1}(g_b(n))
Diese Folge wird oft die "Parallelfolge" (engl. "parallel sequence") genannt.
Diese Folge von Ordinalzahlen ist streng monoton fallend, muss also nach endlich vielen Schritten bei 00 enden (Ordinalzahlen haben eine Wohlordnung). Da Gb(n)≥gb(n)G_b(n) \geq g_b(n) für alle nn und bb gilt, endet also auch die Goodstein-Folge nach endlich vielen Schritten.
Der Satz von Goodstein macht keine Aussage darüber, nach wie vielen Schritten eine Goodstein-Folge endet; er ist also ein reiner Existenzsatz:
Zu jedem natürlichen nn existiert ein bb, so dass gb(n)=0g_b(n)=0 ist.

Unabhängigkeit von der Peano-Arithmetik

Während der Beweis des Satzes von Goodstein noch relativ einfach ist (sofern man mit der Theorie der Ordinalzahlen vertraut ist), ist die Behauptung, dass dieser Satz nicht allein mit der Peano-Arithmetik beweisbar ist, deutlich schwieriger zu beweisen. Dies gelang Laurie Kirby und Jeff Paris 1982. Der nach ihnen benannte Satz von Kirby und Paris verwendet ein so genanntes Nichtstandardmodell der Peano-Arithmetik.

Die Furcht vor der Mathematik steht der Angst erheblich näher als der Ehrfurcht.

Felix Auerbach

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Goodstein-Folge aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Elementare Zahlentheorie