I am trying to solve the following problem :
Let $A = \{n \in \mathbb{N} : \mbox{ for } \mbox{ all } x\in \mathbb{N}, \mbox{ if } {\phi}_{n}^{1}(x) \mbox{ is } \mbox{ defined } \mbox{ then } {\phi}_{n}^{1}(x) \leq 10 \}$.
1) Prove that $A$ and $\mathbb{N} - A$ are not recursive.
2) Prove that $\mathbb{N} - A$ is recursively enumerable and use it to explain why $A$ is not r.e.
I am not very familiar with this area. So any help would be really appreciated.
Thank you in advance!
For 1) you can either use Rice's theorem or prove it directly by showing that some non-recursive set, for example, $K = \{n \in \mathbb{N} \mid \varphi_x(x)\!\downarrow\}$ is $m$-reducible to $\mathbb{N} \setminus A$, i.e., there exists a recursive function $f(x)$ such that $n \in K \Leftrightarrow f(n) \in \mathbb{N} \setminus A$. Consider the following function $$ g(x, y) = \begin{cases} 11,& \text{if } \varphi_x(x)\!\downarrow,\\ \uparrow,& \text{otherwise.} \end{cases} $$ By s-m-n theorem there exists a recursive function $f(x)$ such that $\varphi_{f(x)}(y) = g(x, y)$. We also have $$ n \in K \Leftrightarrow \exists y\, (\varphi_{f(n)}(y) = g(n, y) = 11) \Leftrightarrow f(n) \in \mathbb{N} \setminus A. $$ This shows that $K \leqslant_m \mathbb{N}\setminus A$, and since $K$ is not recursive, so is $\mathbb{N}\setminus A$. The complement of a recursive set is recursive, so $A$ also can't be recursive.
For 2), Post's theorem says that a set is recursive if both itself and its complement are recursively enumerable. So if we show that $\mathbb{N}\setminus A$ is r.e. we are done. Showing that $\mathbb{N} \setminus A$ is r.e. depends on your definition of an r.e. set. We have $$ n \in \mathbb{N}\setminus A \Leftrightarrow \exists x\, (\varphi_n(x)\!\downarrow \wedge\ \varphi_n(x) > 10) \Leftrightarrow f(n)\!\downarrow, $$ where $f(n) = \mu z(z = (z_1, z_2) \wedge \varphi_n(z_1)\!\downarrow \text{in $z_2$ steps} \wedge \varphi_n(z_1) > 10)$. Intuitively, the program for $f(n)$ at step $m$ runs $\varphi_n(0), \dots, \varphi_n(m)$ each for $m$ steps and checks the condition $\varphi_n(x) > 10$ for convergent computations. If it finds one it halts, otherwise it keeps searching. This shows that $\mathbb{N} \setminus A = \mathrm{dom}\,f$ for some recursive $f$ and hence this set is r.e.