Arithmetical Hierarchy So i was reading the book "Turing Computability" of Soare.
I read about the Arithmetical Hierarchy.
There we it's defined that:
$$B \in \Sigma_n \iff  (\exists y)(\forall x_1)(\exists x_2) \dots (Qx_n)R(y,x_1,x_2 \dots x_n)$$ $$B \in \Pi_n \iff  (\forall y)(\exists x_1)(\forall x_2) \dots (Qx_n)R(y,x_1,x_2 \dots x_n) $$
where R is a computable prediacte.
So i found the folowing tasks: Show that:
$$Cof = \{x | W_x \text{ is cofinite}\} \in \Sigma_n$$
$$Cpl = \{x | W_x \equiv_T K \} \in \Pi_n$$
My attempt:
$$Cof = \{x | (\exists y)(\forall z)(\exists s){ (z \geq y \implies  z \in W_{x,s})}\}$$
$s$ is the number of steps. So this shows that cof is $\Sigma_3$. But I can't figure it out for CPL. Any tips?
 A: By definition of Turing equivalence, we have to study the complexity of saying $W_x\le_T K$ and $K\le_T W_x$. Since we know that $K$ is $\Sigma^0_1$-complete, it is enough to check whether $K\le_T W_x$ (the complexity would not change if you check both).
If we write $\varphi_e^A$ for the $e$-th computable function with oracle $A$ and identify a set with its characteristic function, then
$$K \le_T W_x \iff (\exists e)(\varphi_e^{W_x} = K)$$
The inner condition can be rewritten as
$$ (\forall n)((n\in K \rightarrow \varphi_e^{W_x}(n)=1) \land (n\notin K \rightarrow \varphi_e^{W_x}(n)=0))$$
The condition $\varphi_e^{W_x}(n)=k$ is $\Sigma^0_2$ (you need to ask that the machine converges to $k$, but you have a $\Sigma^0_1$ oracle), so the whole line is $\Pi^0_3$ and the condition $K \le_T W_x$ is $\Sigma^0_4$.
Of course every $\Sigma^0_n$ is a $\Pi^0_{n+1}$ set, so this shows that CPL is $\Pi^0_5$, but not sure why this is interesting. Maybe the idea was to write the condition as $(\forall y)(W_y \le_T W_x)$, but then again, this is more complicated than needed. The set is actually $\Sigma^0_4$-complete (check [1, Rem. 4.3.7]).

[1]: Soare, Robert I., Turing computability. Theory and applications, Theory and Applications of Computability. Berlin: Springer (ISBN 978-3-642-31932-7/hbk; 978-3-642-31933-4/ebook). xxxvi, 263 p. (2016). ZBL1350.03001.
