[FOM] 303: PA Completeness (restatement)
Arnon Avron
aa at tau.ac.il
Thu Nov 2 06:39:48 EST 2006
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
More information about the FOM
mailing list