# Recursion Theorem and c.e. sets

1. Jan 26, 2012

### 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.