Natural problems not in the Arithmetical Heirarchy

Question

What are some natural problems not in the Arithmetical Hierarchy?

Answer 1

Great question! There are indeed such problems.

Note: by "problem," I assume you mean "set of natural numbers." E.g. you're looking for sets of natural numbers which are natural and non-arithmetic, as opposed to sets of reals which are natural and non-arithmetic.

The standard example is well-foundedness. We can phrase the well-foundedness problem in a number of ways:

• $WF$ is the set of indices $e$ for Turing machines which describe well-founded linear orderings.

Another formulation, of equivalent Turing degree:

• $\hat{WF}$ is the set of indices $e$ for Turing machines such that $\Phi_e^X(0)$ halts for every oracle $X$.

And yet another:

• Kleene's $\mathcal{O}$. This is basically a more technical version of $WF$, above.

Neither of these sets are in the arithmetic hierarchy. In fact, neither are even hyperarithmetic; they are much more complicated, and are $\Pi^1_1$-complete.

Of course, we know that there are problems not in the arithmetic hierarchy by a simple counting argument. So, why is this a "natural" problem? Well, I think it's intrinsically interesting, but even leaving that aside it, its "relativized" versions $\mathcal{O}^X$ for oracles $X$, and its "continuous analogue", the set of reals coding well-founded trees, are extremely useful in computability and descriptive set theory. Sacks' book on higher recursion theory is a good reference.

---

How about beyond $\Pi^1_1$?

Well, this is just the first layer of the analytic hierarchy. The real number zero sharp, which is extremely important in set theory, is (assuming it exists) $\Delta^1_3$ - significantly worse than $\Pi^1_1$. Note: while $0^\#$ is $\Delta^1_3$, the set $\{0^\#\}$ is $\Pi^1_2$; this is analogous to how e.g. $\{0^{(36)}\}$ is $\Pi^0_2$. The complexity of a real may be much worse than the complexity of the singleton containing it! And "sharps" of more complicated canonical inner models provide even harder problems (assuming of course that they exist in the first place).

Weaker than $0^\#$, but still above $\mathcal{O}$, is the complexity of telling whether a partial order is a better quasi-order; this is $\Pi^1_2$-complete. Girard has a hierarchy of structures he calls "$n$-ptyx" (no, I don't know why); a $2$-ptyke is also called a "dilator", and identifying $n$-ptykes is $\Pi^1_n$-complete.

---

What about weaker than $\mathcal{O}$, which is pretty dang complicated?

Well, the true theory of arithmetic is basically the entire arithmetic hierarchy bundled together. In terms of degrees, it has degree $0^{(\omega)}$. We can take its jump to get $0^{(\omega+1)}$, and keep going - in general, $0^{(\alpha)}$ is meaningful for every computable ordinal $\alpha$ (and there's that "$WO$" again!). The sets computable in some $0^{(\alpha)}$ form the hyperarithmetic hierarchy mentioned above.

Note that "$X\ge_T0^{(n)}$ for every $n$" does not imply "$X\ge_T0^{(\omega)}$"; that is, $0^{(\omega)}$ is not the "least upper bound" of the arithmetic degrees, and indeed the exact pair theorem prevents such a thing from ever happening. However, if $X\ge_T0^{(\omega)}$, then $X''\ge_T0^{(\omega)}$, so it's not far off.

We can keep going beyond the computable ordinals via master codes, but that introduces considerable difficulty. So let's not do that now.

Now, suppose $\mathcal{A}$ is a computable structure. Let's look at the set of indices for computable structures isomorphic to $\mathcal{A}$! This set is often arithmetic, but need not be in general. Indeed, it need not even be hyperarithmetic if $\mathcal{A}$ has high enough Scott rank! It will always,however, be $\Sigma^1_1$ - in particular, Turing reducible to $\mathcal{O}$. We can also study the index set of a class of computable structures, which can yield even more complicated sets, as in this paper by Calvert, Fokina, Goncharov, Knight, Kudinov, Morozov, and Puzarenko. So give me an interesting computable structure or class of computable structures, and I'll give you back a probably-non-arithmetic set!

Answer 2

The simplest example I know of is the theory of true arithmetic - that is, the set of all statements that are true of the natural numbers. This has degree $\mathbf{0}^{(\omega)}$, which computes every arithmetical set.

Noah Schweber above mentioned $WF$ and similar. My personal favorite is the theory of true second-order arithmetic, which is the set of true sentences about the set of subsets of the naturals. This is above $\Pi^1_n$ for every $n$, which makes it huge. It's also, incidentally, recursively isomorphic to the set of true sentences about the Turing degrees (think of "recursively isomorphic" as just "equivalent by way of a Turing machine", though it's a bit more than that).

Now, one thing worth noting is that everything I've suggested (and everything Noah had suggested as of the time of writing) is strictly above every arithmetic set. There are things that are off to the side, too - for example, there are Turing degrees that aren't arithmetic but compute no noncomputable sets (except themselves). But to my knowledge there are no natural examples of problems that are outside and not above the arithmetic hierarchy. I'd be interested in hearing if anyone has an example, though.