Goodstein Sequences

Given a hereditary representation of a number n in base b, let B[b](n) be the nonnegative integer which results if we syntactically replace each b by b+1 (i.e., B[b] is a base change operator that ‘bumps the base’ from b up to b+1). The hereditary representation of 266 in base 2 is,

goodstein-sequence-base-2-hereditary-representation

So bumping the base from 2 to 3 yields,

numberedequation1

We repeatedly bump the base and subtract 1.

goodstein-sequence-generation

Starting this procedure at an integer n gives the Goodstein sequence {G_k(n)}. Amazingly, despite the apparent rapid increase in the terms of the sequence, Goodstein’s theorem states that G_k(n) is 0 for any n and any sufficiently large . Even more amazingly, Paris and Kirby showed in 1982 that Goodstein’s theorem is not provable in ordinary Peano arithmetic.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s