1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila ♦
    Commented Jul 10, 2019 at 10:40
  • $\begingroup$ 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 ... $\endgroup$
    – Noah Schweber
    Commented Jul 11, 2019 at 1:32

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Emanuele Paolini
    Commented Jul 11, 2019 at 13:02
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .