Bounded quantifiers preserve primitive recursiveness

Addition and multiplication are primitive recursive: use $a+0=a$, $a+(m+1)=S(a+m)$, $a\cdot 0=0$, and $a\cdot (m+1)=a\cdot m+a$. Argument permutations are compositions with projections. Constants zero and one are initial functions or their compositions with successor. The function $\mathrm{sg}$ defined by $\mathrm{sg}(0)=0$, $\mathrm{sg}(m+1)=1$ is primitive recursive.

Let $r(\vec{x},u)$ be the $0$-$1$ characteristic function of $R$. Define $B(0,\vec{x})=0$, $B(m+1,\vec{x})=B(m,\vec{x})+r(\vec{x},m)$ and $C(0,\vec{x})=1$, $C(m+1,\vec{x})=C(m,\vec{x})r(\vec{x},m)$. These are primitive-recursion instances with parameters. Consequently $\mathrm{sg}(B(t(\vec{x}),\vec{x}))$ and $C(t(\vec{x}),\vec{x})$ are primitive recursive by composition.

The first expression is one exactly when at least one of the first $t(\vec{x})$ characteristic values is one; the second is one exactly when all are one. At bound zero their values are respectively zero and one. Thus they are the characteristic functions of the existential and universal relations asserted.