[FOM] What does Peano arithmetic have to offer?
Harvey Friedman
friedman at math.ohio-state.edu
Sun May 2 16:18:08 EDT 2010
On May 1, 2010, at 8:38 PM, Vaughan Pratt wrote, responding to my http://www.cs.nyu.edu/pipermail/fom/2010-May/014703.html
> While these very nice theorems strikingly address limitations of
> elementary arguments about numbers, do they carry over for example to
> algebraic number theory as described at
> http://en.wikipedia.org/wiki/Algebraic_number_theory , or they
> specific
> to the proof theory of the elementary theory of numbers?
>
> While I have no problem with the idea that *any* theory of a domain
> such
> as numbers (whether in a finitary or infinitary language) will have
> limitations of one kind or another, as a sort of Heisenberg-Goedel
> uncertainty principle for mathematics, what evidence is there that the
> limitations of a suitably sharply defined formulation of algebraic
> number theory will bear any resemblance to those of PA? This was the
> point of item 3 in my response to Martin, about abstract algebra being
> just as problematic for FOM as category theory.
Before starting my response, there is a typo in http://www.cs.nyu.edu/pipermail/fom/2010-May/014703.html
I wrote
THEOREM 3. Let n >> k. For any f:{1,...,n}^k into {1,...,n} obeying
f(x) <= max(x), there exists x_1 < ... < x_k+2 such that
f(x_1,...,x_k) <= f(x_2,...,x_k+1) <= f(x_3,...,x_k+1).
I should have written
THEOREM 3. Let n >> k. For any f:{1,...,n}^k into {1,...,n} obeying
f(x) <= max(x), there exists x_1 < ... < x_k+2 such that
f(x_1,...,x_k) <= f(x_2,...,x_k+1) <= f(x_3,...,x_k+2).
First let me say something about the nature of my examples from http://www.cs.nyu.edu/pipermail/fom/2010-May/014703.html
These were theorems requiring various portions of PA, or more than PA,
that are very natural combinatorially, and qualify as genuine normal
looking theorems of combinatorics. In fact, substantially more so
than, e.g., Goodstein sequences or the Paris/Harrington Ramsey Theorem.
These were NOT open questions in combinatorics.
So one form of your question would be:
ARE THERE THEOREMS REQUIRING VARIOUS PORTIONS OF PA, OR MORE THAN PA,
THAT ARE VERY NATURAL FROM THE STANDPOINT OF ALGEBRAIC NUMBER THEORY,
AND QUALIFY AS GENUINE NORMAL LOOKING THEOREMS OF ALGEBRAIC NUMBER
THEORY?
My answer,
DEFINITELY YES.
But bear in mind the following.
1. From the historical record, coming up with quality examples like
this is arguably the most difficult achievable well known goal in (at
least) mathematical logic.
2. Doing this for algebraic number theory will require not only the
ability to overcome the difficulties needed for doing this for what
you call "elementary arguments about numbers", but also to be able to
simultaneously make the process interact properly with special
features in algebraic number theory.
3. I have no doubt that this can be done - in fact, even at the level
of the entire large cardinal hierarchy. I am convinced that the
combinatorial structures arising in the study of inductive
constructions that I write about in FOM recently - lately called
Integer Decomposition Theory - is naturally present in all areas of
mathematics.
4. HOWEVER, this will require being fully comfortable with a
substantial amount of algebraic number theory, which I am not.
5. So I am, at least at present, INCOMPETENT to do this.
6. I am sure that we agree that there are incomparably more consumers
of elementary numerical mathematics than algebraic number theory. So I
don't quite see why you are focused on algebraic number theory.
7. I don't think of what I presented in http://www.cs.nyu.edu/pipermail/fom/2010-May/014703.html
as a "sort of Heisenberg-Goedel uncertainty principle". Instead, it
demonstrates some very effective and very necessary uses of higher
principles to prove theorems lower down. A number of people regard it
as a "sort of Goedel certainty principle".
Harvey Friedman
More information about the FOM
mailing list