[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