# How to argue that a set is recursive or recursively enumerable?

I have the two sets listed below, and I want to argue whether each of them is recursive, recursively enumerable or neither recursive nor recursively enumerable.

1. the set $A = \{ i | \text{Dom}(\phi_i) = \emptyset \}$, where $\text{Dom}(\phi_k) = \{x | \phi_k(x) \downarrow \}$, and where $\phi_k(x) \downarrow$ means that function with index $k$ converges at input $x$.

2. the set $B$ of all total recursive functions $a : \mathbb{N} \rightarrow \mathbb{N}$ such that $a(n+1) \geq a(n)$, for all $n \in \mathbb{N}$

Please note that I have this definition for recursive sets, and this definition for recursive enumerable sets (r.e.). I also know that, if a set $A$ is recursive, then $A$ is also r.e.

The problem is that, I don't know how to argue about whether the sets above are recursive, r.e., or none of them. Any ideas about the problems?

EDIT:

$$\text{Halt}(x,y) = \begin{cases} 1, & \mbox{if } \phi_x(y) \downarrow \\ 0, & \mbox{if } \phi_x(y) \uparrow \end{cases}$$

where $\phi_x(y) \downarrow$, means function with index $x$ converges on input $y$, and $\phi_x(y) \uparrow$ means that it diverges.

• Do you know about reductions? One way to prove that something is not recursive is to use non-recursiveness of some fixed set (e.g. the halting problem) and reduce it to your set. Jan 3 '16 at 21:29
• @RandomJack Yes, I know about reductions, but it never occurred to me that it can be used to solve this kind of problems, I though, I only need the definitions. I believe I can define the halting problem as in my edit. But, how will the reduction look like. And by your definition, if I manage to reduce the sets to Halting problem, then it means that they are neither recursive nor r.e., right?
– user72151
Jan 3 '16 at 21:40

Let $K$ be the halting problem set $\{x \in \mathbb{N} \mid \phi_x(x) \downarrow\}$. It is known that $K$ is not recursive and hence (by Post's theorem) its complement $\overline{K}$ is not r.e. We say that $X$ is m-reducible to $Y$ (notation: $X \leq_\text{m} Y$) if there is a total recursive function $f(x)$ with $x \in X \Leftrightarrow f(x) \in Y$. It is quite easy to show that if $X \leq_\text{m} Y$ and $Y$ is recursive (r.e.), so is $X$.

To show that $A$ is not r.e. (and hence is not recursive) we will show that $\overline{K} \leq_\text{m} A$. Consider the following function $$f(x, y) = \begin{cases} 1,& x \in K\\ \uparrow,& x \notin K \end{cases}$$

It is partial recursive and by the $s_m^n$-theorem there is a total recursive $g(x)$ with $\phi_{g(x)}(y) = f(x, y)$. It holds that $$x \notin K \Leftrightarrow (\forall y) \phi_{g(x)}(y) = f(x, y) =\,\uparrow\, \Leftrightarrow g(x) \in A.$$

Now assume that $B$ is r.e. and let $U(n, x) = a_n(x)$ be a total recursive universal function for this set, that is, the functions from $B$ form a sequence $U(0, x), U(1, x), \dots$. Consider the following function: $$g(n) = \sum_{i = 0}^n U(i, n) + 1.$$ It is clearly a total recursive function. Since $U(i, n+1) \geq U(i, n)$ it holds that $$g(n+1) = \sum_{i = 0}^n U(i, n+1) + U(n+1, n+1) + 1 \geq \sum_{i = 0}^n U(i, n) + 1 = g(n),$$ hence $g(n) \in B$. On the other hand, if for some $m$ we have $U(m, n) = g(n)$, then taking $n = m$ we obtain $$U(m, m) = \sum_{i=0}^m U(i, m) + 1,$$ which is false. It means that $g(n) \notin B$, a contradiction. Hence $B$ is not r.e. (and, of course, is not recursive).

• So, as long as I understood, you assert that both set $A$ and $B$, are neither recursive nor r.e., am I right? On the other hand, what do you mean with "$m$-reducible"? What's the significance of $m$?
– user72151
Jan 4 '16 at 13:47
• Yes, both these sets are neither recursive nor r.e. For the set $A$ I use reduction of some fixed non-r.e. set (namely, the complement of $K$) to $A$, and for $B$ I prove it directly by constructing a function $g(n)$ (using diagonalization ideas) that leads to a contradiction. There are many different notions of reducibility (many-one, one-one, Turing, truth table and others), the letter 'm' stands for 'many-one'. Jan 4 '16 at 21:19
• Got it, thanks!
– user72151
Jan 4 '16 at 21:22