[FOM] Reverse Number Theory -- corrected posting

[Stephen G Simpson]

I said "hyperfinitism" where I meant, of course, "ultrafinitism".  The
corrected posting is below.

-----

This is a follow-up to Harvey Friedman's recent postings on what he
calls Strict Reverse Mathematics.

Consider the statement 

   EXP: "for all positive integers n, 2^n exists"

Or, "for all positive integers m and n, m^n exists".  Here m^n denotes
the exponential function, m to the power n.  It appears that a key
step in Strict Reverse Mathematics would be to find mathematically
natural statements which imply EXP over a weak base theory which does
not include EXP.  This line of research is of obvious foundational
interest in relation to the program of ultrafinitism, etc.

I would like to call attention to some work by a group of Europeans
over a number of years, in an area which I propose to call Reverse
Number Theory.  They investigate which theorems of elementary Number
Theory require exponentiation.  One of the papers is by Paola
D'Aquino, in Annals of Pure and Applied Logic, 1996.  She shows that
EXP is equivalent over a certain system of Bounded Arithmetic, IE_1 if
it matters, to the statement

   Every Pell equation has a nontrivial solution in integers.

A Pell equation is a Diophantine equation of the form x^2 - d y^2 = 1,
where d is a positive integer which is not a square.  The trivial
solutions are x = 1, - 1, y = 0.  This existence of nontrivial
solutions is a standard result in Number Theory textbooks.

Another basic, standard theorem in Number Theory is Fermat's Little
Theorem: a^p = a mod p, p prime.  The last time I looked, it was still
an open question whether Fermat's Little Theorem can be proved in
systems of Bounded Arithmetic, without exponentiation.  The question
makes sense, because the 3-place function x^y mod z can be defined in
systems of Bounded Arithmetic.

It is possible that the Europeans working in this area would not want
it to be called Reverse Number Theory.  I say this because at least
one of them is known to be hostile to Reverse Mathematics.  See "The
Strength of Weak Systems", by Angus Macintyre with input from Kreisel,
published in a Wittgenstein symposium, Kluwer Publishing Company,
1986.  Macintyre is D'Aquino's sometime co-author in this area.

There is also recent work in what I might call Reverse Finite
Combinatorics, by Kerry Ojakian at CMU.  He proves that EXP is
equivalent to the Finite Ramsey Theorem with exponent 2.

-- Stephen G. Simpson
Profesor of Mathematics
Pennsylvania State University

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom