Goodstein-Folgen: Die Kraft des Umweges über die Unendlichkeit

Die Autoren des englischen Artikels sind Michèle Artigue und Ferdinando Arzarello.
Die Analyse der Entwicklung eines Naturphänomens führt oft zur Untersuchung numerischer Folgen, insbesondere deren Langzeit-Verhalten und zu der Frage, ob sie eventuell konvergieren. Polynomiale, exponentielle und logarithmische Folgen werden häufig in weiterführenden Schulen behandelt, andere Folgen mit sehr einfachen Bildungsgesetzen zeigen dagegen ein viel komplexeres Verhalten. Beispiele sind die chaotischen Folgen, die bei der Untersuchung dynamischer Systeme auftreten (siehe [1]) und die Syrakus-Folge (oder 3n+1-Folge), die 1937 von Lother Collatz eingeführt wurde. Die Syrakus-Folge forderte Mathematiker über Jahrzehnte heraus. Trotz der riesigen Anzahl von Werten, die berechnet wurden, ist es zurzeit unbekannt, ob die Folge divergiert oder letztlich immer bei 1 endet (siehe [2]).

Die Folgen, die in diesem Klein-Artikel betrachtet werden, wurden 1944 von dem britischen Logiker R.L. Goodstein eingeführt (siehe [3]) und zeigen verschiedene Arten eines ungewöhnlichen Verhaltens. Ihre Anfangswerte steigen so schnell, dass man glauben könnte, dass sie gegen Unendlich streben, aber, erstaunlicherweise, fallen die Folgenglieder irgendwann und erreichen letztendlich die Null. Der Beweis dieses Ergebnisses erfordert eine Verallgemeinerung des Wohlordnungs- Prinzips der ganzen Zahlen (siehe [4]) zu den transfiniten Zahlen. Dabei ist die Grundidee nicht schwer zu verstehen. Um dies – wie Hodgson – zu erklären (siehe [5]), führen wir zunächst eine verwandte Folge ein, die wir schwache Goodstein-Folge nennen, die einfacher, aber eng mit der Goodstein-Folge verwandt ist.

1. Schwache Goodstein-Folgen

Bei Hodgson wird die Definition einer schwachen Goodstein-Folge beginnend mit der Zahl 266 dargestellt. Wie alle positiven natürlichen Zahlen besitzt sie eine eindeutige Zerlegung in eine Summe von Potenzen mit der Basis 2 (siehe [6]): 266 = 2^8 + 2^3 +2^1. Die schwache Goodstein-Folge mit dem Anfangsglied u_0 = 266 ist wie folgt definiert: um den Wert von u_1 zu erhalten, verändert man die Basis 2 von u_0 zur Basis 3, subtrahiert 1 und schreibt die sich daraus resultierenden Zahlen zur Basis 3 um. Folglich erhält man: u_1 = 3^8 + 3^3 + 3^1 - 1 = 3^8 + 3^3 + 2 = 6,590. Zur Bestimmung von u_2 ändert man die Basisdarstellung von u_1 zur Basis 4, subtrahiert 1 und schreibt die daraus resultierenden Zahlen zur Basis 4 um. Folglich erhält man: u_2 = 4^8 + 4^3 + 2 - 1 = 4^8 + 4^3 + 1 = 65,601. Dies wird so lange fortgesetzt, solange alle Glieder ungleich Null sind, indem man die natürliche Zahl in der Basis des vorherigen Glieds durch die nächst größere natürliche Zahl ersetzt, 1 subtrahiert, und das Ergebnis unter Verwendung der neuen Basis umschreibt.

