Goodstein Theorem

On reading a magazine on Gödel’s Incompleteness Theorems, I came across a family of sequences of non-negative integers called Goodstein sequences and the Goodstein Theorem involving these sequences.

Goodstein’s thoerem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence converges to 0.

What is a Goodstein Sequence?

To understand what a Goodstein sequence, first we must understand what hereditary base-n notation is. Whilst this notation is very similar to the usual base-n notation, base-n notation is not sufficient for Goodstein’s theorem.

To convert a base-n representation to a hereditary base-n notation, first rewrite all of the exponents in base-n notation. Then rewrite any exponents inside the exponents, and continue this way until every number in the expression has been converted to base-n notation.

For example, 35 = 25 + 2 + 1 in ordinary base-2 notation but Screen Shot 2017-07-11 at 5.37.45 PM.png in hereditary base-2 notation.

Now we can define the Goodstein sequence G(m) of a natural number m. In general the (n+1)-st term G(m)(n+1) of the Goodstein sequence of m is given as follows (taken from Wikipedia):

  • Take the hereditary base-n + 1 representation of G(m)(n).
  • Replace each occurrence of the base-n + 1 with n + 2.
  • Subtract one. (Note that the next term depends both on the previous term and on the index n.)
  • Continue until the result is zero, at which point the sequence terminates.

In spite of the rapid growth of the terms in the sequence, Goodstein’s theorem states that every Goodstein sequence eventually terminates at 0, no matter what the starting value is.

Mathematicians Laurie Kirby and Jeff Paris proved in 1982 that Goodstein’s theorem is not provable in ordinary Peano arithmetic. In other words, this is the type of theorem described in 1931 by Gödel’s incompleteness theorem.

M x

Advertisements

4 comments

  1. You actually make it seem really easy with your presentation however I to find this matter to be actually one thing that I believe I’d never understand. It kind of feels too complicated and extremely extensive for me. I’m having a look forward to your next submit, I will try to get the dangle of it!

    Like

  2. Great blog right here! Also your site lots up fast! What web host are you the use of? Can I get your associate link in your host? I desire my site loaded up as fast as yours lol

    Like

  3. Great blog here! Also your web site lots up fast! What web host are you the use of? Can I am getting your affiliate hyperlink on your host? I desire my web site loaded up as quickly as yours lol

    Like

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