Talk:Goodstein's theorem

Initial comments

I cannot find any result in the Kirby/Paris paper concerning the derivation length of the Goodstein sequence. Where should this be stated? — Preceding unsigned comment added by 138.232.192.183 (talk) 07:58, 9 July 2012 (UTC)[reply]

Said Timwi:

The undecidability of this theorem is notable, but let's define and prove the theorem first, shall we ;-)

Let's not. The theorem is completely unimportant except as an example of an undecidable but 'natural' statement of number theory. Its one and only interesting property is its undecidability. Since the undecidability is the most interesting thing about the theorem, it should be mentioned first.

Dominus 05:57, 9 Nov 2003 (UTC)

completely unimportant? Thats an extremely closeminded attitude.Rich (talk) 18:21, 22 May 2020 (UTC)[reply]

I actually found the theorem quite interesting even without the reference to its undecidability, but I'm not an expert at writing encyclopedias, so I'll not start an edit war today. :) -- Timwi 02:23, 7 Dec 2003 (UTC)

How does one prove that this theorem is independent of Peano's axioms? AxelBoldt 22:30 Nov 23, 2002 (UTC)

I wanted to put that in, but it's complicated, and I wasn't personally certain of the details. I believe that one proof is that (a) Trnasfinite induction up to ε₀ is required to prove Goodstein's theorem, because the hereditary representations after replacing n with ω are precisely elements of ε₀ (b) Gentzen showed that transfinite induction up to ε₀ was sufficient to prove the consistency of PA; (c) Gödel's second incompleteness theorem says that it's impossible to prove that a system is consistent using methods available in the system itself; so therefore, PA is not capable of doing transfinite induction up to ε₀, and therefore can't prove Goodstein's theorem.

I do have some references, however:

Simpson, Stephen G. Unprovable theorems and fast-growing functions, Contemporary Math. 65 1987, 359-394.

Smorynski, Craig. Some rapidly growing functions, Math. Intell., 2 1980, 149-154. / The Varieties of Arboreal Experience, Math. Intell., 4 1982, 182-188. / "Big" News from Archimedes to Friedman, Notices AMS, 30 1983, 251-256.

The Smorynski papers reprinted in: Harrington, L.A. et.al. (editors) Harvey Friedman's Research on the Foundations of Mathematics, Elsevier 1985.

Also perhaps: Spencer, Joel. Large numbers and unprovable theorems, Amer. Math. Monthly, Dec 1983, 669-675.

Perhaps someone with access to a good library could find an accessible independence proof, write it up, and add it to the article. Dominus 01:50 Nov 24, 2002 (UTC)

Another reference, with a proof:

L. A. S. Kirby and J. B. Paris. Accessible Independence Results for Peano Arithmetic, Bulletin of the London Mathematical Society, 14, 1982, 285-293.

See also this undergrad thesis: http://www.u.arizona.edu/~miller/thesis/thesis.html

One has to be careful when saying things like "replace every instance of n with the first infinite ordinal number ω", as in all the definitions and examples above the coefficients appear on the left, and ordinal multiplication isn't commutative. You don't want to have, e.g., 3·ω = ω, but rather ω·3... Shlomi Hillel 17:55, 10 July 2006 (UTC)[reply]

It seems that original Goodstein theorem (as written in his work) was a bit more strong. He does not restrict changing the base from 2 to 3, from 3 to 4 and so on. He says that if we have _any_ permutation of N and we will change bases accorgind to this permutation, anyway finally we will finish with 0 (starting with any natural number). And (as far as I understand) Goodstein theorem in this (strong) meaning cannot be proved from Peano axioms. It is not clear whether Goodstein theorem in the written in the article (weak) meaning cannot be proved from Peano axioms.

Yes, Goodstein states the theorem that way in his 1944 paper, which I just double-checked. But he isn't proving the independence from PA; he is just showing the the sequence must terminate. When stated in this general form, the theorem is not expressible in the language of Peano arithmetic. To make the theorem expressible in the language, you have to choose some fixed increasing function to use for the base changes. The independence result proved by Kirby and Paris was for the version of the theorem using the increasing function

n\mapsto n+1

. I don't think that the independence result would be sensitive to which increasing function you use, but checking it would be a lot of work. In any event, the theorem that is now known as Goodstein's theorem is the one mentioned in this article. CMummert 12:25, 3 November 2006 (UTC)[reply]

