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.
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).