Is the set of prime numbers arithmetically definable?

Question

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.

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

Asaf Karagila · Accepted Answer · 2016-01-04T21:01:12.003

7

Easily.

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

You are greater than $1$, and
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".

edited Jan 04 '16 at 21:01

answered Jan 04 '16 at 20:55

Asaf Karagila

393,674

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

Is the set of prime numbers arithmetically definable?

1 Answers1