Recently I learned about a family of sequences of nonnegative integers (called Goodstein sequences) and two remarkable theorems about these sequences.

Begin with any positive integer . This is the first term in the sequence. For example, suppose we begin with .

The first step in computing the second term of the sequence, , is to write in *hereditary base 2 notation*. That is, write using only powers of 2 (the base 2 expansion of ): . Then write all of the exponents in their base 2 expansions. Then write all of the exponents of the exponents in that way, etc. Our number written in hereditary base 2 notation is .

To obtain we change all of the 2′s to 3′s, then subtract 1. For our example, . Notice that is very large number; it is approximately

We continue in the same way. We obtain from by writing in hereditary base notation, changing all of the ‘s to ‘s, and subtracting 1.

To obtain we must express in hereditary base 6 notation. First notice that

(An easy way to see this is that written in base 6, is , 1 followed by zeros. So is , fives.) But this expansion of is not in hereditary base 6 notation yet. We must express the towers of exponents in base 6, etc. When that is done, we replace the 6′s with 7′s and subtract 1. In the end, is a gigantic number.

Now here are two amazing theorems about this sequence of integers. In 1944 Reuben Goodstein proved:

**Theorem.** There is a such that .

That is, this sequence, which looks like it is rocketing to infinity, will eventually become zero and terminate. Wow! The proof of this theorem is very sophisticated and uses the theory of ordinal numbers.

I’ll have to file this sequence away as an example that shows why we can’t use the behavior of the first few (or first few million) terms of a sequence to determine the limiting behavior of a sequence.

Then, in 1982 Laurie Kirby and Jeff Paris proved the following theorem.

**Theorem.** Goodstein’s Theorem is not provable using the Peano axioms of arithmetic.

In other words, this is exactly the type of theorem described in 1931 by Gödel’s first incompleteness theorem!

Recall what Gödel’s theorem says. If there is an axiomatic that is rich enough to express all elementary arithmetic (such as that formed from the Peano axioms), then it must be incomplete. In other words, there must be a true statement about arithmetic that cannot be proven from the axioms. In his proof Gödel produces an explicit example of a true, but unprovable statement. But it is complicated to grasp and more reminiscent of a logical paradox than a mathematical statement.

The first nice mathematical example of such a statement was presented in 1977 by Paris and Harrington (in a field called Ramsey theory). Then in 1982 Kirby and Paris proved that Goodstein’s theorem was unprovable and they gave another elementary example, called “Hercules versus the hydra,” which relates to the growth of the hydra (a tree) and its destruction by Hercules.

“In other words, this is exactly the type of theorem predicted in 1931 by Gödel’s first incompleteness theorem!”

Heuristic correction: Godel didn’t “predict” unprovable theorems, he PRESENTED A RECIPE to generate lots and lots of unprovable theorems.

It’s possible by that word “predicted” you were gesturing toward the common noob complaint “but those aren’t “real” or “natural” theorems! they’re so contrived!”. If that’s the issue, then whatever. Theorems are theorems.

Math doesn’t discriminate against its theorems – only mathematicians do. And in the case of Godelian issues, typically only those mathematicians who don’t much bother with “fringe” maths.

By:

sherifffruitflyon August 17, 2010at 12:09 am

Great post! The summer is a good time to be one of your blog readers.

@sherifffruitfly I don’t understand the distinction you are making. Correct me if I’m wrong, but while Godel’s first incompleteness theorem proved the existence of such theorems and provided examples, it certainly did not enumerate the ways to construct all such theorems.

Therefore one could certainly say that Goodstein’s theorem “is exactly the type of theorem **described** in 1931 by Gödel’s first incompleteness theorem.” Checking the etymology of “predict” (and our intuitive sense of the word) “describing in advance” is a reasonable definition, which is exactly the sense in which it was used.

Don’t be so hasty!

By:

Brendanon August 17, 2010at 1:47 am

Thanks for the kind words Brendan! @sherifffruitfly I see what you’re saying that “predicted” probably isn’t the best word choice, although I don’t think it is as bad as you do—I like Brendan’s suggestion of “described.”

By:

Dave Richesonon August 17, 2010at 8:20 am

Very nice – I have been thinking about unprovable theorems a bit, as I recently wrote an article about recent progress in the field: http://www.newscientist.com/article/mg20727731.300-to-infinity-and-beyond-the-struggle-to-save-arithmetic.html?full=true

The lexicon of ‘concrete’ unprovable theorems is more well developed than one might expect. See e.g 48. Unprovable theorems, here:

http://www.math.ohio-state.edu/~friedman/manuscripts.html

Fast growing sequences and gigantic numbers play a prominent role. Another very striking example is H. Friedman’s (again!) finite version of Kruskal’s theorem on trees:

http://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem

By:

Richard Elweson August 17, 2010at 11:55 am

I *meant* to link to your New Scientist article in my blog post—sorry about that. I read your article yesterday and saw the blurb about the Paris/Harrington theorem at theend—it was the first time I’d seen that. It is fascinating. I’m no expert on any of this, but I’ve read all or part of 4 or 5 books on Russell, Gödel, etc. in the last few months. So your article really caught my attention. Thanks.

By:

Dave Richesonon August 17, 2010at 12:12 pm

How does 3^3^3 + 3^3^0 become 6.63 * 10^12 ????

The only way I can get 6.63 * 10^X is by cubing 3 seven times :

3^3^3^3^3^3^3 = 6.628 * 10^347

What’s wrong?

By:

Vivekon August 17, 2010at 1:59 pm

Thanks for catching that typo. It should have been , not . I fixed it.

By:

Dave Richesonon August 17, 2010at 2:35 pm

The link to Gödel’s first incompleteness theorem needs correcting.

By:

Matthewon August 18, 2010at 2:28 pm

Thanks. My blog editor apparently didn’t like the “ö” in the url.

By:

Dave Richesonon August 18, 2010at 2:36 pm

I don’t understand. If there exists a k such that m_k=0, then there should be a trivial proof. All you need to do compute each m_n until you reach m_k=0. Since k exists, this computation will take finite time, and your proof will be of finite length and won’t do anything beyond simple computation.

Sure it’ll take a long time, and we don’t know what the proof will be, but it seems clear that such a proof exists.

If the theorem is true, the only way I can see it being unprovable using the Peano axioms of arithmetic is if you can’t compute m_(n+1) from m_(n) using the Peano axioms of arithmetic, which would mean you can’t even prove what m_2 is.

By:

Mark Jameson August 18, 2010at 11:58 pm

Okay, I misunderstood the problem.

The theorem says that for all m_1 there exists a k such that m_k = 0, not just that if m_1 = 18 there exists a k such that m_k = 0.

By:

Mark Jameson August 19, 2010at 3:19 am

It’s things like this that drive me to want to continue studying mathematics at the graduate level, so I can understand and grasp these proofs. Is either proof particularly elegant or beautiful?

By:

Justinon September 2, 2010at 2:49 am

[...] 一个不可证的定理-从一个数列说起 October 3, 2010 dementrock Leave a comment Go to comments 我在这里看到了这个有趣的数列及由其引出的一些奇特的结论。 [...]

By:

一个不可证的定理-从一个数列说起 « Dementrock's Blogon October 3, 2010at 5:56 am

[...] were expressible in the language of Peano arithmetic itself. In fact, the recently discovered Goodstein’s Theorem is a super-simple number theory statement that you can prove easily using ordinals and ZFC, but [...]

By:

A Couple Nuances « Gracious Livingon December 6, 2010at 4:02 am

[...] We understand that Godel_0 promises exist, with one another with many good examples are actually found out “in the wild” that occur to be not created explicitly for this purpose, as in this article. [...]

By:

Are recursive forms of Godel's statement possible? | Q&A Systemon January 2, 2012at 8:45 pm