7
$\begingroup$

It seems to me that any formula in the language of first-order arithmetic which has only bounded quantifiers can be written as a formula without any quantifiers. For instance, "There exists an n < 1000 such that P(n)" can be written as "P(1) or P(2) or ... or P(999)", and "for all n < 100, P(n)" can be written as "P(1) and P(2) and ... P(99)". So how can bounded arithmetic, i.e. Q + induction on all formulas with bounded quantifiers, be stronger than open induction, i.e. Q + induction on all quantifier-free formulas? Isn't any theorem provable using induction on bounded quantifiers also provable without it, since you can just apply induction to prove the quantifier-free expressions, like P(1), P(2), ..., P(999), using open induction, and then at the end use those propositions to derive the proposition with the bounded quantifiers?

Any help would be greatly appreciated.

Thank You in Advance.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I removed the "number theory" tag; questions like this are not usually considered to be part of number theory $\endgroup$ – Carl Mummert Sep 14 '13 at 2:09
  • $\begingroup$ Universally quantified formula is not same as quantifier free formula. $\endgroup$ – Trismegistos Sep 16 '13 at 8:52
  • $\begingroup$ @Trismegistos Of course it's not. But that doesn't answer the question of whether induction on one class of formulas is just as powerful as induction on another class. $\endgroup$ – Keshav Srinivasan Sep 16 '13 at 14:03
4
$\begingroup$

I think you are assuming that the bound in a bounded quantifier has to be a closed term - a number. But it does not. Here is one bounded quantifier formula in the language of arithmetic: $$ \phi(x) = (x > 1) \land (\forall a < x)(\forall b < x) [ ab = x \to a = 1 \lor b = 1] $$

This formula defines the set of prime natural numbers. That set cannot be defined by a quantifier-free formula. (Proof sketch: verify that a set definable by a quantifier-free formula must be finite or cofinite).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Does that mean that if we restrict induction to formulas with bounded quantifers, with the bounds being either numerals or bound variables, then that gives you no advantage over open induction? $\endgroup$ – Keshav Srinivasan Sep 14 '13 at 19:52
  • $\begingroup$ Yes, with a few requirements. You need enough axioms to prove the scheme $b(m) \equiv (n < \dot{m}) \to (n = \dot{0} \lor n = \dot{1} \lor \cdots \lor n = \dot{m-1})$ for each standard $m$, where $\dot k$ is the closed term denoting $k$, and maybe a few other basic arithmetical axioms. In that case, bounded quantifiers with constant bounds can be converted to conjunctions or disjunctions using the usual rules of inference. $\endgroup$ – Carl Mummert Sep 14 '13 at 20:26
  • $\begingroup$ In general, the way to think about bounded quantifiers is not to think about how they work for standard numbers, but how they work for nonstandard ones. $(\forall n < m)$, where $m$ is a nonstandard element of some model, quantifies over an infinite set of $n$ - all the ones that are less than $m$ in the model. So the truth value of a bounded quantifier depends only on what happens in an initial segment of the original model. By contrast, $\Sigma^0_1$ induction allows us to perform induction on formulas that quantify over the entire model at once, not just over initial segments of it. $\endgroup$ – Carl Mummert Sep 14 '13 at 20:32
  • $\begingroup$ Whatever requirements you're talking about, are they satisfied by Robinson's Q? In other words, is Q + open induction just as powerful as Q + induction on formulas with bounded quantifiers with bounds that are either numerals or bound variables? $\endgroup$ – Keshav Srinivasan Sep 14 '13 at 20:35
  • $\begingroup$ I don't know off the top of my head; perhaps you could ask that as a separate question. $\endgroup$ – Carl Mummert Sep 14 '13 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.