In my note, our professor talk about Arithmetical hierarchy. at the end he wrote all of these is True. My main problem is how these are True? ($N$ means Natural Numbers, and $W_e$ is the set of inputs for which the program encoded by $e$ halts)
{$ x \in \mathbb{N}| W_x$ is recursive } $ \in \Sigma_3$
{$ x \in \mathbb{N} | W_x$ =$N$ } $ \in \Pi_2$
{$ x \in \mathbb{N} | \bar{W}_x$ is finite } $ \in \Sigma_3$
Thanks to any idea or hint.
Edit after 1 answer is received. infact when we want to solve this question via the proposed answer we get stuck when we ran into:
{$ x \in \mathbb{N} | \phi_x$ is total and bounded} $\in \Pi_2$
$\varphi_x$ is total and bounded if and only if it satisfies the following two conditions:
(1) $\forall a\exists b (\varphi_x(a)[b]\downarrow)$ (totality; here . . . $[b]$ means "in $b$ steps"); and
(2) $\exists c\forall a(\varphi_x(a)<c)$ (boundedness).
Now (1) is $\Pi^0_2$, but (2) is $\Sigma^0_2$; so "total and bounded" = "(1) and (2)" is not obviously $\Pi^0_2$.
In fact, the statement is wrong - the right claim should be "total and unbounded is in $\Pi^0_2$" (and, in fact, is $\Pi^0_2$-complete).
Let's show that, in fact, $Y$="total and bounded" is not in $\Pi^0_2$. How would we do this?
Well, a set $A\subseteq\mathbb{N}$ is $\Pi^0_2$ if and only if there is some computable total function $f(x, s)$ of two variables such that $$n\in A\iff\lim \sup_{s\rightarrow\infty} f(n, s)=\infty.$$ So suppose $f(x, s)$ is a computable total function; we'll find some $y$ such that $$y\in Y\iff\lim \sup_{s\rightarrow\infty} f(n, s)\not=\infty.$$ This will show that $Y$ is not $\Pi^0_2$.
This turns out to actually be rather easy: let $y$ be such that $\varphi_y(n)=f(y, n)$. (Exercise: how do we know that such a $y$ exists? This requires a theorem . . .) Then it's clear that $\varphi_y$ is total, so $y\in Y$ iff $\varphi_y$ is bounded.
BUT! $\varphi_y$ is bounded iff the function $s\mapsto f(y, s)$ is bounded, so we have $y\in Y\iff\lim\sup_{s\rightarrow\infty}f(y, s)\not=\infty$, so we are done.