u_0 &= 2^8 + 2^3 + 2^1 = 266
u_1 &= 3^8 + 3^3 + 3^1 - 1 = 3^8 + 3^3 + 2 = 6,590
u_2 &= 4^8 + 4^3 + 2 - 1 = 4^8 + 4^3 + 1 = 65,601
u_3 &= 5^8 + 5^3 + 1 - 1 = 5^8 + 5^3 = 390,750
u_4 &= 6^8 + 6^3 - 1 = 6^8 + 5 . 6^2 + 6^2 - 1 = 6^8 + 5 . 6^2 + 5 . 6 + 6 - 1\\ = 6^8 + 5 . 6^2 + 5 . 6^1 + 5 = 1,679,831
u_5 &= 7^8 + 5 . 7^2 + 5 . 7^1 + 5 - 1 = 7^8 + 5 . 7^2 + 5 . 7^1 + 4 = 5,765,085
u_6 &= 8^8 + 5 . 8^2 + 5 . 8^1 + 4 - 1 = 8^8 + 5 . 8^2 + 5 . 8^1 + 3 = 16,777,579
u_7 &= 9^8 + 5 . 9^2 + 5 . 9^1 + 3 - 1 = 9^8 + 5 . 9^2 + 5 . 9^1 + 2 = 43,047,173
u_8 &= 10^8 + 5 . 10^2 + 5 . 10^1 + 2 - 1 = 10^8 + 5 . 10^2 + 5 . 10^1 + 1 = 100,000,551
u_9 &= 11^8 + 5 . 11^2 + 5 . 11^1 + 1 - 1 = 11^8 + 5 . 11^2 + 5 . 11^1 = 214,359,541
u_{10} &= 12^8 + 5 . 12^2 + 5 . 12^1 - 1 = 12^8 + 5 . 12^2 + 4 . 12^1 + 12 - 1\\ = 12^8 + 5 . 12^2 + 4 . 12^1 + 11 = 429,982,475

Tabelle 1: Anfangsglieder einer schwachen Goodstein-Folge

Da die Glieder der Folge schnell sehr groß werden, wird man sich fragen, ob alle derartigen Folgen so schnell wachsen. Das ist aber nicht der Fall. Wenn z.B. u_0 = 1, ist, dann folgt u_1 = 1 - 1 = 0. Wenn u_0 = 2 = 2^1 ist, dann gilt u_1 = 3^1 - 1 = 2, u_2 = 2 - 1 = 1 und u_3 = 1 - 1 = 0 (da die Basis von u_2 gleich 4 und die Basis für u_3 gleich 5 ist). Ähnlich kann man überprüfen, dass für u_0 = 3 die Glieder der Folge nie größer als 3 werden und in 5 Schritten die Null erreichen (siehe [7]). Sobald die Zerlegung für den Anfangswert eine höhere Potenz als 2^1 beinhaltet, führt das schnelle Ansteigen der Glieder (wie für u_0 = 266 gezeigt) zu der Vermutung, dass die Folgen divergieren. Wie kann das Subtrahieren von 1 in jedem Schritt dem enormen Anstieg der Folge durch das kontinuierliche Erhöhen der Basis um 1 entgegenwirken?

Wirft man einen genaueren Blick auf die Glieder der obigen Tabelle, stellt man fest, dass – obwohl die Glieder der Folge mit dem Anfangswert 266 schnell ansteigen – die Exponenten der aufeinanderfolgenden Basen zu fallen scheinen. Der Exponent 1 in u_0 z.B. ist in u_1 nicht mehr vorhanden, ähnlich ist Exponent 3 in u_3 ersetzt durch eine 2 in u_4. Und bei u_9 ist er zu 1 reduziert. Schließlich wird der Exponent 8 bei u_{10} zu einer 7 reduziert, und diese 7 wird in weiteren Schritten weiter reduziert. Genau diese, für alle Goodstein-Folgen auftretende Charakteristik ermöglicht es zu zeigen, dass sie gegen Null konvergieren. Für den Beweis benötigen wir die transfiniten Ordinalzahlen.

2. Transfinite Ordinalzahlen und Wohlordnungen

Ordinalzahlen:
In der Alltagssprache werden Ordinalzahlen dazu verwendet, um Positionen in einer Reihenfolge anzugeben: erster, zweiter, dritter, usw. Tatsächlich können die positiven natürlichen Zahlen dazu verwendet werden, um Elemente jeder endlichen Menge in dieser Art und Weise zu ordnen. Die Idee der transfiniten Ordinalzahlen erweitert den Begriff Ordinalzahl. Diese ist auf den Mathematiker Georg Cantor zurückzuführen, der sie in einer Reihe von Artikeln Ende des 19. Jahrhunderts entwickelte. Wenn wir uns vorstellen mit der Null zu beginnen und sukzessive mit natürlichen Zahlen weiter zu zählen, würden wir nie damit fertig werden, da die Menge der natürlichen Zahlen unendlich ist. Wir können uns jedoch vorstellen, dass es eine „Zahl“ \omega gibt, welche die erste Zahl größer als jede natürliche Zahl ist. Da unendlich viele natürliche Zahlen kleiner sind als \omega, nennen wir dies eine „transfinite“ Ordinalzahl. Diese hat einen Nachfolger \omega +1, auf den \omega + 2 folgt usw. Die kleinste Ordinalzahl größer als alle Ordinalzahlen der Form \omega +n wird mit\omega + \omega oder \omega. 2 bezeichnet (siehe [8]). Die kleinste Ordinalzahl, die größer ist als alle Ordinalzahlen der Form \omega . n + m (wobei m eine Ordinalzahl kleiner als \omega . n ist) wird mit \omega ^2 bezeichnet. Die kleinste Ordinalzahl, die größer ist als alle Ordinalzahlen der Form \omega ^n + m (wobei m eine Ordinalzahl kleiner als \omega ^n ist) wird mit \omega^{\omega} bezeichnet.


