# 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.

• Since $m<m!+1$ you have an effective bound. So once you prove that bounded products are recursive, you're right to claim that the set of $\{n!\mid n\in\Bbb N\}$ is recursive. Commented Jul 10, 2019 at 10:40
• You or someone else added a now-deleted comment to my answer about the importance of defining the prime counting relation in treating sequences; I've edited my answer so it's clear how to do without this in the definition of factorial. That said, it is indeed important, and it's a good exercise to figure out how to do it - think about defining an appropriate sequence of ordered pairs ... Commented Jul 11, 2019 at 1:32

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 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.

• Maybe I understand better the solution using the $\beta$ function. I have tried to elaborate on that and wrote a possibile quasi explicit answer. If you think it is correct and you include that in your answer I will be glad to accept this answer. Commented Jul 11, 2019 at 13:02

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