Goedel's representability of simple recursive sets

Question

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.

Answer 1

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.

Answer 2

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) $$