Der Unvollständigkeitssatz von Kurt Gödel ist einerseits berühmt, weil der Mathematiker damit gezeigt hat, dass die Mathematik nicht vollständig ist – und niemals sein kann. Jedes ausreichend starke formale logische System enthält zwangsläufig wahre Aussagen, die innerhalb dieses Systems unbeweisbar sind. Andererseits ist der Satz aber auch berühmt, weil Beispiele solcher unbeweisbaren Sätze meist schwer zu verstehen sind. Für die Goodstein-Folge gilt das allerdings nicht:

Um zu verstehen, was hier gemeint ist, braucht es jedoch ein wenig Vorarbeit. Es geht um die Darstellung natürlicher Zahlen, was wir normalerweise im Dezimalsystem tun. Die Zahl 35 zum Beispiel ist gleich 3 mal 10 hoch 1 plus 5 mal 10 hoch 0. Man kann aber problemlos eine andere Basis als zehn verwenden: Im Binärsystem mit der Basis 2 stellt man die 35 als 2⁵ + 2¹ + 2⁰ dar. Doch man kann auch noch die Exponenten entsprechend umwandeln. Im Binärsystem wird 5 als (2² + 1) geschrieben. Und wenn man alles entsprechend zusammensetzt, hat man in dieser Darstellung der Zahl 35 dann keine Exponenten, die größer sind als die Basis 2. Das nennt sich die iterierte Darstellung zur Basis b. Man kann alle natürlichen Zahlen auf diese Art schreiben.

Als Nächstes müssen wir die Aufbläh-Operation a_b definieren, um die obige Formel zu verstehen. Dazu wird in der iterierten Darstellung jede Zahl b durch b + 1 ersetzt, so dass eine neue natürliche Zahl entsteht. Beim Beispiel der 35 wird aus 2 hoch (2² + 1) also 3 hoch (3³ + 1), aus 2¹ wird 3¹ und aus 2⁰ wird 3⁰. Die neue Zahl, die sich daraus berechnet, ist deutlich größer als 35, nämlich 22 876 792 454 965 (wodurch sich auch der Name Aufbläh-Operation erklärt).

Jetzt haben wir alles, um die obige Formulierung der Goodstein-Folge g_b(n) zu verstehen. Ist n eine natürliche Zahl mit Basis b, dann wird das Startglied als g₁(n) = n definiert. Für den nächsten Term muss man dann n zur Basis b = 2 in iterierter Form darstellen, diese Darstellung wie oben beschrieben aufblähen und von der resultierenden Zahl 1 abziehen – und so weiter.

Eine Folge mit klarem Ende

Betrachten wir zum Beispiel den Fall für n = 2. g₁(2) ist per Definition gleich 2. Für g₂ müssen wir die Zahl 2 also zuerst zur Basis 2 darstellen, was 2¹ entspricht. Das wird zu 3¹ = 3 aufgebläht und die finale Subtraktion von 1 ergibt g₂(2) = 2. Für g₃(2) wird dieses Ergebnis jetzt zur Basis 3 dargestellt und der Vorgang wiederholt, was das Resultat 1 liefert – und die Folge endet schließlich mit g₄(2) = 0.

Tatsächlich, und das ist eine der spannenden Eigenschaften dieser Folge, endet sie für jeden Wert von n irgndwann bei 0. Es geht allerdings selten so schnell wie im Beispiel n = 2. Für n = 3 braucht es sechs Iterationsschritte, aber schon im Fall von n = 4 ist eine Zahl von Schritten nötig, die so groß ist, dass man über 121 Millionen Ziffern dafür aufschreiben müsste. Die Goodstein-Folge wächst extrem schnell zu enormen Werten an. Und es kann ebenso lange dauern, bis die Folge am Ende doch die 0 erreicht. Aber - und das konnte der englische Logiker Reuben Louis Goodstein im Jahr 1944 beweisen – egal wie hoch der Startwert ist, die 0 wird auf jeden Fall in endlich vielen Schritten erreicht.

Dieser Satz von Goodstein (und damit sind wir jetzt bei der Unvollständigkeit der Mathematik) ist allerdings nicht mit den Axiomen der Peano-Arithmetik zu beweisen. Das sind die grundlegenden Axiome, die den Umgang mit natürlichen Zahlen, der Addition und der Multiplikation definieren. Obwohl beim Umgang mit der Goodstein-Folge keine anderen Rechenoperationen nötig sind, reichen diese Axiome nicht aus, um den Satz beweisen zu können. Dazu sind stärkere logische Systeme nötig, die aber selbst, so wie die Mathematik an sich, nie vollständig sein können. Der Satz von Goodstein illustriert genau das. Und wer jetzt denkt, dass das alles am Ende doch ein wenig kompliziert war, hat nun eine Vorstellung davon, wie komplex der echte Satz von Gödel ist.