0

By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier.

By a strict arithmetical sentence I mean a quantifier free arithmetical sentence that doesn't contain any logical connective.

Is PA complete for quantifier free arithmetical sentences?

Formally: do we have: if $P$ is a quantifier free arithmetical sentence, then: $(PA \vdash P) \oplus (PA \vdash \neg P)$?

Is PA complete for strict arithmetical sentences?

Formally: do we have: if $P$ is a strict arithmetical sentence, then: $(PA \vdash P) \oplus (PA \vdash \neg P)$?

Zuhair
  • 4,555

1 Answers1

2

First, a comment on terminology: "quantifier free" means, well, "quantifier free," and "arithmetic(al)" is generally understood to refer to arbitrary applications of number quantifiers. Your "quantifier-free" sentences are just universal sentences, and I'll refer to them as such. Meanwhile, your "strict quantifier-free" sentences are just universally quantified equations.

As to your questions, the answers are no and yes(ish) respectively, the crucial point being whether negation is allowed. If negation is allowed, then just note that saying that a Diophantine equation has no solutions is a universal sentence, and we can encode arbitrary $\Pi_1$ queries in this way.

(A bit more explicitly: there is a single Diophantine equation $P(x_1,...,x_n)=0$ such that PA proves $Con(PA)\iff \forall x_1,...,x_n(\neg (P(x_1,...,x_n)=0))$. But the right hand side sentence is universal, since "$P(x_1,...,x_n)=0$" is an atomic formula.)

If however we disallow negation (and don't have "$<$" or "$-$" either - see Andreas' comment below), then we're only looking at sentences of the form "$\forall x_1,...,x_n(P(x_1,...,x_n)=Q(x_1,...,x_n))$" for Diophantine equations $P,Q$. But these sentences are easily seen to be decidable if "$-$" isn't allowed.

Noah Schweber
  • 245,398
  • This not only answers the first question, it very nearly answers the second; all that prevents the example from being strict is that it uses negation. But if $<$ is primitive (as it is in many formalizations of PA), then we can avoid negation: Rewrite the diophantine non-equation $p\neq q$ as $0<(p-q)^2$, multiply out the right side, and transpose any negative terms to the left. – Andreas Blass Dec 07 '18 at 14:57
  • @AndreasBlass That also needs subtraction I think. – Noah Schweber Dec 07 '18 at 15:00
  • There's a minus sign in what I wrote, but the final "transpose any negative terms to the left" seems to put the result back into the standard language of PA. (Note that I'm not claiming to prove the equivalence, between $p\neq q$ and the final inequality, in PA, much less using only a limited supply of formulas. I'm just claiming that they are in fact equivalent and that the final inequality is strict arithmetical if $<$ is available.) – Andreas Blass Dec 07 '18 at 15:06
  • To clarify my previous comment: The equivalence is certainly provable in PA, but I'd expect any proof of it to use subtraction or existential quantifiers. But all I care about is that the equivalence is true. – Andreas Blass Dec 07 '18 at 15:08
  • @NoahSchweber, what is the exact problem with allowing subtraction? Your Diophantine equation lacks subtracion. How allowing it would give equivalent formulation to inequality? Of course I mean allowing subtraction but not $<$. – Zuhair Nov 04 '22 at 12:12