# What is the Arithmetical complexity of determining whether a 2-ary computable predicate has exactly one infinite column

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.

-

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.

-
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