Placing some sets in the arithmetic hierarchy I'm working on the following problem: let $W_e$ be the computably enumerable set which is the domain of the $e$-th Turing program, and $K$ be the Halting problem, at which level of the arithmetic hierarchy does each of the following sets appear?


*

*$A_1=\{e: W_e$ contains no even numbers $\}$

*$A_2=\{e: W_e$ contains some element of $K\;\}$

*$A_3=\{e: W_e$ contains every element of $K\;\}$

*$A_4=\{e: W_e$ is infinite $\}$


I think $A_1 \in \Pi_1$ because it can written as $A_1=\{\exists x \in W_e (\forall n \neg (x=2n) )\}$, i.e. one universal and one bounded quantifier. I'm a little bit worried that the bounded set is c.e., does it change things?
Since $K \in \Sigma_1$ and $A_2=\{e: \exists x \in W_e (x \in K)\}$, $A_2$ is in $\Sigma_1$, but it's not $\Pi_1$ so it's not $\Delta_1$.
$A_3=\{e: \forall x \in K (x \in W_e)\}$ so it's $\Pi_1$
I'm not sure what to do with $A_4$
I would also like to view these sets in the context of Turing machine, but can't wrap my head around it.
 A: The class of recursive languages consists of those languages for which there exists an algorithm that always terminates and answers correctly whether a given input belongs to the language or not. For example, consider the language of all triples $(e,x,t)$ such that the $e$th program, when run on input $x$, stops after at most $t$ steps. This language is recursive since you can simulate the $e$th program on input $x$, and after at most $t$ steps of the simulation, you can tell whether the triplet belongs to the language or not.
Some languages, however, are not recursive. An example is the language $K$ of those programs that halt on the empty input. A classical argument shows that $K$ cannot be recursive. Hypercomputation comes to our rescue. Consider the following algorithm for deciding whether $e$ belongs to $K$:


*

*Put false in the variable flag.

*For $t = 0$ to $\infty$: Simulate $e$ for $t$ steps, and if it halts, put true into flag.

*Return flag.


We schedule the iteration of step $2$ to run in times $1/2,1/4,1/8,\ldots$, and run step $3$ at time $1$. So step $3$ runs after all the infinite number of iterations of step $2$, and can tell whether the program $e$ ever halts or not. Of course, this is not realistic since we cannot really run our program in ever-increasing speeds, so that's why we call it "hypercomputation".
We can abstract this process of "compressing time" by forgetting about the mechanism, and replacing it by a quantifier: $\exists t$ such that program $e$ halts after $t$ steps. We call this "existential compression", and term the languages that can be computed this way $\Sigma_1$. In this type of compression, the hypercomputation accepts iff at least one of the compressed computations accept. The notation comes from the fact that for indicator (zero/one) variables $v_i$, we have $\sum_i v_i \geq 1$ iff there exists some $i$ such that $v_i \geq 1$.
There is also "universal compression", in which the computation rejects if at least one of the compressed computations reject. This is denoted $\Pi_1$, which reminds us of the rule $\prod_i v_i = 0$ iff $v_i = 0$ for some $i$. The corresponding quantifier is $\forall$.
Why are existential and universal compressions considered different? Suppose we take a two-parameter algorithm, and compress it existentially twice. This operation might seem more complicated than single compression, but in fact it's perfectly possible to do the compression only once. All we need is some way to enumerate over all pairs of integers: double existential compression amounts to running some recursive algorithm $A(x,y)$ on all possible pairs $(x,y)$, and deciding whether any of the executions accept. We can replace the enumeration over all pairs by an enumeration of some single variable $z$, and then convert $z$ to $(x,y)$ as follows:
$$ 0 \mapsto (0,0) \; 1 \mapsto (1,0) \; 2 \mapsto (0,1) \; \cdots. $$
So compressing time existentially twice is no stronger than doing it once. The same applies for universal compression. But if we alternate two different kinds of compression, we do get something stronger. Consider, for example, the language of all $e$ such that the $e$th machine halts on all inputs. This can be written as $\forall x \exists t$ such that $e$ halts on $x$ after at most $t$ steps. So first we compress existentially (over $t$), then universally (over $x$). An argument similar to the one showing that $K$ isn't recursive also shows that this new language isn't $\Sigma_1$ or $\Pi_1$. So we've gained something by alternating quantifiers.
Finally, let's address your confusion about bounded quantifiers. These are quantifiers which are bounded by some definite quantity. Consider, for example, the language of all $e$ such that the $e$th mating halts on every input $x$ after at most $2^x$ steps. This can be realized as $\forall x \exists t \leq 2^x$ such that $e$ halts on $x$ after at most $t$ steps. We don't need any "tricks" to handle the quantification over $t$, since all we need is to try all values of $t$ between $0$ and $2^x$, and then we know the answer. So this bounded quantifier "doesn't count". Something like $x \in K$ isn't bounded, since $K$ isn't recursive. It is shorthand for "$\exists t$ such that $x$ halts after $t$ steps", and here the $t$ isn't bounded. The classes $\Sigma_k$/$\Pi_k$ are define by $k$ alternating quantifiers and then a recursive predicate (= language). The predicate $x \in K$ isn't recursive.
A: $(x \in K)$ or $(x \in W_e)$ does not count as a bounded quantifier in Computability Theory where bounded means bounded by a number. Note this is different than in the first order theory of Set theory. 
For all of these, my Halting Problem or Jump $K$ is defined as $K = \{e : \Phi_{e}(e) \downarrow\}$. The notation $\Phi_{e,s}(x)$ means run the $e^\text{th}$ Turing Program for $s$ steps on input $x$. The important part is that this is computable. 


*

*On the surface, $A_1$ is $\Pi_1^0$. 


$A_1 = \{e : (\forall n)(\forall s)(\Phi_{e,s}^\emptyset(2n)\uparrow)\}$
This is $\Pi_1^0$. In fact, it well known that $K$ is the $\Sigma_1^0$ 1-complete (complete via 1-reductions). Therefore, the complement of $K$ is $\Pi_1^0$ 1-complete. The claim is that $A_1$ is also $\Pi_1^0$ 1-complete. Define the function $f$ as follows : 
$\Phi_{f(e)}(x) = \begin{cases}
1 & \quad x = 0 \wedge (\Phi_e(e)\downarrow) \\
\uparrow & \quad \text{otherwise}
\end{cases}$
By some theorem (maybe the s-m-n theorem), the function $f$ exists and is injective and used to prove the 1-reduction $\bar{K} \leq_1 A_1$. That is, if $e \in \bar{K}$, then $W_{f(e)} = \emptyset$. Thus $f(e) \in A_1$. If $e \in K$, then $W_{f(e)} = \{0\}$, then $f(e) \notin A_1$.  Thus $\bar{K} \equiv_1 A_1$. 
For the second one, one can write
$A_2 = \{e : (\exists x)(\exists s)(\Phi_{x,s}(x)\downarrow)\}$
This is $\Sigma_1^0$. This set is also $\Sigma_1^0$-complete. Define the function $f$ as follows : 
$\Phi_{f(e)}(x) = \begin{cases}
1 & \quad x = e \\
\uparrow & \quad \text{otherwise}
\end{cases}$
Note that $W_{f(e)} = \{e\}$. Thus, this function witnesses $K \leq_1 A_2$. 
The third one as far as I can tell is $\Pi_2^0$
$A_3 = \{e : (\forall n)((\exists s)(\Phi_{n,s}(n)\downarrow) \Rightarrow (\exists t)(\Phi_{e,t}(n)\downarrow))\}$
I believe $A_3$ is $\Pi_2^0$ 1-complete. $A_4$ or $Inf$ is $\Pi_2^0$ complete (as I will say again below). I will show $A_3$ is $\Pi_2^0$ complete by reducing $Inf$ to it. Define the function $f$
$\Phi_{f(e)}(x) = \begin{cases}
1 & \quad (\exists s)(\exists t)(s > x \wedge \Phi_{e,t}(s)\downarrow \wedge \Phi_{e,s}(e)\downarrow \\
\uparrow & \quad \text{otherwise}
\end{cases}$
I believe this function witness that $Inf \leq_1 A_3$. If $e \in Inf$, then $W_{f(e)}$ contains $K$ since if $x \in K$ there exists a $s > x$ such that $s \in W_e$ and $\Phi_{e,s}(e)\downarrow$. Thus $x \in W_{f(e)}$. If $e \notin Inf$, then $W_e$ is finite. Let $j$ be the largest element in $W_e$. Since $K$ is infinite, it is clear that $W_{f(e)}$ does not contain $K$ since $W_{f(e)}$ is bounded by $j$. 
The fourth one is well known. It is often called Inf
$A_4 = Inf = \{e : (\forall n)(\exists x)(\exists t)(x > n \wedge \Phi_{e,t}(x)\downarrow)\}$
$Inf$ is $\Pi_2^0$ complete. Look in Soare's book for a proof. 
If my proofs are correct, all you sets above can certainly be defined by a $\Pi_1^0$, $\Sigma_1^0$, $\Pi_2^0$ and $\Pi_2^0$ formula, respectively, but in some sense you can even prove the lowest they can be on the hierarchy are these places. 
A: As I understand, by "$W_e$ is infinite" you mean that $\varphi_e(x)$ halts for infinitely many $x$, where $\varphi_e$ is the TM corresponding to $e$.
The set $W_e$ is infinite iff for every $x$ there is some $y > x$ which is in $W_e$, i.e. for every $x$ there is some $y > x$ such that $\varphi_e(y)$ halts. Does that help?