Rendered by QuickLaTeX.com

Dann wird \omega^{\omega} gefolgt von \omega^{\omega} + 1, \omega^{\omega} + 2, … , \omega^{2 \omega} , \omega^{2 \omega} + 1, …, \omega^{2 \omega} + \omega, … , \omega^{3 \omega}, …, \omega^{\omega^{\omega}}, usw. Wir definieren \varepsilon_0 als die kleinste Ordinalzahl, die größer als alle Summen von iterierten Potenzen von \omega ist, und erlauben, dass es immer so weitergeht. In der Tat bilden alle bis hier genannten Ordinalzahlen nur den Beginn einer Kette von Ordinalzahlen, da sie eine abzählbare Menge bilden. D.h. sie können eins zu eins mit den positiven natürlichen Zahlen in Beziehung gesetzt werden.

Ordinalzahlen und Wohlordnungen:
Ein wesentlicher Unterschied zwischen transfiniten Ordinalzahlen und nicht-negativen natürlichen Zahlen ist, dass jede natürliche Zahl größer als 0 einen unmittelbaren Vorgänger hat, während Ordinalzahlen wie \omega, \omega . 2 und \omega^{\omega} dies nicht haben. Allerdings, so wie die Menge der natürlichen Zahlen, ist auch die erweiterte Menge der Ordinalzahlen in dem Sinne „wohlgeordnet“, dass jede nichtleere Menge von Ordinalzahlen ein kleinstes Element hat. Diese Eigenschaft ist der Grund dafür, dass es keine unendliche streng fallende Folge von Ordinalzahlen gibt. Angenommen, so eine unendliche Folge u_0, u_1, u_2, …, existiere. Sei S die Menge aller Glieder und nicht leer. Dann hat die Menge mindestens ein Element \alpha, also gilt \alpha = u_k für eine natürliche Zahl k. Aber solange die Folge streng fällt, gilt u_{k+1} < u_k = \alpha. Somit ist \alpha nicht das kleinste Element von S, was ein Widerspruch zur Annahme ist. Wir werden nun zeigen, wie man die Ordinalzahlen verwenden kann, um das Ergebnis über die schwachen Goodstein-Folgen zu zeigen.

3. Der Beweis, dass eine schwache Goodstein-Folge gegen Null konvergiert

Jeder schwachen Goodstein-Folge u_n wird eine streng fallende Folge von Ordinalzahlen \alpha_n zugeordnet, indem man die Basis jeden Glieds u_n durch \omega ersetzt. Da die Anfangsbasis einer schwachen Goodstein-Folge 2 ist und die Basis bei jedem Schritt um 1 ansteigt, führt dies bei u_n zur Basis (n+2). Somit hat die Folge, die der mit dem Anfangswert 266 entspricht, folgende Anfangswerte:


Rendered by QuickLaTeX.com

Tabelle 2: Die Folge von Ordinalzahlen, die einer schwachen
Goodstein-Folge zugeordnet ist

Jeder Term \alpha_n ist größer als der dazugehörige Term u_n. Während u_n jedoch ansteigt, fällt \alpha_n. Der Grund dafür ist, dass in der Entwicklung von u_n mit der Basis n + 2 der Term von u_n entweder Null oder ungleich Null ist. Es gibt zwei verschiedene Wege, um von dem einem zum anderen Glied zu gelangen:

  • Wenn u_n ungleich Null ist, dann ist u_{n+1} um eins kleiner als u_n, da man bei jedem Schritt 1 subtrahiert. (In Tabelle 2 kann man dies anhand den Schritte von u_1 zu u_2, von u_2 zu u_3, von u_4 zu u_5, und von u_5 zu u_6 beobachten.)
  • Wenn u_n gleich Null ist, muss man den Term mit dem kleinsten Exponent zerlegen. (In Tabelle 2 kann man dies anhand der Schritten von u_0 zu u_1, von u_3 zu u_4, und von u_9 zu u_{10} beobachten. Siehe Tabelle 1 für die Details der Berechnungen.) (siehe [9])

