[FOM] PA Completeness/progress

[Harvey Friedman]

I have been able to prove the following.

THEOREM. Let A be a sentence in 0,S,+,dot, with two quantifiers, in which
all terms use at most two operation symbols. Then A is true iff A is
provable in (a weak fragment of) PA.

This class of sentences contains the axioms of PA except for the axiom
scheme of induction.

I believe that the following is within reach:

CONJECTURE. Let A be a sentence in 0,S,+,dot, with three quantifiers, in
which all terms use at most two operation symbols. Then A is true iff A is
provable in (a weak fragment of) PA.

This class of sentences also includes the associative law of addition.

To include the distributive law, we make the following conjecture.

CONJECTURE. Let A be a sentence in 0,S,+,dot, with three quantifiers, in
which all terms use at most three operation symbols. Then A is true iff A is
provable in (a weak fragment of) PA.

This, also, will be proved with some effort.

Harvey Friedman