[FOM] 303: PA Completeness (restatement)

[Arnon Avron]

Even if Friedman's stronger conjecture concerning PA  is true, I have 
strong doubts concerning the value of such a result and its
possible philosophical implications. The reasons are:

1) It seems to me somewhat misleading to talk about the induction
  schema as mentioning only one variable (or two, if the metavariable
  R is counted too - is it?). In the actual language of PA instances
  of it might involve a huge number of variables. It is quite likely
  that the only proofs in PA of some (2,2) theorems require instances
  of the induction scheme involving more (and maybe much more)
  variables. In such a case what is really hapening is that a system 
  with axioms of high complexity can decide some fragment of lower
  complexity. So what?

2) The (2,2) fragment of PA seems to me too weak to be significat
   or interesting. Even the most elementary properties of the 
   structure N (like associativity of + or the transitivity of <)
   need at least 3 quantifiers for their formulation. Indeed,
   it seems to me that only corresponding results about sentences
   with at least 3 variables might be really interesting. I strongly
   doubt that such results may be obtained. As an example: suppose
   that instead of using as primitives 0,S,+, and dot we
   take as primitives 0,1,+,<, and | (where the meaning of x|y is
   "x devides y"). The two languages are equivalent in their expressive
   power (concerning N), and it is not difficult to produce
   a system equivalent to PA in the second language, which 
   has the same syntactic properties as those noted by Friedman in PA.
   Now in this language Goldbach's conjecture can be formulated using
   a sentence of complexity (3,1) (and involving 4 quantifiers). This
   seems to indicate that already the (3,1 )-level may be very
   difficult.


Arnon Avron