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
Robin Chapman wrote:
> In article <35516712.127A9…@math.columbia.edu>,
> Richard Carr <c…@math.columbia.edu> wrote:
[description of Goodstein's Theorem deleted]
> > 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).
[sketch of proof deleted]
> 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