So actually it's well possible that this version of the theorem is possible to (state and) prove in the PA, and only the one depending on some permutation β of the naturals is not...?! And actually one cannot even say that the "full" version cannot be proved in PA, but actually the main (only?) problem is that "it cannot be expressed in PA language"?!! That's actually nice and reassuring because on a first glance it seems that one needs not to know the theory of infinite ordinal numbers, but that it should be sufficient (since actually equivalent) to "code" the numbers using "vectors" (nested lists) of finite length, together with sufficient description of how the "bump to base b+1" and "minus 1" is done with these vectors (i.e., keeping track of length and "height" of these vectors). — MFH:Talk 20:06, 19 February 2017 (UTC)[reply]

From this article:

The value 0 is reached at base 3 · 2^402653211 − 1, which, curiously, is a generalized Woodall number, just as all ...

From Woodall number:

A generalized Woodall number is defined to be a number of the form n · bⁿ − 1, where n + 2 > b

This is inconsistent as 3 ≠ 402653211. All references (and they are scarce) that I can find on the Internet suggest Woodall number's definition is the correct one, so where does this claim come from? Can 3 · 2^402653211 − 1 be written differently? If so it should be altered. --Alex Watson 21:08, 5 September 2007 (UTC)[reply]

Just move 2²⁷ from the right factor into the left. 3 · 2^402653211 = 402653184 · 2^402653184. Goplat 02:02, 18 October 2007 (UTC)[reply]

Two Firsts

Both this article and the article for Paris-Harrington theorem claim to be the first natural theorems not provable by PA. I don't know which is true, but I suspect they can't both be true at the same time. 165.125.144.16 (talk) 20:35, 13 April 2009 (UTC)[reply]

One First

The natural theorem expressible but not provable in PA is Gentzen's induction principle. He maks this very clear in 1943 and it has been noted many times, e.g., in Schwichtenberg's paper in the Handbook of Mathematical Logic, ed. Barwise. 1977. —Preceding unsigned comment added by SternJacob (talk • contribs) 13:54, 24 May 2009 (UTC)[reply]

What about CON(PA), certainly a natural statement since the whole Hilbert school was chasing after a proof of it before Gödel showed that was impossible? I guess both CON(PA) and Gentzen's induction principle would count as "metamathematical", though I personally don't see why that should matter. 67.122.209.126 (talk) 07:52, 1 June 2009 (UTC)[reply]

ordinal strength

Is there some analysis of the ordinal strength of this theorem? It looks to me like it follows from induction on $\epsilon _{0}$ , which makes it equivalent to CON(PA), but the article doesn't come out and say so, and I might be missing something. Could someone knowledgeable update the article one way or another? Thanks. 67.122.209.126 (talk) 12:03, 1 June 2009 (UTC)[reply]

Question on Proof

"for example, $\omega ^{\omega ^{\omega }}+\omega$ decreases to $\omega ^{\omega ^{\omega }}+4$ " - well I somewhat get that. However, can someone please describe what happens when we decrease $\omega ^{\omega ^{\omega }}+\omega$ ? --Hirak 99 (talk) 19:49, 2 November 2009 (UTC)[reply]

If you start with

4^{4^{4}}+4

, which corresponds to

\omega ^{\omega ^{\omega }}+\omega

, the next element in the Goodstein sequence is

5^{5^{5}}+5-1=5^{5^{5}}+4

, which corresponds to

\omega ^{\omega ^{\omega }}+4

because only the 5s are replaced by ωs. If this is not what you are asking, could you rephrase your question? — Carl (CBM · talk) 19:57, 2 November 2009 (UTC)[reply]

Connected to Sprouts?

The Hydra game appears to be a derivation of Sprouts (game). —Preceding unsigned comment added by Dexter Nextnumber (talk • contribs) 22:46, 9 January 2010 (UTC)[reply]

Improving the main page of this Article

This is excerpted from the main page:

 "In order to define a Goodstein sequence, first define hereditary base-n notation."

Shouldn't hereditary base-n notation be given an article all unto itself? The definition given so far, may make sense to a professional mathematician, but somehow the underlying gist escapes me, a fairly ordinary person.

The main page of this article describes "Base 2 notation" but wouldn't standard binary notation make a lot more sense? Isn't Base 2 the same thing as binary? I think a lot more people would understand 35 in binary to be %00100011, and not 2 ^ 2 ^ 2 + 1. I guess all I am saying, is that the example given in the main page, seemed/seems to proceed from the assumption that binary was not the same thing as base 2, and base 2 was not binary, even though all these years (over 25 years) I have assumed the two were one and the same.

