Recursion Theorem and c.e. sets

[jgens]

Let $\varphi_e$ denote the p.c. function computed by the Turing Machine with code number $e$. Given $M=\{x : \neg(y<x)[\varphi_y=\varphi_x]\}$ prove that $M$ is infinite and contains no infinite c.e. subset.

I have already proved that $M$ is infinite. A necessary and sufficient condition to prove that $M$ has no c.e. subset is that given any one-to-one computable function $f$ it follows that $f(\omega) \nsubseteq M$. One way to demonstrate that this holds is to use the Recursion Theorem to show that there is some index $x_0$ such that $\varphi_{x_0}=\varphi_{f(x_0)}$ but $x_0 < f(x_0)$. I am having trouble doing this however and was wondering is someone here could help.

I think that this is the right way to approach the problem since the text suggested we use the Recursion Theorem to tackle it.

 

[mmwave]

Let's start by assuming that there exists a one-to-one computable function f such that f(\omega) \subseteq M. This means that for every x \in \omega, there exists some y \in f(\omega) such that \varphi_y = \varphi_x. We can use the Recursion Theorem to construct a Turing Machine with code number e such that \varphi_e = \varphi_{f(e)}. Now, since f is one-to-one, there exists some x_0 \in \omega such that f(x_0) = e. This means that \varphi_{x_0} = \varphi_{f(x_0)} = \varphi_e. However, since x_0 \in \omega and f(\omega) \subseteq M, we have x_0 \in M. This means that \varphi_{x_0} = \varphi_x for some x \in M. But since x_0 < f(x_0) = e, this contradicts the definition of M. Therefore, f(\omega) \nsubseteq M and M does not have any c.e. subset.