In article <35516712.127A9…@math.columbia.edu>,
Richard Carr <c…@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?
- Hide quoted text — Show quoted text -
> 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).
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