Articles written for Wikipedia should not be dumbed down, but they should be organized in such a way that ordinary people can make heads or tails out of what you are saying. If you want to use 35 as an example for some strange superscript/subscript notation system, you might want to start out by saying how far above the baseline of the text counts as superscript, and how much farther it has to go, to be super-superscript, and conversely, how far below the baseline you should go, to make it a subscript, and so on. Naturally, I will assume you are already familiar with Hewlett-Packard Laserjet escape sequences since those sequences are a worldwide standard after all these years. Now that you have done that, what is the purpose in raising numbers up to a superscript, or bringing them down to a subscript. Are you suggesting they have exponential effects of some kind? In any case, don't pepper your examples up with 'C" source code, that's downright inscrutable. Just frame your argument in terms of ordinary lines of BASIC code, if you will, and I, like many others who come by this area, will probably understand what you are talking about. Dexter Nextnumber (talk) 09:58, 10 January 2010 (UTC)[reply]

This theorem is more or less the only place that hereditary base-n notation is used. So having an extra article on that would probably give it more weight than it deserves. When people learn the theorem, they are not likely to be familiar with hereditary base-n notation first.

You are right that "hereditary base 2 notation" is not the same as "base 2 notation", but they are ver similar. In base 2, 35 is %100011 which means

35 = 1*2^5 + 0*2^4 + 0*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 2^5 + 2^1 + 2^0

Note that the exponent "5" is not itself in base 2 notation. So in hereditary base 2 notation, we would write

35 = 2^(2^2 + 2^0) + 2^1 + 2^0.

Now everything is in base 2, including the exponents. — Carl (CBM · talk) 12:31, 10 January 2010 (UTC)[reply]

Why is this notation system called "hereditary"? This basically looks like a way of avoiding superscripts (upward departures from the baseline). Dexter Nextnumber (talk) 22:51, 11 January 2010 (UTC)[reply]

No, it does not avoid superscripts; 2^(2^2 + 2^0) + 2^1 + 2^0 means

2^{(2^{2}+1)}+2^{1}+1

. "Hereditary" means that everything is put into base n notation, not just the first level. — Carl (CBM · talk) 22:56, 11 January 2010 (UTC)[reply]

Unless I'm failing to see something, this expression is not a base-2 expression on any level, let alone on all levels, since it contains the digit 2. A base-n expression cannot contain a digit representing n, just like base-10 doesn't have a single digit representing the number 10. Denis Kasak (talk) 06:39, 20 July 2018 (UTC)[reply]

It is a base-2 expansion, so a sum of powers of 2, not a base-2 expression. You start by expanding 35 as such a sum, viz. 35 = 2^5 + 2^1 + 2^0. Then you do the same for all of the exponents you used in that base-2 expansion: replace them with their base-2 expansions, so 5 = 2^2 + 2^0, 1 = 2^0, and then 35 = 2^(2^2+2^0) + 2^(2^0) + 2^0. That corresponds to the base-2 expression 100011. This doesn't quite agree with the way the article writes it, though I don't think it makes a difference to the construction since b^0=1 for any b anyway. 100.14.63.221 (talk) 04:38, 24 December 2022 (UTC)[reply]

Hydra games

The article had contained the following two external links (the second one, recently added, being to a page of my own creation):

A user removed the second link (but left the first one), commenting that it was "not directly related". However, trees can be represented using either graphs (as at the first link) or by using bracket expressions (as at the second link). The relationship to Goodstein's theorem is exactly the same for both representations of the Hydra game, so I suggest a more evenhanded treatment. The fact that the second link presents the game as the execution of a "program" composed of trees, and also explains a more general form of the game, would hardly seem to matter in this regard. On the other hand, if the concern is really about academic or other credentials (rather than relevancy), then I don't wish to pursue the matter. Discussion? — r.e.s. (talk) 12:53, 8 April 2010 (UTC)[reply]

I lean toward removing both, actually, but you really shouldn't add a link to your own research, even though your academic credentials are not being questioned—it's not a matter of academic credentials, but of WP:EL#ADV. I think relevancy may have been the wrong reason for deletion, and I apologize for not checking more carefully. I'll to consider this more closely, and determine whether your page is the better one; if so, I'll restore it. — Arthur Rubin (talk) 13:53, 8 April 2010 (UTC)[reply]

Perhaps it would be best to have a WP page on Hydra games; but, lacking that, I hope at least one of these links is retained. If it's a choice between the two, I recommend the first link, since pictorial graphs are the "standard" and are probably visually preferable. Aside from some generalisations, the second link primarily shows how these games can be played using bracket expressions rather than graphs. — r.e.s. (talk) 14:26, 8 April 2010 (UTC)[reply]

a statement made?

The lede is carefully worded to avoid giving the impression that the result can be "proved" in PA but as a result the lede never actually states that Goodstein actually proved anything, only "stated". Should this be clarified? Tkuvho (talk) 11:53, 14 May 2012 (UTC)[reply]

Yeah, that's silly. The easiest solution is just to say "proved", and then explain further down how much strength you need to prove it, and that that's more than PA. --Trovatore (talk) 19:15, 14 May 2012 (UTC)[reply]

Proof of termination of Goodstein sequence

I corrected the proof since there were a misunderstanding of the argument (G(m) does note converge, G(m) terminates, the fact that P(m) dominates G(m) plays no role at all). Please carefully read it before blind cancellation of my edit... ;-) — Preceding unsigned comment added by Gasole (talk • contribs) 10:02, 18 May 2014 (UTC)[reply]

" ....an infinite strictly decreasing sequence cannot exist, or equivalently, every strictly decreasing sequence of ordinals do terminate (and cannot be infinite)." The grammar seems to have gone awry here. Most of us use a singular verb after "every". "All things come to an end" but "Every man comes to an end". Apart from that, the statement seems (to the uninitiated) incorrect. The sequence ω, ω - 1, ω - 2 .... looks strictly decreasing to me and it seems to go for ever. I think non-specialists would appreciate either a bit more explanation here or a reference to an article which explains the meaning of the statement about strictly decreasing sequences and proves that is true.

Bukovets (talk) 10:55, 3 December 2014 (UTC)[reply]

I think you're absolutely right on the grammar. (There's a tiny question in my mind whether this could be a Yank–Brit difference but I don't think so.) I'll fix it if no one else does.

On your other point — you can't get an ordinal smaller than ω by subtracting 1. Every ordinal less than ω is finite. The expression "ω−1" either does not make sense at all, or else evaluates to ω, depending on your notational choices.

As to how to explain this to non-specialists, open to suggestions. Is a detailed explication of the notion of ordinal really on-topic here? Maybe it actually would be OK to say a little about it. Usually I'm skeptical about that sort of digression, but this is a topic where you might expect to attract readers who haven't really seen the concept, and it's central to the argument. --Trovatore (talk) 16:28, 3 December 2014 (UTC)[reply]

Sorry to be dim but if ω - 1 equates to ω how can we say that P(m) decreases? Surely P(m + 1)= P(m) Bukovets (talk) 00:40, 6 December 2014 (UTC)[reply]

As an ordinal number, using subtraction, ω - 1 = ω in the sense that 1 + (ω - 1) = ω. As an ordinal number, ω - 1, in the sense that (ω - 1) + 1 = ω, doesn't exist. As a surreal number, ω - 1 does exist, but has nothing to do with this topic. — Arthur Rubin (talk) 17:26, 11 December 2014 (UTC)[reply]

Thanks for clarifying that ordianls are not the same a surreal numbers. I get it now ω is not replaced by ω - 1 but by some number which is always finite. But I still think the articel could be clearer. Bukovets (talk) 00:06, 15 December 2014 (UTC)[reply]

Reformatting

Long time no edit …

I converted many of the inline < math> tags with no more than one level of super/subscript to inline HTML, and corrected the italicization of such phrases as G(m)(n) to G(m)(n). (This looks more clear when you edit it in WikiText mode; using the Visual Editor does not see the difference.) If anyone objects, please let me know. — Arthur Rubin (talk) 23:23, 21 June 2015 (UTC)[reply]

Bad proof

The whole para “Then f(G(m)(n), n+1) = f(G'(m)(n), n+2). Now we apply the minus 1 operation, and f(G'(m)(n),n+2) > f(G(m)(n+1),n+2), as G'(m)(n)=G(m)(n+1)+1. […] is not an ordinal.” is hard to understand. Could please someone rewrite it starting with simple steps and ending with conclusions? Already the second sentence is not understandable, and the whole para (in fact, the whole claim) needs a complete clean rewrite from scratch. A so-called “example” is not helpful the way it is written. Even if it were, an example is not a proof. — Preceding unsigned comment added by PeterMuellerr0 (talk • contribs) 20:51, 2 February 2024 (UTC)[reply]

I don't think it's that bad. Apparently the first sentence is considered self-evident since it just says replacing the base n+1 by n+2 and then n+2 by ω is equivalent to directly replacing n+1 by ω. The second sentence makes use of the fact that f(u, k) is strictly monotone in u (which is maybe not that obvious, but at least somewhat intuitive), and the part after "as" is just the observation G(m)(n+1)=G'(m)(n)-1 from the last paragraph stated in reverse. It probably could be better, but it's not that bad. Bbbbbbbbba (talk) 05:56, 30 May 2024 (UTC)[reply]