[FOM] 303: PA Completeness (restatement)

[A.P. Hazen]

Harvey Friedman has made the interesting conjecture that  PA is 
complete for arithmètic sentences containing no more than two 
quantifiers.  If true, I think this would qualify as a SURPRISING 
result: most of the classical work on PA has regarded "bounded" 
quantifiers as free (which is equivalent to allowing the basic 
non-logical vocabulary  of the language to be enriched with symbols 
for arbitrary primitive recursive functions and relations).  And of 
course PA is very far from being complete for sentences with two 
UNBOUNDED quantifiers!  (So, my guess is that many of us have 
"intuitions" that are not properly tutored for thinking  about 
Harvey's conjecture.  And that if it turns out to be true we will 
therefore be surprised by it.)

On the more general topic of whether First-Orlder Logic (FOL) is the 
"Appropriate" logical framework for research in the Foundations of 
Mathematics (FoM), Harvey a few posts back suggested that it is clear 
that nothing much  weaker than (full) FOL will do.  One obvious 
weakening would be to FOL with only a limited number of distinct 
variables allowed: 3-variable FOL being, for example, equivalent in 
expressive power to the "Algebra of Relations."  Interestingly, a 
moderately strong THEORY can compensate for the weakening of the 
LOGIC: Tarski and Givant's "Set Theory without Variables" shows that 
ZFC (and any of a wide variety of other theories of FoM-interest in 
which pairing functions are definable) can be formulated in 
3-variable FOL.

--

Allen Hazen
Philosophy Department
University of Melbourne