3
$\begingroup$

Let $W_e$ be the $e$th computably enumerable set in a standard enumeration. For $A\subseteq \omega$, let $A^{[i]}:=${ $ a : \langle a,i\rangle \in A$}. What is the arithmetical complexity of {$e : (\exists ! i) W_e^{[i]}$ is infinite }. Specifically whether it is $\Pi^0_4$-complete or so.

$\endgroup$

1 Answer 1

7
$\begingroup$

Definitely not $\Pi^0_4$-complete. Note that it can be expressed as the conjunction of a $\Sigma^0_3$ formula and a $\Pi^0_3$ formula:

$\exists i \forall n \exists m, s [m > n \wedge \langle m, i\rangle \in W_{e,s}]$ and $\neg \exists i, j \forall n \exists m, k, s [i \neq j \wedge m > n \wedge k > n \wedge \langle m, i\rangle \in W_{e, s} \wedge \langle k, j\rangle \in W_{e, s}]$.

In fact, it's complete for such sets. Given quantifier free $\phi(e,i,n)$ and $\psi(e,i,n)$, let $\langle 3i, n\rangle \in V_e \iff \phi(e,i,n)$, and let $\langle 3i+1,n\rangle \in V_e \iff \langle 3i+2, n\rangle \in V_e \iff \psi(e,i,n)$. Then $V_e$ has a unique infinite column precisely when $\exists i \exists^\infty n \phi(e,i,n) \wedge \neg \exists i \exists^\infty n \psi(e,i,n)$.

Edit: As Joel observed, we need that for each $e$, there is at most one $i$ with $\exists^\infty n \phi(e,i,n)$. Fortunately, there's a trick for that. Given $\phi$, we'll define $\phi'$ with this property. To aid us, we'll also define a function $f(e,i,n)$. We begin by setting $f(e,i,0) = i$ for all $e$ and $i$. We then proceed recursively in $n$. We define $\phi'(e,f(e,i,n),n) \iff \phi(e,i,n)$, and we define $\phi'(e,k,n)$ to be false for all $k$ not in the range of $f(e,-,n)$. If $\phi(e,j,n)$ holds for some $j < i$, we define $f(e,i,n+1) = f(e,i,n)+1$; otherwise we define $f(e,i,n+1) = f(e,i,n)$.

The idea is that we're going to copy column $i$ of $\phi$ to column $f(i)$ of $\phi'$, but $f(i)$ can grow with $n$ (it also varies with $e$, but that doesn't play any role). Every time an earlier column shows up with another entry, $f(i)$ gets pushed one step to the right. So the least infinite column can only be pushed finitely many times, by the finitely many finite columns before it, while all later columns are pushed infinitely many times, and thus no later column of $\phi'$ can receive more than finitely many elements.

$\endgroup$
2
  • $\begingroup$ Dan, regarding your completeness claim, couldn't your relation $V_e$ have two infinite columns, just if there are two $i$'s with $\exists^\infty n\phi(e,i,n)$, irrespective of $\psi$? $\endgroup$ Jun 7, 2013 at 14:51
  • $\begingroup$ Good catch. I've edited to address that. $\endgroup$ Jun 7, 2013 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.