Is PA complete when multiplication is bounded?

Question

Working in PA.

Fix some natural number "$n"$.

Is PA complete for sentences that do not use the symbol $``\times"$ unless all of their variables are bounded $< n$.

Answer 1

In fact, a much stronger fact holds. Say that a formula $\varphi$ of arithmetic is multiplicatively bounded if for every term $t$ of the form $t_1\times t_2$ for $t_1,t_2$ terms which occurs in $\varphi$, every variable occurring in $t$ is within the scope of a bounded quantifier with bound a variable-free term. So e.g. if $\theta(x,y,z)$ is quantifier-free and the variable $y$ doesn't occur in any multiplicand in $\theta$ then the sentence $$\forall x<\underline{7}\forall y\exists z<\underline{120}[\theta(x,y,z)]$$ is multiplicatively bounded.

Then:

$\mathsf{PA}$ proves every true multiplicatively bounded sentence.

The point is that we can computably transform each multiplicatively bounded $\varphi$ into a $\mathsf{PA}$-provably-equivalent $\hat{\varphi}$ which does not use "$\times$" simply by enumerating all the finitely many possibilities for the relevant variables, and then appeal to Presburger arithmetic. For example, if $\theta$ is as above we have $$\forall x<\underline{7}\forall y\exists z<\underline{120}[\theta(x,y,z)]\quad\equiv\quad\bigwedge_{i<7}[\forall y\bigvee_{j<120}(\theta(\underline{i}, y,\underline{j}))],$$ and all terms of the form "$t_1\times t_2$" inside $\theta(\underline{i}, y,\underline{j})$ are now varaible-free and so can be replaced with numerals. The result is a sentence of the form $$\bigwedge_{i<7}\forall y\bigvee_{j<120}\eta_{i,j}(y),$$ where for each $i<7,j<120$ the formula $\eta_{i,j}$ is $\times$-free. The equivalence between this formula and the original one is provable in $\mathsf{PA}$, as is this new formula itself (being a consequence of Presburger arithmetic).

(And as usual, $\mathsf{PA}$ here is overkill - Presburger arithmetic plus Robinson arithmetic is already enough.)