Show that maximal set is not recursive

Question

Define set $M$ such that its complement is infinite and for any computable set the intersection $M^C\cap R$ and $M^C\cap R^C$ are not both infinite.

How to show that $M$ is NOT recursive, given we know it is r.e. (recursively enumerable)?

Answer 1

For simplicity, let $A:=M^C$. To show that $M$ is not recursive it is enough to show that $A$ is not recursive.

Assume it is. By hypothesis, $A$ is infinite.
Consider an enumeration $(a_n)_n$ of $A$ in increasing order. Such a sequence is computable, because $A$ is.

Now define $R:=\{a_{2n}:n\in\mathbb{N} \}$. Such a set is computable (because the enumeration of $A$ is computable). However, by definition of $R$, we have that $\{a_{2n+1}:n\in\mathbb{N} \}\subset R^C$.

In other words, there is a recursive set $R$ s.t. $A\cap R$ and $A\cap R^C$ are both infinite, contradicting the hypothesis.