By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free such that for every number $n$: \[ n\in A\longleftrightarrow \mathfrak{N}\vDash\varphi(\overline{n}) \] where $\mathfrak{N}$ is the standard model of the first-order language of Peano Arithmetic.
I have the following question: given a r.e. set $A$ can we always find a $\Sigma_1$-formula defining it?
On
By the axiom of choice there is a function that maps each r.e. set to one of its definitions. We can 'find' the definition in that sense. This function cannot be too nice, however, because that would decide the extensional equivalence of two definitions.
Let $f$ be a function that maps each set to one of its definitions. For each arithmetical statement $p$ there is a set $\{n|p\}$. The equality of definitions $f(\{n|p\}) = f(\mathbb N)$ is way to decide if $p$ is true. G\"odel's incompleteness theorems say we can't do that.
The definition of a recursive enumerable set is that it is the domain of some partial recursive function.
There is a recursive primitive function $\psi$, such that $\psi(n,t,x)=0$ if and only if $\phi_n(x)$ (the recursive function $n$ on entry $x$) halts in less than $t$ steps, else $\psi(n,t,x)=1$. Any recursive primitive function can be defined by a $\Delta_0$-formula. Hence
$$\phi_n(x)\mbox{ halts } \Leftrightarrow \exists t\; \psi(n,t,x)=0$$
The existence of $\psi$ is a consequence of Kleene T-predicate