Proof that $\{ e \ | \ \forall p$ prime$: \varphi_e (p) \downarrow \}$ is not $\Delta_2$ 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 \}.$
 A: 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.
