2
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ As a non-interesting example, if you know of an R.E. set $A$ which is not recursive, then the complement of $A$ is not R.E. but is certainly arithmetical since the arithmetical sets are closed under complements. You could take $A$ to be set of codes of theorems of $PA$ or something similar if you need a specific example. $\endgroup$
    – Ned
    Sep 6, 2020 at 21:13
  • $\begingroup$ Have you studied Gödel numberings of formulas? $\endgroup$
    – hardmath
    Sep 6, 2020 at 21:15
  • $\begingroup$ Do you mean the process for proving the incompleteness theorem? In that case yes, I have studied Gödel numbering of formulas. $\endgroup$
    – Miral
    Sep 6, 2020 at 21:28

1 Answer 1

3
$\begingroup$

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$).

$\endgroup$
2
  • 1
    $\begingroup$ Incidentally, if you're familiar with the Borel hierarchy you may see a resemblance here. That's not accidental! The arithmetical hierarchy is just an initial segment of the longer hyperarithmetical hierarchy, which "mimics" the Borel hierarchy in a precise way. The relevant topic here is (effective) descriptive set theory. $\endgroup$ Sep 6, 2020 at 21:42
  • $\begingroup$ Thank you very much for this answer. I have found a lot of interesting topics I didn't knew (and which I want to study now) reading this post. I expected some mention to the arithmetical hierarchy, but the two connections you have mentioned are far beyond what I had imagine, that has been a happy surprise. Again, thank you very much. $\endgroup$
    – Miral
    Sep 6, 2020 at 22:10

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.