6
$\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!

$\endgroup$
0

3 Answers 3

13
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Gotcha. I completely forgot you could diagonalize. Thanks! $\endgroup$ Jun 25, 2012 at 22:07
10
$\begingroup$

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.

$\endgroup$
1
3
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ I'm not familiar with the notation $0^\omega$. Do you have a reference on where I could learn more about it? $\endgroup$ Jun 27, 2012 at 20:54
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2012 at 21:25
  • $\begingroup$ 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)}$ $\endgroup$ Jun 27, 2012 at 21:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .