Number Theory Problem
Richard Carr
I remember reading about this problem on sci.math one time:
take a natural number n and write it in base 2, with the
exponents in base 2 etc.
e.g. 53=2^{2^2+1}+2^{2^2}+2^2+1.
Then replace the 2's by 3's and subtract 1 and write it in base 3.
3^{3^3+1}+3^{3^3}+3^3.
Then replace the 3's by 4's and subtract 1 and write it in base 4.
4^{4^4+1}+4^{4^4}+4^4-1=4^{4^4+1}+4^{4^4}+3.4^3+3.4^2+3.4+3
etc.
The problem is to show that this sequence eventually hits 0,
independent of which n you start at.
It is "fairly easy to see" that this is going to happen for any given n,
although it will generally take a long time to go to 0. For instance, by
direct computation one finds that if n=4, then one needs to go to the
(2^{402653211}3-3)rd term (starting at 0)- see below.
Apparently one cannot prove this for all n in ZFC (although one can for
individual n) but one can with some large cardinal assumption. I have
never seen a reference for it though. Does anybody know of such a
reference? This is to settle an quarrel (not a bet) with a number theory
colleague that there are number theoretical statements that cannot be
proven in ZFC but can with additional (large cardinal) assumptions.
Since my claim was based on this result, which I read about here, I
assume somebody knows something about it. On the other hand, if I am
mistaken and you can prove me wrong then that will be equally good.
Anyway, this guy wants a reference with a proof because he says sci.math
isn't a good enough source if without references or proof (which is fair
enough).
(To "see" that it works in general look convince yourself that after a
certain point all you do is keep subtracting 1, an awful lot of times.
This occurs as soon as you are at the stage "replace all r's by (r+1)'s
but everything is less than r.
The following is an example, not a proof of course (I will start
counting terms from 2, not 0, to facilitate notation and then subtract 2
from the number I get at the end.):
n=4
2: 2^2=4
3: 3^3-1=2.3^2+2.3+2=26 (Here the square changed into a cube but then
went back to a square again- it will not increase again. Generally, it
may increase for a while before falling.)
4: 2.4^2+2.4+1=41
5: 2.5^2+2.5=60
6: 2.6^2+6+5=83
7: 2.7^2+7+4=109
11: 2.11^2+11=253
12: 2.12^2+11=299
23: 2.23^2=1058
24: 24^2+23.24+23=1151 (Now the squared term has a coefficient of just
1.)
47: 47^2+23.47=3290
48: 48^2+22.48+47=3407
402653183: 402653183^2 (To get from r: r^2+sr to
v: v^2+(s-1)v, where s<r, just note that v=2r+3 (not in the general
case, of course). For, r+1: (r+1)^2+(s-1)(r+1)+r and then the next r
terms increase the r+1 by r, decrease the r to 0 and leave the s-1
fixed, arriving at 2r+1: (2r+1)^2+(s-1)(2r+1). Applying this to r=47 and
s=23<47 we go first to 95, then to 191 etc. (s decreases so certainly
remains less than r, as r is increasing.)
i.e. we iterate the operation 2m+1 (ith initial value 47, say), 23
times, finally arriving at 402653183.
402653184: 402653183.402653184+402653183 (finally, we have eliminated
the quadratic part).
805306367: 402653183.805306367 (the next 402653183 after 402653184
eliminated the 402653183 in the "units" place while increasing the
base).
805306368: 402653182.805306368+805306367
Note that to go from r: s.r+r-1 to v: (s-1).v+v-1 one just has to double
r, v=2r, provided that s<r of course. Since r-1,s<r one gets to
2r-1: s(2r-1) by reducing the r-1 in the "units" column (which is less
than the base), successively by 1, increasing the base succesively by 1
and keeping s (which is less than the base) fixed. Then one gets
2r: s.2r-1=(s-1).2r+(2r-1) as required.
Applying this 402653182 times, one arrives at
2^{402653182}805306368: 2^{402653182}805306368-1
or, since 805306368=2^28.3,
2^{402653210}3: 2^{402653210}3-1
Now the base is bigger than anything on the right (we have got to the
units column) so we keep subtracting 1:
2^{402653211}3-2: 1
2^{402653211}3-1: 0
Now I recall that I started counting at 2 instead of 0, so I really took
2^{402653211}3-3 iterations to get to 0.
A simpler example takes n=3:
0: 3=2^1+1
1: 3=3^1+0
2: 3 (=4^1-1 which is 3 in base 4)
3: 2
4: 1
5: 0
So it only takes 5 iterations to get to 0, that is the sixth term of the
sequence is 0.
"Analyzing is paralysing, Mister" - Tilt
Robin Chapman
In article <35516712...@math.columbia.edu>,
Richard Carr <ca...@math.columbia.edu> wrote:
Before starting, I should point out that I have only a very dim understanding
of the issues involved here, and I don't know where the references
may be found, but when has that ever stopped anyone on USENET?
No. This can be settled in ZF. It's known as Goodstein's theorem.
What it can't be proved in is the usual first-order formalization N
of the theory of natural numbers (language including symbols for 0,
successor, + and x, axioms including schema for induction).
The proof of Goodstein is really beautiful. At each stage you have
an expression involving sums and powers of a number k, successively
2, 3, 4 etc. Simply replace this number k by the first infinite ordinal
omega. For instance the first three terms in Richard's example become
omega^{omega^omega+1}+omega^{omega^omega}+omega^omega+1,
omega^{omega^omega+1}+omega^{omega^omega}+omega^omega, and
omega^{omega^omega+1}+omega^{omega^omega}+omega^3.3+omega^2.3+omega.3+3
etc. Now one sees that these infinite ordinals always form a DECREASING
sequence. By well-ordering the series terminates. This depends on the set of
ordinals below epsilon_0 (the first fixed point of the map a:|--> omega^a)
being well-ordered.
I think the independence proof goes something like this: Gentzen gave
a consistency proof of first order arithmetic N, using the technique
of "cut-elimination". But whay does this not contradict Godel? It's
because Gentzen's method used in effect transfinite induction on the
initial segment of ordinals below epsilon_0 (certainly OK in ZF).
This principle can be formalized in N somehow, but the moral of Godel's
theorem is that this transfinite induction schema contains instances
which are not deducible from the axioms of N. Now I think that from
Goodstein one can deduce this full induction schema and so Goodstein
is not provable in N.
There are other results of this nature: Paris and Harrington proved
a Ramsey-type result which requires transfinite induction up to a much
larger (but still countable) ordinal than epsilon_0. As for large cardinals,
their existence will imply arithmetic results, but as for examples,
my ignorance is total.
Robin Chapman + "They did not have proper
Department of Mathematics - palms at home in Exeter."
University of Exeter, EX4 4QE, UK +
r...@maths.exeter.ac.uk - Peter Carey,
http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/ Now offering spam-free web-based newsreading
Bill Dubuque
Below is one of my posts on Goodstein's theorem, which contains
plenty of references if you desire further details. See also
Simpson's excellent exposition [Sim] which is available in one
of my prior posts, cf. the URL at [Sim] in the biblio below.
-Bill Dubuque
From: w...@zurich.ai.mit.edu (Bill Dubuque)
Newsgroups: sci.math
Subject: Re: Goedel's theorem: about anything in real world?
Date: 11 Dec 95 02:34:50
Kenneth A. Regas <k...@sqrt-1.com> wrote on 10 Dec 1995:
|
| ... What I'm getting at here is that G [Godel's undecidable
| sentence] is not the kind of sentence that one would come up
| against and be obliged to evaluate in the world of physical
| phenomena. It seems to be purely a product of "formal systems."
|
| It is my layman's understanding that Goedel's proof relies
| upon constructing a proposition like G. In that case,
| does Goedel's theorem have anything to say about "old
| mathematics" the kind that scientists and engineers are
| taught, wherein which "statements" such as G don't come up?
Yes, recent discoveries yield a number of so-called 'natural
independence' results that provide much more natural examples
of independence than does Godel's contrived example based upon
the liar paradox. See the bibliography below. In particular,
your question is essentially the title of Gina Kolata's
article "Does Godel's theorem matter to mathematics?",
referenced below.
As an example of such results, I'll sketch a simple example due
to Goodstein of a concrete number theoretic theorem whose proof
is independent of formal number theory (following [Sim]).
Let b be a positive integer >= 2. Any nonnegative integer n
can be written uniquely in base b representation:
n n
1 k
n = c b + ... + c b
1 k
where k >= 0, 0 < c < b, n > ... > n >= 0, for i = 1, ..., k.
i 1 k
For example the base 2 representation of 266 is
8 3
266 = 2 + 2 + 2
We may extend this by writing each of the exponents n , ..., n
1 k
in base b notation, then doing the same for each of the exponents
in the resulting representations, ... until the process stops.
This yields the so-called 'hereditary base b representation of n'
For example the hereditary base 2 representation of 266 is
2 + 1
2 2 + 1
266 = 2 + 2 + 2
Let B[b](n) be the nonnegative integer which results if we take the
hereditary base b representation of n and then syntactically replace
each b by b+1, i.e. B[b] is a base change operator that 'Bumps the Base'
from b up to b+1. For example bumping the base from 2 to 3 in the above
equation yields
3 + 1
3 3 + 1
B[2](266) = 3 + 3 + 3
Consider a sequence of integers obtained by repeatedly applying
the operation: bump the base then subtract one from the result.
For example, iteratively applying this operation to 266 yields
2 + 1
2 2 + 1
266[0]:= 2 + 2 + 2 = 266
3 + 1
3 3 + 1
266[1] = 3 + 3 + 3 - 1 = B[2](266[0]) - 1
3 + 1
3 3 + 1
= 3 + 3 + 2
4 + 1
4 4 + 1
266[2] = 4 + 4 + 1 = B[3](266[1]) - 1
5 + 1
5 5 + 1
266[3] = 5 + 5 = B[4](266[2]) - 1
6 + 1 .
6 6 + 1 .
266[4] = 6 + 6 - 1 .
7
using 6 - 1 = 10000000 - 1 = 5555555 in base 6
6 + 1
6 6 5
= 6 + 5 6 + 5 6 + ... + 5 6 + 5
7 + 1
7 7 5
266[5] = 7 + 5 7 + 5 7 + ... + 5 7 + 4
.
.
.
266[k+1] = ... = B[k+2](266[k]) - 1
In general, if we start this procedure at the integer n then
we obtain what is known as the Goodstein sequence starting at n.
More precisely, for each nonegative integer n we recursively define
a sequence of nonnegative integers n[0], n[1], ..., n[k], ... by
n[0] := n
[ B[k+2](n[k]) - 1 if n[k] > 0
n[k+1] := |
[ 0 if n[k] = 0
for all k >= 0.
If we examine the above Goodstein sequence for 266 numerically
we find that the sequence initially increases quite rapidly:
2^2^(2+1)+2^(2+1)+2 ~= 2^2^3 ~= 3 10^2
3^3^(3+1)+3^(3+1)+2 ~= 3^3^4 ~= 4 10^38
4^4^(4+1)+4^(4+1)+1 ~= 4^4^5 ~= 3 10^616
5^5^(5+1)+5^(5+1) ~= 5^5^6 ~= 3 10^10921
6^6^(6+1)+5*6^6+5*6^5+..+5*6+5 ~= 6^6^7 ~= 4 10^217832
7^7^(7+1)+5*7^7+5*7^5+..+5*7+4 ~= 7^7^8 ~= 1 10^4871822
8^8^(8+1)+5*8^8+5*8^5+..+5*8+3 ~= 8^8^9 ~= 2 10^121210686
9^9^(9+1)+5*9^9+5*9^5+..+5*9+2 ~= 9^9^10 ~= 5 10^3327237896
10^10^(10+1)+5*10^10+5*10^5+..+5*10+1 ~= 10^10^11 ~= 1 10^100000000000
Nevertheless, despite appearances, it can be proved that this
sequence converges to 0. In other words, 266[k] = 0 for all
sufficiently large k. This surprising result is due to Goodstein
(1944) who actually proved the same result for *all* Goodstein
sequences:
GOODSTEIN'S THEOREM. For all n there exists k such that n[k]=0.
In other words every Goodstein sequence converges to 0.
The secret underlying Goodstein's theorem is that the hereditary
expression of n in base b mimicks an ordinal notation for
ordinals less than eps[0]. For such ordinals, the base bumping
operation leaves the ordinal fixed whereas the subtraction of
one decreases the ordinal. But these ordinals are well-ordered
and this allows us to conclude that a Goodstein sequence
eventually converges to zero. Goodstein actually proved his
theorem for a general increasing base-bumping function f:N->N
(vs. f(b)=b+1 above) and he showed that convergence of all such
f-Goodstein sequences is equivalent to transfinite induction
below the ordinal eps[0].
One of the primary measures of strength for a system of logic is
the size of the largest ordinal for which transfinite induction
holds. It is a classical result of Gentzen that the consistency
of PA (Peano arithmetic, or formal number theory) can be proved
by transfinite induction on ordinals below eps[0]. But we know
from Godel's second incompleteness theorem that the consistency
of PA cannot be proved in PA. It follows that neither can
Goodstein's theorem be proved in PA. Thus we have an example of
a very simple concrete number theoretical statement in PA whose
proof is nonetheless independent of PA.
Another way to see Goodstein's theorem cannot be proved in PA
is to note that the sequence takes too long to terminate, e.g.
4[k] first reaches 0 for k = 3*(2^402653211-1) ~= 10^121210695
In general, if 'for all n there exists k such that P(n,k)' is
provable, then it must be witnessed by a provably computable
choice function F: 'for all n: P(n,F(n))'. But the problem
is that F(n) grows too rapidly to be provably computable in PA,
see [Smo] 1980 for details.
Goodstein's theorem was one of the first examples of so-called
'natural independence phenomena', which are considered by most
logicians as more natural than the metamathematical
incompleteness results first discovered by Godel. Other finite
combinatorial examples were discovered around the same time,
e.g. a finite form of Ramsey's theorem, and a finite form of
Kruskal's tree theorem, see [KiP], [Smo] and [Gal]. [Kip]
presents the Hercules vs. Hydra game which provides an
elementary example of a finite combinatorial tree theorem
closely related to the Goodstein example above.
Kruskal's tree theorem plays a fundamental role in computer
science because it is one of the main tools for showing that
certain orderings on trees are well-founded. These orderings
play a crucial role in proving the termination of rewrite rules
and the correctness of the Knuth-Bendix equational completion
procedures. See [Gal] for a survey of results in this area.
See the references below for further details, especially
Smorynski's papers. Start with Rucker's book if you know no
logic, then move on to Smorynski's papers, and then the others,
which are original research papers. For more recent work, see
the references cited in Gallier, especially to Friedman's school
of 'Reverse Mathematics', and see [JSL].
-Bill Dubuque
[Gal] Gallier, Jean.
What's so special about Kruskal's theorem and the ordinal Gamma[0]?
A survey of some results in proof theory,
Ann. Pure and Applied Logic, 53 (1991) 199-260.
[HFR] Harrington, L.A. et.al. (editors)
Harvey Friedman's Research on the Foundations of Mathematics,
Elsevier 1985.
[KiP] Kirby, Laurie, and Paris, Jeff.
Accessible independence results for Peano arithmetic,
Bull. London Math. Soc., 14 (1982), 285-293.
[JSL] The Journal of Symbolic Logic, v. 53, no. 2, 1988.
This issue contains papers from the Symposium "Hilbert's Program
Sixty Years Later".
[Kol] Kolata, Gina. Does Godel's theorem matter to mathematics?,
Science 218 11/19/1982, 779-780; reprinted in [HFR].
[Ruc] Rucker, Rudy. Infinity and The Mind, 1995, Princeton Univ. Press.
[Sim] Simpson, Stephen G. Unprovable theorems and fast-growing functions,
Contemporary Math. 65 1987, 359-394; contained in full in my post:
http://search.dejanews.com/dnquery.xp?QRY=dubuque%2Bsimpson%2Bbudnik&svcclass=dnold
[Smo] Smorynski, Craig (all three papers are reprinted in [HFR])
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.
[Spe] Spencer, Joel. Large numbers and unprovable theorems,
Amer. Math. Monthly, Dec. 1983, 669-675.
Robert E. Beaudoin
Robin Chapman wrote:
>
> In article <35516712...@math.columbia.edu>,
> Richard Carr <ca...@math.columbia.edu> wrote:
>
> > This is to settle an quarrel (not a bet) with a number theory
> > colleague that there are number theoretical statements that cannot be
> > proven in ZFC but can with additional (large cardinal) assumptions.
> > Since my claim was based on this result, which I read about here, I
> > assume somebody knows something about it. On the other hand, if I am
> > mistaken and you can prove me wrong then that will be equally good.
> > Anyway, this guy wants a reference with a proof because he says sci.math
> > isn't a good enough source if without references or proof (which is fair
> > enough).
>
> There are other results of this nature: Paris and Harrington proved
> a Ramsey-type result which requires transfinite induction up to a much
> larger (but still countable) ordinal than epsilon_0. As for large cardinals,
> their existence will imply arithmetic results, but as for examples,
> my ignorance is total.
>
The statement "The axioms of ZFC are consistent" is known to be
equivalent to the non-existence of a root of a certain polynomial (in
several variables, with integral
coefficients) all of whose entries are integral. More generally, there
is a polynomial
p in Z[x,y,...,z] (I believe something like 9 variables are known to
suffice, but I really don't remember the best known bound) such that,
for any r.e. set S of axioms
phraseable in a first-order language there is an integer n so that
p(n,y,...,z) = 0
has a solution with y,...,z integral if and only if S is consistent.
(This follows
from the celebrated result that r.e. sets are Diophantine, which finally
settled
Hilbert's Tenth Problem. This result is discussed in Bell and
Machover's text on
mathematical logic, but I don't recall if they draw the corollary about
consistency
of theories.) But your colleague may decide that existence of an
integral
root of this polynomial is not really a "number-theoretic statement",
but more of a
"logical" or "meta-mathematical" one. So if what you really want is to
score a
victory I'd suggest you first try to get your opponent, er, colleague,
to agree to a
definition of "number-theoretic statement" that will clearly include
solvability of
arbitrary Diophantine equations. Then you can spring this theorem on
him/her, and
claim a win: existence of an inaccessible cardinal implies Con(ZFC)
(which you've
agreed is "number-theoretic"), and yet Con(ZFC) cannot be proved in ZFC
alone.
(One reference for proofs of these two facts is Jech's book _Set
Theory_.)
In my opinion, the most mathematically natural statements which follow
from existence
of large cardinals but not from ZFC alone are determinacy axioms. (Let
S be a set of
reals. Define a game G(S) played by two players, Alice and Bob, who
produce a real
number by taking turns choosing digits after the decimal point. Alice
wins if the
real they produce is in S. If there is a measurable cardinal then for
any set S
which is the continuous image of a closed set of reals either Alice or
Bob must have
a winning strategy. If you assume more about large cardinals you can
get similar
results for more sets S, and conversely knowing such determinacy results
for
sufficiently complex S implies consistency of various large cardinal
axioms.) But
these axioms seem more "analytic" than "number-theoretic/arithmetic".
I'm not
aware of any statements that follow from large cardinals but not ZFC
that would
gain any broader acceptance as "number theoretic" than those of the last
paragraph.
Hope this was interesting, if not helpful.
Robert E. Beaudoin