# A non-arithmetical set?

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!

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.

• Gotcha. I completely forgot you could diagonalize. Thanks! Jun 25 '12 at 22:07

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.

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.

• I'm not familiar with the notation $0^\omega$. Do you have a reference on where I could learn more about it? Jun 27 '12 at 20:54
• I think Peter might mean what's usually designated $0^{(\omega)}$, the $\omega$-th Turing Jump (en.wikipedia.org/wiki/Turing_jump) of a computable set. Jun 27 '12 at 21:25
• Yah, sorry for being sloppy...I have macros to do that for me. If you still want a reference try Classical Recursion Theory Vol 2 More simply it's just $\oplus_{i \in \omega} 0^{(i)}$ Jun 27 '12 at 21:32