Recently, I was studying Gödel's incompleteness theorems, and I came across a theorem that was stated as: "All recursive functions and predicates are arithmetically definable". It used induction to prove the theorem. While, as we know recursive functions are built up from projection functions, constant-0 functions, the successor function using composition, primitive recursion and minimization. The proof used projection, zero and successor functions as base cases, and then went on to use composition, primitive recursion and minimalization as inductive cases.

But, what about the set of prime numbers? Is the set of prime numbers arithmetically definable? If yes, how can it be proved? And when I say arithmetically definable, I mean this.

  • $\begingroup$ Isn't arithmetic definability of a set the same as being able to write a computer program that enumerates its members? $\endgroup$ – Justpassingby Jan 4 '16 at 20:48
  • $\begingroup$ @Justpassingby We are talking about more mathematical definition here. See this. $\endgroup$ – user72151 Jan 4 '16 at 20:51
  • $\begingroup$ @Justpassingby: No, that is being recursively enumerable. It means being definable by formula which is $\Sigma^0_1$, whatever that means. $\endgroup$ – Asaf Karagila Jan 4 '16 at 20:56
  • $\begingroup$ @AsafKaragila: I think you know what $\Sigma_1^0$ means! $\endgroup$ – Rob Arthan Jan 4 '16 at 21:54
  • $\begingroup$ @Rob: Sure, I know what it means, but the OP might not know what it means. $\endgroup$ – Asaf Karagila Jan 4 '16 at 22:19


What does it mean to be a prime number? It means that:

  1. You are greater than $1$, and
  2. Every proper divisor is $1$.

The first property can be simply stated as $x>1$ or $x>S0$, if $1$ is not in your language. Here $S$ is the unary successor function.

The second property is slightly more complicated, for that we will first note that $k$ is a proper divisor of $n$ if and only if: $k<n$ and there exists $m$ such that $k\cdot m=n$. You can even say that $m<Sn$ as well, that will be important later on.

So to state the second property we say that $\forall k(k<x\land\exists m(k\cdot m=x)\rightarrow k=S0)$.

Now the conjunction of the two properties gives you exactly the property "$x$ is a prime number".

  • $\begingroup$ Sorry but if you consider $1$ a proper divisor of $n$, then your ``$m$'' will not necessarily be less than $n$, right? $\endgroup$ – TomGrubb Jan 4 '16 at 20:59
  • $\begingroup$ You're right. It should be $m<Sn$. $\endgroup$ – Asaf Karagila Jan 4 '16 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy