Posted by: Dave Richeson | August 16, 2010

Goodstein’s unprovable theorem

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 {m_{1}}. This is the first term in the sequence. For example, suppose we begin with {m_{1}=18}.

The first step in computing the second term of the sequence, {m_{2}}, is to write {m_{1}} in hereditary base 2 notation. That is, write {m_{1}} using only powers of 2 (the base 2 expansion of {m_{1}}): {m_{1}=\sum a_{i}2^{i}}. 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 {m_{1}=18=2^{4}+2^{1}=2^{2^{2}}+2^{2^{0}}}.

To obtain {m_{2}} we change all of the 2’s to 3’s, then subtract 1. For our example, {m_{2}=3^{3^{3}}+3^{3^{0}}-1}. Notice that {m_{2}} is very large number; it is approximately {7.63\times 10^{12}}

We continue in the same way. We obtain {m_{n}} from {m_{n-1}} by writing {m_{n-1}} in hereditary base {n} notation, changing all of the {n}‘s to {(n+1)}‘s, and subtracting 1.

{m_{1}=2^{2^{2}}+2^{2^{0}}=18}

{m_{2}=3^{3^{3}}+3^{3^{0}}-1=3^{3^{3}}+2\cdot 3^{0}\approx 7.63\times 10^{12}}

{m_{3}=4^{4^{4}}+2\cdot 4^{0}-1=4^{4^{4}}+4^{0}\approx 1.34\times 10^{154}}

{m_{4}=5^{5^{5}}+5^{0}-1=5^{5^{5}}\approx 1.91\times 10^{2184}}

{m_{5}=6^{6^{6}}-1\approx 2.66\times 10^{36305}}

To obtain {m_{6}} we must express {m_{5}} in hereditary base 6 notation. First notice that

{m_{5}=6^{6^{6}}-1=5\cdot 6^{6^{6}-1}+5\cdot 6^{6^{6}-2}+\cdots+5\cdot 6^{1}+5\cdot 6^{0}.}

(An easy way to see this is that written in base 6, {6^{6^{6}}} is {100\cdots 00_{6}}, 1 followed by {6^{6}} zeros. So {6^{6^{6}}-1} is {55\cdots 55_{6}}, {6^{6}} fives.) But this expansion of {m_{5}} 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, {m_{6}} is a gigantic number.

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

Theorem. There is a {k} such that {m_{k}=0}.

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.

About these ads

Responses

  1. “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.

  2. 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!

    • 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.”

  3. 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

    • 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.

  4. 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?

    • Thanks for catching that typo. It should have been 7.63\times 10^{12}, not 6.63\times 10^{12}. I fixed it.

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

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

  6. 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.

  7. 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.

  8. 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?

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

  10. [...] 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 [...]

  11. [...] 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. [...]


Categories

Follow

Get every new post delivered to your Inbox.

Join 212 other followers

%d bloggers like this: