# Why is bounded induction stronger than open induction?

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.

• I removed the "number theory" tag; questions like this are not usually considered to be part of number theory – Carl Mummert Sep 14 '13 at 2:09
• Universally quantified formula is not same as quantifier free formula. – Trismegistos Sep 16 '13 at 8:52
• @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. – Keshav Srinivasan Sep 16 '13 at 14:03

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]$$
• 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. – Carl Mummert Sep 14 '13 at 20:26
• 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. – Carl Mummert Sep 14 '13 at 20:32