3

This is a problem I've come across in my exam studies, and neither me nor my friend in the same course have been able to solve, so it would be good to see how it's done before the exam in a couple of days.

If we let $D = \{ e \ | \ \forall p$ prime$: \varphi_e (p) \downarrow \}$, it can be seen that $e \in D \iff \forall p \exists s R(p, s, e)$, where $R(p, s, e)$ is the computable relation: $(p $ prime $ \implies \varphi_e^s (p) \downarrow)$.

I.e. $R(p, s, e)$ iff $\varphi_e$ halts on prime $p$ within s steps of the computation, or $p$ isn't prime.

So $D$ is $\Pi_2$, and hence it needs to be shown that $D$ isn't $\Sigma_2$, I.e. there is no computable relation $Q$ such that $e \in D \iff \exists t \forall s Q(t, s, e)$.

Another tact would be to show $D \not \leq_T 0'$ or $D \not \leq_T K$, where $K$ is the halting set $\{ e \ | \ \varphi_e (e) \downarrow \}.$

G. H. Faust
  • 1,766
  • 1
    What other $\Pi_2$ sets that are not $\Sigma_2$ do you know? The usual trick is to reduce to a set about which you know more information. – Thomas Andrews Jun 28 '14 at 18:03
  • For example, do you know that ${e\mid \phi_e\text{ is total}}$ is $\Pi_2$ but not $\Sigma_2$? – Thomas Andrews Jun 28 '14 at 20:17
  • @ThomasAndrews There are no specific sets I know aren't $\Sigma_2$, though I did just proove Tot $ =_T D$, where Tot is the set you describe. If I could justify that Tot wasn't $\Sigma_2$, I would be done.

    Taking many more liberties, I think I may have that $K' \leq_T D$ (which contradicts $D \leq_T K$), but my argument is iffy at best. It relies on being able to compute (for a given index $n$ in an enumeration of oracle machines $\Phi_n^K$) $m$ such that $\varphi_m = \Phi_n^\emptyset$, and the notion that $\Phi_n^\emptyset$ is total if $\Phi_n^K$ is.

     – G. H. Faust Jun 28 '14 at 20:42
  • Ah, well, that's the limit of my memory on this issue, sorry. – Thomas Andrews Jun 28 '14 at 21:08

1 Answers1

1

Here is a reduction showing that the set $D$ from the question is $\Pi^0_2$ hard. Let $(\forall n)(\exists w)\phi(m,n,x)$ be an arbitrary $\Pi^0_2$ formula with free variable $m$, in which $\phi(m,n,w)$ is $\Sigma^0_0$.

Given a number $m$, we can make a program $e_m$ which, on each input $p$, immediately halts if $p$ is not prime, and otherwise finds the $n$ for which $p$ is the $(n+1)$st prime. Then $e_m$ searches for a $w$ such that $\phi(m,n,w)$ holds, and halts if and only if such a $w$ is found. (At this point, you may want to stop and complete the argument yourself, if you're studying for an exam.)

Now we have that, for all $m$, $e_m \in D$ if and only if $(\forall n)(\exists w)\phi(m,n,w)$. (We also have that $e_m \in \text{Tot}$ if and only if $(\forall n)(\exists w)\phi(m,n,w)$, by the way.) This completes the reduction.

This shows that $D$ cannot be $\Delta^0_2$, by Post's theorem.

A separate calculation shows that $D$ is itself $\Pi^0_2$, and thus with the previous reduction we have that $D$ is a $\Pi^0_2$ complete set.

The same thing could be obtained by showing that $D$ is $1$-equivalent to the complement of $\emptyset''$, but reducing that specific set to $D$ is somehow more difficult than reducing an arbitrary $\Pi^0_2$ set to $D$.

There is another, heuristic way to see that the set $D$ in the question should not be $\Delta^0_2$. If it was, by Post's theorem it would be computable from $\emptyset'$. But to decide whether an number is in $D$ seems to require asking infinitely many questions to $\emptyset'$. This immediately suggests the reduction method above.

Carl Mummert
  • 81,604
  • Showing that $D$ is $\Pi_2$ hard is enough for me to get the result, but I'm not sure how you're arguing so directly after that. The only route I'm seeing is that $D$ being $\Pi_2$ hard implies $\overline{D}$ is $\Sigma_2$ hard, then $0'' =T \overline{D} =_T D$, so $D \not \leq_T 0'$. _Then from Post's theorem I have $D$ isn't $\Delta_2$. Am I missing something? – G. H. Faust Jun 30 '14 at 10:00
  • 1
    I don't think you're missing anything. That last part is a completely general argument, though. Post's theorem and the fact that $\emptyset^{(n+1)} \not\leq_T \emptyset^{(n)}$ imply (as you argue) that the arithmetical hierarchy does not collapse. So, as soon as we know any set is $\Pi^0_n$ or $\Sigma^0_n$ hard for some $n \geq 1$, we know the set cannot be $\Delta^0_n$. – Carl Mummert Jun 30 '14 at 11:14