[FOM] PA Completeness/progress

Harvey Friedman friedman at math.ohio-state.edu
Fri Nov 3 11:30:00 EST 2006


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 



More information about the FOM mailing list