For each formula $\phi(x)$ in arithmetic language construct formula $\#\phi(x)$ (also in arithmetic language) such that:
$(\mathbb{N},x:n)\models \#\phi(x)\leftrightarrow > |\{m\in\mathbb{N}:(\mathbb{N},x:m)\models \phi(x)\}|=n$
Arithmetic language is: $\langle \mathbb{N},+,\cdot,0,1 \rangle$
My trial:
$\#\phi(n)=\exists_{n_1}\exists_{n_2}..\exists_{n} \phi(n) \wedge Diff(n_1,n_2,..,n) \wedge\forall_n \phi(n)\to n\in \{n_1,n_2,..,n\}$
Of course it seems to be working, however I afraid of that it is not in arithmetic language. Can you help me ?
Edit after hint of @Noah
I am using beta function.
$$\#\phi(x)=\exists_t \forall_{1\le i\le n} [\forall_y (\phi(y) \leftrightarrow\exists_i \beta (t, i,y)) \wedge \forall_{i,j}\exists_c((\beta(t,i,c)\wedge \beta(t,j,c)) \to i=j)] $$
The problem is that your $\#\varphi$ depends on $n$. You're supposed to build a single formula $\#\varphi$ which works, so in particular you don't know $n$ ahead of time.
Intuitively, $\#\varphi(x)$ should say "There are exactly $x$-many naturals with property $\varphi$." Now, of course, on the face of it this is not first order. However, remember that arithmetic can talk about sequences!
Specifically, let's represent the sequence $a_1...a_k$ by the natural number $2^{a_1}3^{a_2}...p_k^{a_k}=\prod_{1\le i\le k} p_i^{a_i}$ (here "$p_i$" denotes the $i$th prime).
Now we want to say "There are exactly $x$-many elements with property $\varphi$. Well, this means that the set of naturals with property $\varphi$ can be put into correspondence with the set $\{1, 2, . . . , x\}$. Well, that correspondence is a sequence - of length $x$, whose elements are ordered pairs of the form $(a, b)$ with $a\in\{1, 2 , . . . , x\}$ and $b$ some natural with property $\varphi$, such that no two $a$s get the same $b$.
I've described how to talk about sequences in first-order logic; can you see a way to get at sequences of ordered pairs? Can you see how to use this to finish the problem?