5
$\begingroup$

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!

3 Answers 3

12

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.

  • 0
    Gotcha. I completely forgot you could diagonalize. Thanks!2012-06-25
10

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.

  • 0
    Note: this is [Tarski's Theorem](http://en.wikipedia.org/wiki/Tarski's_undefinability_theorem).2012-07-09
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.

  • 0
    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)}$2012-06-27