Wiki Googologie
Advertisement
Wiki Googologie

Une séquence de Goodstein est une certaine classe de séquences d'entiers Gk(n) qui donnent lieu à une fonction de Goodstein G(n) à croissance rapide qui finit par dominer toutes les fonctions récursives dont le total est prouvé en arithmétique de Peano (PA), mais il est lui-même prouvé qu'il est total dans PA + " est bien ordonné".[1] Ici, l'axiome supplémentaire " est bien ordonné" doit être formulé en termes d'induction transfinie le long d'une notation ordinale définissable en PA mais non prouvable bien fondée en PA.

Définition

Supposons que nous écrivions un entier non négatif n sous la forme d'une somme de puissances de k, puis nous écrivons les k exposants eux-mêmes sous la forme de sommes similaires de puissances, en répétant ce processus jusqu'à ce que nous obtenions tous les exposants supérieurs inférieurs à k. Par exemple, nous pouvons écrire 100 sous la forme 26 + 25 + 22 = 222 + 2 + 222 + 1 + 22. C'est ce que nous appelons la représentation héréditaire de base-k en tant que n.

In the above representation of 100, we can "bump" the base 2 up by one, forming a different number 333 + 3 + 333 + 1 + 33. We write this larger number as B[2](100), and in general, B[b](n) means finding the base-b hereditary representation of n and bumping the base.

Now we define the recursive sequence G0(n) = n and Gk(n) = B[k + 1](Gk - 1(n)) - 1. In other words, as k increases, we are repeatedly bumping the base and subtracting one:

G0(100) = 100 = 222 + 2 + 222 + 1 + 22
G1(100) = B[2](100) - 1 = 333 + 3 + 333 + 1 + 33 - 1 = 228,767,924,549,636
G2(100) = B[3](G1(100)) - 1 = 444 + 4 + 444 + 1 + 2 x 42 + 2 x 4 + 2 x 1 - 1 = 3.486030062 x 10156

This rapidly growing sequence is known as a Goodstein sequence. Surprisingly, for all values of n, Gk(n) eventually peaks, declines, and returns to zero. This fact is known as Goodstein's theorem. Even more surprisingly, it can be shown that Goodstein's theorem cannot be proved in Peano arithmetic.

Goodstein function

The Goodstein function, G(n) is defined as the number of steps it takes for the Goodstein sequence starting with n to terminate (i.e. reach zero). Formally, G(n) as the smallest k for which Gk(n) = 0. G(n) is an extremely fast-growing function. Note that some authors define G(n) as the length of the Goodstein sequence starting with n, which increases the outputs of the function by 1 because in this case the first step (G0(n)) is included.

Define \(R^\omega_b (n)\) to be the ordinal obtained by writing n in base-b hereditary notation, then replacing every instance of b by ω, for instance

Then \(G(n) = H_{R^\omega_2 (n)} (3) - 3\) in the hiérarchie de Hardy with Wainer hierarchy, which shows that G(2↑↑n) is .

Since this function grows faster than any function provably recursive in Peano arithmetic, Goodstein's theorem is not provable in Peano arithmetic.

Calcul

  • Comme 4 = 22
    • G(4) = Hωω(3) - 3 = fω(3) - 3 = f3(3) - 3 = f2(f2(f2(3))) - 3 = f2(f2(24)) - 3 = f2(24×224) - 3 = f2(3×227) - 3 = 3×227 × 23×227 - 3 = 3×23×227+27 - 3 = 3×2402653211 - 3
    • où f is hiérarchie de croissance rapide avec la hiérarchie de Wainer, et \(H_{\omega^\alpha}(n) = f_\alpha(n)\) pour \(\alpha < \varepsilon_0\)
    • Donc G(4) ≈ 10121210695 ≈ 10108
  • Comme 100 =
    • G(100) =
  • Comme 1024 =
    • G(1024) =
  • Comme 65536 =
    • G(65536) =
  • Comme 65540 =
    • G(65540) =
    • parce que pour tout α,β < ε0 tel que γ qui satisfait α + β = γ + β et γ < α n'existe pas, Hα+β(n) = Hα(Hβ(n))
    • Donc G(65540) ≈ fωωω (10108) (voir le calcul de G(4))

External links

Vidéos

Le théorème de Goodstein | Infini 14

Références

Advertisement