A non-arithmetical set?

Question

A set is called arithmetical if it can be defined by a first-order formula in Peano arithmetic. I first encountered these sets when exploring the arithmetical hierarchy in the context of computability theory. However, I have not encountered any examples of sets that are not arithmetical.

Is there a canonical example of an non-arithmetical set?

Thanks!

Answer 1

There are countably many first order formulas defining arithmetical sets. Let $\varphi_n$, $n\in\mathbb N$, be a list of those. Consider the set that contains a natural number $n$ iff $n$ is not contained in the set defined by the $n$-th formula.

Answer 2

One example is the set of Gödel numbers for all true arithmetic sentences. If this was arithmetical, then Berry's paradox could be formalized and yield a contradiction.

Answer 3

The usual examples are things like:

$0^{\omega}$ or anything bigger. Any arithmetically generic set. The set of ordinal notations or equivalently the indexes for computable well-orderings or even the indexes of well-founded computable trees.

I figured I'd add these because these are natural examples not merely a diagonalization.

Though the godel numbers of true statements of arithmetic is quite natural.