Why is $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ a recursive set? Let $\mathcal{N}=(\mathbb{N},+,\cdot,0,1)$. I want to show that $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ is a recursive set. Here $\#F$ is the Gödel number of $F$ and I think that $\exists$-formula just means a formula on the form $\exists v_0 \dots\exists v_n F$, without any occurrence of universal quantifiers. The problem is from an old mock-exam from a second-level logic course given at my university.
This was my original attempt, which, as Carl Mummert pointed out, is clearly wrong:

My idea is to show that $\{\#F\mid\mathcal{N}\models F \}$ is
  recursive and then just multiply its characteristic funtion with
  something like $f(x)=\left[1\,\dot{-}\,sg(\vert \beta_3^3(x)-7\vert  )\right]$, i.e. something that takes the Gödel number of $x$ and
  returns $0$ if the last digit is not $7$ and $1$ if it is (i.e. if it
  is an $\exists$-formula). That would give me the characteristic
  funtion for the original set. But then my problem is that I don't know
  how to show that $\{\#F\mid\mathcal{N}\models F \}$ is recursive.

 A: It's not recursive.
Whether this is easy or very hard to show depends on exactly what "$\exists$-sentence" means. 
 Specifically, the issue is whether "bounded quantifiers" (like $\forall x<5$, $\exists y<z+w$) are permitted. Formulas of the form $\exists x_1,...,x_n G$ where $G$ uses only bounded quantifiers are called "$\Sigma_1$" (or "$\Sigma^0_1$"); to me, "$\exists$-formula" sounds like a stronger condition, namely we require that the matrix $G$ be genuinely quantifier-free (and this is your interpretation in the comments above). 
But in each case, the resulting set is non-recursive.

Showing that the $\Sigma_1$ theory of $\mathcal{N}$ is non-recursive isn't too hard. There is a $\Sigma_1$ formula $Halt(x)$ such that for each $n\in\mathbb{N}$ we have $\mathcal{N}\models Halt(\underline{n})$ iff $\varphi_n(n)\downarrow$ - writing "$\varphi_e(x)\downarrow$" for "the $e$th Turing machine halts on input $x$" and "$\underline{k}$" for the numeral corresponding to $k$ - but this means that the $\Sigma_1$-theory of $\mathcal{N}$ is at least as complicated as (in fact, it's equivalent to) the halting problem, which is non-recursive.
Gauging the complexity of the genuinely $\exists$-theory of $\mathcal{N}$ is harder, but ultimately still the same. This is the MRDP theorem: that the set of Diophantine equations with solutions (which is about as $\exists$ as it gets) is non-recursive, and in fact has complexity again equal to that of the halting problem.
