Locating the set in the arithmetic hierarchy

Question

Let $W_x$ be the domain of a program (number) $x$. Let $S=\{x:\exists y (y\in W_x\land W_y\text{ is infinite})\}$. The exercise consists in determining of where this set belongs in arithmetic hierarchy.

Here's what I got: $$x\in S\iff\exists y(\exists z T(x,y,z)\land \forall N\exists t > N \exists w T(x,t,w))$$

($T$ is the Kleene $T$-predicate). Now I guess I can "factor out" either $\exists z$ or $\forall N$ (and I'm free to choose any option in my understanding). Let's factor out $\exists z$:

$$\iff \exists y\exists z(T(x,y,z)\land \forall N\exists t(t>N\to \exists w T(x,t,w))$$

Now I can factor out $\exists w$:

$$\iff \exists y\exists z(T(x,y,z)\land \forall N\exists t\exists w(t>N\to T(x,t,w))$$

Now I can factor out the group of quantifiers $\forall N\exists t\exists w$ (officially, one by one):

$$\iff \exists y\exists z \forall N\exists t\exists w(T(x,y,z)\land (t>N\to T(x,t,w))$$

So it looks like the answer is $\Sigma_3$.

Is this reasoning correct? And is there an easy way to show that $\Sigma_3$ is the best that we can get (if this is so)?

Answer 1

It is indeed $\Sigma^0_3$. In natural language, it's:

The set of $y$ such that at some point $y$ appears in $W_x$ and for each $z$ there is some $w>$ which sometime appears in $W_y$.

This is of the form $\Sigma^0_1(\Sigma^0_1\wedge\Pi^0_2)$, so $\Sigma^0_3$. (Obviously that's not a proof, but it's a good outline of how to do the rewriting.)

---

As to optimality, this is optimal in a very strong sense: the set $S$ in question is $\Sigma^0_3$-complete, meaning that any other $\Sigma^0_3$ set $A$ is many-one reducible to $S$. As a consequence, not only is it not $\Sigma^0_2$, it's not even $\Pi^0_3$.

• This last bit uses the fact that the arithmetical hierarchy does not collapse: for every $n>0$ we have $\Sigma^0_n\not\subseteq \Pi^0_n$ and $\Pi^0_n\not\subseteq\Sigma^0_n$, and so a fortiori $\Sigma^0_n\supsetneq\Pi^0_{n-1}\cup\Sigma^0_{n-1}$ and $\Pi^0_n\supsetneq\Pi^0_{n-1}\cup\Sigma^0_{n-1}$.

Soare's old book has quite a bit of material on this. The arguments can get a bit technical, especially for higher levels of the arithmetic hierarchy, but aren't too bad. One way to make them simpler is to think "modularly:" e.g. in the proof that $S$ is $\Sigma^0_3$-complete you'll want to use the idea of the proof that the set of infinite c.e. sets is $\Pi^0_2$-complete.