Is there a set $A \subset \mathbb{N}$ s.t. $A$ is not the interpretation set of any formula in Peano arithmetic?

Question

More formally, what I want to find is a set $A \subset \mathbb{N}$ s.t. for every formula $\phi$ with only one free variable $x$ in Peano arithmetic, there exists $a \in A$ s.t. $\{ x \mapsto a \} \not\models \phi$.

Intuitively, I think the set of Fibonacci numbers cannot be the interpretation set of any formula in Peano arithmetic, but I don't know how to prove that.

Answer 1

Thanks for @David C. Ullrich.

There are only countably many formulas, but the power set of natural numbers is uncountable. Thus, all sets that could be represented by some formula are countable, which is a proper subset of $2^\mathbb{N}$. Thus, there must be some $A \subset \mathbb{N}$ s.t. $A$ cannot be represented by any formula.

Answer 2

We can do better than a cardinality argument. By Tarski's undefinability theorem we can take $A$ to be the set of Godel codes of the true statements of Peano arithmetic.