From: Bill Daly Subject: Goodstein's Theorem Date: Thu, 17 Aug 2000 18:08:16 GMT Newsgroups: sci.math Summary: [missing] Someone once informed me that the proof of Goodstein's Theorem requires transfinite induction. I have been skeptical of this, and I believe that I have a fairly simple proof which requires only ordinary induction. If I am in error, I would like to understand where. The following is a bit longer than I would have liked for a newsgroup message, so for the sake of brevity I will omit the definitions of the Goodstein process and of Smullyan's Urn. We require the following preliminary result. Definition: A locally finite tree is a tree in which each node is of finite degree. Theorem: If a locally finite tree is of finite height, then it contains a finite number of nodes. This is easily proved by induction on the height of the tree. This theorem is better known in its contrapositive form: If a locally finite tree contains an infinite number of nodes, then there is an infinite path from the root. Smullyan's Urn can be represented by a polynomial f(X) in a dummy variable X, where each term k*X^n represents k balls labelled "n". The replacement process can then be stated as follows: 1. If a ball labelled "0" is removed, it is not replaced. In terms of f(X), this means that the term k*X^0 is replaced by (k-1)*X^0. 2. If a ball labelled "n" is removed, where n > 0, it is replaced by b balls labelled "n-1", where b is an arbitrary natural number. In terms of f(X), this means that the term k*X^n for n > 0 is replaced by (k-1)*X^n + b*X^(n-1). We can prove that the replacement process always terminates after a finite number of steps, as follows. If the replacement process for a term X^n always terminates, then the replacement process for k*X^n must also terminate, and the sum of a finite number of terms of the form k*X^n must also terminate, thus every f(X) must terminate. Thus it is sufficient to prove that the replacement process for X^n always terminates. Construct a tree in the following way: Label the root as X^n, and give it b children labelled X^(n-1), where b is the arbitrary natural number designated in step 2 of the replacement process for X^n. Then recursively for each node X^m which arises, with m > 0, give it b children labelled X^(m-1), where b is another arbitrary natural number designated in step 2 for X^m. The nodes labelled X^0 are leaf nodes, corresponding to step 1 of the replacement process. The result is a tree of finite height in which each node is of finite degree, and by the theorem stated above, such a tree contains a finite number of nodes. Since each step of the replacement process corresponds to a unique non-leaf node, there can be only a finite number of steps in the replacement process. The Goodstein process can be represented similarly. We can represent a value in the Goodstein process as a polynomial f(X) in X, whose exponents are also polynomials in X. The dummy variable X represents the current number base in the Goodstein process. For any such f(X), let min(f(X)) be the smallest term in f(X), and let notmin(f(X)) be the sum of all the terms in f(X) except min(f(X)). To decrement a value, we formally subtract 1 from f(X) according to the following rules: 1. f(X) - 1 = notmin(f(X)) + (min(f(X)) - 1). 2. If e <> 0, k*X^e - 1 = (k-1)*X^e + (X^e - 1). 3. If e <> 0, X^e - 1 = b*X^(e-1) + (X^(e-1) - 1), where b is the value of the current number base, and e-1 is the result of formally subtracting 1 from e. 4. k*X^0 - 1 = (k-1)*X^0. After decrementing f(X) in this way, the current number base (initially 2) is incremented by 1. It is natural to define f(X) - n = (f(X) - (n-1)) - 1 for all n > 0. To simplify the following argument, suppose that the value of b in step 3 above can be an arbitrary natural number. This will then include the case that the value of b is a specific natural number. We say that the Goodstein process for f(X) terminates if, for any choices of b whatsoever, there is some natural number n for which f(X) - n = 0. We define the height of a polynomial as follows: If m is a natural number, then height(m) = 1. For any term k*X^e where e <> 0, height(k*X^e) = height(e)+1. For any polynomial f(X), height(f(X)) is the height of the highest term in f(X). Suppose that we have proved that every polynomial f(X) of height less than h terminates. If every term X^e of height h terminates, then every polynomial of height h must also terminate, thus it is sufficient to show that every term X^e of height h terminates. Note that the induction hypothesis is true for h = 2, since the polynomials of height 1 are the natural numbers, and every natural number terminates. First, we must consider that the calculation of X^e - 1 creates terms X^(e-m) for all natural numbers m, but since e is of height h-1, there can be only a finite number of values e-m, since by the induction hypothesis, e-m = 0 for some natural number m. Thus, the decrementation process itself is finite. Suppose then that we construct a tree whose root is labelled X^e, and such that each node labelled X^d for d <> 0 has (b+1) children, each labelled X^(d-1). This corresponds to step 3 of the decrementation process, with one of the children representing the value (X^(d-1)-1). Note that the latter is valid, since if (b+1)*X^(d-1) terminates, then also (b+1)*X^(d-1) - 1 = b*X^(d-1) + (X^(d-1)-1) terminates. Observe that each node of this tree is of finite degree, and that there can be no infinite path from the root, since the exponent values (e-m) which arise must ultimately terminate with e-m = 0. Thus the tree must be of finite height, and therefore, by the theorem given at the beginning, the tree contains a finite number of nodes. Since the number of decrementation steps is less than the number of nodes, there can be only a finite number of decrementation steps, thus every term X^e of height h terminates, and also every f(X) of height h terminates. Since every f(X) of height 1 terminates, it follows by induction that every f(X) of finite height terminates, i.e. the Goodstein process always terminates. QED? Regards, Bill Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Torkel Franzen Subject: Re: Goodstein's Theorem Date: 17 Aug 2000 20:27:51 +0200 Newsgroups: sci.math Bill Daly writes: > Someone once informed me that the proof of Goodstein's Theorem requires > transfinite induction. I have been skeptical of this, and I believe that > I have a fairly simple proof which requires only ordinary induction. My apologies for not actually studying your proof. Goodstein's theorem does not necessarily require transfinite induction for its proof, but it's not provable in elementary arithmetic. It can be proved by ordinary induction on a statement involving quantification over sets - is this perhaps the case in your proof? ============================================================================== From: Bill Dubuque Subject: Re: Goodstein's Theorem Date: 24 Aug 2000 13:06:28 -0400 Newsgroups: sci.math Torkel Franzen writes: > Bill Daly writes: > > > Someone once informed me that the proof of Goodstein's Theorem requires > > transfinite induction. I have been skeptical of this, and I believe that > > I have a fairly simple proof which requires only ordinary induction. > > My apologies for not actually studying your proof. Goodstein's > theorem does not necessarily require transfinite induction for its > proof, but it's not provable in elementary arithmetic. It can be > proved by ordinary induction on a statement involving quantification > over sets - is this perhaps the case in your proof? Goodstein proved that tranfinite induction below the ordinal eps_0 is equivalent to convergence of all f-goodstein sequences, where an f-goodstein sequence allows a general base bumping function f:N->N. See my earlier posts for references (archived at Deja or Swarthmore). -Bill Dubuque