I saw some examples of reduction one of them is this:
We say set $B$ is many-one reducible to $A$ if there exists a total cumputable fucntion $f$ that:$$x\in B \iff f(x) \in A$$ and we write $B\leq_m A$.
Prove that for every $x \in \mathbb{N}$ : $$K^c \le_m \{y: w_x = w_y\} $$ Where $K=\{e\in \mathbb{N}|e\in W_e\}$ and $w_e = Dom(\phi_e(x))$ is the set of all numbers that on which the e-th Turing machine halt
Update
I removed unnecessary sentences(Rice's theorem, etc.). I realize if we prove that any $\sum^0_{n}$ set is many-one reducible to an arbitrary set $P\in\sum^0_{n+1}$, we can get the result. see for more Arithmetic hierarchy
We know $\phi\,_{e,t}(x)\!\downarrow$ is computable relation so we get these results that come below:
- $A\leq_m B \iff A\,^c\leq_m B\,^c$ so needs to prove $K \le_m \{y: w_x \ne w_y\} $. Also know that the set if $Y=\{y: w_x \ne w_y\}$ than $Y \in \sum^0_2$. $$y\in Y \iff \exists <s,p>[\:\forall s\:[\:\phi_{y,t}(p)\!\downarrow \wedge\ \phi_{x,t}(p)\!\uparrow\:]\:]$$ where $\phi_{x,t}(p)\downarrow$ means $x$-th Turring machien halt on $p$ after atmost $t$ step other wise we write $\phi_{x,t}(p)\uparrow$ and $<.,.>$ is a one-one function maps $\mathbb{N}^2$ onto $\mathbb{N}$
- $K\in\sum^0_1$: $$x \in K \iff \exists \:s \:\phi\,_{x,s}(x)\!\downarrow$$