Recall that a function $f:\mathbb{N}^k\rightarrow\mathbb{N}$ is representable in Peano arithmetic if there exists a formula $\varphi(x_1,\dots ,x_k,y)$ such that for every $n_1,\dots,n_k,m\in\mathbb{N}$,
- If $m=f(n_1,\dots,n_k)$ then $\mathcal{A}\vdash \varphi(\underline{n_1},\dots ,\underline{n_k},\underline{m})$
- If $m\neq f(n_1,\dots,n_k)$ then $\mathcal{A}\vdash \neg\varphi(\underline{n_1},\dots ,\underline{n_k},\underline{m})$
Here, $\mathcal{A}$ is the theory (set of axioms) of Peano arithmetic, and $\underline{n}$ is the term $S(S(\dots S(0)\dots))$ (with $n$ operations of $S$).
I have two related questions regarding this definition. Suppose that $f$ is representable by a formula $\varphi(x_1,\dots ,x_k,y)$ (as defined above);
- Is it necessarily true that for every $n_1,\dots,n_k$, $$\mathcal{A}\vdash\exists !y(\varphi(\underline{n_1},\dots ,\underline{n_k},y))$$?
- Is it necessarily true that $$\mathcal{A}\vdash\forall x_1\cdots\forall x_k\exists !y(\varphi(x_1,\dots ,x_n,y))$$?
I wanted to prove these by contradiction, i.e assume that $\mathcal{A}\vdash\psi$ doesn't hold, but the problem is that I can't deduce that $\mathcal{A}\vdash\neg\psi$ since Peano arithmetic isn't complete.
Other than that I'm quite clueless so I'd appriciate your help.