Ακολουθία Goodstein

Ανάπτυξη ενός αριθμού n σε υπερβάση p

Π.χ. n = 266 p =2, 266 = 2⁸ + 2³+ 2¹ = 2^a + 2³+ 2¹ , a = 2²⁺¹

Ορίζουμε μια διαδικασία "φούσκωμα" f_p(n) ενός αριθμού n στην υπερβάση p την αντικατάσταση του p με τον αριθμό p+1

Π.χ. f₂(266) = 3⁸¹+84 > 4*10³⁸

Για κάθε ακέραιο αριθμό n ορίζουμε την Ακολουθία Goodstein g ως εξής

g₁(n) = n

g_p(n) = f_p(g_p-1(n))-1

Π.χ.

n=256

g₁(256) = n, g₂(256) = 3⁸¹+84 -1, g₃(256) > 10^₆₁₆,...

Ο Reuben Goodstein απόδειξε οτι:

Για κάθε φυσικό αριθμό n η Goodstein ακολουθία μηδενίζεται,

παρόλο που αυξάνει με τρομάκτικο ρυθμό τελικά καταλήγει στο 0, και μόνο επειδή αφαιρείται ο αριθμός 1 κάθε φορά, έστω και αν φαινομενικά είναι ασήμαντος σε σύγκριση με το f_p(g_p-1(n)).

Ο αριθμός των βημάτων για το μηδενισμό είναι τρομακτικά μεγάλος, π.χ περίπου 10 στην 10⁹ βήματα για n=5

Goodstein, R., On the restricted ordinal theorem, Journal of Symbolic Logic, 9 (1944), 33-41.