Beachten Sie, dass in beiden Fällen {\alpha_n} echt kleiner ist als der vorhergehende. Da die Ordinalzahlen geordnet sind, gibt es keine unendliche streng fallende Folge von Ordinalzahlen und somit muss eine natürliche Zahl m existieren für die gilt \alpha_m = 0. Weiterhin, da u_n \leqslant \alpha_n für alle n, also muss u_m gleich Null sein. u_n erreicht nach einer endlichen Anzahl an Schritten die Null, auch wenn die Anzahl der Schritte sehr groß sein kann.
Man kann nun fragen, für welchen Wert von n die Gleichung \alpha_n = \omega gilt, wenn man die Glieder von u_n und \alpha angefangen mit u_0 =5 betrachtet. Was ist der Wert von u_n und was sind die nachfolgenden Glieder für jede der zwei Folgen? (siehe [10]).
Untersucht man nun die Goodstein-Folgen genauer, stellt man fest, dass sie ein wenig anders definiert sind als die schwachen Goodstein-Folgen, und sie wachsen noch viel spektakulärer. Dennoch ist die Beweisstrategie dafür, dass sie letztendlich gegen Null konvergieren – erstaunlicherweise – ähnlich zu der eben betrachteten Strategie.

4. Goodstein-Folgen

Betrachtet man die Darstellung von 266 zur Basis 2. 266: 2^8 + 2^3 + 2^1 und schreibt man die Exponenten nur unter der Verwendung der Basis 2, so erhält man: 3 = 2^1 + 1 und 8 = 2^3 = 2^{2^1 +1}. Infolgedessen kann der ganze Ausdruck von 266 mit Basen kleiner gleich 2 geschrieben werden. Sei {m_n} die Goodstein-Folge, die mit m_0 = 266 startet. Um m_1 zu erhalten, ersetzt man den Wert 2 in allen vorkommenden Basen und Exponenten durch den Wert 3, subtrahiert 1 und schreibt das Ergebnis, ohne die Verwendung größerer Zahlen als die mit der Basis 3. Um sukzessive Terme von m_n zu erhalten, setzt man wie in Tabelle 3 gezeigt diesen Prozess iterativ fort. (siehe [11]).

m_0 = 2^{2^{2+1}} + 2^{2+1} + 2^1
m_1 = 3^{3^{3+1}} + 3^{3+1} +3^1 - 1 = 3^{3^{3+1}} + 3^{3+1} + 2\\ = 443 426 488 243 037 769 948 249 630 619 149 892 886 \approx 10^{38}
m_2 = 4^{4^{4+1}} + +4^{4+1} +1 \approx 10^{616}
m_3 = 5^{5^{5+1}} + 5^{5+1} \approx 10^{10921}
m_4 = 6^{6^{6+1}} + 6^{6+1} -1 = 6^{6^{6+1}} + 5.6^6 + 5.6^5 + 5. 6^4 +5.6^3 + 5.6^2 +5.6^1 + 5\\ \approx10^{217832}
m_5 = 7^{7^{7+1}} + 5.7^7 + 5.7^5 + 5. 7^4 +5.7^3 + 5.7^2 +5.7^1 + 4\\ \approx 10^{4 871 822}

Tabelle 3

Aus Tabelle 3 wird das spektakuläre Wachstum der Terme ersichtlich und dennoch fängt diese Folge, wie alle Goodstein-Folgen, letztendlich an zu fallen und konvergiert schließlich gegen Null. Der Beweis ist dem Beweis für eine schwache Goodstein-Folge sehr ähnlich. Man setzt eine Folge \beta_n mit der Folge m_n in Beziehung, indem man jede vorkommende Basis durch \omega ersetzt. So erhält man folgende Terme für \beta_n:

