Recursion Theorem and c.e. sets

[jgens]

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

I have already proved that [itex]M[/itex] is infinite. A necessary and sufficient condition to prove that [itex]M[/itex] has no c.e. subset is that given any one-to-one computable function [itex]f[/itex] it follows that [itex]f(\omega) \nsubseteq M[/itex]. One way to demonstrate that this holds is to use the Recursion Theorem to show that there is some index [itex]x_0[/itex] such that [itex]\varphi_{x_0}=\varphi_{f(x_0)}[/itex] but [itex]x_0 < f(x_0)[/itex]. 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.