Goedel's representability of simple recursive sets I'm referring to Goedel's theorem as exposed here:
https://plato.stanford.edu/entries/goedel-incompleteness/
The formal system in question is named Q and is a first order formalization of natural numbers with addition and multiplication operations. A set S of natural numbers is said to be "weakly representable" if there exists a formula A(x) in Q such that for all n in S the formula A(n) can be proved in Q. A set is "strongly representable" if both itself and its complementary set are weakly representable.
It turns out that the notions of strongly/weakly representable sets in Q is equivalent to recursive and recursive enumerable sets which. I think this is the core of Goedel's proof.
I believe that the set of factorial numbers {n | exists m: m!=n} is recursive and hence should be strongly and also weakly representable. So there must exist a formula A(n) in Q which represents the property of n being the factorial of some number m. What is such a formula? I cannot find anything easy... 
I feel there is something I'm missing in the story so far.
 A: The key to this result is that addition and multiplication let us talk about finite sequences. To see why finite sequences are relevant, consider the following informal definition:

$n!=k$ iff there is a sequence $\langle x_i\rangle_{1\le i\le u}$ such that

*

*$x_1=1$,


*$x_u=k$,


*for each $1\le i<n$ we have $x_{i+1}=x_i\cdot (i+1)$, and


*$x_{u-1}\cdot n=x_u$.

More generally, we can use definitions like this to encode arbitrary recursive functions, the point being that "$f(\overline{x})=y$" gets represented as the sentence asserting the existence of a finite sequence witnessing the computation.
Now, it's rather easy to implement sequences in addition, multiplication, and exponentiation using prime factorization - the sequence $\langle x_i\rangle_{1\le i\le n}$ being represented by the number $\prod_{1\le i\le n}p_i^{x_i+1}$ (the "$+1$" being to avoid ambiguity in the case of $x_n=0$). Then for example we can refer to the last term of a sequence by looking at the smallest/largest prime factor of the number representing it, and talk about relations between successive terms via the relation "$a$ is the next prime after $b$," which is easily definable.
Without exponentiation things are trickier, and this is where Godel's $\beta$ function comes in. But the idea is still the same. Personally, I think it's best to first understand the version with exponentiation, and then turn to the version without exponentiation.
A: Thanks to the answer of @Noah Schweber and the description of the $\beta$ function in wikipedia here is a possibile way to write the requested formula:
$$
rem(a,b)=c \colon \qquad (c<b) \land \exists n\colon a=b\cdot n + c\\
\beta(a,b,i) = c\colon \qquad rem(a,1+(i+1)\cdot b) = y\\
a_i = c \colon \qquad \beta(a,b,i) = c
$$
$$
n!=k\colon \qquad
\exists a \exists b \colon (a_1 = 1) \land (a_n =k) \land \forall i\colon ((i+1\le n \land i\ge 1)\implies a_{i+1} = (i+1)\cdot a_i)    
$$
