Jump to content

User:Sligocki/Goodstein sequences

From Wikipedia, the free encyclopedia
This article is now available on my blog: https://www.sligocki.com/2009/10/14/goodstein-sequences.html

Goodstein sequences are very long sequences which eventually reach 0, but run for so long that Peano arithmetic cannot be used to prove that they reach 0.

Introduction

[edit]

Let be the Goodstein sequence starting with n and ending at 0.

Let be the base of the hereditary notation of the last term of (Alternatively, it is the length of the Goodstein sequence + 1). We shall call these the Goodstein numbers

0 2
1 3
2 5
3 7
4

Now, in fact, if , then . I show that this function has a meaning.

Growth of Goodstein Numbers

[edit]

Let us define a family of functions:


Ah ha,

  • and


In fact:

0 2
1
2
3
4
5
6
7

Notice the pattern? If appears in then (where B is the base and k<B). Likewise, if appears, then .


In fact, let's rename our functions (here is a label, not a variable — in fact, it is actually an ordinal number, or generalized index, who's properties I hope to take advantage of):

And add a new one:

Thus, if we have a value of the form at base B in , then .

Derivation of Growth Function

[edit]
Note: It turns out that the function I define here is a variant of the fast-growing hierarchy much like the Hardy hierarchy.

Goodstein talks about the hereditary form of a number and the unique ordinal number associated with each hereditary form. For example:

is in form

Let us identify the hereditary form with that ordinal number.

If N has hereditary form with base B, then let be the base at which the the Goodstein sequence starting at N in base B will end.

For some values of :







Note: . So Graham's number .

Now where we remember that . So,





...


Now let's look back at the table:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16