There is any arithmetical set which is not recursively enumerable

logic

We say that a $k$-ary relation $r$ over $\mathbb{N}$ is arithmetical if there is a formula $\varphi (\vec{a})$ with $k$ free variables $\vec{a}$, such that, for every $\vec{n}=(n_1,\dots, n_k)\in\mathbb{N}^k$,

$$r(\vec{n}) \text{ holds }\ \text{ iff }\ \ \mathbf{N}\vDash\varphi(\vec{\underline{n}})$$

Where $\mathbf{N}$ is the standard model of arithmetic (that is, $\mathbf{N}=\langle\mathbb{N}, +, \cdot, s, 0, =\rangle$), $\vec{\underline{n}}$ is the $k$-tuple $(\underline{n_1},\dots,\underline{n_k})$ and $\underline{n_i}$ is the $n_i$ application of the $s$ symbol to the $0$ symbol (that is, $ss\cdots ss0$ $\ n_i$ times).

We say that a function is arithmetical iff it is arithmetical as a relation.

It is possible to prove that any recursively enumerable set $R$ is arithmetical. However, I don't find the converse anywhere, yet, I don't know how to obtain an arithmetical set which is not a recursively enumerable one.

My first question is if all arithmetical sets are recursively enumerable or if there is a counterexample of this.

And, if there is a counterexample, I have another question.

In case of total functions, we have that a total function $f$ is recursive iff there is a formula $\varphi(\vec{a},b)$ with $k+1$ free variables $\vec{a}, b$ such that

  1. $f(\vec{n})=m$ implies $\text{PA}\vdash \varphi(\underline{\vec{n}}, \underline{m})$ for all $\vec{n}, m\in\mathbb{N}$

  2. $\text{PA}\vdash\exists b (\varphi(\underline{\vec{n}}, b)\wedge (\forall c (\varphi(\underline{\vec{n}}, c)\rightarrow b=c)))$ (where $\text{PA}$ is the Peano Arithmetic theory).

This definition looks to me as an stronger version of the first one. In particular, since we know that there is arithmetical sets which are not recursive (since not any recursively enumerable set is recursive) we have a similar characterization for total formulas which are defined, instead of $\mathbf{N}$, in Peano Arithmetic (so in fact we have a characterization for recursive sets in terms of definability in $\text{PA}$ since its characteristic function is a total recursive function with ones and zeroes as possible outputs).

My second question is, if there is some arithmetical set which is not a recursively enumerable set, is there any characterization in terms of definability between this other two?

Summarizing, is there any arithmetical set which is not a recursively enumerable set? and if the answer is yes, is there any characterization in terms of definability with natural numbers for recursively enumerable sets?

Thanks

Best Answer

Yes, there are lots of these - and the relevant notion is the arithmetic hierarchy.

There's a potential point of confusion worth addressing here, especially since it appeared in a now-deleted answer: we cannot conflate "true in $\mathbb{N}$" with "provable in $\mathsf{PA}$." In particular, for each formula $\varphi$ the set $$\{x: \mathsf{PA}\vdash\varphi(x)\}$$ is indeed r.e., but that does not mean that the set $$\{x: \mathbb{N}\models\varphi(x)\}$$ need be anywhere close to r.e.

Here's a brief summary. Every formula $\psi$ in the language of arithmetic is ($\mathsf{PA}$-provably) equivalent to one of the form $$Q_1x_1Q_2x_2....Q_nx_n\varphi(x_1,...,x_n)$$ where each $Q_i$ is a quantifier (either $\forall$ or $\exists$) and $\varphi$ uses only bounded quantifiers (quantifiers of the form $\forall y<n$ and $\exists y<n$). We can get an upper bound on the complexity of the set defined by $\psi$ by looking at:

  • the outermost quantifier $Q_1$, and

  • the number of quantifier alternations ("$\forall\exists$" or "$\exists\forall$" - this can be much less than the total number of quantifiers).

A formula of the above type whose outer quantifier is $\exists$ and which has $i$-many quantifier alternations is called $\Sigma_{i+1}$; a formula whose outer quantifier is $\forall$ and which has $i$-many quantifier alternations is called $\Pi_{i+1}$.

The first part of the connection between the arithmetic hierarchy and computational complexity is the following:

A set is r.e. iff it is definable by a $\Sigma_1$ formula.

See here. More generally, there is a connection between the arithmetical hierarchy on the one hand and Turing reducibility and the Turing jump and :

For each $n\in\mathbb{N}$ we have $X\le_T{\bf 0^{(n)}}$ iff $X$ is definable by a $\Sigma_{n+1}$ formula and $X$ is definable by a $\Pi_{n+1}$ formula.

This is due to Post. You may also find Shoenfield's limit lemma to be of interest. The simplest natural example of an arithmetic set which is not r.e., or indeed Turing-equivalent to any r.e. set (to rule out things like "the complement of the halting problem") is in my opinion the set of indices for Turing machines which halt on all inputs. This set, which is often denoted "$\mathsf{Tot}$" (for "total"), has Turing degree ${\bf 0''}$ and is $\Pi_2$ but not $\Sigma_2$.

(We say that a set is $\Sigma_n$ if it is definable by a $\Sigma_n$ formula, and similarly for $\Pi_n$; additionally, we say that a set is $\Delta_n$ iff it is both $\Sigma_n$ and $\Pi_n$. Note that there is no such thing as a "$\Delta_n$ formula" - whereas $\Sigma_n$-ness and $\Pi_n$-ness are syntactic properties, $\Delta_n$-ness is genuinely "semantic.")

Another important class of examples comes from the notion of bounded truth predicates. Per Tarski, the set $$\{\ulcorner\psi\urcorner: \mathbb{N}\models\psi\}$$ is not arithmetical (here "$\ulcorner\cdot\urcorner$" is your favorite Godel numbering function). However, for each $n$ the set of Godel numbers of true $\Sigma_n$ sentences is indeed $\Sigma_n$. The set of Godel numbers for false $\Sigma_n$ sentences (or Turing-equivalently the set of Godel numbers of true $\Pi_n$ sentences) is therefore $\Pi_n$ but not $\Sigma_n$. Similarly, the set of Godel numbers of false $\Pi_n$ sentences (or Turing-equivalently the set of Godel numbers of true $\Sigma_n$ sentences) is $\Sigma_n$ but not $\Pi_n$. Now just pick some really big $n$ (that is, $n>1$).

Related Question