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!

$\endgroup$
0
12
$\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
  • $\begingroup$ Gotcha. I completely forgot you could diagonalize. Thanks! $\endgroup$ Jun 25 '12 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
  • $\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 '12 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 '12 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 '12 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.