Is the set of prime numbers first-order definable in $(\mathbb{N}, +)$?

Question

The clearly intuitive answer is no. But I'm unsure of how to prove this, as there are no nontrivial automorphisms of $(\mathbb{N}, +)$, so the standard method doesn't work. What is the correct approach here?

Answer 1

The definable sets in $(\mathbb{N};+)$ are all eventually periodic - this follows from the usual quantifier-elimination (in an expanded language) argument used to show the completeness of Presburger arithmetic - so the answer to your question is negative (and we can similarly use this to rule out the existence of a definable pairing function and similar constructions). But indeed this takes more work than a simple automorphism construction, and I'm not aware of any proof that doesn't go through some form of QE.