Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

3 Answers

up vote 9 down vote accepted

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.

share|improve this answer
    
Gotcha. I completely forgot you could diagonalize. Thanks! –  templatetypedef Jun 25 '12 at 22:07
add comment

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.

share|improve this answer
    
Note: this is Tarski's Theorem. –  Quinn Culver Jul 9 '12 at 15:27
add comment

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.

share|improve this answer
    
I'm not familiar with the notation $0^\omega$. Do you have a reference on where I could learn more about it? –  templatetypedef 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. –  Steven Stadnicki 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)}$ –  Peter Gerdes Jun 27 '12 at 21:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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