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.