\beta_0 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1} + \omega^1
\beta_1 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1} + 2
\beta_2 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1} + 1
\beta_3 = \omega^{\omega^{\omega +1}} + \omega^{\omega +1}
\beta_4 = \omega^{\omega^{\omega +1}} + 5. \omega^{\omega} + 5 . \omega^{5} + 5 . \omega^{4} + 5 . \omega^{3} + 5 . \omega^{2} + 5 . \omega^{1} + 5
\beta_5 = \omega^{\omega^{\omega +1}} + 5. \omega^{\omega} + 5 . \omega^{5} + 5 . \omega^{4} + 5 . \omega^{3} + 5 . \omega^{2} + 5 . \omega^{1} + 4

Das strenge Fallen der Folge \beta_n von Ordinalzahlen impliziert, dass sie ein letztes Element hat. Die Terme können so lange berechnet werden, bis das letzte Element der Folge Null ist. Eine ähnliche Argumentation kann für alle Goodstein-Folgen verwendet werden. Gewöhnliche Arithmetik mit natürlichen Zahlen wird oft als Peano-Arithmetik bezeichnet, da der italienische Mathematiker Giuseppe Peano im 19. Jahrhundert als Erster ihre Axiome formulierte. Das Bemerkenswerteste über den obigen eleganten Beweis ist, dass er über die Peano-Arithmetik hinausgeht, um ein Theorem zu beweisen, dass komplett in der Peano-Arithmetik liegt. Mit anderen Worten: Es wird eine verallgemeinerte Mengentheorie, die transfinite Ordinalzahlen beinhaltet, verwendet, um ein Theorem über nicht-negative natürliche Zahlen, nämlich dass jede Goodstein-Folge gegen die Null konvergiert, zu beweisen. Es ist naheliegend sich zu fragen, ob die Konvergenz der Goodstein-Folge ohne Rückgriff auf transfinite Ordinalzahlen bewiesen werden kann. Die Antwort ist nein! Dies wurde 1982 von Laurie Kirby und Jeff Paris bewiesen, ca. 40 Jahre nachdem die Folgen eingeführt wurden (siehe [12]). Sie zeigten, falls die Konvergenz nur durch die Verwendung des Ordnungsprinzips der natürlichen Zahlen bewiesen werden kann (d.h. innerhalb der Peano-Arithmetik), dann kann der Satz über Goodstein-Folgen auf einen Satz von Gentzen (1936) zurückgeführt werden, aus dem die Widerspruchsfreiheit der Peano-Arithmetik abgeleitet werden kann. Wir wissen aber aus dem Unvollständigkeitstheorem von Gödel (1931), dass die Widerspruchsfreiheit der Peano-Arithmetik nicht nur mit der Peano-Arithmetik bewiesen werden kann. Es ist daher nicht anzuraten, nach einem Beweis zu suchen!

Auf der anderen Seite ist es überraschend, dass die Konvergenz der schwachen Goodstein-Folgen gegen Null innerhalb der Peano-Arithmetik bewiesen werden kann. Der Grund dafür ist im Wesentlichen, dass die Terme der verknüpften Folgen von Ordinalzahlen kleiner gleich \omega^{\omega} sind. Ein Beweis wurde 1987 von E.A. Cichon gegeben, der die schwachen Goodstein-Folgen einführte (siehe [13]). Zu jedem Glied u_n einer schwachen Goodstein-Folge kann man das m-Tupel von Koeffizienten der Entwicklung mit der Zerlegung in eine Basis n + 2 zuordnen und zeigen, dass die m-Tupel eine streng fallende lexikographische Wohlordnung darstellen.

5. Goodstein-Folgen und das Hydra Spiel

In ihrem Artikel erwähnen Kirby und Paris einen anderen Prozess, das Hydra-Spiel, der viele Ähnlichkeiten zu den Goodstein-Folgen besitzt. Das Spiel (siehe [14]) bekam seinen Namen von der Beschreibung der griechischen Mythologie des Kampfes zwischen Herakles und einer vielköpfigen Bestie: die lernäischen Hydra. Jedes Mal, wenn einer der Hydraköpfe abgeschlagen wurde, wuchsen an derselben Stelle zwei neue Köpfe nach. In diesem Spiel wird die Hydra durch einen Baum modelliert und die Köpfe der Hydra entsprechen den Endknoten oder Blättern des Baumes. Wenn Herakles einen Kopf, der nicht direkt mit der Wurzel des Baumes verbunden war, abschlägt, wird die Kante , die zum Kopf führt, entfernt. Der Hydra wachsen jedoch neue Köpfe aus den Verzweigungsknoten, die unter dem abgetrennten Kopf liegen. Dies kann auf verschiedenen Wegen realisiert werden. In dem Beispiel, das von Kirby und Paris gegeben und von Hodgson wieder verwendet wurde (siehe [4]): Wenn ein Kopf im Schritt n des Spieles abgetrennt wurde, generiert die Hydra n Kopien aus dem Teil des Baumes oberhalb des Verzweigungsknotens von dem der Kopf entfernt wurde. In dem unten aufgeführten Diagramm wird der Teil, der abgetrennt wird, als gepunktete Linie dargestellt, der regenerierte Teil in Rot und der Teil, der neu wachsen wird, ist in Blau dargestellt.

Man kann zeigen, dass bei beliebiger Anfangskonfiguration der Köpfe der Hydra und beliebiger Strategie des Herakles, er immer im Abschlagen aller Köpfe erfolgreich sein wird, obwohl er eine außergewöhnlich lange Zeit brauchen kann, um dies zu beenden. Wie bei den Goodstein-Folgen beruht der Beweis auf einer Beziehung zwischen aufeinander folgenden Bäumen und einer streng fallenden Folge von Ordinalzahlen. Wie man schon an dem obigen Diagramm erkennen kann, werden die Bäume immer breiter, aber die Höhe sich verringert schließlich. Letzlich ist Herakle sin einer Position alle Köpfe, die mehr als eine Ebene über der Wurzel liegen, zu entfernen. An diesem Punkt (wie Schritt 3 zeigt) kann er einen nach dem anderen von den übrig gebliebenen Köpfen abschlagen, ohne dass neue nachwachsen.

6. Die Lehren aus diesem Beispiel

Die Beispiele in dieser Kurzdarstellung sind aus mehreren Gründen interessant. Sie zeigen, dass mathematische Logik für mehr als nur Metamathematik relevant ist, dass Theoreme wie das Gödelsche Unvollständigkeitstheorem und Begriffe wie transfinite Ordinalzahlen für die Untersuchung gewöhnlicher mathematischer Objekte sowie für die Folgen von natürlichen Zahlen und mathematischer Graphen (hier Bäume) gebraucht werden. Durch den Beweis, dass eine Eigenschaft der natürlichen Zahlen innerhalb der allgemeinen Mengentheorie, aber nicht innerhalb der Peano-Arithmetik bewiesen werden kann, lenken diese Beispiele unsere Aufmerksamkeit auf den sprachlichen und theoretischen Rahmen der Beweise. In diesem Fall zeigen sie, dass die Peano -Arithmetik schwächer als die gewöhnliche Mengentheorie ist.

Eine andere Lehre aus diesen Beispielen ist die Strategie, ein schwieriges Problem zu lösen(hier die die Konvergenz der allgemeinen Goodstein-Folgen), indem man es in ein einfacher zugänglicheres Problem umwandelt (die Konvergenz einer schwachen Goodstein-Folge). Zusätzlich zeigen die Beispiele, dass ein typisches Beispiel – eine Folge, deren Anfangswert 266 ist – alle wichtigen Eigenschaften des allgemeinen Falls verdeutlichen kann. Die Beispiele sind auch lehrreich, da sie uns die Grenzen unserer Intuition aufzeigen. Folgen die anscheinend divergieren, tun dies aber nicht; sie beginnen letztlich zu fallen und konvergieren in einer endlichen Anzahl an Schritten gegen die Null. Schließlich ermöglichen uns die Beispiele beides zu sehen, die Stärken und die Grenzen von Computern, da sie uns ein Gefühl für das schnelle Anwachsen der Glieder der Folge vermitteln, aber sie sind von begrenztem Nutzen, wenn man mit der Flut der numerischen Daten, die durch die Definition der Folge generiert werden, konfrontiert wird.

Literatur

[1] Elert, Glenn (1995-2007). The Chaos HypertextbookTM, Bodnar, M. & Ramsden P. Discrete Logistic Equation, Wolfram Demonstrations Project. Perrin, D. (2008). La suite logistique et le chaos.

[2] Lagarias, J. C. (2001) The Syracuse Problem. In Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer.

[3] Goodstein, R. L. (1944). On the Restricted Ordinal Theorem, Journal of Symbolic Logic, 9, 33-41.

[4] Das Wohlordnungs-Prinzip der ganzen Zahlen sagt aus: Wenn jedes Element in einer Menge S ganzer Zahlen größer ist als eine bestimmte Zahl m, dann hat S ein kleines Element.

[5] Hodgson B. (2004). Herculean of Sisyphean tasks? EMS Newsletter, March 2004, pp. 11-16.

[6] Gegeben sei eine ganze Zahl b > 0 mit b \neq 1, jede positive ganze Zahl n hat eine Darstellung der folgenden Form zur Basis b: n = d_m . {b^m} + d_{m-1} . b^{m-1} + ... + d_1 . b^1 + d_0, wobei alle d_i wobei alle 0 und b - 1 und d_m \neq 0 sind. Beachte, dass b^m < n < b^{m+1}. Dies ist eine Verallgemeinerung der Darstellung von Zahlen im Stellenwertsystem zur Basis 10.

[7] Wenn u_0 = 3 (= 2^1+ 1), dann ist u_1= 3^1 + 1 - 1 = 3, u_2 = 4^1 - 1 = 3, u_3 = 3 - 1 = 2, u_4 = 2 - 1 = 1, und u^5 = 1 - 1 = 0. Beginnend mit u_3, ist jeder folgende Term um 1 geringer als der vorhergehende, weil in jedem Fall die Basis größer ist als im vorhergehenden Term.

[8] Wir Erweiterten die Summen- und Produktoperationen von den ganzen Zahlen zu den transfiniten Ordinalzahlen, allerdings bleibt die Kommutativität von Addition und Multiplikation nicht erhalten.

[9] Im Allgemeinen, wenn u_n Null ist, dann hat der kleinste Term von u_n die Form a . (b - 1)^k, wobei k eine positive ganze Zahl ist und es gilt: a < b - 1. Da die Basis um 1 größer wird und weil 1 vom Ergebnis abgezogen wird, ist die Entwicklung von u_{n+1}: a.b^k - 1 = (a - 1) . b^k + b^k - 1 = (a - 1) . b^k + (b - 1) . b^{k-2} + (b - 1) . b^{k-3} + ... + (b - 1) . b^1 + (b - 1).
Der Koeffizient der kleinsten Hochzahl der Basis ist um 1 reduziert und der Term u_n wird um eins kleiner als die neue Basis.

[10] Die Antwort lautet wie folgt: \alpha_n = \omega mit n = 29, also u_{29} = 31^1. Um u_{30}, zu erhalten, ersetzt man die Basis 31 durch die Basis 32 und subtrahiert 1. Also gilt: u_{30} = 32^1 - 1 = 31, also \alpha_{30} = 31. Da die Basis von u_{30} 32 ist und da 31 < 32, haben – beginnend mit dem Index 30 – die Folgen u_n und \alpha_n die gleichen Werte. Sie bilden eine abnehmende arithmetische Folge mit der konstanten Differenz -1, woraus dann folgt, dass u_{61} = \alpha_{61} = 0.

[11] Der Term von mn – in Tab. 3 – wurde berechnet mit: http://www.wolframalpha.com.

[12] Kirby, L. and Paris, J. (1982). Accessible Independence Results for Peano Arithmetic, Bulletin of the London Mathematical Society, 14, 285-293.

[13] Cichon, E. A. (1983). A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods, Proc. Amer. Math. Soc., 87, 704-706.

[14] Bauer, A. Java applet for the Hydra Game. (Falls das Applet in einem Browser nicht läuft, versuchen Sie es mit einem anderen Browser) Dehornoy, P. (2001) L’infini est-il nécessaire? Pour la Science, Dossier, and Dehornoy, P. (2009) Cantor et les infinis.

Anmerkung: Der Artikel wurde von Herbert Glaser, Christin Landeck und Hans-Georg Weigand (Universität Würzburg – www.dmuw.de) vom Englischen ins Deutsche übersetzt.

Weitere Klein-Artikel in in anderen Sprachen verfügbar: Englisch, Französisch, …

Andere Sprachen: Englisch, Französisch, Italienisch, Spanisch, Arabisch, Khmer, Portugiesisch, Brasilien

This entry was posted in Vignettes. Bookmark the permalink.

  1. My brother recommended I might like this web site. He was totally right. This publish truly made my day. You can not imagine just how much time I had spent for this info! Thank you!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.