I'm stuck at the following exercise:
I want to show that for every quantifier-free formula in the language of $\mathsf{PA}$ there are polynomials $P(y,\vec{x}),Q(y,\vec{x})$ such that for all $\vec{n} = n_1,...,n_k \in\mathbb{N}$ it holds \begin{align*} \big(\mathcal{N} \models\exists y.\varphi[y,\vec{n}] \big) \Leftrightarrow \big( \exists z \in \mathbb{N}. P(z,\vec{n}) = Q(z,\vec{n}) \big), \end{align*} where $\mathcal{N} \models \mathsf{PA}$ is the natural model.
I tried proceeding by induction on the complexity of $\varphi$. Of course, the base case is straightforward and I believe $\vee$ is not that hard. I didn't succeed in the induction step regarding $\neg$ however.
I think this induction step comes down to finding, for any polynomial $R(y,\vec{n})$ a polynomial $S(y,\vec{n})$ such that \begin{align*} \forall \vec{n} ( \exists y. R(y,\vec{n}) \not=0 \leftrightarrow \exists z. S(z,\vec{n}) = 0). \end{align*}