[FOM] What does Peano arithmetic have to offer?

[Harvey Friedman]

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