Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
    
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$? –  Joel David Hamkins Jun 7 '13 at 14:51
    
Good catch. I've edited to address that. –  Dan Turetsky Jun 7 '13 at 15:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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